Stably computable predicates are semilinear

ABSTRACT

We consider the model of population protocols introduced by Angluin et al. [2], in which anonymous finite-state agents stably compute a predicate of their inputs via two-way interactions in the all-pairs family of communication networks. We prove that all predicates stably computable in this model (and certain generalizations of it) are semilinear, answering a central open question about the power of the model.

REFERENCES

• 1: Dana Angluin, James Aspnes, Melody Chan, Michael J. Fischer, Hong Jiang, and René Peralta. Stably computable properties of network graphs. In Viktor K. Prasanna, Sitharama Iyengar, Paul Spirakis, and Matt Welsh, editors, Distributed Computing in Sensor Systems: First IEEE International Conference, DCOSS 2005, Marina del Rey, CA, USA, June/July, 2005, Proceedings, volume 3560 of Lecture Notes in Computer Science, pages 63--74. Springer-Verlag, June 2005.
• 2: Dana Angluin , James Aspnes , Zoë Diamadi , Michael J. Fischer , René Peralta, Computation in networks of passively mobile finite-state sensors, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada [doi>10.1145/1011767.1011810]
• 3: Dana Angluin, James Aspnes, David Eisenstat, and Eric Ruppert. On the power of anonymous one-way communication. In Ninth International Conference on Principles of Distributed Systems, pages 307--318, December 2005.
• 4: G. Higman. Ordering by divisibility in abstract algebras. Proceedings of the London Mathematical Society, 3(2):326--336, 1952.
• 5: J. Hopcroft and J. Pansiot. On the reachability problem for 5-dimensional vector addition systems. Theoretical Computer Science, 8(2):135--159, 1978.
• 6: Oscar H. Ibarra , Zhe Dang , Omer Egecioglu, Catalytic P systems, semilinear sets, and vector addition systems, Theoretical Computer Science, v.312 n.2-3, p.379-399, 30 January 2004 [doi>10.1016/j.tcs.2003.10.028]
• 7: Serge Lang. Algebra (Revised Third Edition). Springer-Verlag, 2002.
• 8: Steven R. Lay. Convex Sets and their Applications. Krieger Publishing Company, 1992.
• 9: Mojzesz Presburger. Über die Vollständigkeit eines gewissen Systems der Arithmetik ganzer Zahlen, in welchem die Addition als einzige Operation hervortritt. In Comptes-Rendus du I Congrès de Mathématiciens des Pays Slaves, pages 92--101, Warszawa, 1929.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Unbounded-action devices (e.g., cellular automata, circuits, networks of machines)

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

General Terms:
Theory

Keywords:
population protocols, semilinear sets, stable computation