article

The computational power of population protocols

Authors:

David Eisenstat,

Eric RuppertAuthors Info & Claims

Distributed Computing, Volume 20, Issue 4

Pages 279 - 304

https://doi.org/10.1007/s00446-007-0040-2

Published: 01 November 2007 Publication History

Abstract

We consider the model of population protocols introduced by Angluin et al. (Computation in networks of passively mobile finite-state sensors, pp. 290---299. ACM, New York, 2004), in which anonymous finite-state agents stably compute a predicate of the multiset of their inputs via two-way interactions in the family of all-pairs 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. Removing the assumption of two-way interaction, we also consider several variants of the model in which agents communicate by anonymous message-passing where the recipient of each message is chosen by an adversary and the sender is not identified to the recipient. These one-way models are distinguished by 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. We characterize the classes of predicates stably computable in each of these one-way models using natural subclasses of the semilinear predicates.

References

[1]

Angluin, D., Aspnes, J., Chan, M., Fischer, M.J., Jiang, H., Peralta, R.: Stably computable properties of network graphs. In: Prasanna, V.K., Iyengar, S., Spirakis, P., Welsh, M. (eds) 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, pp. 63---74. Springer, Berlin (2005)

Digital Library

[2]

Angluin, D., Aspnes, J., Diamadi, Z., Fischer, M.J., Peralta, R.: Urn automata. Technical Report YALEU/DCS/TR-1280, Yale University Department of Computer Science (2003)

[3]

Angluin, D., Aspnes, J., Diamadi, Z., Fischer, M.J., Peralta, R.: Computation in networks of passively mobile finite-state sensors. In: PODC '04: Proceedings of the Twenty-Third Annual ACM Symposium on Principles of Distributed Computing, pp. 290---299. ACM, New York (2004)

Digital Library

[4]

Angluin D., Aspnes J., Diamadi Z., Fischer M.J. and Peralta R. (2006). Computation in networks of passively mobile finite-state sensors. Distrib. Comput. 18(4): 235---253

Digital Library

[5]

Angluin, D., Aspnes, J., Eisenstat, D.: Fast computation by population protocols with a leader. In: Distributed Computing: 20th International Symposium, DISC 2006: Stockholm, Sweden, September 2006: Proceedings, pp. 61---75 (2006)

Digital Library

[6]

Angluin, D., Aspnes, J., Eisenstat, D.: Stably computable predicates are semilinear. In: Proceedings of the 25th ACM Symposium on Principles of Distributed Computing, pp. 292---299 (2006)

Digital Library

[7]

Angluin, D., Aspnes, J., Eisenstat, D., Ruppert, E.: On the power of anonymous one-way communication. In: Principles of Distributed Systems; 9th International Conference, OPODIS 2005; Pisa, Italy; December 2005; Revised Selected Papers, volume 3974 of Lecture Notes in Computer Science, pp. 396---411 (2005)

Digital Library

[8]

Angluin, D., Aspnes, J., Fischer, M.J., Jiang, H.: Self-stabilizing population protocols. In: Principles of Distributed Systems; 9th International Conference, OPODIS 2005; Pisa, Italy; December 2005; Revised Selected Papers, volume 3974 of Lecture Notes in Computer Science. pp. 103---117 (2005)

Digital Library

[9]

Angluin, D., Fischer, M.J., Jiang, H.: Stabilizing consensus in mobile networks. In: Proceedings of Distributed Computing in Sensor Systems: Second IEEE International Conference, volume 4026 of Lecture Notes in Computer Science, pp. 37---50 (2006)

Digital Library

[10]

Attiya H., Gorbach A. and Moran S. (2002). Computing in totally anonymous asynchronous shared memory systems. Inform. Comput. 173(2): 162---183

Digital Library

[11]

Angluin, D.: Local and global properties in networks of processors. In: Proceedings of the 12th ACM Symposium on Theory of Computing, pp. 82---93 (1980)

Digital Library

[12]

Aspnes, J., Shah, G., Shah, J.: Wait-free consensus with infinite arrivals. In: Proceedings of the 34th ACM Symposium on Theory of Computing, pp. 524---533 (2002)

Digital Library

[13]

Bailey N.T.J. (1975). The Mathematical Theory of Infectious Diseases, Second Edition. Charles Griffin & Co., London

[14]

Buhrman H. (2006). Alessandro Panconesi, Riccardo Silvestri and Paul Vitanyi. On the importance of having an identity or, is consensus really universal?. Distrib. Comput. 18(3): 167---176

Digital Library

[15]

