TY - GEN

T1 - Leader election in well-connected graphs

AU - Gilbert, Seth

AU - Robinson, Peter

AU - Sourav, Suman

N1 - Funding Information:
†Peter Robinson acknowledges the support of the Natural Sciences and Engineering Research Council of Canada (NSERC). This research was supported by AcRF Tier 1 grant T1 251RES1719 (Adaptive Data Structures: Concurrent, Cache-Efficient, Distributed).
Publisher Copyright:
© 2018 Copyright held by the owner/author(s). Publication rights licensed to ACM.

PY - 2018/7/23

Y1 - 2018/7/23

N2 - In this paper, we look at the problem of randomized leader election in synchronous distributed networks with a special focus on the message complexity. We provide an algorithm that solves the implicit version of leader election (where non-leader nodes need not be aware of the identity of the leader) in any general network with O(n log7/2 n · tmix ) messages and in O(tmix log2 n) time, where n is the number of nodes and tmix refers to the mixing time of a random walk in the network graph G. For several classes of well-connected networks (that have a large conductance or alternatively small mixing times e.g. expanders, hypercubes, etc), the above result implies extremely efficient (sublinear running time and messages) leader election algorithms. Correspondingly, we show that any substantial improvement is not possible over our algorithm, by presenting an almost matching lower bound for randomized leader election. We show that Ω(n/3/4) messages are needed for any leader election algorithm that succeeds with probability at least 1 − o(1), where refers to the conductance of a graph. To the best of our knowledge, this is the first work that shows a dependence between the time and message complexity to solve leader election and the connectivity of the graph G, which is often characterized by the graph's conductance . Apart from the Ω(m) bound in [23] (where m denotes the number of edges of the graph), this work also provides one of the first non-trivial lower bounds for leader election in general networks.

AB - In this paper, we look at the problem of randomized leader election in synchronous distributed networks with a special focus on the message complexity. We provide an algorithm that solves the implicit version of leader election (where non-leader nodes need not be aware of the identity of the leader) in any general network with O(n log7/2 n · tmix ) messages and in O(tmix log2 n) time, where n is the number of nodes and tmix refers to the mixing time of a random walk in the network graph G. For several classes of well-connected networks (that have a large conductance or alternatively small mixing times e.g. expanders, hypercubes, etc), the above result implies extremely efficient (sublinear running time and messages) leader election algorithms. Correspondingly, we show that any substantial improvement is not possible over our algorithm, by presenting an almost matching lower bound for randomized leader election. We show that Ω(n/3/4) messages are needed for any leader election algorithm that succeeds with probability at least 1 − o(1), where refers to the conductance of a graph. To the best of our knowledge, this is the first work that shows a dependence between the time and message complexity to solve leader election and the connectivity of the graph G, which is often characterized by the graph's conductance . Apart from the Ω(m) bound in [23] (where m denotes the number of edges of the graph), this work also provides one of the first non-trivial lower bounds for leader election in general networks.

KW - Conductance

KW - Leader election

KW - Mixing time

KW - Random walks

UR - http://www.scopus.com/inward/record.url?scp=85052442156&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85052442156&partnerID=8YFLogxK

U2 - 10.1145/3212734.3212754

DO - 10.1145/3212734.3212754

M3 - Conference contribution

AN - SCOPUS:85052442156

SN - 9781450357951

T3 - Proceedings of the Annual ACM Symposium on Principles of Distributed Computing

SP - 227

EP - 236

BT - PODC 2018 - Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing

PB - Association for Computing Machinery

T2 - 37th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC 2018

Y2 - 23 July 2018 through 27 July 2018

ER -