共查询到20条相似文献,搜索用时 15 毫秒
1.
Murali Krishna Ramanathan Ronaldo A. Ferreira Suresh Jagannathan Ananth Grama Wojciech Szpankowski 《Distributed Computing》2007,19(5-6):403-418
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. 相似文献
2.
Maor Ganz 《Quantum Information Processing》2017,16(3):73
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. 相似文献
3.
Dolev S. Israeli A. Moran S. 《Parallel and Distributed Systems, IEEE Transactions on》1997,8(4):424-440
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 相似文献
4.
5.
Gurdip Singh 《Distributed Computing》1997,10(3):159-165
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 相似文献
6.
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∈eO(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 相似文献
7.
Fetzer C. Cristian F. 《IEEE transactions on pattern analysis and machine intelligence》1999,25(5):603-618
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 相似文献
8.
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. 相似文献
9.
10.
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 相似文献
11.
Jacob Brunekreef Joost-Pieter Katoen Ron Koymans Sjouke Mauw 《Distributed Computing》1996,9(4):157-171
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 相似文献
12.
Yu ZHOU Nvqi ZHOU Tingting HAN Jiayi GU Weigang WU 《Frontiers of Computer Science》2018,12(4):763-776
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. 相似文献
13.
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). 相似文献
14.
Rebecca Ingram Tsvetomira Radeva Patrick Shields Saira Viqar Jennifer E. Walter Jennifer L. Welch 《Distributed Computing》2013,26(2):75-97
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. 相似文献
15.
Ajoy K. Datta Lawrence L. LarmorePriyanka Vemula 《Theoretical computer science》2011,412(40):5541-5561
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. 相似文献
16.
《Theoretical computer science》1987,54(1):53-64
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. 相似文献
17.
Ryu Mizoguchi Hirotaka Ono Shuji Kijima Masafumi Yamashita 《Distributed Computing》2012,25(6):451-460
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. 相似文献
18.
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. 相似文献
19.
《国际计算机数学杂志》2012,89(11):2450-2457
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. 相似文献
20.
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. 相似文献