Computing on an anonymous ring

Chagit Attiya, Marc Snir, Manfred Warmuth

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

The computational capabilities of a system of indistinguishable processors arranged on a ring in the synchronous and asynchronous model of distributed computation are analyzed. A precise characterization of the functions that can be computed in such setting is given. It is shown that any function can be computed in O(n2) messages in the asynchronous model, and ?(n2) lower bounds are given for elementary functions such as AND, SUM and orientation. In the synchronous model any function can be computed in O(n lg n) Messages. A ring can be oriented and synchronized within the same bounds. These bounds are tight.

Original languageEnglish (US)
Title of host publicationProceedings of the 4th Annual ACM Symposium on Principles of Distributed Computing, PODC 1985
EditorsRay Strong, Michael Malcolm
PublisherAssociation for Computing Machinery
Pages196-203
Number of pages8
ISBN (Electronic)0897911687
DOIs
StatePublished - Aug 1 1985
Externally publishedYes
Event4th Annual ACM Symposium on Principles of Distributed Computing, PODC 1985 - Minaki, Canada
Duration: Aug 5 1985Aug 7 1985

Publication series

NameProceedings of the Annual ACM Symposium on Principles of Distributed Computing

Other

Other4th Annual ACM Symposium on Principles of Distributed Computing, PODC 1985
CountryCanada
CityMinaki
Period8/5/858/7/85

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Cite this