Deterministic leader election takes \(\Theta (D + \log n)\) bit rounds (Q1741851)

The paper presents a novel distributed algorithm for electing a leader in an arbitrary network in which the electors have unique identifiers. The algorithm complexity is properly discussed in terms of time, message and rounds. In particular, for the round complexity it is shown that the proposed algorithm has \(O(D+ \log n)\) where \(D\) is the diameter of the network and \(n\) is the number of electors; this complexity value is proved to be optimal and, furthermore, it is an improvement of the state of the art by lowering the previously known value of \(O(D\log n)\).