Improved Tradeoffs for Leader Election

DOI10.1145/3583668.3594576MaRDI QIDQ6202275zbMATH OpenOpenAlexFDO

Authors Shay Kutten, Peter Robinson, Ming Ming Tan

Publication date 26 March 2024

Published in Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

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

zbMATH Keywords

lower bounddistributed algorithmleader election

Mathematics Subject Classification ID

Distributed algorithms (68W15) Distributed systems (68M14)

Abstract: We consider leader election in clique networks, where $n$ nodes are connected by point-to-point communication links. For the synchronous clique under simultaneous wake-up, i.e., where all nodes start executing the algorithm in round $1$, we show a tradeoff between the number of messages and the amount of time. More specifically, we show that any deterministic algorithm with a message complexity of $nf(n)$ requires $Omegaleft(fraclognlogf(n)+1ight)$ rounds, for $f(n)=Omega(logn)$. Our result holds even if the node IDs are chosen from a relatively small set of size $Theta(nlogn)$, as we are able to avoid using Ramsey's theorem. We also give an upper bound that improves over the previously-best tradeoff. Our second contribution for the synchronous clique under simultaneous wake-up is to show that $Omega(nlogn)$ is in fact a lower bound on the message complexity that holds for any deterministic algorithm with a termination time $T(n)$. We complement this result by giving a simple deterministic algorithm that achieves leader election in sublinear time while sending only $o(nlogn)$ messages, if the ID space is of at most linear size. We also show that Las Vegas algorithms (that never fail) require $Theta(n)$ messages. For the synchronous clique under adversarial wake-up, we show that $Omega(n^{3/2})$ is a tight lower bound for randomized $2$-round algorithms. Finally, we turn our attention to the asynchronous clique: Assuming adversarial wake-up, we give a randomized algorithm that achieves a message complexity of $O(n^{1+1/k})$ and an asynchronous time complexity of $k+8$. For simultaneous wake-up, we translate the deterministic tradeoff algorithm of Afek and Gafni to the asynchronous model, thus partially answering an open problem they pose.

Cites work

• scientific article; zbMATH DE number 996442 (Why is no real title available?)
• A trade-off between information and communication in broadcast protocols
• Computation in networks of passively mobile finite-state sensors
• Construction and impromptu repair of an MST in a distributed network with \(o(m)\) communication
• Distributed Computing: A Locality-Sensitive Approach
• Electing a leader in a synchronous ring
• Elections in anonymous networks
• Leader election and shape formation with self-organizing programmable matter
• Leader election in complete networks
• On the Complexity of Universal Leader Election
• Randomized leader election
• Time and Message Bounds for Election in Synchronous and Asynchronous Complete Networks

This page was built for publication: Improved Tradeoffs for Leader Election

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