Browsing LCS Technical Memos (1974 - 2003) by Title
Now showing items 237-256 of 492
-
A Lattice-structured Proof Technique Applied to a Minimum Spanning Tree Algorithm
(1988-06)Higly-optimized concurrent algorithms are often hard to prove correct because they have no natural decomposition into separately provable parts. This paper presents a proof technique for the modular verification of such ... -
Layouts for the Suffle-Exchange Graph Based on the Complex Plane Diagram
(1982-06)The shuffule-exchange graph is one of the best structures known for parallel computation. Among other things, a shuffle-exchange computer can be used to compute discrete. Fourier transforms, multiply matrices, evaluate ... -
Lazy Reference Counting for Transactional Storage Systems
(1997-10)HAC is a novel technique for managing the direct the client cache in a distributed, persistent object storage system. In a companion paper, we showed that it outperforms other techniques across a wide range of cache sizes ... -
Lazy Task Creation: A Technique for Increasing the Granularity of Parallel Programs
(1991-06)Many parallel algorithms are naturally expressed at a fine level of granularity, often finer than MIMD parallel system can exploit efficiently. Most builders of parallel systems have looked to either the programmer or a ... -
Light Traps
(1996-10)In the February 1992 issue of the American Mathematical Monthly, J. E. Connett [1] asked whether it is possible to construct a 'light trap': a reflective-sided container with the property that a beam of light, shone into ... -
Limitless Directories: A Scalable Cache Coherence Scheme
(1991-06)Caches enhance the performance of multiprocessors by reducing network traffic and average memory access latency. However, cache-based systems must address the problem of cache coherence. We propose the LimitLESS directory ... -
Linearizable Counting Networks
(1991-11)The counting problem requires n asynchronous processors to assign themselves successive values. A solution is linearizable if the order of the values assigned reflects the real-time order in which they were requested. ... -
Local Rule Switching Mechanism for Viral Shell Geometry
(1995-06)In a previous paper [Berger et al., PNAS 91 7732,1994] a theory of virus shell formation was proposed in which shell assembly is directed by local interactions of the coat ans scaffolding subunits. This theory requires ... -
Local Rules Modeling of Nucleation-Limited Virus Capsid Assembly
(1998-08)We describe an application of computer modeling to the study of the kinetics of virus capsid (protein shell) assembly. We examine two proposed models of the source of nucleation-limited growth, an observed growth pattern ... -
A Logic Design for the Cell Block of a Data-flow Processor
(1977-12)Recently studies on parallel computation architecture have yielded a new type of computer architecture known as the data-flow processor. As part of the effort in realizing the data-flow processor, a logic design for the ... -
Low-cost Support for Fine-grain Synchronization in Multiprocessors
(1992-06)As multiprocessors scale beyond the limits of a few tens of processors, they must look beyond traditional methods of synchronization to minimize serialization and achieve the high degrees of parallelism required to utilize ... -
Lower Bounds on Information Transfer in Distributed Computations
(1978-04)We derive a lower bound on the interprocessor information transfer required for computing a function in a distributed network. The bound is expressed in terms of the function's derivatives, and we use it to exhibit functions ... -
LSB Manual
(1981-06)LSB (for Layered System Building) is an integrated set of facilities for aiding in the construction of highly-modular, multi-layered, implementation-independent Lisp systems. It provides for conditional inclusion of source ... -
The Macaims Data Management System
(1971-04)MacAIMS (MAC Advanced Interactive Management System) is a relatively small research project that was initiated in the summer of 1968 to investigate the feasibility of using some of the then existing computer facilities at ... -
A Machine Language Instruction Set for a Data Flow Processor
(1979-12)A data flow processor is a computer in which instructions are data driven and enabled for execution by the arrival of their operands. Data flow processors execute data flow programs, normally represented as program graphs, ... -
Maclisp Extensions
(1981-07)This document describes a common subset of selected facilities available in Maclisp and its derivatives: PDP-10 and Multics Maclisp., List Machine Lisp (Zetalisp), and NIL. The object of this document is to aid people in ... -
A Manager for Named, Permanent Objects
(1980-04)Storing data in a computing system for a long time has been of interest ever since it was possible to do so. Classically, on stores bit- or byte- strings, or perhaps arrays of "records." Yet, current programming philosophy ... -
Maps: a Compiler-Managed Memory System for RAW Machines
(1998-07)Microprocessors of the next decade and beyond will be built using VLSI chips employing billions of transistors. In this generation of microprocessors, achieving a high level of parallelism at a reasonable clock speed will ... -
The Markov Chain Tree Theorem
(1983-11)Let M be a finite first-order stationary Markov chain. We define an arborescence to be a set of edges in the directed graph for M having at most one edge out of every vertex, no cyles, and maximum cardinality. The weight ...
