Dana Angluin, James Aspnes, David Eisenstat, and Eric Ruppert. On the power of anonymous one-way communication. Principles of Distributed Systems; 9th International Conference, OPODIS 2005; Pisa, Italy; December 2005; Revised Selected Papers, December 2005, pp. 396–411.
We consider a network of anonymous processes communicating via anonymous message-passing, where the recipient of each message is chosen by an adversary and the sender is not identified to the recipient. Even with unbounded message sizes and process states, such a system can compute only limited predicates on inputs held by the processes. In the finite-state case, we show how the exact strength of the model depends critically on design choices that are irrelevant in the unbounded-state case, such as whether messages are delivered immediately or after a delay, whether a sender can record that it has sent a message, and whether a recipient can queue incoming messages, refusing to accept new messages until it has had a chance to send out messages of its own. These results may have implications for the design of distributed systems where processor power is severely limited, as in sensor networks.
@inproceedings(AngluinAER2005,
title="On the power of anonymous one-way communication",
author="Dana Angluin and James Aspnes and David Eisenstat and Eric Ruppert",
booktitle="Principles of Distributed Systems;
9th International Conference, OPODIS 2005;
Pisa, Italy; December 2005; Revised Selected Papers",
series="Lecture Notes in Computer Science",
volume=3974,
month=dec,
year=2005,
pages={396--411}
)