Search
Now showing items 1-10 of 44
Brief announcement: Hardness of broadcasting in wireless networks with unreliable communication
(Association for Computing Machinery, 2009)
We prove two broadcast lower bounds for a wireless network model that includes unreliable links. For deterministic algorithms, we show n − 1 rounds are required, where n is the number of processes. For randomized algorithms, ...
Structuring Unreliable Radio Networks
(Association for Computing Machinery (ACM), 2011)
In this paper we study the problem of building a connected dominating set with constant degree (CCDS) in the dual graph radio network model [4,9,10]. This model includes two types of links: reliable, which always deliver ...
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 ...
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 ...
Brief Announcement: Partial Reversal Acyclicity
(Association for Computing Machinery (ACM), 2011)
Partial Reversal (PR) is a link reversal algorithm which ensures that an initially directed acyclic graph (DAG) is eventually a destination-oriented DAG. While proofs exist to establish the acyclicity property of PR, they ...
Reliably Detecting Connectivity Using Local Graph Traits
(Springer, 2010-12)
Local distributed algorithms can only gather sufficient information to identify local graph traits, that is, properties that hold within the local neighborhood of each node. However, it is frequently the case that global ...
Perspectives on the CAP Theorem
(Institute of Electrical and Electronics Engineers, 2012-02)
Almost twelve years ago, in 2000, Eric Brewer introduced the idea that there is a fundamental trade-off between consistency, availability, and partition tolerance. This trade-off, which has become known as the CAP Theorem, ...
Distributed House-Hunting in Ant Colonies
(Association for Computing Machinery (ACM), 2015-07)
We introduce the study of the ant colony house-hunting problem from a distributed computing perspective. When an ant colony's nest becomes unsuitable due to size constraints or damage, the colony relocates to a new nest. ...
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 ...
A Local Broadcast Layer for the SINR Network Model
(Association for Computing Machinery (ACM), 2015-07)
We present the first algorithm that implements an abstract MAC (absMAC) layer in the Signal-to-Interference-plus-Noise-Ratio (SINR) wireless network model. We first prove that efficient SINR implementations are not possible ...