# The ICICS/CS Reading Room

## UBC CS TR-87-08 Summary

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

- Probabilistic Solitude Detection I: Ring Size Known Approximately, March 1987 Karl Abrahamson, Andrew Adler, Lisa Higham and David G. Kirkpatrick
Matching upper and lower bounds for the bit complexity of a problem on asynchronous unidirectional rings are established, assuming that
algorithms must reach a correct conclusion with probability $1 - \epsilon$, for
some $\epsilon > 0$. Processors can have identities, but the identities are not
necessarily distinct. The problem is that of a distinguished processor determining whether it is the only distinguished processor. The
complexity depends on the processors' knowledge of the size $n$ of the
ring. When no upper bound is known, only nondistributive termination is possible, and $\Theta (n \log (1 / \epsilon)) $ bits are necessary and sufficient.
When only an upper bound $N$ is known, distributive termination is
possible, but the complexity of achieving distributive termination is
$ \Theta (n \sqrt{\log ( \frac{N}{n})} + n \log (\frac{1}{\epsilon}))$. When processors know that $(\frac{1}{2} + \rho)N \leq n \leq
N$ for $\rho > 0$, then the bound drops to $\Theta (n \log \log (\frac{1}{\epsilon}) + n \log (\frac{1}{\rho}))$, for
both distributive and nondistributive termination, for sufficiently large
$N$.

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