Technical Reports

The ICICS/CS Reading Room


UBC CS TR-87-11 Summary

Probabilistic Solitude Detection II: Ring Size Known Exactly, April 1987 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 (\frac{1}{\epsilon})}, \sqrt{\log n}, \log \log (\frac{1}{\epsilon}))) \), where $\nu (n)$ is the least nondivisor

of $n$. For nondistributive termination, $ \sqrt{\log \log (\frac{1}{\epsilon})}$ and $\sqrt{\log n}$ are

replaced by $\log \log \log(\frac{1}{\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.