How to Elect a Leader Faster than a Tournament
We give message-optimal randomized algorithms for two fundamental distributed assignment tasks, leader election and renaming. In leader election, all n participants compete for a single item, whereas in renaming the n participants each compete for one of n distinct items, or names. The setting is the classic asynchronous message-passing model, where the n processors communicate over unreliable channels, while timing and t < n / 2 processor crashes are controlled by a strong adaptive adversary.
We prove that both tasks can be solved using expected O( n^2 ) messages—asymptotically the same as a single all-to-all broadcast—and that this is in fact optimal. Our protocols are also time-efficient: the election algorithm terminates in expected O( \log* n ) communication rounds, whereas the renaming protocol terminates in expected O( \log^2 n ) rounds.