Probabilistic Solitude Detection I: Ring Size Known Approximately

ID
TR-87-08
Authors
Karl Abrahamson, Andrew Adler, Lisa Higham and David G. Kirkpatrick
Publishing date
March 1987
Abstract

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