Browsing LCS Technical Memos (1974 - 2003) by Title
Now showing items 235-254 of 492
-
K+1 Heads are Better Than K
(1976-09)There are languages which can be recognized by a deterministic (k+1)-headed one-way finite automaton but which cannot be recognized by a k-headed one-way (deterministic or non-deterministic) finite automaton. Furthermore, ... -
Knowledge and Common Knowledge in a Byzantine Environment: Crash failures
(1986-07)By analyzing the states of knowledge that the processors attain in an unreliable system of a simple type, we capture some of the basic underlying structure of such systems. In particular, we study what facts become common ... -
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 ...