Probabilistic Evaluation of Common Functions On Rings of Known Size

Karl Abrahamson, Andrew Adler, Lisa Higham and David G. Kirkpatrick
Publishing date
June 1988

In [5]. Duris and Galil prove an $ \Omega (n \log n)$ lower bound for the average number of messages required by any deterministic algorithm which elects a leader on an asynchronous ring with distinct identifiers where ring size $n$ is known and is a power of 2. Their results imply the same lower bound for the expected complexity of any randomized leader election algorithm for an anonymous ring of known size $2^{k}$. If their new techniques are used to achieve the randomized result directly, the resulting proof is significantly simpler than the original deterministic one. This simplicity facilitates extension of the result in two directions; namely, for arbitrary known ring size, and for algorithms that permit error with probability at most $\epsilon $. Specifically, we prove that the expected message complexity of any probabilistic algorithm that selects a leader with probability at least $1 - \epsilon $ on an anonymous ring of known size $n$, is $\Omega (n \min(\log n, \log \log(l / \epsilon ))) $. A number of common function evaluation problems (including AND, OR, PARITY, and SUM) on rings of known size, are shown to inherit this complexity bound and that the bound is tight to within a constant factor.