Sublinear bounds for randomized leader election

Shay Kutten, Gopal Pandurangan, David Peleg, Peter Robinson*, Amitabh Trehan

*Corresponding author for this work

Research output: Contribution to journalArticle

13 Citations (Scopus)

Abstract

This paper concerns randomized leader election in synchronous distributed networks. A distributed leader election algorithm is presented for complete n-node networks that runs in O(1) rounds and (with high probability) uses only O(√ √nlog<sup>3/2</sup>n) messages to elect a unique leader (with high probability). When considering the "explicit" variant of leader election where eventually every node knows the identity of the leader, our algorithm yields the asymptotically optimal bounds of O(1) rounds and O(. n) messages. This algorithm is then extended to one solving leader election on any connected non-bipartite n-node graph G in O(τ(. G)) time and O(τ(G)n√log<sup>3/2</sup>n) messages, where τ(. G) is the mixing time of a random walk on G. The above result implies highly efficient (sublinear running time and messages) leader election algorithms for networks with small mixing times, such as expanders and hypercubes. In contrast, previous leader election algorithms had at least linear message complexity even in complete graphs. Moreover, super-linear message lower bounds are known for time-efficient deterministic leader election algorithms. Finally, we present an almost matching lower bound for randomized leader election, showing that Ω(n) messages are needed for any leader election algorithm that succeeds with probability at least 1/. e+. ε, for any small constant ε. >. 0. We view our results as a step towards understanding the randomized complexity of leader election in distributed networks.

Original languageEnglish
Pages (from-to)134-143
Number of pages10
JournalTheoretical Computer Science
Volume561
Issue numberPart B
Early online date22 Feb 2014
DOIs
Publication statusPublished - 04 Jan 2015

Fingerprint

Leader Election
Mixing Time
Distributed Networks
Vertex of a graph
Lower bound
Message Complexity
Expander
Optimal Bound
Linear Complexity
Asymptotically Optimal
Hypercube
Complete Graph
Random walk

Bibliographical note

Special Issue on Distributed Computing and Networking

Keywords

  • Distributed algorithm
  • Leader election
  • Lower bound
  • Randomization

Cite this

Kutten, S., Pandurangan, G., Peleg, D., Robinson, P., & Trehan, A. (2015). Sublinear bounds for randomized leader election. Theoretical Computer Science, 561(Part B), 134-143. https://doi.org/10.1016/j.tcs.2014.02.009
Kutten, Shay ; Pandurangan, Gopal ; Peleg, David ; Robinson, Peter ; Trehan, Amitabh. / Sublinear bounds for randomized leader election. In: Theoretical Computer Science. 2015 ; Vol. 561, No. Part B. pp. 134-143.
@article{ff6de80770f146c78e340106666c57a8,
title = "Sublinear bounds for randomized leader election",
abstract = "This paper concerns randomized leader election in synchronous distributed networks. A distributed leader election algorithm is presented for complete n-node networks that runs in O(1) rounds and (with high probability) uses only O(√ √nlog3/2n) messages to elect a unique leader (with high probability). When considering the {"}explicit{"} variant of leader election where eventually every node knows the identity of the leader, our algorithm yields the asymptotically optimal bounds of O(1) rounds and O(. n) messages. This algorithm is then extended to one solving leader election on any connected non-bipartite n-node graph G in O(τ(. G)) time and O(τ(G)n√log3/2n) messages, where τ(. G) is the mixing time of a random walk on G. The above result implies highly efficient (sublinear running time and messages) leader election algorithms for networks with small mixing times, such as expanders and hypercubes. In contrast, previous leader election algorithms had at least linear message complexity even in complete graphs. Moreover, super-linear message lower bounds are known for time-efficient deterministic leader election algorithms. Finally, we present an almost matching lower bound for randomized leader election, showing that Ω(n) messages are needed for any leader election algorithm that succeeds with probability at least 1/. e+. ε, for any small constant ε. >. 0. We view our results as a step towards understanding the randomized complexity of leader election in distributed networks.",
keywords = "Distributed algorithm, Leader election, Lower bound, Randomization",
author = "Shay Kutten and Gopal Pandurangan and David Peleg and Peter Robinson and Amitabh Trehan",
note = "Special Issue on Distributed Computing and Networking",
year = "2015",
month = "1",
day = "4",
doi = "10.1016/j.tcs.2014.02.009",
language = "English",
volume = "561",
pages = "134--143",
journal = "Theoretical Computer Science",
issn = "0304-3975",
publisher = "Elsevier",
number = "Part B",

}

