# The ICICS/CS Reading Room

## UBC CS TR-88-15 Summary

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

- Probabilistic Evaluation of Common Functions On Rings of Known Size, June 1988 Karl Abrahamson, Andrew Adler, Lisa Higham and David G. Kirkpatrick
In [5]. Duris and Galil prove an $ \Omega (n \log n)$ lower bound for the average number
of messages required by any deterministic algorithm which elects a leader on an
asynchronous ring with distinct identifiers where ring size $n$ is known and is a
power of 2. Their results imply the same lower bound for the expected complexity
of any randomized leader election algorithm for an anonymous ring of known size
2^{k}$. If their new techniques are used to achieve the randomized result directly,
the resulting proof is significantly simpler than the original deterministic one.
This simplicity facilitates extension of the result in two directions; namely, for
arbitrary known ring size, and for algorithms that permit error with probability
at most $\epsilon $. Specifically, we prove that the expected message complexity of any
probabilistic algorithm that selects a leader with probability at least $1 - \epsilon $ on an
anonymous ring of known size $n$, is $\Omega (n \min(\log n, \log \log(l / \epsilon ))) $. A number of
common function evaluation problems (including AND, OR, PARITY, and SUM)
on rings of known size, are shown to inherit this complexity bound and that the
bound is tight to within a constant factor.

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