The Message Complexity of Asynchronous Assignment

Dan Alistarh, Rati Gelashvili, and Adrian Vladu


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 \log n ) communication rounds,
whereas the renaming protocol terminates in expected O( \log^2 n ) rounds.


Publication typeTechReport
> Publications > The Message Complexity of Asynchronous Assignment