James Aspnes, Faith Ellen Fich, and Eric Ruppert. Relationships between broadcast and shared memory in reliable anonymous distributed systems. Distributed Computing 18(3):209–219, February 2006. (DISC 2004 special issue.) An earlier version appeared in Proceedings of the Eighteenth International Symposium on Distributed Computing (DISC 2004), October 2004, pp. 260–274.
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 communications mechanisms: anonymous broadcast, read-write registers, or registers supplemented with 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 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.
@article(AspnesFR2006,
title="Relationships between broadcast and shared memory in reliable anonymous distributed systems",
author="James Aspnes and Faith Ellen Fich and Eric Ruppert",
journal={Distributed Computing},
volume=18,
number=3,
month=feb,
year=2006,
pages={209--219}
)