BETTER COMPUTING ON THE ANONYMOUS RING

We consider a bidirectional ring of n processors, where processors are anonymous, i.e., are indistinguishable. In this model it is known that "most" functions (in particular XOR and orientation) have worst case message complexity Θ(n2) for asynchronous computations, and Θ(n log n) for synchronous computations. The average case behavior is different; an algorithm that computes XOR asynchronously with O(n n messages on the average is known. In this paper we give tight bounds on the average complexity of various problems. We show the following: • •An asynchronous deterministic algorithm that computes any computable function with O(n log n) messages, on the average (improving the O(n n algorithm). A matching lower bound is proven for functions such as XOR and orientation. • •An asynchronous probabilistic algorithm that computes any computable function with O(n log n) expected messages on any input, using one random bit per processor. A matching lower bound is proven. • •A Monte-Carlo asynchronous algorithm that computes any computable function with O(n) expected messages on any input, using one random bit per processor, with fixed error probability ε > 0. • •A synchronous algorithm that computes any computable function optimally in O(n) messages, on the average. • •A synchronous probabilistic algorithm that computes any computable function optimally in O(n) expected messages on any input, using one random bit per processor • •Lower bounds on the complexity of Monte-Carlo algorithms that always terminate. © 1991.