Access Restriction

Author Attiya, Hagit ♦ Snir, Marc ♦ Warmuth, Manfred K.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1988
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Abstract The computational capabilities of a system of $\textit{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 $\textit{O}(\textit{n}2)$ 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 $\textit{O}(\textit{n}$ log $\textit{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 $&thgr;(\textit{n}$ log $\textit{n})$ (for particular $\textit{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.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1988-10-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 35
Issue Number 4
Page Count 31
Starting Page 845
Ending Page 875

Open content in new tab

   Open content in new tab
Source: ACM Digital Library