Although much research has been devoted to designing and experimenting on ad hoc networks of tiny devices, very little has focussed on devising theoretical models to capture the inherent power and limitations of such networks. A notable exception is the population protocol model of Angluin et al. [Distributed Computing, 18(4):235-253]. This model is simple and elegant but is sometimes considered too restrictive because of its anonymity: mobile agents have no identities and all look the same.

We investigate in this paper the inherent power of the population protocol model augmented with the ability of each agent to be uniquely identified as well as store a constant number of other agents' identifiers. We provide an exact characterization of what can be computed in this new community protocol model: a function can be computed if and only if it is symmetric and in NSPACE(n log n). This is shown using a simulation of pointer machines.

We also consider the ability of our community protocol model to handle failures. We describe what can be computed when there are a constant number of benign failures and show that non-trivial computations can be achieved even if agents can be Byzantine.

Download paper in PDF format.

The documents distributed by this server have been provided by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a noncommercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.