We present two geometric routing algorithms that reliably deliver messages to all devices in a geocast region. One algorithm is based on flooding, the other on concurrent geometric routing. They are the fist known stateless geocasting algorithms. We formally prove the algorithms correct, evaluate their performance through abstract and concrete simulation and estimate their message complexity.

We propose a new approach to specifying and reasoning about forward recovery fault tolerant programs. We call it \emph{ideal stabilization}. The program is ideally stabilizing if its every state is legitimate. Ideal stabilization allows the specification designer to prescribe, with arbitrary degree of precision, not only the fault-free program behavior but also its recovery operation. Unlike the classic variant, ideal stabilization is particularly suitable for program composition. Specifications may or may not mention all possible states. We identify approaches to designing ideal stabilization to both classes of specifications. For the first class, we state the necessary condition for an ideally stabilizing solution. On the basis of this condition we prove that there is no ideally stabilizing solution to the leader election problem. We illustrate the utility of the concept of ideal stabilization by providing examples of well-known programs and proving them ideally stabilizing. Specifically, we prove ideal stabilization of the conflict manager, the alternator, the propagation of information with feedback and the alternating bit protocol.

We generalize the classic dining philosophers problem to separate the conflict and communication neighbors of each process. Communication neighbors may directly exchange information while conflict neighbors compete for the access to the exclusive critical section of code. This generalization is motivated by a number of practical problems in distributed systems including problems in wireless sensor networks. We present a self-stabilizing deterministic algorithm— GDP that solves this generalized problem. Our algorithm is terminating. We formally prove GDP correct and evaluate its performance. We extend the algorithm to handle a similarly generalized drinking philosophers and the committee coordination problem. We describe how GDP can be implemented in wireless sensor networks and demonstrate that this implementation does not jeopardize its correctness or termination properties.

We pose and study the problem of Byzantine-robust topology discovery in an arbitrary asynchronous network. The problem is an abstraction of fault-tolerant routing. We formally state the weak and strong versions of the problem. The weak version requires that either each node discovers the topology of the network or at least one node detects the presence of a faulty node. The strong version requires that each node discovers the topology regardless of faults. We focus on non-cryptographic solutions to these problems. We explore their bounds. We prove that the weak topology discovery problem is solvable only if the connectivity of the network exceeds the number of faults in the system. Similarly, we show that the strong version of the problem is solvable only if the network connectivity is more than twice the number of faults. We present solutions to both versions of the problem. The presented algorithms match the established graph connectivity bounds. The algorithms do not require the individual nodes to know either the diameter or the size of the network. The message complexity of both programs is low polynomial with respect to the network size. We describe how our solutions can be extended to add the property of termination, handle topology changes, and perform neighborhood discovery.

In this announcement, we report recent results where we address the open problem of snap-stabilization in message-passing systems.

We describe Emuli - a method of replacing sensor data with a network-wide model of stimuli events. Sensor readings are generated on demand from the modeling data stored at each device. This approach allows for both repeatable and variable experimentation with a network of physical devices for existing and planned sensing modalities. We illustrate the approach with (i) a light sensor and (ii) a hypothetical range sensor used in a tracking application.

The Kansei testbed at the Ohio State University is designed to facilitate research on networked sensing applications at scale. Kansei embodies a unique combination of characteristics as a result of its design focus on sensing and scaling: (i) Heterogeneous hardware infrastructure with dedicated node resources for local computation, storage, data exfiltration and back-channel communication, to support complex experimentation, (ii) Time accurate hybrid simulation engine for simulating substantially larger arrays using testbed hardware resources, (iii) High fidelity sensor data generation and real-time data and event injection, (iv) Software components and associated job control language to support complex multi-tier experiments utilizing real hardware resources and data generation and simulation engines. In this paper, we present the elements of Kansei testbed architecture, including its hardware and software platforms as well as its hybrid simulation and sensor data generation engines.

We present DRIFT - a total order multicast algorithm for ad hoc networks with mobile or static nodes. Due to the ad hoc nature of the network, DRIFT uses flooding for message propagation. The key idea of DRIFT is virtual flooding - a way of using unrelated message streams to propagate message causality information in order to accelerate message delivery. We describe DRIFT in detail. We evaluate its performance in a simulator and in a wireless sensor network. In both cases our results demonstrate that the performance of DRIFT exceeds that of the simple total order multicast algorithm designed for wired networks, on which it is based. In simulation at scale, for certain experiment settings, DRIFT achieved speedup of several orders of magnitude

