This paper concerns designing distributed algorithms that are singularly optimal, i.e., algorithms that are simultaneously time and message optimal, for the fundamental leader election problem in networks. Our main result is a randomized distributed leader election algorithm for asynchronous complete networks that is essentially (up to a polylogarithmic factor) singularly optimal. Our algorithm uses O(n) messages with high probability and runs in O(\log^2 n) time (with high probability) to elect a unique leader. The O(n) message complexity should be contrasted with the \Omega(n \log n) lower bounds for the deterministic message complexity of leader election algorithms (regardless of time), proven by Korach, Moran, and Zaks (TCS, 1989) for asynchronous algorithms and by Afek and Gafni (SIAM J. Comput., 1991) for synchronous networks. Hence, our result also separates the message complexities of randomized and deterministic leader election. More importantly, our (randomized) time complexity of O(\log^2 n) for obtaining the optimal O(n) message complexity is significantly smaller than the long-standing \tilde{\Theta}(n) time complexity obtained by Afek and Gafni and by Singh (SIAM J. Comput., 1997) for message optimal (deterministic) election in asynchronous networks. Afek and Gafni also conjectured that \tilde{\Theta}(n) time would be optimal for message-optimal asynchronous algorithms. Our result shows that randomized algorithms are significantly faster.
Turning to synchronous complete networks, Afek and Gafni showed an essentially singularly optimal deterministic algorithm with O(\log n) time and O(n \log n) messages. Ramanathan et al. (Distrib. Comput. 2007) used randomization to improve the message complexity, and showed a randomized algorithm with O(n) messages but still with O(\log n) time (with failure probability O(1 / \log^{\Omega(1)}n)). Our second result shows that synchronous complete networks admit a tightly singularly optimal randomized algorithm, with O(1) time and O(n) messages (both bounds are optimal). Moreover, our algorithm's time bound holds with certainty, and its message bound holds with high probability, i.e., 1-1/n^c for constant c.
Our results demonstrate that leader election can be solved in a simultaneously message and time-efficient manner in asynchronous complete networks using randomization. It is open whether this is possible in asynchronous general networks.
This talk is based on joint work with Shay Kutten, Gopal Pandurangan, and David Peleg which was published at DISC 2020.
Bio: William K. Moses Jr. is currently a postdoc at the University of Houston in Houston, USA, where he is hosted by Gopal Pandurangan. Prior to that, he was a postdoc at the Technion and received his PhD from IIT Madras in 2018. He is interested in the theory of distributed computing with a focus on distributed algorithms. His three current areas of focus are problems in general graphs, programmable matter, and mobile robots. He has in the past worked on problems related to SINR networks and load balancing. His profile can be accessed here: https://sites.google.com/view/wkmjr/home
Zoom link:
https://zoom.us/j/98132227553?pwd=K2cyQllKVjExdUhlRm0vc0ZHcEt0Zz09
