Browsing Works of Nancy Lynch by Issue Date
Now showing items 21-40 of 107
-
Brief announcement: Minimum spanning trees and cone-based topology control
(Association for Computing Machinery, 2009)Consider a setting where nodes can vary their transmission power thereby changing the network topology, the goal of topology control is to reduce the transmission power while ensuring the communication graph remains ... -
On the weakest failure detector ever
(Springer Berlin Heidelberg, 2009-01)Many problems in distributed computing are impossible to solve when no information about process failures is available. It is common to ask what information about failures is necessary and sufficient to circumvent some ... -
Self-Stabilizing Message Routing in Mobile ad hoc Networks
(2009-01-28)We present a self-stabilizing algorithm for routing messages between arbitrary pairs of nodes in a mobile ad hoc network. Our algorithm assumes the availability of a reliable GPS service, which supplies mobile nodes with ... -
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 ... -
Modeling Radio Networks
(2009-06-04)We describe a modeling framework and collection of foundational composition results for the study of probabilistic distributed algorithms in synchronous radio networks. Existing results in this setting rely on informal ... -
Self-stabilizing robot formations over unreliable networks
(Association for Computing Machinery, 2009-07)We describe how a set of mobile robots can arrange themselves on any specified curve on the plane in the presence of dynamic changes both in the underlying ad hoc network and in the set of participating robots. Our strategy ... -
Simulating fixed virtual nodes for adapting wireline protocols to MANET
(Institute of Electrical and Electronics Engineers, 2009-08)The virtual node layer (VNLayer) is a programming abstraction for mobile ad hoc networks (MANETs). It defines simple virtual servers at fixed locations in a network, addressing a central problem for MANETs, which is the ... -
The abstract MAC layer
(Association for Computing Machinery, 2009-09)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 ... -
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 ... -
Timeout Order Abstraction for Time-Parametric Verification of Loosely Synchronized Real-Time Distributed Systems
(Artist Consortium, 2009-12)We present timeout order abstraction (TO-abstraction), a technique to systematically abstract a given loosely synchronized real-time distributed system (LSRTDS) into an untimed model. We define the subclass of LSRTDS’s ... -
Task-Structured Probabilistic I/O Automata
(2009.)Modeling frameworks such as Probabilistic I/O Automata (PIOA) and Markov Decision Processes permit both probabilistic and nondeterministic choices. In order to use these frameworks to express claims about probabilities of ... -
Distributed computation in dynamic networks
(Association for Computing Machinery, 2010)In this paper 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 ... -
Neighbor discovery in mobile ad hoc networks using an abstract MAC layer
(Institute of Electrical and Electronics Engineers, 2010-01)We explore the problem of neighbor discovery in a mobile ad hoc network environment. We describe a protocol for learning about neighboring nodes in such an environment. The protocol is used for establishing and tearing ... -
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 ... -
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 ... -
Broadcasting in unreliable radio networks
(Association for Computing Machinery, 2010-07)Practitioners agree that unreliable links, which sometimes deliver messages and sometime do not, are an important characteristic of wireless networks. In contrast, most theoretical models of radio networks fix a static set ... -
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 ... -
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 ... -
Rambo: a robust, reconfigurable atomic memory service for dynamic networks
(Springer-Verlag, 2010-09)n this paper, we present Rambo, an algorithm for emulating a read/write distributed shared memory in a dynamic, rapidly changing environment. Rambo provides a highly reliable, highly available service, even as participants ... -
Decomposing broadcast algorithms using abstract mac layers
(Association for Computing Machinery, 2010-09)In much of the theoretical literature on wireless algorithms, issues of message dissemination are considered together with issues of contention management. This combination leads to complicated algorithms and analysis, ...
