Abstract

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.