Technical Reports

The ICICS/CS Reading Room


UBC CS TR-90-03 Summary

Optimal Algorithms for Probalistic Solitude Detection On Anomymous Rings, January 1990 Karl Abrahamson, Andrew Adler, Lisa Higham and David G. Kirkpatrick

Probabilistic algorithms that err with probability at most $\epsilon \geq 0$ are developed for the Solitude Detection problem on anonymous asynchronous unidirectional rings. Solitude Detection requires that a nonempty set of distinguished processors determine whether or not there is only one distinguished processor. The algorithms transmit an optimal expected number of bits, to within a constant factor. Las Vegas and Monte Carlo algorithms that terminate both distributively and nondistributively are developed. Their bit complexities display a surprisingly rich dependence on the kind of algorithm and on the processors' knowledge of the size of the ring.


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