## Abstract

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 Θ(n^{2}) 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.

Original language | English (US) |
---|---|

Pages (from-to) | 204-238 |

Number of pages | 35 |

Journal | Journal of Algorithms |

Volume | 12 |

Issue number | 2 |

DOIs | |

State | Published - Jun 1991 |

Externally published | Yes |

## ASJC Scopus subject areas

- Control and Optimization
- Computational Mathematics
- Computational Theory and Mathematics