Randomized Distributed Computing on Rings

ID
TR-89-05
Authors
Lisa Higham
Publishing date
January 1989
Abstract

The communication complexity of fundamental problems in distributed computing on an asynchronous ring are examined from both the algorithmic and lower bound perspective. A detailed study is made of the effect on complexity of a number of assumptions about the algorithms. Randomization is shown to influence both the computability and complexity of several problems. Communication complexity is also shown to exhibit varying degrees of sensitivity to additional parameters including admissibility of error, kind of error, knowledge of ring size, termination requirements, and the existence of identifiers. A unified collection of formal models of distributed computation on asynchronous rings is developed which captures the essential characteristics of a spectrum of distributed algorithms --- those that are error free (deterministic, Las Vegas, and nondeterministic) and those that err with small probability (Monte Carlo and nondeterministic/probabilistic). The nondeterministic and nondeterministic/probabilistic models are introduced as natural generalizations of the Las Vegas and Monte Carlo models respectively, and prove useful in deriving lower bounds. The unification helps to clarify the essential differences between the progressively more general notions of a distributed algorithm. In addition, the models reveal the sensitivity of various problems to the parameters listed above. Complexity bounds derived using these models typically vary depending on the type of algorithm being investigated. The lower bounds are complemented by algorithms with matching complexity while frequently the lower bounds hold on even more powerful models than those required by the algorithms. Among the algorithms and lower bounds presented are two specific results which stand out because of their relative significance. If $g$ is any nonconstant cyclic function of n variables. then any nondeterministic algorithm for computing $g$ on an anonymous ring of size $n$ has complexity $\Omega (n \sqrt{\log n})$ bits of communication; and. there is a is nonconstant cyclic boolean function $f$, such that f can be computed by a Las Vegas algorithm in $O (n \sqrt{\log n})$ expected bits of communication on a ring of size $n$. \item The expected complexity of computing AND (and a number of other natural functions) on a ring of fixed size n in the Monte Carlo model is \( \Theta (n \min \{ \log n, \log \log ( 1 / \epsilon ) \} ) \) messages and bits where $\epsilon $ is the allowable probability of error.