Improved Tradeoffs for Leader Election

DOI10.1145/3583668.3594576arXiv2301.08235OpenAlexW4380875831MaRDI QIDQ6202275FDOQ6202275

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)

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.

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)

Cites Work

• Title not available (Why is that?)
• A trade-off between information and communication in broadcast protocols
• Electing a leader in a synchronous ring
• Distributed Computing: A Locality-Sensitive Approach
• Leader election in complete networks
• Sublinear bounds for randomized leader election
• Computation in networks of passively mobile finite-state sensors
• Randomized leader election
• Time and Message Bounds for Election in Synchronous and Asynchronous Complete Networks
• Leader Election and Shape Formation with Self-organizing Programmable Matter
• Elections in anonymous networks
• On the Complexity of Universal Leader Election
• Construction and impromptu repair of an MST in a distributed network with \(o(m)\) communication

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)