Technical Reports

The ICICS/CS Reading Room


UBC CS TR-90-04 Summary

Tight Lower Bounds for Probabilistic Solitude Verification on Anomynous Rings, January 1990 Karl Abrahamson, Andrew Adler, Lisa Higham and David G. Kirkpatrick

Tight lower bounds on the expected bit complexity of the Solitude Verification problem on anonymous asynchronous unidirectional rings are established that match the upper bounds demonstrated in a companion paper [5]. In the algorithms of [5], a variety of techniques are applied; In contrast, we find that a single technique, applied carefully, suffices for all of the lower bounds. The bounds demonstrate that, for this problem, the expected bit complexity depends subtly on the processors' knowledge of the size of the ring, and on the type of algorithm (Las Vegas or Monte Carlo / distributive or nondistributive termination).


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