Relationships between broadcast and shared memory in reliable anonymous distributed systems |
| |
Authors: | James Aspnes Faith Ellen Fich Eric Ruppert |
| |
Affiliation: | (1) Department of Computer Science, Yale University, 51 Prospect Street, P.O. Box 208285, 06520-8285 New Haven, CT, U.S.A.;(2) Department of Computer Science, University of Toronto, 10 King's College Road, Toronto, M5S 3G4, Ontario, Canada;(3) Department of Computer Science and Engineering, York University, 4700 Keele Street, Toronto, M3J 1P3, Ontario, Canada |
| |
Abstract: | We study the power of reliable anonymous distributed systems, where processes do not fail, do not have identifiers, and run
identical programmes. We are interested specifically in the relative powers of systems with different communication mechanisms:
anonymous broadcast, read-write registers, or read-write registers plus additional shared-memory objects. We show that a system
with anonymous broadcast can simulate a system of shared-memory objects if and only if the objects satisfy a property we call
idemdicence this result holds regardless of whether either system is synchronous or asynchronous. Conversely, the key to simulating anonymous
broadcast in anonymous shared memory is the ability to count: broadcast can be simulated by an asynchronous shared-memory
system that uses only counters, but read-write registers by themselves are not enough. We further examine the relative power
of different types and sizes of bounded counters and conclude with a non-robustness result.
James Aspnes is a Professor of Computer Science at Yale University. He received his Ph.D. from Carnegie-Mellon University in 1992.
Faith Ellen Fich is a Professor of Computer Science at the University of Toronto. She received her Ph.D. from the University of California,
Berkeley in 1982.
Eric Ruppert was educated at the University of Toronto, where he completed his doctorate in 1999. He spent a year as a postdoctoral fellow
at Brown University and is an Associate Professor at York University. |
| |
Keywords: | Anonymous Broadcast Shared memory Robustness Simulations |
本文献已被 SpringerLink 等数据库收录! |
|