Browsing LCS Publications by Title
Now showing items 251-270 of 1163
-
Coordination of Parallel Processes in the Actor Model of Computation
(1976-12)Two algorithms for the mutual exclusion problem are described and proven to operate correctly. The algorithms are unique in that they use very simple synchronization primitives yet are fair and retain their fairness even ... -
Coping with Syntactic Ambiguity or How to Put the Block in the Box on the Table
(1982-04)Sentences are far more ambiguous than one might have thought. There may be hundreds, perhaps thousands of syntatic parse trees for certain very natural sentences of English. This fact has been a major problem confronting ... -
Copmutationally Sound Proofs
(2000)This paper puts forward a new notion of a proof based on computational complexity and explores its implications for computation at large. Computationally sound proofs provide, in a novel and meaningful framework, answer ... -
Copying Complex Structures in a Distributed System
(1979-07)This thesis presents a model of a distributed system. The universe of objects in the distributed system is divided into mutually exclusive sets, each set corresponding to a context. This model allows naming beyond the ... -
Correctness Conditions for Highly Available Replicated Databases
(1986-06)Correctness conditions are given which describe some of the properties exhibited by highly available distributed database systems such as the SHARD (System for Highly Available Replicated Data) system currently being ... -
Correctness of Communications Protocols, A case Study
(1993-11)During the past few years, the technology for formal specification and verification of communication protocols has matured to the point where we believe that it now provides practical assistance for protocol design and validation. -
Correctness Proof for a Network Synchronizer
(1993-12)In this paper we offer a formal, rigorous proof of the correctness of Awerbuch's algorithm for network synchronization [1]. We specify both the algorithm and the correctness condition using the I/O automaton model. -
A Correctness Proof for a Practical Byzantine-Fault-Tolerant Replication Algorithm
(1999-06)We have developed a practical algorithm for state-machine replication [7,11] that tolerates Byzantine faults. The algorithm is described in [4]. It offers a strong safety property - it implements a linearizable [5] object ... -
Cost Analysis of Debugging Systems
(1971-09)A general method is presented for performing cost analysis of interactive debugging systems. The method is based on an abstract model of program execution. This model is derived from the interpreter used in the Vienna ... -
Cost-sensitive Analysis of Communication Protocols
(1991-06)This paper introduces the notion of cost-sensitive communication complexity and exemplifies it on the following basic communication problems: computing a global function, network synchornization, clock synchronization, ... -
Counting Networks
(1991-06)Many fundamental multi-processor coordination problems can be expressed as counting problems: processes must cooperate to assign successive values from a given range, such as addresses in memory of destinations on an ... -
Covering Graphs by Simple Circuits
(1980-02) -
Creating a Computer-based Learning Environment for Physically Handicapped Children
(1983-09)The objective of this research is to develop a computer-based learning environment for children physically handicapped by cerebral palsy and to study several issues related to the use of this environment for diagnostic, ... -
Creating and Rendering Image-Based Visual Hulls
(1999-05)In this paper, we present efficient algorithms for creating and rendering image-based visual hulls. These algorithms are motivated by our desire to render real-time views of dynamic, real-world scenes. We first describe ... -
Credible Compilers
(1999-03)This paper presents a new concept in compiler correctness: instead of proving that the compiler performs all of its transformations correctly, the compiler generates a proof that the transformed program correctly implements ... -
Critical Path Scheduling of Task Systems with Resource and Processor Constraints
(1980-03)Several papers over the past few years have investigated minimum execution time scheduling of unit execution time (UET) task systems with resources. Because such scheduling problems are, in general, NP-hard, a variety of ... -
CRL: High - Performance All-Software Distributed Shared Memory*
(1995-03)This paper introduces the C Region Library (CRL), a new all-software distributed shared memory (DSM) system. CRL requires no special compiler, hardware , or operating system support beyond the ability to send and receive ... -
The Cryptographic Security of Compact Knapsacks (Preliminary Report)
(1980-04)In 1978, Merkle and Hellman introduced a knapsack-based public-key cryptosystem, which received widespread attention. The two major open problems concerning this cryptosystem are: (i) Security: How difficult are the ... -
CTSS Technical Notes
(1965-03)This report is a technical description of the 7094 Compatible Time-Sharing System in use at Project MAC and the M.I.T. Computation Center. It is designed to acquaint a system programmer with the techniques of construction ...
