Even Small Birds are Unique: Population Protocols with Identifiers

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. [2]. 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 nontrivial computations can be achieved even if agents can be Byzantine.