Rati Gelashvili: Leader Election and Renaming with Optimal Message Complexity

Abstract:  Asynchronous message-passing system is a standard distributed model, where $n$ processors communicate over unreliable channels, controlled by a strong adaptive adversary. The asynchronous nature of the system and the fact that $t < n / 2$ processes may fail by crashing are the great obstacles for designing efficient algorithms.

\emph{Leader election (test-and-set)} and \emph{renaming} are two fundamental distributed tasks. We prove that both tasks can be solved using expected $O( n^2 )$ messages---the same asymptotic complexity as a single all-to-all broadcast---and that this message complexity is in fact optimal.