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