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

Leader election is, together with consensus, one of the most central problems in distributed computing. This paper presents a distributed algorithm, called $$\mathcal{STT}$$STT , for electing deterministically a leader in an arbitrary network, assuming processors have unique identifiers of size $$O(\log n)$$O(logn), where n is the number of processors. It elects a leader in $$O(D +\log n)$$O(D+logn) 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)$$O(D+logn). This substantially improves upon the best known algorithm whose bit round complexity is $$O(D\log n)$$O(Dlogn). In fact, using the lower bound by Kutten et al. (J ACM 62(1):7:1–7:27, 2015) and Kutten et al. (Theor Comput Sci 561:134–143, 2015) and a result of Dinitz and Solomon (Theor Comput Sci 384(2–3):168–183, 2007), we show that the bit round complexity of $$\mathcal{STT}$$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)$$O(Dlogn) barrier is general.