The Bit Complexity of Randomized Leader Election on a Ring

The inherent bit complexity of leader election on asynchronous unidirectional rings of processors is examined under various assumptions about global knowledge of the ring. If processors have unique identities with a maximum of $m$ bits, then the expected number of communication bits sufficient to elect a leader with probability 1, on a ring of (unknown) size $n$ is $O(nm)$. If the ring size is known to within a multiple of 2, then the expected number of communication bits sufficient to elect a leader with probability 1 is $O(n \log n)$.

These upper bounds are complemented by lower bounds on the communication complexity of a related problem called solitude verification that reduces to leader election in $O(n)$ bits. If processors have unique identities chosen from a sufficiently large universe of size $s$, then the average, over all choices of identities, of the communication complexity of verifying solitude is $\Omega (n \log s)$ bits. When the ring size is known only approximately, then $\Omega (n \log n)$ bits are required for solitude verification. The lower bounds address the complexity of certifying solitude. This is modelled by tbe best case behaviour of non-deterministic solitude verification algorithms.