2026-07-21T23:59:07Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18167 2024-03-06T11:01:12Z ddc:004 open_access

Population Protocols with Unordered Data Blondin, Michael Ladouceur, François Population protocols unordered data colored Petri nets Population protocols form a well-established model of computation of passively mobile anonymous agents with constant-size memory. It is well known that population protocols compute Presburger-definable predicates, such as absolute majority and counting predicates. In this work, we initiate the study of population protocols operating over arbitrarily large data domains. More precisely, we introduce population protocols with unordered data as a formalism to reason about anonymous crowd computing over unordered sequences of data. We first show that it is possible to determine whether an unordered sequence from an infinite data domain has a datum with absolute majority. We then establish the expressive power of the "immediate observation" restriction of our model, namely where, in each interaction, an agent observes another agent who is unaware of the interaction. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Michael Blondin and François Ladouceur 2023 Is Part Of LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2023.115 urn:nbn:de:0030-drops-181673 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.115 eng https://creativecommons.org/licenses/by/4.0/legalcode