Computing on an Anonymous Ring

Hagit Attiya, Marc Snir, Manfred K. Warmuth

Research output: Contribution to journalArticlepeer-review

Abstract

The computational capabilities of a system of n indistinguishable (anonymous) processors arranged on a ring in the synchronous and asynchronous models of distributed computation are analyzed. A precise characterization of the functions that can be computed in this setting is given. It is shown that any of these functions can be computed in O(n2) messages in the asynchronous model. This is also proved to be a lower bound for such elementary functions as AND, SUM, and Orientation. In the synchronous model any computable function can be computed in O(n log n) messages. A ring can be oriented and start synchronized within the same bounds. The main contribution of this paper is a new technique for proving lower bounds in the synchronous model. With this technique tight lower bounds of θ(n log n) (for particular n) are proved for XOR, SUM, Orientation, and Start Synchronization. The technique is based on a string-producing mechanism from formal language theory, first introduced by Thue to study square-free words. Two methods for generalizing the synchronous lower bounds to arbitrary ring sizes are presented.

Original languageEnglish (US)
Pages (from-to)845-875
Number of pages31
JournalJournal of the ACM (JACM)
Volume35
Issue number4
DOIs
StatePublished - Oct 1 1988
Externally publishedYes

Keywords

  • Communication complexity
  • coordination
  • distributed algorithms

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'Computing on an Anonymous Ring'. Together they form a unique fingerprint.

Cite this