Better computing on the anonymous ring

Hagit Attiya, Marc Snir

Research output: Contribution to journalArticlepeer-review

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 Θ(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.

Original languageEnglish (US)
Pages (from-to)204-238
Number of pages35
JournalJournal of Algorithms
Volume12
Issue number2
DOIs
StatePublished - Jun 1991
Externally publishedYes

ASJC Scopus subject areas

  • Control and Optimization
  • Computational Mathematics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Better computing on the anonymous ring'. Together they form a unique fingerprint.

Cite this