TY - GEN
T1 - Improved Tradeoffs for Leader Election
AU - Kutten, Shay
AU - Robinson, Peter
AU - Tan, Ming Ming
AU - Zhu, Xianbin
N1 - Publisher Copyright:
© 2023 ACM.
PY - 2023/6/19
Y1 - 2023/6/19
N2 - 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. The previous lower bound side of such a tradeoff, in the seminal paper of Afek and Gafni (1991), was shown only assuming adversarial wake-up. Interestingly, our new tradeoff also improves the previous lower bounds for a large part of the spectrum, even under simultaneous wake-up. More specifically, we show that any deterministic algorithm with a message complexity of n f(n) requires ω((log n) / (log f(n)+1)) rounds, for f(n) > 1. Our result holds even if the node IDs are chosen from a relatively small set of size ω(n log n), as we are able to avoid using Ramsey's theorem, in contrast to many existing lower bounds for deterministic algorithms. We also give an upper bound that improves over the previously-best tradeoff achieved by the algorithm of Afek and Gafni. Our second contribution for the synchronous clique under simultaneous wake-up is to show that ω (n log n) is in fact a lower bound on the message complexity that holds for any deterministic algorithm with a termination time T(n) (i.e., any function of n), for a sufficiently large ID space. We complement this result by giving a simple deterministic algorithm that achieves leader election in sublinear time while sending only o(n log n) messages, if the ID space is of at most linear size. We also show that Las Vegas algorithms (that never fail) require ω(n) messages. This exhibits a gap between Las Vegas and Monte Carlo algorithms.For the synchronous clique under adversarial wake-up, we show that ω(n3/2) is a lower bound for 2-round algorithms. Our result is the first superlinear lower bound for randomized leader election algorithms in the clique. We also give a simple algorithm that matches this bound.Finally, we turn our attention to the asynchronous clique: Assuming adversarial wake-up, we give a randomized algorithm that, for any k ĝ [2, O(log n/log log n)], achieves a message complexity of O(n1+1/k) and an asynchronous time complexity of k + 8. Our algorithm achieves the first tradeoff between messages and time in the asynchronous model. 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.
AB - 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. The previous lower bound side of such a tradeoff, in the seminal paper of Afek and Gafni (1991), was shown only assuming adversarial wake-up. Interestingly, our new tradeoff also improves the previous lower bounds for a large part of the spectrum, even under simultaneous wake-up. More specifically, we show that any deterministic algorithm with a message complexity of n f(n) requires ω((log n) / (log f(n)+1)) rounds, for f(n) > 1. Our result holds even if the node IDs are chosen from a relatively small set of size ω(n log n), as we are able to avoid using Ramsey's theorem, in contrast to many existing lower bounds for deterministic algorithms. We also give an upper bound that improves over the previously-best tradeoff achieved by the algorithm of Afek and Gafni. Our second contribution for the synchronous clique under simultaneous wake-up is to show that ω (n log n) is in fact a lower bound on the message complexity that holds for any deterministic algorithm with a termination time T(n) (i.e., any function of n), for a sufficiently large ID space. We complement this result by giving a simple deterministic algorithm that achieves leader election in sublinear time while sending only o(n log n) messages, if the ID space is of at most linear size. We also show that Las Vegas algorithms (that never fail) require ω(n) messages. This exhibits a gap between Las Vegas and Monte Carlo algorithms.For the synchronous clique under adversarial wake-up, we show that ω(n3/2) is a lower bound for 2-round algorithms. Our result is the first superlinear lower bound for randomized leader election algorithms in the clique. We also give a simple algorithm that matches this bound.Finally, we turn our attention to the asynchronous clique: Assuming adversarial wake-up, we give a randomized algorithm that, for any k ĝ [2, O(log n/log log n)], achieves a message complexity of O(n1+1/k) and an asynchronous time complexity of k + 8. Our algorithm achieves the first tradeoff between messages and time in the asynchronous model. 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.
KW - distributed algorithm
KW - leader election
KW - lower bound
UR - http://www.scopus.com/inward/record.url?scp=85164032844&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85164032844&partnerID=8YFLogxK
U2 - 10.1145/3583668.3594576
DO - 10.1145/3583668.3594576
M3 - Conference contribution
AN - SCOPUS:85164032844
T3 - Proceedings of the Annual ACM Symposium on Principles of Distributed Computing
SP - 355
EP - 365
BT - PODC 2023 - Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing
PB - Association for Computing Machinery
T2 - 42nd ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC 2023
Y2 - 19 June 2023 through 23 June 2023
ER -