@inproceedings{76cb548c7d0b49ce835704832b307e46,

title = "Computing on an anonymous ring",

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.",

author = "Chagit Attiya and Marc Snir and Manfred Warmuth",

note = "Publisher Copyright: {\textcopyright} 1985 ACM.; 4th Annual ACM Symposium on Principles of Distributed Computing, PODC 1985 ; Conference date: 05-08-1985 Through 07-08-1985",

year = "1985",

month = aug,

day = "1",

doi = "10.1145/323596.323614",

language = "English (US)",

series = "Proceedings of the Annual ACM Symposium on Principles of Distributed Computing",

publisher = "Association for Computing Machinery",

pages = "196--203",

editor = "Ray Strong and Michael Malcolm",

booktitle = "Proceedings of the 4th Annual ACM Symposium on Principles of Distributed Computing, PODC 1985",

address = "United States",

}