Synchronous vs. Asynchronous Unison

This paper considers the self-stabilizing unison problem in uniform distributed systems. The contribution of this paper is threefold. First, we establish that when any self-stabilizing asynchronous unison protocol runs in synchronous systems, it converges to synchronous unison if the size of the clock K is greater than C _G , C _G being the length of the maximal cycle of the shortest maximal cycle basis if the graph contains cycles, 2 otherwise (tree networks). The second result demonstrates that the asynchronous unison in Boulinier et al. (In PODC ’04: Proceedings of the twenty-third annual ACM symposium on principles of distributed computing, pp. 150–159, 2004) provides a general self-stabilizing synchronous unison for trees which is optimal in memory space, i.e., it works with any K≥3, without any extra state, and stabilizes within 2D rounds, where D is the diameter of the network. This protocol gives a positive answer to the question whether there exists or not a general self-stabilizing synchronous unison for tree networks with a state requirement independent of local or global information of the tree. If K=3, then the stabilization time of this protocol is equal to D only, i.e., it reaches the optimal performance of Herman and Ghosh (Inf. Process. Lett. 54:259–265, 1995). The third result of this paper is a self-stabilizing unison for general synchronous systems. It requires K≥2 only, at least K+D states per process, and its stabilization time is 2D only. This is the best solution for general synchronous systems, both for the state requirement and the stabilization time. A preliminary version of this work was presented at the 7th International Symposium on Self-Stabilizing Systems (SSS 2005), Barcelona, Spain, October 2005.     

Self-stabilizing depth-first token circulation in arbitrary rooted networks

Abstract. We present a deterministic distributed depth-first token passing protocol on a rooted network. This protocol uses neither the processor identifiers nor the size of the network, but assumes the existence of a distinguished processor, called the root of the network. The protocol is self-stabilizing, meaning that starting from an arbitrary state (in response to an arbitrary perturbation modifying the memory state), it is guaranteed to reach a state with no more than one token in the network. Our protocol implements a strictly fair token circulation scheme. The proposed protocol has extremely small state requirement – only states per processor, i.e., bits per processor, where is the degree of the network. The protocol can be used to implement a strictly fair distributed mutual exclusion in any rooted network. This protocol can also be used to construct a DFS spanning tree. Received: July 1998 / Accepted: April 2000     

Fault-containing self-stabilizing distributed protocols

Self-stabilization is an elegant approach for designing a class of fault-tolerant distributed protocols. A self-stabilizing protocol is guaranteed to eventually converge to a legitimate state after a transient fault. However, even a minor transient fault can cause vast disruption in the system before legitimacy is reached. This paper introduces the notion of fault-containment to address this particular weakness of self-stabilizing systems. Informally, a fault-containing self-stabilizing protocol, in addition to providing self- stabilization, contains the effects of faults. This ensures that disruption during recovery from faults, is proportional to the extent of the faults. The paper begins with a formal framework for specifying and evaluating fault-containing self-stabilizing protocols. The main result of the paper is a transformer that converts any non-reactive self-stabilizing protocol into an equivalent fault-containing self-stabilizing protocol that can repair any single fault in the system in O(1) time. For a large class of input protocols, the corresponding output protocols produced by the transformer have O(1) space overhead. The small time and space overhead make the fault-containing self-stabilizing protocol a practical alternative to the original self-stabilizing protocol. The transformer is based on a novel stabilizing timer paradigm that significantly simplifies the task of fault-containment.     

Dynamic Analysis of the Arrow Distributed Protocol

Distributed queuing is a fundamental coordination problem that arises in a variety of applications, including distributed directories, totally ordered multicast, and distributed mutual exclusion. The arrow protocol is a solution to distributed queuing that is based on path reversal on a pre-selected spanning tree of the network. We present a novel and comprehensive competitive analysis of the arrow protocol. We consider the total cost of handling a finite number of queuing requests, which may or may not be issued concurrently, and show that the arrow protocol is -competitive to the optimal queuing protocol, where s and D are the stretch and the diameter, respectively, of the spanning tree. In addition, we show that our analysis is almost tight by proving that for every spanning tree chosen for execution, the arrow protocol is -competitive to the optimal queuing protocol. Our analysis reveals an intriguing connection between the arrow protocol and the nearest neighbor traveling salesperson tour on an appropriately defined graph.     

Randomized self-stabilizing and space optimal leader election under arbitrary scheduler on rings