Boldi, P., Vigna, S.: Computing anonymously with arbitrary knowledge. In: Proceedings of the 18th ACM Symposium on Principles of Distributed Computing, pp. 173---179 (1999)

Digital Library

[16]

Boldi, P., Vigna, S.: An effective characterization of computability in anonymous networks. In: Distributed Computing, 15th International Conference, pp. 33---47 (2001)

Digital Library

[17]

Diamadi, Z., Fischer, M.J.: A simple game for the study of trust in distributed systems. Wuhan Univ. J. Natural Sci. 6(1---2), 72---82 (2001). Also appears as Yale Technical Report TR---1207, January 2001

[18]

Delporte-Gallet, C., Fauconnier, H., Guerraoui, R., Ruppert, E.: When birds die: Making population protocols fault-tolerant. In: Proceedings of the Second IEEE International Conference on Distributed Computing in Sensor Systems (DCOSS '06), pp. 51---66 (2006)

Digital Library

[19]

Dickson L.E. (1913). Finiteness of the odd perfect and primitive abundant numbers with n distinct prime factors. Am. J. Math. 35(4): 413---422

[20]

Daley D.J. and Kendall D.G. (1965). Stochastic rumours. J. Inst. Math. Appl. 1: 42---55

[21]

Eğecioğlu Ö. and Singh A.K. (1994). Naming symmetric processes using shared variables. Distrib. Comput. 8(1): 19---38

Digital Library

[22]

Fischer, M.J., Jiang, H.: Self-stabilizing leader election in networks of finite-state anonymous agents. In: Tenth International Conference on Principles of Distributed Systems, volume 4305 of Lecture Notes in Computer Science, pp. 395---409 (2006)

Digital Library

[23]

Fich F. and Ruppert E. (2003). Hundreds of impossibility results for distributed computing. Distrib. Comput. 16(2---3): 121---163

Digital Library

[24]

Gibson M.A. and Bruck J. (2000). Efficient exact stochastic simulation of chemical systems with many species and many channels. J. Phys. Chem. A 104: 1876---1880

[25]

Gillespie D.T. (1992). A rigorous derivation of the chemical master equation. Physica A 188: 404---425

[26]

Guerraoui, R., Ruppert, E.: Anonymous and fault-tolerant shared-memory computing. Distrib. Comput. (2007, in press)

Digital Library

[27]

Higman G. (1952). Ordering by divisibility in abstract algebras. Proc. Lond. Math. Soc. 3(2): 326---336

[28]

Hopcroft J. and Pansiot J. (1978). On the reachability problem for 5-dimensional vector addition systems. Theoret. Comput. Sci. 8(2): 135---159

[29]

Ibarra O.H., Dang Z. and Egecioglu O. (2004). Catalytic P systems, semilinear sets, and vector addition systems. Theor. Comput. Sci. 312(2---3): 379---399

Digital Library

[30]

Jiang, H.: Distributed Systems of Simple Interacting Agents. PhD thesis, Yale University (2007)

Digital Library

[31]

Jayanti, P., Toueg, S.: Wakeup under read/write atomicity. In: Distributed Algorithms, 4th International Workshop, volume 486 of LNCS, pp. 277---288 (1990)

Digital Library

[32]

Kutten S., Ostrovsky R. and Patt-Shamir B. (2000). The Las-Vegas processor identity problem (How and when to be unique). J. Algorithms 37(2): 468---494

Digital Library

[33]

Lang S. (2002). Algebra (revised third edition). Springer, Berlin

[34]

Lay, S.R.: Convex Sets and their Applications. Krieger Publishing Company, (1992)

[35]

Lipton R.J. and Park A. (1990). The processor identity problem. Inform. Process. Lett. 36(2): 91---94

Digital Library

[36]

Parikh R.J. (1966). On context-free languages. J. ACM 13(4): 570---581

Digital Library

[37]

Panconesi A., Papatriantafilou M., Tsigas P. and Vitányi P. (1998). Randomized naming using wait-free shared variables. Distrib. Comput. 11(3): 113---124

Digital Library

[38]

Presburger, M.: Ü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, pp. 92---101, Warszawa (1929)

[39]

Sakamoto, N.: Comparison of initial conditions for distributed algorithms on anonymous networks. In: Proc. 18th ACM Symposium on Principles of Distributed Computing, pp. 173---179 (1999)

Digital Library

[40]

Teng S.-H. (1990). Space efficient processor identity protocol. Inform. Process. Lett. 34(3): 147---154

Digital Library

Cited By

Eichler PJacobs SWeil-Kennedy C(2025)Parameterized Verification of Systems with Precise (0,1)-Counter AbstractionVerification, Model Checking, and Abstract Interpretation10.1007/978-3-031-82700-6_5(101-124)Online publication date: 20-Jan-2025
https://dl.acm.org/doi/10.1007/978-3-031-82700-6_5
Charron-Bost BLambein-Monette PKuznetsov PGelles ROlivetti D(2024)Brief Announcement: Know Your AudienceProceedings of the 43rd ACM Symposium on Principles of Distributed Computing10.1145/3662158.3662784(243-246)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3662158.3662784
Kanaya HSudo Y(2024)Complete Graph Identification in Population ProtocolsStabilization, Safety, and Security of Distributed Systems10.1007/978-3-031-74498-3_9(126-140)Online publication date: 20-Oct-2024
https://dl.acm.org/doi/10.1007/978-3-031-74498-3_9
Show More Cited By

The computational power of population protocols
1. Theory of computation

Recommendations

On the computational power of pushdown automata

We present a relation between the sets accepted by two-way pushdown automataand certain tape complexity classes of off-line Turing machines. Specifically, let L be a language accepted by a nondeterministic off-line Turing machine T. Let T have a t-...
Homonym Population Protocols

The population protocol model was introduced by Angluin et al. as a model of passively mobile anonymous finite-state agents. This model computes a predicate on the multiset of their inputs via interactions by pairs. The original population protocol ...
The computational power of synchronized alternation

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Distributed Computing

Distributed Computing Volume 20, Issue 4

November 2007

66 pages

ISSN:0178-2770

Issue’s Table of Contents

Copyright © Copyright © 2007 Springer-Verlag.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 November 2007

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

92
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 27 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Eichler PJacobs SWeil-Kennedy C(2025)Parameterized Verification of Systems with Precise (0,1)-Counter AbstractionVerification, Model Checking, and Abstract Interpretation10.1007/978-3-031-82700-6_5(101-124)Online publication date: 20-Jan-2025
https://dl.acm.org/doi/10.1007/978-3-031-82700-6_5
Charron-Bost BLambein-Monette PKuznetsov PGelles ROlivetti D(2024)Brief Announcement: Know Your AudienceProceedings of the 43rd ACM Symposium on Principles of Distributed Computing10.1145/3662158.3662784(243-246)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3662158.3662784
Kanaya HSudo Y(2024)Complete Graph Identification in Population ProtocolsStabilization, Safety, and Security of Distributed Systems10.1007/978-3-031-74498-3_9(126-140)Online publication date: 20-Oct-2024
https://dl.acm.org/doi/10.1007/978-3-031-74498-3_9
Basu SSankararaman AOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Double auctions with two-sided bandit feedbackProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3666290(3841-3852)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3666290
Czerner PEsparza JLeroux J(2023)Lower bounds on the state complexity of population protocolsDistributed Computing10.1007/s00446-023-00450-436:3(209-218)Online publication date: 15-Jun-2023
https://dl.acm.org/doi/10.1007/s00446-023-00450-4
Di Stefano LLang F(2023)Compositional Verification of Stigmergic Collective SystemsVerification, Model Checking, and Abstract Interpretation10.1007/978-3-031-24950-1_8(155-176)Online publication date: 16-Jan-2023
https://dl.acm.org/doi/10.1007/978-3-031-24950-1_8
Bankhamer GBerenbrink PBiermeier FElsässer RHosseinpour HKaaser DKling PMilani AWoelfel P(2022)Population Protocols for Exact Plurality ConsensusProceedings of the 2022 ACM Symposium on Principles of Distributed Computing10.1145/3519270.3538447(224-234)Online publication date: 20-Jul-2022
https://dl.acm.org/doi/10.1145/3519270.3538447
Leroux JMilani AWoelfel P(2022)State Complexity of Protocols with LeadersProceedings of the 2022 ACM Symposium on Principles of Distributed Computing10.1145/3519270.3538421(257-264)Online publication date: 20-Jul-2022
https://dl.acm.org/doi/10.1145/3519270.3538421
Cho DFügger MHopper CKushwaha MNowak TSoubeyran Q(2022)Distributed computation with continual population growthDistributed Computing10.1007/s00446-021-00404-835:6(547-569)Online publication date: 1-Dec-2022
https://dl.acm.org/doi/10.1007/s00446-021-00404-8
Almalki NMichail O(2022)On Geometric Shape Construction via Growth OperationsAlgorithmics of Wireless Networks10.1007/978-3-031-22050-0_1(1-17)Online publication date: 8-Sep-2022
https://dl.acm.org/doi/10.1007/978-3-031-22050-0_1
Show More Cited By

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents