Deterministic Leader Election Takes $\Theta (D+\log n)$ Bit Rounds

Abstract

Leader election is, together with consensus, one of the most central problems in distributed computing. This paper presents a distributed algorithm, called \STT, for electing deterministically a leader in an arbitrary network, assuming processors have unique identifiers of size $O(\log n)$, where $n$ is the number of processors. It elects a leader in $O(D+\log n)$ rounds, where $D$ is the diameter of the network, with messages of size $O(1)$. Thus it has a bit round complexity of $O(D+\log n)$. This substantially improves upon the best known algorithm whose bit round complexity is $O(D\log n)$. In fact, using the lower bound by Kutten et al. (2015) and a result of Dinitz and Solomon (2007), we show that the bit round complexity of \STT is optimal (up to a constant factor), which is a significant step forward in understanding the interplay between time and message optimality for the election problem. Our algorithm requires no knowledge on the graph such as $n$ or $D$, and the pipelining technique we introduce to break the $O(D\log n)$ barrier is general.

Accepted for publication in Algorithmica