Kutten, S, Pandurangan, G, Peleg, D, Robinson, P & Trehan, A 2015, 'Sublinear bounds for randomized leader election', Theoretical Computer Science, vol. 561, no. Part B, pp. 134-143. https://doi.org/10.1016/j.tcs.2014.02.009

Sublinear bounds for randomized leader election. / Kutten, Shay; Pandurangan, Gopal; Peleg, David; Robinson, Peter; Trehan, Amitabh.

In: Theoretical Computer Science, Vol. 561, No. Part B, 04.01.2015, p. 134-143.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Sublinear bounds for randomized leader election

AU - Kutten, Shay

AU - Pandurangan, Gopal

AU - Peleg, David

AU - Robinson, Peter

AU - Trehan, Amitabh

N1 - Special Issue on Distributed Computing and Networking

PY - 2015/1/4

Y1 - 2015/1/4

N2 - This paper concerns randomized leader election in synchronous distributed networks. A distributed leader election algorithm is presented for complete n-node networks that runs in O(1) rounds and (with high probability) uses only O(√ √nlog3/2n) messages to elect a unique leader (with high probability). When considering the "explicit" variant of leader election where eventually every node knows the identity of the leader, our algorithm yields the asymptotically optimal bounds of O(1) rounds and O(. n) messages. This algorithm is then extended to one solving leader election on any connected non-bipartite n-node graph G in O(τ(. G)) time and O(τ(G)n√log3/2n) messages, where τ(. G) is the mixing time of a random walk on G. The above result implies highly efficient (sublinear running time and messages) leader election algorithms for networks with small mixing times, such as expanders and hypercubes. In contrast, previous leader election algorithms had at least linear message complexity even in complete graphs. Moreover, super-linear message lower bounds are known for time-efficient deterministic leader election algorithms. Finally, we present an almost matching lower bound for randomized leader election, showing that Ω(n) messages are needed for any leader election algorithm that succeeds with probability at least 1/. e+. ε, for any small constant ε. >. 0. We view our results as a step towards understanding the randomized complexity of leader election in distributed networks.

AB - This paper concerns randomized leader election in synchronous distributed networks. A distributed leader election algorithm is presented for complete n-node networks that runs in O(1) rounds and (with high probability) uses only O(√ √nlog3/2n) messages to elect a unique leader (with high probability). When considering the "explicit" variant of leader election where eventually every node knows the identity of the leader, our algorithm yields the asymptotically optimal bounds of O(1) rounds and O(. n) messages. This algorithm is then extended to one solving leader election on any connected non-bipartite n-node graph G in O(τ(. G)) time and O(τ(G)n√log3/2n) messages, where τ(. G) is the mixing time of a random walk on G. The above result implies highly efficient (sublinear running time and messages) leader election algorithms for networks with small mixing times, such as expanders and hypercubes. In contrast, previous leader election algorithms had at least linear message complexity even in complete graphs. Moreover, super-linear message lower bounds are known for time-efficient deterministic leader election algorithms. Finally, we present an almost matching lower bound for randomized leader election, showing that Ω(n) messages are needed for any leader election algorithm that succeeds with probability at least 1/. e+. ε, for any small constant ε. >. 0. We view our results as a step towards understanding the randomized complexity of leader election in distributed networks.

KW - Distributed algorithm

KW - Leader election

KW - Lower bound

KW - Randomization

U2 - 10.1016/j.tcs.2014.02.009

DO - 10.1016/j.tcs.2014.02.009

M3 - Article

AN - SCOPUS:84927964405

VL - 561

SP - 134

EP - 143

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

IS - Part B

ER -

Kutten S, Pandurangan G, Peleg D, Robinson P, Trehan A. Sublinear bounds for randomized leader election. Theoretical Computer Science. 2015 Jan 4;561(Part B):134-143. https://doi.org/10.1016/j.tcs.2014.02.009