Randomized leader election

We present an efficient randomized algorithm for leader election in large-scale distributed systems. The proposed algorithm is optimal in message complexity (O(n) for a set of n total processes), has round complexity logarithmic in the number of processes in the system, and provides high probabilistic guarantees on the election of a unique leader. The algorithm relies on a balls and bins abstraction and works in two phases. The main novelty of the work is in the first phase where the number of contending processes is reduced in a controlled manner. Probabilistic quorums are used to determine a winner in the second phase. We discuss, in detail, the synchronous version of the algorithm, provide extensions to an asynchronous version and examine the impact of failures.     

Quantum leader election

A group of n individuals \(A_{1},\ldots A_{n}\) who do not trust each other and are located far away from each other, want to select a leader. This is the leader election problem, a natural extension of the coin flipping problem to n players. We want a protocol which will guarantee that an honest player will have at least \(\frac{1}{n}-\epsilon \) chance of winning (\(\forall \epsilon >0\)), regardless of what the other players do (whether they are honest, cheating alone or in groups). It is known to be impossible classically. This work gives a simple algorithm that does it, based on the weak coin flipping protocol with arbitrarily small bias derived by Mochon (Quantum weak coin flipping with arbitrarily small bias, arXiv:0711.4114, 2000) in 2007, and recently published and simplified in Aharonov et al. (SIAM J Comput, 2016). A protocol with linear number of coin flipping rounds is quite simple to achieve; we further provide an improvement to logarithmic number of coin flipping rounds. This is a much improved journal version of a preprint posted in 2009; the first protocol with linear number of rounds was achieved independently also by Aharon and Silman (New J Phys 12:033027, 2010) around the same time.     

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     

Efficient leader election using sense of direction

Summary.  This paper presents a protocol for leader election in complete networks with a sense of direction. Sense of direction provides nodes the capability of distinguishing between their incident links according to a global scheme. We propose a protocol for leader election which requires O(N) messages and O(log N) time. The protocol is message optimal and the time complexity is a significant improvement over currently known protocols for this problem. Received August 1995 / Accepted December 1996     

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     

A highly available local leader election service

We define the highly available local leader election problem (G. LeLann, 1977), a generalization of the leader election problem for partitionable systems. We propose a protocol that solves the problem efficiently and give some performance measurements of our implementation. The local leader election service has been proven useful in the design and implementation of several fail-aware services for partitionable systems     

How much memory is needed for leader election

We study the minimum memory size with which nodes of a network have to be equipped, in order to solve deterministically the leader election problem. Nodes are unlabeled, but ports at each node have arbitrary fixed labelings which, together with the topology of the network, can create asymmetries to be exploited in leader election. We consider two versions of the leader election problem: strong LE in which exactly one leader has to be elected, if this is possible, while all nodes must terminate in a state “infeasible” when the election of a unique leader fails, and weak LE, which differs from strong LE in that no requirement on the behavior of nodes is imposed, if leader election is impossible. Nodes are modeled as identical automata and we ask what is the minimum amount of memory of such an automaton to enable leader election. We show that logarithmic memory is optimal for both strong and weak leader election in the class of arbitrary connected graphs. By contrast we show that strong LE can be accomplished in the class of trees of maximum degree Δ using only O(log log Δ) bits of memory, thus proving an exponential gap in memory requirements for leader election between the class of trees and the class of arbitrary graphs.     

New model and algorithms for leader election in synchronousfiber-optic networks

We improve on I. Cidon, I. Gopal and S. Kutten's leader election algorithm (Proc. 7th ACM Symp. Principles Distrib. Computing, Toronto, Ont., Canada. Aug. 1988) by presenting an algorithm that uses only O(√n log D + f) time units to run on synchronous networks of degree f and diameter D, where f⩾3. When f is 2, the algorithm uses only O(log D) time units     

Design and analysis of dynamic leader election protocols in broadcast networks

Summary.  The well-known problem of leader election in distributed systems is considered in a dynamic context where processes may participate and crash spontaneously. Processes communicate by means of buffered broadcasting as opposed to usual point-to-point communication. In this paper we design a leader election protocol in such a dynamic context. As the problem at hand is considerably complex we develop the protocol in three steps. In the initial design processes are considered to be perfect and a leader is assumed to be present initially. In the second protocol, the assumption of an initial leader is dropped. This leads to a symmetric protocol which uses an (abstract) timeout mechanism to detect the absence of a leader. Finally, in the last step of the design processes may crash without giving any notification of other processes. The worst case message complexity of all protocols is addressed. A formal approach to the specification and verification of the leader election protocols is adopted. The requirements are specified in a property-oriented way and the protocols are denoted by means of extended finite state machines. It is proven using linear-time temporal logic that the fault-tolerant protocol satisfies its requirements. Received: September 1993 / Revised: September 1995     

Probabilistic verification of hierarchical leader election protocol in dynamic systems

Leader election protocols are fundamental for coordination problems—such as consensus—in distributed computing. Recently, hierarchical leader election protocols have been proposed for dynamic systems where processes can dynamically join and leave, and no process has global information. However, quantitative analysis of such protocols is generally lacking. In this paper, we present a probabilistic model checking based approach to verify quantitative properties of these protocols. Particularly, we employ the compositional technique in the style of assume-guarantee reasoning such that the sub-protocols for each of the two layers are verified separately and the correctness of the whole protocol is guaranteed by the assume-guarantee rules. Moreover, within this framework we also augment the proposed model with additional features such as rewards. This allows the analysis of time or energy consumption of the protocol. Experiments have been conducted to demonstrate the effectiveness of our approach.     

Fast leader election in anonymous rings with bounded expected delay

We propose a probabilistic network model, called asynchronous bounded expected delay (ABE), which requires a known bound on the expected message delay. In ABE networks all asynchronous executions are possible, but executions with extremely long delays are less probable. Thus, the ABE model captures asynchrony that occurs in sensor networks and ad-hoc networks.At the example of an election algorithm, we show that the minimal assumptions of ABE networks are sufficient for the development of efficient algorithms. For anonymous, unidirectional ABE rings of known size n we devise a probabilistic election algorithm having average message and time complexity O(n).     

A leader election algorithm for dynamic networks with causal clocks

An algorithm for electing a leader in an asynchronous network with dynamically changing communication topology is presented. The algorithm ensures that, no matter what pattern of topology changes occurs, if topology changes cease, then eventually every connected component contains a unique leader. The algorithm combines ideas from the Temporally Ordered Routing Algorithm for mobile ad hoc networks (Park and Corson in Proceedings of the 16th IEEE Conference on Computer Communications (INFOCOM), pp. 1405–1413 (1997) with a wave algorithm (Tel in Introduction to distributed algorithms, 2nd edn. Cambridge University Press, Cambridge, MA, 2000), all within the framework of a height-based mechanism for reversing the logical direction of communication topology links (Gafni and Bertsekas in IEEE Trans Commun C–29(1), 11–18 1981). Moreover, a generic representation of time is used, which can be implemented using totally-ordered values that preserve the causality of events, such as logical clocks and perfect clocks. A correctness proof for the algorithm is provided, and it is ensured that in certain well-behaved situations, a new leader is not elected unnecessarily, that is, the algorithm satisfies a stability condition.     

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.     

New protocols for the election of a leader in a ring

In this paper we investigate the impact of time for the election of a leader in a distributed environment. We propose a new protocol schema that can be specialized to obtain several protocols with different communication-time characteristics when the network is ring-shaped and the communications between processors are synchronous.     

On space complexity of self-stabilizing leader election in mediated population protocol

Chatzigiannakis et al. (Lect Notes Comput Sci 5734:56–76, 2009) extended the Population Protocol (PP) of Angluin et al. (2004) and introduced the Mediated Population Protocol (MPP) by introducing an extra memory on every agent-to-agent communication link (i.e., edge), in order to model more powerful networks of mobile agents with limited resources. For a general distributed system of autonomous agents, Leader Election (LE) plays a key role in their efficient coordination. A Self-Stabilizing (SS) protocol has ideal properties required for distributed systems of huge numbers of not highly reliable agents typically modeled by PP or MPP; it does not require any initialization and tolerates a finite number of transient failures. Cai et al. (2009) showed that for a system of $n$ agents, any PP for SS-LE requires at least $n$ agent-states, and gave a PP with $n$ agent-states for SS-LE. In this paper, we show, for a system of $n$ agents, any MPP for SS-LE with 2 edge-states (i.e., 1 bit memory) on every edge requires at least $(1/2) \lg {n}$ agent-states, and give an MPP for SS-LE with $(2/3)n$ agent-states and 2 edge-states on every edge. Furthermore, we show that a constant number of edge-states on every edge do not help in designing an MPP for SS-LE with a constant number of agent-states, and that there is no MPP for SS-LE with 2 agent-states, regardless of the number of edge-states; the edge-state is not a complete alternative of the agent-state, although it can help in reducing the number of agent-states, when solving SS-LE.     

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.     

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.     

Fast protocols for leader election and spanning tree construction in a distributed network

We consider leader election and spanning tree construction problems in a synchronous network. Protocols are designed under the assumption that nodes in the network have identifiers but the size of an identifier is unlimited. We present fast protocols with runtime O(D log L+L), where L is the size of the minimal identifier and D is the network diameter.