# The ICICS/CS Reading Room

## UBC CS TR-86-03 Summary

- No on-line copy of this technical report is available.

- The Bit Complexity of Randomized Leader Election on a Ring, February 1986 Karl Abrahamson, Andrew Adler, Rachel Gelbart, Lisa Higham and David G. Kirkpatrick
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.

If you have any questions or comments regarding this page please send mail to
help@cs.ubc.ca.