Access Restriction

Author Abrahamson, Karl ♦ Adler, Andrew ♦ Higham, Lisa ♦ Kirkpatrick, David
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1994
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Leader Election ♦ Solitude Verification ♦ Anonymous ring ♦ Asynchronous unidirectional ring ♦ Bit complexity ♦ Lower bounds ♦ Nondeterminism
Abstract A model that captures communication on asynchronous unidirectional rings is formalized. Our model incorporates both probabilistic and nondeterministic features and is strictly more powerful than a purely probabilistic model. Using this model, a collection of tools are developed that facilitate studying lower bounds on the expected communication complexity of Monte Carlo algorithms for language recognition problems on anonymous asynchronous unidirectional rings. The tools are used to establish tight lower bounds on the expected bit complexity of the Solitude Verification problem that asymptotically match upper bounds for this problem. The bounds demonstrate that, for this problem, the expected bit complexity depends subtly on the processors' knowledge of the size of the ring and on whether or not processor-detectable termination is required.
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 1994-03-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 41
Issue Number 2
Page Count 34
Starting Page 277
Ending Page 310

Open content in new tab

   Open content in new tab
Source: ACM Digital Library