Self-Stabilizing Routing and Related Protocols

Aself-stabilizingsystem is a distributed system which can tolerateany numberandany typeof faults in the history. After the last fault occurs the system converges to alegitimate behavior. The self-stabilization property is very useful for systems in which processors may malfunction for a while and then recover. When there is a long enough period during which no processor malfunctions the system stabilizes.Dynamicdistributed systems are systems in which communication links and processors may fail and recover during normal operation. Such failures could cause partitioning of the system communication graph. The application of self-stabilizing protocols to dynamic systems is natural. Following the last topology change each connected component of the system stabilizes independently. We present self-stabilizing dynamic protocols for a variety of tasks including: routing, leader election, and topology update. For systems that support local broadcasts to neighbors in a single time unit the protocol for each of those tasks stabilizes in Θ(d) time, wheredis theactualdiameter of the system.     

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.     

Analyzing expected time by scheduler-luck games

We introduce a novel technique, the scheduler luck game (in short sl-game) for analyzing the performance of randomized distributed protocols. We apply it in studying uniform self-stabilizing protocols for leader election under read/write atomicity. We present two protocols for the case where each processor in the system can communicate with all other processors and analyze their performance using the sl-game technique     

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.     

Possible and Impossible Self-Stabilizing Digital Clock Synchronization in General Graphs

We study digital clock synchronization for multiprocessor systems, where processors are triggered by a common clock pulse and communicate with others via shared memory.A self-stabilizing digital clock synchronization protocol for systems with a general communication graph is presented. The protocol can commence in an arbitrary non-consistent system state and converges to a legitimate state in which the clocks are synchronized and incremented by one in every subsequent pulse.To enhance the fault-tolerance of our protocol, we allow that during and following convergence processors may stop operating. Crash failures may partition the communication graph into several connected components. Our protocol synchronizes the clocks of the processors in every such connected component. For the case in which faulty processors can exhibit Byzantine behavior, we prove that there is no digital clock synchronization protocol that tolerates even one single faulty processor.     

Self-stabilizing distributed queuing

Distributed queuing is a fundamental coordination problem arising in a variety of applications, including distributed shared memory, distributed directories, and totally ordered multicast. A distributed queue can be used to order events, user operations, or messages in a distributed system. This paper presents a new self-stabilizing distributed queuing protocol. This protocol adds self-stabilizing actions to the arrow distributed queuing protocol, a simple path-reversal protocol that runs on a spanning tree of the network. We present a proof that the protocol stabilizes to a stable state irrespective of the (perhaps faulty) initial state, and also present an analysis of the time until convergence. The self-stabilizing queuing protocol is structured as a layer that runs on top of any self-stabilizing spanning tree protocol. This additional queuing layer is guaranteed to stabilize in time bounded by a constant number of message delays across an edge, thus establishing that the stabilization time for distributed queuing is not much more than the stabilization time for spanning tree maintenance. The key idea in our protocol is that the global predicate defining the legality of a protocol state can be written as the conjunction of many purely local predicates, one for each edge of the spanning tree.     

A Self-Stabilizing Leader Election Algorithm for Tree Graphs

We propose a self-stabilizing algorithm (protocol) for leader election in a tree graph. We show the correctness of the proposed algorithm by using a new technique involving induction.     

Uniform leader election protocols for radio networks

A radio network is a distributed system with no central arbiter, consisting of n radio transceivers, henceforth referred to as stations. We assume that the stations are identical and cannot be distinguished by serial or manufacturing number. The leader election problem asks to designate one of the stations as leader. In this work, we focus on single-channel, single-hop radio networks. We assume that time is slotted and all transmissions occur at slot boundaries. In each time slot, the stations transmit on the channel with some probability until, eventually, one of the stations is declared leader. A leader election protocol is said to be uniform if, in each time slot, every station transmits with the same probability. In a seminal paper, Willard (1986) presented a uniform leader election protocol for single-channel single-hop radio stations terminating in log log n+o(log log n) expected time slots. It was open for more than 15 years whether Willard's protocol featured the same time performance with "high probability." One of our main contributions is to show that, unfortunately, this is not the case. Specifically, we prove that for every parameter f∈e^O(n), in order to ensure termination with probability exceeding 1-1/f, Willard's protocol must take log log n+Ω(√f) time slots. The highlight of this work is a novel uniform leader election protocol that terminates, with probability exceeding 1-1/f, in log log n+o(log log n)+O(log f) time slots. Finally, we provide simulation results that show that our leader election protocol outperforms Willard's protocol in practice     

Self-stabilizing leader election in optimal space under an arbitrary scheduler

A silent self-stabilizing asynchronous distributed algorithm, SSLE, is given for the leader election problem in a connected unoriented (bidirectional) network with unique IDs. SSLE also constructs a BFS tree on the network rooted at that leader. SSLE uses O(logn) space per process and stabilizes in O(n) rounds, against the unfair daemon, where n is the number of processes in the network.     

A new solution for the Byzantine agreement problem

Reliability is an important research topic in distributed computing systems consisting of a large number of processors. To achieve reliability, the fault-tolerance scheme of the distributed computing system must be revised. This kind of problem is known as a Byzantine agreement (BA) problem. It requires all fault-free processors to agree on a common value, even if some components are corrupt. Consequently, there have been significant studies of this agreement problem in distributed systems. However, the traditional BA protocols focus on running ⌊(n−1)/3⌋+1 rounds of message exchange continuously to make each fault-free processor reach an agreement. In other words, since having a large number of messages results in a large protocol overhead, those protocols are inefficient and unreasonable, especially for some network environments which have large number of processors. In this study, we propose a novel and efficient protocol to reduce the number of messages. Our protocol can collect, compare and replace the received values to find the reliable processors and replace the values sent by the unreliable processors. Subsequently, each processor can agree on a common value through three rounds of message exchange. Furthermore, the proposed protocol can use the minimum number of messages to tolerate the maximum number of faulty components in a distributed system.     

A note on leader election in directed split-stars and directed alternating group graphs

A leader node is defined to be any node of the network unambiguously identified by some characteristics. In this paper, we first present a distributed algorithm for finding a leader node of a directed split-star. Moreover, an efficient self-stabilizing leader election algorithm that converges with linear rounds is proposed for directed split-stars. Actually, the distributed algorithm and the self-stabilizing algorithm are also applicable to the problem of directed alternating group graphs. As far as we know, no self-stabilizing leader election algorithm was known for the two graphs.     

Eventual strong consensus with fault detection in the presence of dual failure mode on processors under dynamic networks

The fault tolerance capability and reliability of a distributed system can be enhanced if the Strong Consensus (SC) problem can be properly addressed. Most of the extant SC protocols are designed for static networks. Besides, the number of rounds of message exchange required by all of the extant SC protocols is determined by the total number of processors in the network rather than by the actual number of faulty processors in the network. Even if there is only a few or no faulty processor in the network, the SC protocols may waste a lot of time and memory space on many unnecessary rounds of message exchange. Thus, this paper revisits the SC problem in dynamic networks and uses two rules, Detection Rule for Malicious fault in dynamic network (DRM_dyn) and Early Stopping Rule for Strong Consensus protocol in dynamic networks (ESRSC_dyn), to reduce the time consumption and space complexity of SC protocols. DRM_dyn is a rule that detects malicious processors, and ESRSC_dyn is a rule that determines whether the messages collected are enough for reaching a strong consensus. To be succinct, the proposed SC protocol can not only work in dynamic networks consisting of both dormant processors and malicious processors (dual failure mode) but also ensure that all correct processors reach a SC value within fewer rounds of message exchange than required by the extant SC protocols.     

Optimal asynchronous agreement and leader election algorithm for complete networks with Byzantine faulty links

Summary.  We consider agreement and leader election on asynchronous complete networks when the processors are reliable, but some of the channels are subject to failure. Fischer, Lynch, and Paterson have already shown that no deterministic algorithm can solve the agreement problem on asynchronous networks if any processor fails during the execution of the algorithm. Therefore, we consider only channel failures. The type of channel failure we consider in this paper is Byzantine failure, that is, channels fail by altering messages, sending false information, forging messages, losing messages at will, and so on. There are no restrictions on the behavior of a faulty channel. Therefore, a faulty channel may act as an adversary who forges messages on purpose to prevent the successful completion of the algorithm. Because we assume an asynchronous network, the channel delays are arbitrary. Thus, the faulty channels may not be detectable unless, for example, the faulty channels cause garbage to be sent. We present the first known agreement and leader election algorithm for asynchronous complete networks in which the processors are reliable but some channels may be Byzantine faulty. The algorithm can tolerate up to [n−22] faulty channels, where n is the number of processors in the network. We show that the bound on the number of faulty channels is optimal. When the processors terminate their corresponding algorithms, all the processors in the network will have the same correct vector, where the vector contains the private values of all the processors. Received: May 1994/Accepted: July 1995     