Secure location verification is a recently stated problem that has a number of practical applications. The problem requires a wireless sensor network to confirm that a potentially malicious prover is located in a designated area. The original solution to the problem, as well as solutions to related problems, exploits the difference between propagation speeds of radio and sound waves to estimate the position of the prover. In this paper, we propose a solution that leverages the broadcast nature of the radio signal emitted by the prover and the distributed topology of the network. The idea is to separate the functions of the sensors. Some sensors are placed such that they receive the signal from the prover if it is inside the protected area. The others are positioned so that they can only receive the signal from the prover outside the area. Hence, the latter sensors reject the prover if they hear its signal. Our solution is versatile and it deals with provers using either omni-directional or directional propagation of radio signals without requiring any special hardware besides a radio transceiver. We estimate the bounds on the number of sensors required to protect the areas of various shapes and extend our solution to handle complex radio signal propagation, optimize sensor placement, and operate without precise topology information

Geometric routing algorithms like GFG (GPSR) are lightweight, scalable algorithms that can be used to route in resource-constrained ad hoc wireless networks. However, such algorithms run on planar graphs only. To efficiently construct a planar graph, they require a unit-disk graph. To make the topology unit-disk, the maximum link length in the network has to be selected conservatively. In practical setting this leads to the designs where the node density is rather high. Moreover, the network diameter of a planar subgraph is greater than the original graph, which leads to longer routes. To remedy this problem, we propose a void traversal algorithm that works on arbitrary geometric graphs. We describe how to use this algorithm for geometric routing with guaranteed delivery and compare its performance with GFG

Project ExScal (for extreme scale) fielded a 1000+ node wireless sensor network and a 200+ node peer-to-peer ad hoc network of 802.11 devices in a 13km by 300m remote area in Florida, USA during December 2004. In comparison with previous deployments, the ExScal application is relatively complex and its networks are the largest ones of either type fielded to date. In this paper, we overview the key requirements of ExScal, the corresponding design of the hardware/software platform and application, and some results of our experiments.

We present a solution to the problem of dining philosophers. Our solution tolerates malicious crashes. In a malicious crash the failed process behaves arbitrarily for a finite time and then ceases all operation undetectably to other processes. The tolerance of our solution is achieved by the combination of stabilization and crash failure locality. Stabilization allows our program to recover from an arbitrary state. Crash failure locality ensures that only a limited number of processes are affected by a process crash. The crash failure locality of our solution is optimal. Finally, we argue that the malicious crash fault model and its extensions are worthy of further study as they admit tolerances that are not achieved under stronger fault models and are unnecessary under weaker fault models.

An ideal approach to deal with faults in large-scale distributed systems is to contain the effects of faults as locally as possible and, additionally, to ensure some type of tolerance within each fault-affected locality. Existing results using this approach accommodate only limited faults (such as crashes) or assume that fault occurrence is bounded in space and/or time. In this paper, we define and explore possibility/impossibility of local tolerance with respect to arbitrary faults (such as Byzantine faults) whose occurrence may be unbounded in space and in time. Our positive results include programs for graph coloring and dining philosophers, with proofs that the size of their tolerance locality is optimal. The type of tolerance achieved within fault-affected localities is self-stabilization. That is, starting from an arbitrary state of the distributed system, each non-faulty process eventually reaches a state from where it behaves correctly as long as the only faults that occur henceforth (regardless of their number) are outside the locality of this process.

We dispel the myth that it is impossible for any stabilizing message passing program to be terminating. We identify fixpoint-symmetry as a necessary condition for a message passing stabilizing program to be terminating. Our results do confirm that a number of well-known input-output problems (e.g., leader election and consensus) do not admit a terminating and stabilizing solution. On the flip side, they show that reactive problems such as mutual exclusion and reliable-transmission do admit such solutions. We go on to present stabilizing and terminating programs for both problems. Also, we describe a way to add termination to a stabilizing program, and demonstrate it in the context of our design of a solution to the reliable-transmission problem.

In 1974, Dijkstra introduced the notion of self-stabilization and presented a token circulation distributed mutual exclusion (DMX) protocol as the first self-stabilizing (SS) algorithm. Since then, many variations of SS DMX algorithms have been presented. Most, if not all, of these algorithms impose stronger assumptions on their execution environments than those provided by common distributed systems. Independently, non SS DMX algorithms have been studied extensively in the last 15 years. This paper presents two SS DMX algorithms that are based on existing non SS DMX algorithms: one is based on a link-locking algorithm and the other is on a node-locking algorithm. Our algorithms assume execution environments that are close to those provided by common distributed systems. Furthermore, they provide better synchronization delays than token circulation SS DMX algorithms. We have implemented our algorithms and tested them with various initial configurations.