Browsing LCS Publications by Title
Now showing items 870-889 of 1163
-
RAMBO II: Rapidly Reconfigurable Atomic Memory for Dynamic Networks
(2003-03)Future civilian rescue and military operations will depend on a complex system of communicating devices that can operate in highly dynamic environments. In order to present a consistent view of a complex world, these devices ... -
A Random Server Model for Private Information Retrieval (or Information Theoretic PIR Avoiding Database Replication
(1997-04)Private information retrieval (PIR) schemes provide a user with information from a database while keeping his query secret from the database manager. We propose a new model for PIR, utilizing auxiliary random servers ... -
A Randomized Data Structure for Ordered Sets
(1986-05)In this paper, we consider a simple randomized data structure for representing ordered sets, and give a precise combinatorial analysis of the time required to perform various operations. In addition to a practical data ... -
Randomized Encryption Techniques
(1983-01)A randomized encryption procedure enciphers a message by randomly choosing a ciphertext from a set of ciphertexts corresponding to the message under the current encryption key. At the cost of increasing the required ... -
Randomized Routing on Fat-trees
(1986-05)Fat-trees are a class of routing networks for hardware-efficient paralle computation. This paper presents a randomized algorithm for routing messages on a fat-tree. The quality of the algorithm is measured in terms of the ... -
Randomness and Robustness in Hypercube Computation
(1991-04)In this thesis we explore means by which hypercubes can compute despite faulty processors and links. We also study techniques which enable hypercubes to simulate dynamically changing networks and data structures. -
Randomness Versus Non-Determinism in Distributed Computing
(1994-10)This thesis is devoted to the analysis and illustration of the effects of the interplay between randomness and non-determinism in randomized computing. Using ideas from game theory , we provide a general model for randomized ... -
Rank 2 Type Systems and Recursive Definitions
(1995-11)We demonstrate an equivalence between the rank 2 fragments of the polymorphic lambda calculus (System F) and the intersection type discipline: exactly the same terms are typable in each system. An immediate consequence ... -
Rank 2 Type Systems and Recursive Definitions
(1995-08)We demonstrate an equivalence between the rank 2 fragments of the polymorphic lambda calculus (System F) and the intersection type discipline: exactly the same terms are typable in each system. An immediate consequence is ... -
Rate-based Congestion Control in Networks with Smart Links
(1990-01)I use a network simulator to explore rate-based congestion control in networks with "smart" links that can feed back information to tell senders to adjust their transmission rates. This method differs in a very important ... -
Ratings in Distributed Systems: A Bayesian Approach
(2001-05)For distributed systems at large and e-commerce systems in particular, ratings play an increasingly important role. Rating confer reputation measures about sources. This paper reports our formalization of the rating process. ... -
Reaching Approximate Agreement in the Presence of Faults
(1985-10)This paper considers a variant of the Byzantine Generals problem, in which processes start with arbitrary real values rather than Booleann values or values from some bounded range, and in which approximate, rather than ... -
Reaching Approximate Agreement in the Presence of Faults
(1985-05)This paper considers a variant of the Byzantine Generals problem, in which processes start with arbitrary real values rather than Booleann values or values from some bounded range, and in which approximate, rather than ... -
Reactive Synchronization Algorithms for Multiprocessors
(1995-06)Efficient synchronization algorithms are hard to design because their performance depends on run-time factors that are hard to predict. In particular, the designer has a choice of protocols to implement the synchronization ... -
Real-time Control Structures for Block Diagram Schemata
(1978-08)Block diagram schemata model computation systems in the context of an external environment. The environment imposes various constraints on the real-time performance of any implementation of a block diagram schema. The ... -
The Real-time Cost of Timing Uncertainty: Consensus and Failure Detection
(1991-11)In real distributed systems, processes may have only inexact information about the amount of real time needed for primitive operations such as process steps. This thesis studies the effect of this timing uncertainty on ... -
Real-time Simulation of Multidimensional Turing Machines by Storage Modification Machines
(1973-12)In [1] the author introduced a new machine model, now called the Storage Modification Machine (SMM). It was claimed, but not proved, that SMM's can simulate all sorts of Turing machines-- those with multidimensional worktapes ...
