Sublinear bounds for randomized leader election

DOI10.1007/978-3-642-35668-1_24zbMATH Open1303.68034arXiv1210.4822OpenAlexW2069689700MaRDI QIDQ477103FDOQ477103

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

Publication date: 2 December 2014

Published in: Theoretical Computer Science, Distributed Computing and Networking (Search for Journal in Brave)

Abstract: This paper concerns {em 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(sqrtnlo{g}^{3/2}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(au(G))$ time and $O(au(G)sqrtnlo{g}^{3/2}n)$ messages, where $au(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 {em deterministic} leader election algorithms. Finally, we present an almost matching lower bound for randomized leader election, showing that $Omega(sqrtn)$ messages are needed for any leader election algorithm that succeeds with probability at least $1/e+eps$, for any small constant $eps>0$. We view our results as a step towards understanding the randomized complexity ofleader election in distributed networks.

Full work available at URL: https://arxiv.org/abs/1210.4822

Recommendations

• Sublinear bounds for randomized leader election
• On the Complexity of Universal Leader Election
• On the complexity of universal leader election
• Leader election in well-connected graphs
• Randomized leader election

zbMATH Keywords

randomizationlower bounddistributed algorithmleader election

Mathematics Subject Classification ID

Randomized algorithms (68W20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distributed algorithms (68W15) Distributed systems (68M14)

Cites Work

• Title not available (Why is that?)
• Design and Analysis of Distributed Algorithms
• Distributed Computing: A Locality-Sensitive Approach
• A Distributed Algorithm for Minimum-Weight Spanning Trees
• Time, clocks, and the ordering of events in a distributed system
• Title not available (Why is that?)
• Title not available (Why is that?)
• Optimal lower bounds for some distributed algorithms for a complete network of processors
• Randomized leader election
• Distributed agreement in dynamic peer-to-peer networks
• Title not available (Why is that?)
• Time and Message Bounds for Election in Synchronous and Asynchronous Complete Networks
• Low Communication Self-stabilization through Randomization
• The Optimality of Distributive Constructions of Minimum Weight and Degree Restricted Spanning Trees in a Complete Network of Processors
• Efficient leader election using sense of direction
• Probabilistic quorum systems
• Efficient distributed approximation algorithms via probabilistic tree embeddings

Cited In (18)

• Leader election in well-connected graphs
• Deterministic leader election takes \(\Theta (D + \log n)\) bit rounds
• Title not available (Why is that?)
• Message lower bounds via efficient network synchronization
• Cost distribution of the Chang-Roberts leader election algorithm and related problems
• Message Lower Bounds via Efficient Network Synchronization
• Improved deterministic leader election in diameter-two networks
• Exponential Separations in the Energy Complexity of Leader Election
• Improved Tradeoffs for Leader Election
• Performance and robustness of discrete and finite time average consensus algorithms
• The Bit Complexity of Randomized Leader Election on a Ring
• Smoothed Analysis of Leader Election in Distributed Networks
• Sublinear message bounds of authenticated implicit Byzantine agreement
• Singularly optimal randomized leader election
• Termination of amnesiac flooding
• Tight bounds for distributed minimum-weight spanning tree verification
• The complexity of leader election in diameter-two networks
• On the Complexity of Universal Leader Election

Uses Software

• Pastry

This page was built for publication: Sublinear bounds for randomized leader election

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q477103)