We present a randomized self-stabilizing leader election protocol and a randomized self-stabilizing token circulation protocol under an arbitrary scheduler on anonymous and unidirectional rings of any size. These protocols are space optimal. We also give a formal and complete proof of these protocols. To this end, we develop a complete model for probabilistic self-stabilizing distributed systems which clearly separates the non deterministic behavior of the scheduler from the randomized behavior of the protocol. This framework includes all the necessary tools for proving the self- stabilization of a randomized distributed system: definition of a probabilistic space and definition of the self-stabilization of a randomized protocol. We also propose a new technique of scheduler management through a self-stabilizing protocol composition (cross-over composition). Roughly speaking, we force all computations to have a fairness property under any scheduler, even under an unfair one. This work was done while Maria Gradinariu was working at LRI, Univ. Paris-Sud, CNRS.     

Distributed fault tolerant computation of weakly connected dominating set in ad hoc networks

Our purpose in this paper is to propose a self-stabilizing protocol for weakly connected dominating set (WCDS) set in a given ad hoc network graph. WCDS is a particular variant of graph domination predicates which play an important role in routing in ad hoc networks. There are many variants of domination problems in bidirectional networks; WCDS is also useful in forming clusters in ad hoc networks. There are many heuristic and distributed algorithms to compute WCDS in network graphs while almost all of them will need complete information about the network topology and most of them are not fault tolerant or mobility tolerant. Self-stabilization is a protocol design paradigm that is especially useful in resource constrained infrastructure-less networks since nodes can make moves based on local knowledge only and yet a global task is accomplished in a fault tolerant manner; it also facilitates for nodes to enter and exit the network freely. There exist self-stabilizing protocols for minimal spanning tree, total domination, and others. We have shown that the paradigm is capable of designing a protocol for WCDS. Our objective is to mathematically prove the correctness and the convergence of the protocol in any worst-case scenario, as is usually done for self-stabilizing protocols for other graph predicates used for ad hoc networks.     

Uniform dynamic self-stabilizing leader election

A distributed system is self-stabilizing if it can be started in any possible global state. Once started the system regains its consistency by itself, without any kind of outside intervention. The self-stabilization property makes the system tolerant to faults in which processors exhibit a faulty behavior for a while and then recover spontaneously in an arbitrary state. When the intermediate period in between one recovery and the next faulty period is long enough, the system stabilizes. A distributed system is uniform if all processors with the same number of neighbors are identical. A distributed system is dynamic if it can tolerate addition or deletion of processors and links without reinitialization. In this work, we study uniform dynamic self-stabilizing protocols for leader election under readwrite atomicity. Our protocols use randomization to break symmetry. The leader election protocol stabilizes in O(ΔD log n) time when the number of the processors is unknown and O(ΔD), otherwise. Here Δ denotes the maximal degree of a node, D denotes the diameter of the graph and n denotes the number of processors in the graph. We introduce self-stabilizing protocols for synchronization that are used as building blocks by the leader-election algorithm. We conclude this work by presenting a simple, uniform, self-stabilizing ranking protocol     

SELF-STABILIZING DISTRIBUTED SORTING IN TREE NETWORKS

This paper presents a self-stabilizing distributed sorting algorithm for tree networks. The distributed sorting problem can be informally described as follows: Nodes cooperate to reach a global configuration where every node, depending on its identifier, is assigned a specific final value taken from a set of input values distributed across all nodes. The input values may change in time. In our solution, the system reaches its final configuration in a finite time after the input values are stable and the faults cease. The fault-tolerance and the adaptivity to changing input is achieved using Dijkstra's paradigm of self-stabilization. A self-stabilizing algorithm, regardless of the initial system state, will converge in finite time to a set of legitimate states without the need for explicit exception handlers or backward recovery. Our solution is based on a continuous broadcast with acknowledgment along the tree edges to achieve the synchronization among processes in the system. It has 0(n ×h) time complexity and only 0(log(n) × ) memory requirement where h is the degree of the tree and h is the height of the tree.     

Local Stabilizer

A local stabilizer protocol that takes any on- or off-line distributed algorithm and converts it into a synchronous self-stabilizing algorithm with local monitoring and repairing properties is presented. Whenever the self-stabilizing version enters an inconsistent state, the inconsistency is detected, in O(1) time, and the system state is repaired in a local manner. The expected computation time that is lost during the repair process is proportional to the largest diameter of a faulty region.     

Maximum lifetime data sensing and extraction in energy constrained networked sensor systems

