Article

Stably computable predicates are semilinear

Authors:

Dana Angluin,

James Aspnes,

David EisenstatAuthors Info & Claims

PODC '06: Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing

Pages 292 - 299

https://doi.org/10.1145/1146381.1146425

Published: 23 July 2006 Publication History

Get Access

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.

Digital Library

Google Scholar

[2]

Dana Angluin, James Aspnes, Zoë Diamadi, Michael J. Fischer, and René Peralta. 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, pages 290--299. ACM Press, 2004.

Digital Library

Google Scholar

[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.

Digital Library

Google Scholar

[4]

G. Higman. Ordering by divisibility in abstract algebras. Proceedings of the London Mathematical Society, 3(2):326--336, 1952.

Crossref

Google Scholar

[5]

J. Hopcroft and J. Pansiot. On the reachability problem for 5-dimensional vector addition systems. Theoretical Computer Science, 8(2):135--159, 1978.

Crossref

Google Scholar

[6]

Oscar H. Ibarra, Zhe Dang, and Omer Egecioglu. Catalytic p systems, semilinear sets, and vector addition systems. Theor. Comput. Sci., 312(2-3):379--399, 2004.

Digital Library

Google Scholar

[7]

Serge Lang. Algebra (Revised Third Edition). Springer-Verlag, 2002.

Google Scholar

[8]

Steven R. Lay. Convex Sets and their Applications. Krieger Publishing Company, 1992.

Google Scholar

[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.

Google Scholar

Cited By

View all

Luchsinger ADoty DSoloveichik DKuznetsov PGelles ROlivetti D(2024)Brief Announcement: Optimally Encoding Information in Chemical Reaction NetworksProceedings of the 43rd ACM Symposium on Principles of Distributed Computing10.1145/3662158.3662827(61-64)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3662158.3662827
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://doi.org/10.1007/978-3-031-74498-3_9
Chen HDoty DReeves WSoloveichik D(2023)Rate-independent Computation in Continuous Chemical Reaction NetworksJournal of the ACM10.1145/359077670:3(1-61)Online publication date: 23-May-2023
https://dl.acm.org/doi/10.1145/3590776
Show More Cited By

Index Terms

Stably computable predicates are semilinear

Recommendations

Computation in networks of passively mobile finite-state sensors
PODC '04: Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing

We explore the computational power of networks of small resource-limited mobile agents. We define two new models of computation based on pairwise interactions of finite-state agents in populations of finite but unbounded size. With a fairness condition ...
On the Context-Freeness Problem for Vector Addition Systems
LICS '13: Proceedings of the 2013 28th Annual ACM/IEEE Symposium on Logic in Computer Science

Petri nets, or equivalently vector addition systems (VAS), are widely recognized as a central model for concurrent systems. Many interesting properties are decidable for this class, such as bounded ness, reach ability, regularity, as well as context-...
The Algebraic Theory of Parikh Automata

The Parikh automaton model equips a finite automaton with integer registers and imposes a semilinear constraint on the set of their final settings. Here the theories of typed monoids and of rational series are used to characterize the language classes ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

PODC '06: Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing

July 2006

230 pages

ISBN:1595933840

DOI:10.1145/1146381

General Chair:
Eric Ruppert
York U., Canada
,
Program Chair:
Dahlia Malkhi
Microsoft Research, USA & Hebrew University, Israel

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 July 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

PODC06

Sponsor:

PODC06: ACM Symposium on Principles of Distributed Computing 2006

July 23 - 26, 2006

Colorado, Denver, USA

Acceptance Rates

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

95
Total Citations
View Citations
314
Total Downloads

Downloads (Last 12 months)17
Downloads (Last 6 weeks)4

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Luchsinger ADoty DSoloveichik DKuznetsov PGelles ROlivetti D(2024)Brief Announcement: Optimally Encoding Information in Chemical Reaction NetworksProceedings of the 43rd ACM Symposium on Principles of Distributed Computing10.1145/3662158.3662827(61-64)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3662158.3662827
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://doi.org/10.1007/978-3-031-74498-3_9
Chen HDoty DReeves WSoloveichik D(2023)Rate-independent Computation in Continuous Chemical Reaction NetworksJournal of the ACM10.1145/359077670:3(1-61)Online publication date: 23-May-2023
https://dl.acm.org/doi/10.1145/3590776
Doyen L(2023)Stochastic Games with Synchronization ObjectivesJournal of the ACM10.1145/358886670:3(1-35)Online publication date: 23-May-2023
https://dl.acm.org/doi/10.1145/3588866
Gaitonde JTardos É(2023)The Price of Anarchy of Strategic Queuing SystemsJournal of the ACM10.1145/358725070:3(1-63)Online publication date: 23-May-2023
https://dl.acm.org/doi/10.1145/3587250
Rutschmann DWettstein M(2023)Chains, Koch Chains, and Point Sets with Many TriangulationsJournal of the ACM10.1145/358553570:3(1-26)Online publication date: 23-May-2023
https://dl.acm.org/doi/10.1145/3585535
Liu AMoitra A(2023)Robustly Learning General Mixtures of GaussiansJournal of the ACM10.1145/358368070:3(1-53)Online publication date: 23-May-2023
https://dl.acm.org/doi/10.1145/3583680
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
Doty DEftekhari MGasieniec LSeverson EUznanski PStachowiak G(2022)A time and space optimal stable population protocol solving exact majority2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS52979.2021.00104(1044-1055)Online publication date: Feb-2022
https://doi.org/10.1109/FOCS52979.2021.00104
Michail OSpirakis PTheofilatos M(2022)Simple and fast approximate counting and leader election in populationsInformation and Computation10.1016/j.ic.2021.104698285(104698)Online publication date: May-2022
https://doi.org/10.1016/j.ic.2021.104698
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Computation in networks of passively mobile finite-state sensors

On the Context-Freeness Problem for Vector Addition Systems

The Algebraic Theory of Parikh Automata