Leader election problem on networks in which processor identitynumbers are not distinct

In the networks considered in this paper, processors do not have distinct identity numbers. On such a network, we discuss the leader election problem and the problem of counting the number of processors having the same identity number. As the communication mode, we consider port-to-port, broadcast-to-port, port-to-mail box, and broadcast-to-mailbox. For each of the above communication modes, we present: an algorithm for counting the number of processors with the same identity number; an algorithm for solving the leader election problem; and a graph theoretical characterization of the solvable class for the leader election problem     

On automatic verification of self-stabilizing population protocols

The population protocol model has emerged as an elegant computation paradigm for describing mobile ad hoc networks, consisting of a number of mobile nodes that interact with each other to carry out a computation. The interactions of nodes are subject to a fairness constraint. One essential property of population protocols is that all nodes must eventually converge to the correct output value (or configuration). In this paper, we aim to automatically verify self-stabilizing population protocols for leader election and token circulation in the Spin model checker. We report our verification results and discuss the issue of modeling strong fairness constraints in Spin.     

A self-stabilizing ring orientation algorithm with a smaller numberof processor states

A distributed system is said to be self-stabilizing if it will eventually reach a legitimate system state regardless of its initial state. Because of this property, a self-stabilizing system is extremely robust against failures; it tolerates any finite number of transient failures. The ring orientation problem for a ring is the problem of all the processors agreeing on a common ring direction. This paper focuses on the problem of designing a deterministic self-stabilizing ring orientation system with a small number of processor states under the distributed daemon. Because of the impossibility of symmetry breaking, under the distributed daemon, no such systems exist when the number n of processors is even. Provided that n is odd, the best known upper bound on the number of states is 256 in the link-register model, and eight in the state-reading model. We improve the bound down to 6³=216 in the link-register model     

A survey on self-stabilizing algorithms for independence,domination, coloring,and matching in graphs

Dijkstra defined a distributed system to be self-stabilizing if, regardless of the initial state, the system is guaranteed to reach a legitimate (correct) state in a finite time. Even though the concept of self-stabilization received little attention when it was introduced, it has become one of the most popular fault tolerance approaches. On the other hand, graph algorithms form the basis of many network protocols. They are used in routing, clustering, multicasting and many other tasks. The objective of this paper is to survey the self-stabilizing algorithms for dominating and independent set problems, colorings, and matchings. These graph theoretic problems are well studied in the context of self-stabilization and a large number of algorithms have been proposed for them.     

Grouping Byzantine Agreement

The reliability of the distributed system has always been an important topic of research. Byzantine Agreement (BA) protocol, which allows the fault-free processors to agree on a common value, is one of the most fundamental problems studied in a distributed system. In previous works, the problem was visited in a fully connected network or an unfully connected network with fallible processors. In this paper, the BA problem is reexamined in a group-oriented network, which has the feature of grouping, and the network topology does not have to be fully connected. We also enlarge the fault tolerant capability by allowing dormant faults and malicious faults (also called as the dual failure mode) to exist in a group-oriented network simultaneously. The proposed protocol is more efficient than the traditional BA protocols and can tolerate the maximum number of tolerable faulty processors.     

From immediate agreement to eventual agreement: early stopping agreement protocol for dynamic networks with malicious faulty processors

With the rapid advancement of wireless networking technology, networks have evolved from static to dynamic. Reliability of dynamic networks has virtually become an important issue. Fortunately, a solution to the above issue can be derived from solutions to the Byzantine Agreement (BA) problem. BA problem can be solved by protocols that make processors reach an agreement through message exchange. Protocols used to solve the problem can be divided into Immediate Byzantine Agreement (IBA) protocols and Eventual Byzantine Agreement (EBA) protocols. In IBA protocols, the number of rounds of message exchange is determined by the total number of processors in the network. Even if no faulty processor is present in the network, IBA protocols still require a fixed number of rounds of message exchange, causing a waste of time. In contrast, EBA protocols dynamically adjust the number of rounds of message exchange according to the interference of faulty processors. In terms of efficiency, EBA protocols certainly outperform IBA protocols. Due to the fact that the existing EBA protocols have been designed for static networks, they cannot work on dynamic networks. In this paper, we revisit the EBA problem in dynamic networks to increase the reliability of dynamic networks. Simulations will be conducted to validate that the proposed protocol requires the minimum rounds of message exchange and can tolerate the maximum number of malicious faulty processors compared to other existing protocols.