We focus on data gathering problems in energy constrained networked sensor systems. The system operates in rounds where a subset of the sensors generate a certain number of data packets during each round. All the data packets need to be transferred to the base station. The goal is to maximize the system lifetime in terms of the number of rounds the system can operate. We show that the above problem reduces to a restricted flow problem with quota constraint, flow conservation requirement, and edge capacity constraint. We further develop a strongly polynomial time algorithm for this problem, which is guaranteed to find an optimal solution. We then study the performance of a distributed shortest path heuristic for the problem. This heuristic is based on self-stabilizing spanning tree construction and shortest path routing methods. In this heuristic, every node determines its sensing activities and data transfers based on locally available information. No global synchronization is needed. Although the heuristic cannot guarantee optimality, simulations show that the heuristic has good average case performance over randomly generated deployment of sensors. We also derive bounds for the worst case performance of the heuristic.     

An energy-efficient,self-stabilizing and distributed algorithm for maximal independent set construction in wireless sensor networks

Maximal independent set (MIS) is a very important structure that provides data aggregation, topology control and routing for wireless sensor networks (WSNs). Energy-efficient and fault-tolerant construction of MIS on WSNs is one of the vital tasks. A distributed sensor network is self-stabilizing if it can initially start at any state and regain a legal state in a finite time without any external intervention. Self-stabilization is a considerable method to provide fault tolerance in WSNs. This paper presents a distributed self-stabilizing MIS algorithm which is an improved version of Turau’s algorithm under a fully distributed scheduler for WSNs. The proposed algorithm is theoretically analyzed and evaluated with its counterparts. The proposed algorithm is compared with the other studies through testbed experiments on IRIS nodes and simulations on TOSSIM environment. It is shown that the proposed algorithm outperforms other algorithms in terms of move count and energy consumption.     

How to Prove Impossibility Under Global Fairness: On Space Complexity of Self-Stabilizing Leader Election on a Population Protocol Model

A population protocol is one of distributed computing models for passively-mobile systems, where a number of agents change their states by pairwise interactions between two agents. In this paper, we investigate the solvability of the self-stabilizing leader election in population protocols without any kind of oracles. We identify the necessary and sufficient conditions to solve the self-stabilizing leader election in population protocols from the aspects of local memory complexity and fairness assumptions. This paper shows that under the assumption of global fairness, no protocol using only n−1 states can solve the self-stabilizing leader election in complete interaction graphs, where n is the number of agents in the system. To prove this impossibility, we introduce a novel proof technique, called closed-set argument. In addition, we propose a self-stabilizing leader election protocol using n states that works even under the unfairness assumption. This protocol requires the exact knowledge about the number of agents in the system. We also show that such knowledge is necessary to construct any self-stabilizing leader election protocol.     

A one-round secure message broadcasting protocol through a key sharing tree

A key sharing graph is one in which each vertex corresponds to a player, and each edge corresponds to a secret key shared by the two players incident with the edge. Assume that, given a key sharing graph which contains a spanning tree, any designated player wishes to broadcast a message to all the other players securely against an eavesdropper. This can be easily done by flooding the message on the tree using the one-time pad scheme. However, the number of communication rounds in such a protocol is equal to the height of the tree. This paper provides another efficient protocol, which has exactly one communication round, i.e., we give a non-interactive protocol.     

Finding the k most vital edges with respect to minimum spanning tree

For a connected, undirected and weighted graph G = (V,E), the problem of finding the k most vital edges of G with respect to minimum spanning tree is to find k edges in G whose removal will cause greatest weight increase in the minimum spanning tree of the remaining graph. This problem is known to be NP-hard for arbitraryk. In this paper, we first describe a simple exact algorithm for this problem, based on t he approach of edge replacement in the minimum spanning tree of G. Next we present polynomial-time randomized algorithms that produce optimal and approximate solutions to this problem. For and , our algorithm producing optimal solution has a time complexity of O(mn) with probability of success at least , which is 0.90 for and asymptotically 1 when k goes to infinity. The algorithm producing approximate solution runs in time with probability of success at least , which is 0.998 for , and produces solution within factor 2 to the optimal one. Finally we show that both of our randomized algorithms can be easily parallelized. On a CREW PRAM, the first algorithm runs in O(n) time using processors, and the second algorithm runs in time using mn/logn processors and hence is RNC. Received 30 October 1995 / 5 November 1998     

An efficient fault-containing self-stabilizing algorithm for the shortest path problem

Shortest path finding has a variety of applications in transportation and communication. In this paper, we propose a fault-containing self-stabilizing algorithm for the shortest path problem in a distributed system. The improvement made by the proposed algorithm in stabilization times for single-fault situations can demonstrate the desirability of an efficient fault-containing self-stabilizing algorithm. For single-fault situations, the worst-case stabilization time of the proposed algorithm is O(Δ), where Δ is the maximum node degree in the system, and the contamination number of the proposed algorithm is 1.     

