# The ICICS/CS Reading Room

## UBC CS TR-86-26 Summary

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

- Probabilistic Solitude Detection on Rings of Known Size, December 1986 Karl Abrahamson, Andrew Adler, Lisa Higham and David G. Kirkpatrick
Upper and lower bounds that match to within a constant factor are found
for the expected bit complexity of a problem on asynchronous unidirectional
rings of known size $n$, for algorithms that must reach a correct conclusion with
probability at least $1 - \epsilon$ for some small preassigned $\epsilon \geq 0$. The problem is
for a nonempty set of contenders to determine whether there is precisely one
contender. If distributive termination is required, the expected bit complexity is \( \Theta (n \min ( \log \nu (n) + \sqrt{ \log \log (1 / \epsilon)}, \sqrt{ \log n}, \log \log (1 / \epsilon))) \), where $ \nu (n) $ is
the least nondivisor of $n$. For nondistributive termination, $ \sqrt{\log \log (1 / \epsilon)} $ and
$ \sqrt{\log n}$ are replaced by $\log \log \log (l/ \epsilon)$ and $\log \log n$ respectively. The lower
bounds hold even for probabilistic algorithms that exhibit some nondeterministic features.

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