self-stabilization

We propose ProSe, a programming tool that enables the designers to (1) specify protocols in simple, abstract models, (2) reuse existing fault-tolerant/self-stabilizing protocols from the literature, and (3) automatically generate and deploy code. ProSe hides the deficiencies of existing programming platforms that require the designers to explicitly deal with buffer management, stack management, and flow control. As a result, we expect that ProSe will enable rapid prototyping and quick deployment of protocols.

We focus on stabilizing interference-free slot assignment to WMN nodes. These slot assignments allow each node to transmit its data while ensuring that it does not interfere with other nodes.

In this paper, we propose a self-stabilizing deterministic TDMA algorithm where a sensor is aware of only its neighbors. We show that the slots are assigned to the sensors in a concurrent fashion and starting from arbitrary initial states, the algorithm converges to states where collision-free communication among the sensors is restored. Moreover, this algorithm facilitates the transformation of abstract programs into programs in WAC model that are deterministically correct.

To enable the designers to prototype power management protocols in target platform (e.g., nesC/TinyOS), in this paper, we use ProSe, a programming tool for sensor networks. ProSe enables the designers to specify their programs in simple abstract models while hiding low-level challenges of sensor networks and programming-level challenges. As a case study, in this paper, we specify a power management protocol with ProSe, automatically generate the corresponding nesC/TinyOS code, and evaluate its performance.

In this paper, we present a self-stabilizing deterministic algorithm for TDMA in networks where a sensor is only aware of its neighbors. To our knowledge, this is the first such algorithm that achieves these properties. Moreover, this is the firrst algorithm that demonstrates the feasibility of stabilization-preserving deterministic transformation of a program in shared-memory model on an arbitrary topology into a program that is consistent with the sensor network model.

We consider a new atomicity model, write all with collision (WAC), that captures the computations of sensor networks and focus on transformations from read/write model to WAC model and vice versa. We show that the transformation from WAC model to read/write model is stabilization preserving, and the transformation from read/write model to WAC model is stabilization preserving for timed systems. In the transformation from read/write model to WAC model, if the system is untimed (asynchronous) and processes are deterministic then under reasonable assumptions, we show that (1) the resulting program in WAC model can allow at most one process to execute, and (2) the resulting program in WAC model cannot be stabilizing.

We focus on the problem of designing a TDMA service for a grid-based sensor network. Such networks are readily found in many applications in the area of monitoring, hazard detection, and so on. We consider three communication patterns, broadcast, convergecast and local gossip, that occur frequently in these systems.

In this paper, we present a self-stabilizing, deterministic algorithm for TDMA in networks where a sensor is aware of only its neighbors. This is the first such algorithm that achieves these properties. Moreover, this is the first algorithm that demonstrates the feasibility of stabilization preserving, deterministic transformation of a shared memory distributed program on an arbitrary topology into a program that is consistent with the sensor network model.

We present TDMA algorithms customized for different communication patterns, namely, broadcast,convergecast and local gossip, that occur commonly in sensor networks.

In this paper, we consider a new atomicity model, write all with collision (WAC), and compare it with existing models considered in the literature. This model captures the computations in sensor networks. We show that it is possible to transform a program from WAC model into a program in read/write model, and vice versa.