An efficient fault-containing self-stabilizing algorithm for finding a maximal independent set

An independent set is a useful structure because, in some situations, it defines a set of mutually compatible operations, i.e., operations that can be executed simultaneously. We design a fault-containing self-stabilizing algorithm that finds a maximal independent set for an asynchronous distributed system. Our algorithm is an improvement on the self-stabilizing algorithm in Shukla et al. [1995]. In the single-fault situation, the worst-case stabilization time of Shukla's algorithm is /spl Omega/(n), where n is the number of nodes in the system, whereas the worst-case stabilization time of our algorithm is O(/spl Delta/), where /spl Delta/ is the maximum node degree in the system. Compared also with the fault-containing algorithm that is induced from applying the general transformer in Ghosh et al. [1996] to Shukla's algorithm, our algorithm is also seen to be faster in stabilization time, in the single-fault situation. Therefore, our algorithm can be considered to be the most efficient fault-containing self-stabilizing algorithm for the maximal independent set finding up to this point.     

Efficient detection and resolution of OR deadlocks in distributed systems

This paper proposes a distributed algorithm for resolving deadlocks under the OR request model. The algorithm builds a distributed spanning tree by propagating probes. An encoding scheme is devised to deduce the ancestor–descendant relationship between tree nodes, so that the initiator of the algorithm collects only non-tree edge information to detect deadlock, whereas the current algorithms require all the edge information for deadlock detection. The proposed algorithm resolves all deadlocks reachable from the initiator. Its performance in terms of number of messages and execution time is better than or comparable to that of the existing algorithms. We further showed through analytic evaluation that the suggested algorithm substantially shortens deadlock detection time.     

Symbolic model checking for self-stabilizing algorithms

A distributed system is said to be self-stabilizing if it converges to safe states regardless of its initial state. In this paper we present our results of using symbolic model checking to verify distributed algorithms against the self-stabilizing property. In general, the most difficult problem with model checking is state explosion; it is especially serious in verifying the self-stabilizing property, since it requires the examination of all possible initial states. So far applying model checking to self-stabilizing algorithms has not been successful due to the problem of state explosion. In order to overcome this difficulty, we propose to use symbolic model checking for this purpose. Symbolic model checking is a verification method which uses Ordered Binary Decision Diagrams (OBDDs) to compactly represent state spaces. Unlike other model checking techniques, this method has the advantage that most of its computations do not depend on the initial states. We show how to verify the correctness of algorithms by means of SMV, a well-known symbolic model checker. By applying the proposed approach to several algorithms in the literature, we demonstrate empirically that the state spaces of self-stabilizing algorithms can be represented by OBDDs very efficiently. Through these case studies, we also demonstrate the usefulness of the proposed approach in detecting errors     

Bipartite Linear χ‐Consensus of Double‐Integrator Multi‐Agent Systems With Measurement Noise

The bipartite consensus problem is investigated for double‐integrator multi‐agent systems in the presence of measurement noise. A distributed protocol with time‐varying consensus gain is proposed. By using tools of state transition matrix and algebraic graph theory, necessary and sufficient conditions for the designed protocol to be a mean square bipartite linear χ‐consensus protocol are given. It is shown that the signed digraph being structurally balanced and having a spanning tree are not only sufficient, but also necessary for bipartite consensus. Furthermore, the protocol is proved to be a mean square bipartite average consensus protocol if the signed graph is weight balanced.     

Uniform and self-stabilizing token rings allowing unfair daemon

A distributed system consists of a set of processes and a set of communication links, each connecting a pair of processes. A distributed system is said to be self-stabilizing if it converges to a correct system state no matter which system state it starts with. A self-stabilizing system is considered to be an ideal fault tolerant system, since it tolerates any kind and any finite number of transient failures. In this paper, we investigate uniform randomized self-stabilizing mutual exclusion systems on unidirectional rings. As far as deterministic systems are concerned, it is well-known that there is no such system when the number 6 of processes (i.e., ring size) is composite, even if a fair central-daemon (c-daemon) is assumed. A fair daemon guarantees that every process will be selected for activation infinitely many times. As for randomized systems, regardless of the ring size, we can design a self-stabilizing system even for a distributed-daemon (d-daemon). However, every system proposed so far assumes a daemon to be fair, and effectively replies on this assumption. This paper tackles the problem of designing a self-stabilizing system, without assuming the fairness of a daemon. As a result, we present a randomized self-stabilizing mutual exclusion system for any size n (including composite size) of a unidirectional ring. The number of process states of the system is 2(n-1)