Tight Lower Bounds for Probabilistic Solitude Verification on Anomynous Rings

ID
TR-90-04
Authors
Karl Abrahamson, Andrew Adler, Lisa Higham and David G. Kirkpatrick
Publishing date
January 1990
Abstract

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).