Browsing Technical Reports and Memos by Title
Now showing items 1-20 of 40
-
A Reliable Broadcast Scheme for Sensor Networks
(2003-08-11)In this short technical report, we present a simple yet effective reliable broadcast protocol for sensor networks. This protocol disseminates packets throughout the sensor network by flooding and recovers from losses ... -
The Abstract MAC Layer
(2009-05-11)A diversity of possible communication assumptions complicates the study of algorithms and lower bounds for radio networks. We address this problem by defining an Abstract MAC Layer. This service provides reliable local ... -
The Abstract MAC Layer
(2010-08-26)A diversity of possible communication assumptions complicates the study of algorithms and lower bounds for radio networks. We address this problem by defining an abstract MAC layer. This service provides reliable local ... -
Asynchronous Failure Detectors
(2013-01-30)Failure detectors -- oracles that provide information about process crashes -- are an important abstraction for crash tolerance in distributed systems. The generality of failure-detector theory, while providing great ... -
Asynchronous Failure Detectors
(2013-10-10)Failure detectors -- oracles that provide information about process crashes -- are an important abstraction for crash tolerance in distributed systems. The generality of failure-detector theory, while providing great ... -
Bounded-Contention Coding for Wireless Networks in the High SNR Regime
(2012-08-27)Efficient communication in wireless networks is typically challenged by the possibility of interference among several transmitting nodes. Much important research has been invested in decreasing the number of collisions in ... -
Broadcasting in Unreliable Radio Networks
(2010-06-08)Practitioners agree that unreliable links, which fluctuate between working and not working, are an important characteristic of wireless networks. In contrast, most theoretical models of radio networks fix a static set of ... -
Coded Emulation of Shared Atomic Memory for Message Passing Architectures
(2013-07-17)This paper considers the communication and storage costs of emulating atomic (linearizable) read/write shared memory in distributed message-passing systems. We analyze the costs of previously-proposed algorithms by Attiya, ... -
A Coded Shared Atomic Memory Algorithm for Message Passing Architectures
(2014-08-01)This paper considers the communication and storage costs of emulating atomic (linearizable) multi-writer multi-reader shared memory in distributed message-passing systems. The paper contains three main contributions: (1) ... -
Consensus using Asynchronous Failure Detectors
(2015-03-02)The FLP result shows that crash-tolerant consensus is impossible to solve in asynchronous systems, and several solutions have been proposed for crash-tolerant consensus under alternative (stronger) models. One popular ... -
The Cost of Global Broadcast Using Abstract MAC Layers
(2010-02-09)We analyze greedy algorithms for broadcasting messages throughout a multi-hop wireless network, using a slot-based model that includes message collisions without collision detection. Our algorithms are split formally into ... -
Decomposing Broadcast Algorithms Using Abstract MAC Layers
(2011-02-23)In much of the theoretical literature on global broadcast algorithms for wireless networks, issues of message dissemination are considered together with issues of contention management. This combination leads to complicated ... -
Distributed Computation in Dynamic Networks
(2009-11-10)In this report we investigate distributed computation in dynamic networks in which the network topology changes from round to round. We consider a worst-case model in which the communication links for each round are chosen ... -
Dynamic Input/Output Automata: a Formal and Compositional Model for Dynamic Systems
(2013-07-08)We present dynamic I/O automata (DIOA), a compositional model of dynamic systems, based on I/O automata. In our model, automata can be created and destroyed dynamically, as computation proceeds. In addition, an automaton ... -
Dynamic Input/Output Automata: A Formal Model for Dynamic Systems
(2003-07-26)We present a mathematical state-machine model, the Dynamic I/O Automaton (DIOA) model, for defining and analyzing dynamic systems of interacting components. The systems we consider are dynamic in two senses: (1) components ... -
GeoQuorums: Implementing Atomic Memory in Mobile Ad Hoc Networks
(2004-02-25)We present a new approach, the GeoQuorums approach, for implementing atomic read/write shared memoryin mobile ad hoc networks. Our approach is based on associating abstract atomic objects with certain geographiclocations. ... -
Impossibility of boosting distributed service resilience
(2005-02-25)We prove two theorems saying that no distributed system in whichprocesses coordinate using reliable registers and f-resilient servicescan solve the consensus problem in the presence of f+1 undetectableprocess stopping ... -
Leader Election Using Loneliness Detection
(2011-10-12)We consider the problem of leader election (LE) in single-hop radio networks with synchronized time slots for transmitting and receiving messages. We assume that the actual number n of processes is unknown, while the size ... -
MAC Design for Analog Network Coding
(2010-08-02)Most medium access control mechanisms discard collided packets and consider interference harmful. Recent work on Analog Network Coding (ANC) suggests a different approach, in which multiple interfering transmissions are ... -
Modeling Computational Security in Long-Lived Systems, Version 2
(2008-11-22)For many cryptographic protocols, security relies on the assumption that adversarial entities have limited computational power. This type of security degrades progressively over the lifetime of a protocol. However, some ...
