The problem of electing a leader in a synchronous ring of n processors is considered.
Both positive and negative results are obtained. On the one hand, if processor IDs are
chosen from some countable set, then there is an algorithm that uses only O(n) messages
in the worst case. On the other hand, any algorithm that is restricted to use only
comparisons of IDs requires (n log n) messages in
the worst case. Alternatively, if the number of rounds is required to be bounded by some
t in the worst case, and IDs are chosen from any set having f(n,t) elements, for a
certain very fast-growing function f, then any algorithm requires
(n log n) messages in the worst case.