Abstract:
A token ring is an arrangement of N processors that take turns engaging in an activity which must be controlled. A token confers the right to engage in the controlled activity. Processors communicate with neighbors in the ring to obtain and release a token. The communication mechanism investigated in this paper is the safe register abstraction, which may arbitrarily corrupt a value that a processor reads when the operation reading a register is concurrent with an write operation on that register by a neighboring processor. The main results are simple protocols for quasi-atomic communication, constructed from safe registers. A quasi-atomic register behaves atomically except that a special undefined value may be returned in the case of concurrent read and write operations. Under certain conditions that constrain the number of writes and registers, quasi-atomic protocols are adequate substitutes for atomic protocols. The paper demonstrates how quasi-atomic protocols can be used to implement a self-stabilizing token ring, either by using two safe registers between neighboring processors or by using O(lg N) safe registers between neighbors, which lowers read complexity.

Abstract:
Phase clocks are synchronization tools that implement a form of logical time in distributed systems. For systems tolerating transient faults by self-repair of damaged data, phase clocks can enable reasoning about the progress of distributed repair procedures. This paper presents a phase clock algorithm suited to the model of transient memory faults in asynchronous systems with read/write registers. The algorithm is self-stabilizing and guarantees accuracy of phase clocks within O(k) time following an initial state that is k-faulty. Composition theorems show how the algorithm can be used for the timing of distributed procedures that repair system outputs.

Abstract:
Neighbor discovery is a component of communication and access protocols for ad hoc networks. Wireless sensor networks often must operate under a more severe low-power regimen than do traditional ad hoc networks, notably by turning off radio for extended periods. Turning off a radio is problematic for neighbor discovery, and a balance is needed between adequate open communication for discovery and silence to conserve power. This paper surveys recent progress on the problems of neighbor discovery for wireless sensor networks. The basic ideas behind these protocols are explained, which include deterministic schedules of waking and sleeping, randomized schedules, and combinatorial methods to ensure discovery.

Abstract:
This paper describes a heap construction that supports insert and delete operations in arbitrary (possibly illegitimate) states. After any sequence of at most O(m) heap operations, the heap state is guarantee to be legitimate, where m is the initial number of items in the heap. The response from each operation is consistent with its effect on the data structure, even for illegitimate states. The time complexity of each operation is O(lg K) where K is the capacity of the data structure; when the heap's state is legitimate the time complexity is O(lg n) for n equal to the number items in the heap.

Abstract:
The first self-stabilizing algorithm [Dij73] assumed the existence of a central daemon, that activates one processor at time to change state as a function of its own state and the state of a neighbor. Subsequent research has reconsidered this algorithm without the assumption of a central daemon, and under different forms of communication, such as the model of link registers. In all of these investigations, one common feature is the atomicity of communication, whether by shared variables or read/write registers. This paper weakens the atomicity assumptions for the communication model, proposing versions of [Dij73] that tolerate various weaker forms of atomicity. First, a solution for the case of regular registers is presented. Then the case of safe registers is considered, with both negative and positive results presented. The paper also presents an implementation of [Dij73] based on registers that have probabilistically correct behavior, which requires a notion of weak stabilization.

Abstract:
Designing protocols and formulating convenient programming units of abstraction for sensor networks is challenging due to communication errors and platform constraints. This paper investigates properties and implementation reliability for a \emph{local read-write} abstraction. Local read-write is inspired by the class of read-modify-write operations defined for shared-memory multiprocessor architectures. The class of read-modify-write operations is important in solving consensus and related synchronization problems for concurrency control. Local read-write is shown to be an atomic abstraction for synchronizing neighborhood states in sensor networks. The paper compares local read-write to similar lightweight operations in wireless sensor networks, such as read-all, write-all, and a transaction-based abstraction: for some optimistic scenarios, local read-write is a more efficient neighborhood operation. A partial implementation is described, which shows that three outcomes characterize operation response: success, failure, and cancel. A failure response indicates possible inconsistency for the operation result, which is the result of a timeout event at the operation's initiator. The paper presents experimental results on operation performance with different timeout values and situations of no contention, with some tests also on various neighborhood sizes.

Abstract:
Transient faults corrupt the content and organization of data structures. A recovery technique dealing with such faults is stabilization, which guarantees, following some number of operations on the data structure, that content of the data structure is legitimate. Another notion of fault tolerance is availability, which is the property that operations continue to be applied during the period of recovery after a fault, and successful updates are not lost while the data structure stabilizes to a legitimate state. The available, stabilizing 2-3 tree supports find, insert, and delete operations, each with O(lg n) complexity when the tree's state is legitimate and contains n items. For an illegitimate state, these operations have O(lg K) complexity where K is the maximum capacity of the tree. Within O(t) operations, the state of the tree is guaranteed to be legitimate, where t is the number of nodes accessible via some path from the tree's root at the initial state. This paper resolves, for the first time, issues of dynamic allocation and pointer organization in a stabilizing data structure.

Abstract:
This work reports experiences on using radio ranging to position sensors in a grid topology. The implementation is simple, efficient, and could be practically distributed. The paper describes an implementation and experimental result based on RSSI distance estimation. Novel techniques such as fuzzy membership functions and table lookup are used to obtain more accurate result and simplify the computation. An 86% accuracy is achieved in the experiment in spite of inaccurate RSSI distance estimates with errors up to 60%.

Abstract:
Self-stabilizing distributed control is often modeled by token abstractions. A system with a single token may implement mutual exclusion; a system with multiple tokens may ensure that immediate neighbors do not simultaneously enjoy a privilege. For a cyber-physical system, tokens may represent physical objects whose movement is controlled. The problem studied in this paper is to ensure that a synchronous system with m circulating tokens has at least d distance between tokens. This problem is first considered in a ring where d is given whilst m and the ring size n are unknown. The protocol solving this problem can be uniform, with all processes running the same program, or it can be non-uniform, with some processes acting only as token relays. The protocol for this first problem is simple, and can be expressed with Petri net formalism. A second problem is to maximize d when m is given, and n is unknown. For the second problem, the paper presents a non-uniform protocol with a single corrective process.

Abstract:
This technical report documents the poster session of SSS 2005, the Symposium on Self-Stabilizing Systems published by Springer as LNCS volume 3764. The poster session included five presentations. Two of these presentations are summarized in brief abstracts contained in this technical report.