[{"supplementarymaterial":"no","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"OA_type":"gold","language":[{"iso":"eng"}],"file_date_updated":"2026-07-21T07:31:29Z","author":[{"first_name":"Niccolò","full_name":"D'Archivio, Niccolò","last_name":"D'Archivio"},{"first_name":"Hind","full_name":"Almahmoud, Hind","last_name":"Almahmoud"},{"first_name":"Emanuele","full_name":"Natale, Emanuele","last_name":"Natale"},{"id":"68748c44-84d5-11f1-b4f6-ca083374e553","last_name":"Mallmann-Trenn","full_name":"Mallmann-Trenn, Frederik","first_name":"Frederik"}],"das_tickbox":"0","_id":"22368","license":"https://creativecommons.org/licenses/by/4.0/","date_updated":"2026-07-21T07:34:49Z","publication_status":"published","department":[{"_id":"MoHe"}],"date_published":"2026-07-01T00:00:00Z","publication_identifier":{"isbn":["9798400725128"]},"oa_version":"Published Version","article_processing_charge":"No","title":"Order statistics in population protocols via simple dynamics","publisher":"Association for Computing Machinery","month":"07","status":"public","quality_controlled":"1","acknowledgement":"This work has been supported by the AID INRIA-DGA project\r\nn°2023000872 “BioSwarm”, the French government National Research Agency (ANR) through the UCA JEDI (ANR-15-IDEX-01),\r\nthe EUR DS4H (ANR-17-EURE-004) and the 3IA Cote d’Azur Investments ANR-23-IACL-0001, and EPSRC grant EP/W005573/1","researchdata_availability":"no","type":"conference","year":"2026","corr_author":"1","citation":{"short":"N. D’Archivio, H. Almahmoud, E. Natale, F. Mallmann-Trenn, in:, Proceedings of the Annual ACM Symposium on Principles of Distributed Computing, Association for Computing Machinery, 2026, pp. 425–436.","ama":"D’Archivio N, Almahmoud H, Natale E, Mallmann-Trenn F. Order statistics in population protocols via simple dynamics. In: <i>Proceedings of the Annual ACM Symposium on Principles of Distributed Computing</i>. Association for Computing Machinery; 2026:425-436. doi:<a href=\"https://doi.org/10.1145/3796701.3815922\">10.1145/3796701.3815922</a>","ista":"D’Archivio N, Almahmoud H, Natale E, Mallmann-Trenn F. 2026. Order statistics in population protocols via simple dynamics. Proceedings of the Annual ACM Symposium on Principles of Distributed Computing. PODC: Symposium on Principles of Distributed Computing, 425–436.","ieee":"N. D’Archivio, H. Almahmoud, E. Natale, and F. Mallmann-Trenn, “Order statistics in population protocols via simple dynamics,” in <i>Proceedings of the Annual ACM Symposium on Principles of Distributed Computing</i>, Egham, United Kingdom, 2026, pp. 425–436.","mla":"D’Archivio, Niccolò, et al. “Order Statistics in Population Protocols via Simple Dynamics.” <i>Proceedings of the Annual ACM Symposium on Principles of Distributed Computing</i>, Association for Computing Machinery, 2026, pp. 425–36, doi:<a href=\"https://doi.org/10.1145/3796701.3815922\">10.1145/3796701.3815922</a>.","chicago":"D’Archivio, Niccolò, Hind Almahmoud, Emanuele Natale, and Frederik Mallmann-Trenn. “Order Statistics in Population Protocols via Simple Dynamics.” In <i>Proceedings of the Annual ACM Symposium on Principles of Distributed Computing</i>, 425–36. Association for Computing Machinery, 2026. <a href=\"https://doi.org/10.1145/3796701.3815922\">https://doi.org/10.1145/3796701.3815922</a>.","apa":"D’Archivio, N., Almahmoud, H., Natale, E., &#38; Mallmann-Trenn, F. (2026). Order statistics in population protocols via simple dynamics. In <i>Proceedings of the Annual ACM Symposium on Principles of Distributed Computing</i> (pp. 425–436). Egham, United Kingdom: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3796701.3815922\">https://doi.org/10.1145/3796701.3815922</a>"},"OA_place":"publisher","conference":{"end_date":"2026-07-10","name":"PODC: Symposium on Principles of Distributed Computing","start_date":"2026-07-06","location":"Egham, United Kingdom"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","has_accepted_license":"1","oa":1,"scopus_import":"1","doi":"10.1145/3796701.3815922","page":"425-436","day":"01","abstract":[{"lang":"eng","text":"We study simple dynamics in the population protocol model, in\r\nwhich 𝑛 agents start with totally ordered initial opinions 𝑥1, 𝑥2, . . . ,\r\n𝑥𝑛 and, in each round, a randomly chosen agent changes its opinion\r\nas a function of the opinion of other randomly chosen agents. Such\r\ndynamics often converge to consensus on a single fixation value 𝑋ˆ.\r\nThis paper asks how to control the distribution of 𝑋ˆ as a randomised\r\nchoice among the initial opinions by designing suitable simple\r\ndynamics. Writing the sorted initial values as 𝑥(1) ≤ · · · ≤ 𝑥(𝑛)\r\n,\r\nwe design two protocols that realise natural target laws over order\r\nstatistics.\r\nFirst, for a parameter 𝑝 ∈ (0, 1), our geometric protocol biases\r\ntoward larger opinions and satisfies P\r\n\r\n𝑋ˆ = 𝑥(𝑘)\r\n\r\n∝ 𝑝\r\n𝑛−𝑘\r\n, for\r\n𝑘 = 1, . . . , 𝑛. Equivalently, P\r\n\r\n𝑋ˆ = 𝑥(𝑘)\r\n\r\n= (1 − 𝑝)𝑝\r\n𝑛−𝑘\r\n/(1 − 𝑝\r\n𝑛\r\n).\r\nSecond, our binomial protocol assigns a shifted binomial law to the\r\nranks in ascending order: if 𝐾 −1 ∼ Bin(𝑛−1, 1−𝑝), then 𝑋ˆ = 𝑥(𝐾)\r\n,\r\ni.e., P\r\n\r\n𝑋ˆ = 𝑥(𝑘)\r\n\r\n=\r\n𝑛−1\r\n𝑘−1\r\n\u0001\r\n𝑝\r\n𝑛−𝑘\r\n(1 − 𝑝)\r\n𝑘−1\r\n, for 𝑘 = 1, . . . , 𝑛.\r\nApplications of this include computing the Top-𝑘 values for\r\nsmall 𝑘 on general interaction graphs. A central contribution of\r\nthis work is that, in contrast to most population protocols, we can\r\ncharacterise the fixation distribution in closed form. This is enabled\r\nby a novel analysis technique, which also yields applications: we\r\nderive new results for the Median protocol that extend the state of\r\nthe art."}],"date_created":"2026-07-19T22:01:47Z","ddc":["000"],"file":[{"file_id":"22379","content_type":"application/pdf","date_updated":"2026-07-21T07:31:29Z","file_name":"2026_ACMPODC_dArchivio.pdf","success":1,"creator":"dernst","access_level":"open_access","relation":"main_file","date_created":"2026-07-21T07:31:29Z","checksum":"e8208393a016d8e71d7b26c402045488","file_size":824239}],"publication":"Proceedings of the Annual ACM Symposium on Principles of Distributed Computing"},{"language":[{"iso":"eng"}],"OA_type":"gold","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"supplementarymaterial":"no","author":[{"full_name":"Cooper, Colin","first_name":"Colin","last_name":"Cooper"},{"first_name":"Frederik","full_name":"Mallmann-Trenn, Frederik","last_name":"Mallmann-Trenn","id":"68748c44-84d5-11f1-b4f6-ca083374e553"},{"last_name":"Radzik","full_name":"Radzik, Tomasz","first_name":"Tomasz"},{"full_name":"Shimizu, Nobutaka","first_name":"Nobutaka","last_name":"Shimizu"},{"full_name":"Shiraga, Takeharu","first_name":"Takeharu","last_name":"Shiraga"}],"file_date_updated":"2026-07-21T07:51:58Z","_id":"22367","das_tickbox":"1","department":[{"_id":"MoHe"}],"publication_identifier":{"isbn":["9798400725128"]},"date_published":"2026-07-01T00:00:00Z","oa_version":"Published Version","external_id":{"arxiv":["2603.02636"]},"date_updated":"2026-07-21T07:54:01Z","publication_status":"published","title":"Undecided state dynamics with many opinions","publisher":"Association for Computing Machinery","article_processing_charge":"No","month":"07","acknowledgement":"Nobutaka Shimizu is supported by JSPS KAKENHI Grant Number\r\n23K16837. Takeharu Shiraga is supported by JSPS KAKENHI Grant\r\nNumber 23K16840, and JST CRONOS Grant Number JPMJCS24K2.\r\nColin Cooper is supported by a Mercator Fellowship from DFG\r\nProject 491453517 at the University of Hamburg. We thank the\r\nanonymous reviewers for their helpful comments and suggestions.","researchdata_availability":"no","status":"public","quality_controlled":"1","type":"conference","year":"2026","corr_author":"1","citation":{"chicago":"Cooper, Colin, Frederik Mallmann-Trenn, Tomasz Radzik, Nobutaka Shimizu, and Takeharu Shiraga. “Undecided State Dynamics with Many Opinions.” In <i>Proceedings of the Annual ACM Symposium on Principles of Distributed Computing</i>, 77–87. Association for Computing Machinery, 2026. <a href=\"https://doi.org/10.1145/3796701.3815920\">https://doi.org/10.1145/3796701.3815920</a>.","apa":"Cooper, C., Mallmann-Trenn, F., Radzik, T., Shimizu, N., &#38; Shiraga, T. (2026). Undecided state dynamics with many opinions. In <i>Proceedings of the Annual ACM Symposium on Principles of Distributed Computing</i> (pp. 77–87). Egham, United Kingdom: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3796701.3815920\">https://doi.org/10.1145/3796701.3815920</a>","ieee":"C. Cooper, F. Mallmann-Trenn, T. Radzik, N. Shimizu, and T. Shiraga, “Undecided state dynamics with many opinions,” in <i>Proceedings of the Annual ACM Symposium on Principles of Distributed Computing</i>, Egham, United Kingdom, 2026, pp. 77–87.","mla":"Cooper, Colin, et al. “Undecided State Dynamics with Many Opinions.” <i>Proceedings of the Annual ACM Symposium on Principles of Distributed Computing</i>, Association for Computing Machinery, 2026, pp. 77–87, doi:<a href=\"https://doi.org/10.1145/3796701.3815920\">10.1145/3796701.3815920</a>.","ama":"Cooper C, Mallmann-Trenn F, Radzik T, Shimizu N, Shiraga T. Undecided state dynamics with many opinions. In: <i>Proceedings of the Annual ACM Symposium on Principles of Distributed Computing</i>. Association for Computing Machinery; 2026:77-87. doi:<a href=\"https://doi.org/10.1145/3796701.3815920\">10.1145/3796701.3815920</a>","short":"C. Cooper, F. Mallmann-Trenn, T. Radzik, N. Shimizu, T. Shiraga, in:, Proceedings of the Annual ACM Symposium on Principles of Distributed Computing, Association for Computing Machinery, 2026, pp. 77–87.","ista":"Cooper C, Mallmann-Trenn F, Radzik T, Shimizu N, Shiraga T. 2026. Undecided state dynamics with many opinions. Proceedings of the Annual ACM Symposium on Principles of Distributed Computing. PODC: Symposium on Principles of Distributed Computing, 77–87."},"OA_place":"publisher","has_accepted_license":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","keyword":["consensus dynamics","undecided state dynamics","gossip model","population protocol model"],"conference":{"location":"Egham, United Kingdom","start_date":"2026-07-06","name":"PODC: Symposium on Principles of Distributed Computing","end_date":"2026-07-10"},"day":"01","page":"77-87","arxiv":1,"oa":1,"scopus_import":"1","doi":"10.1145/3796701.3815920","abstract":[{"lang":"eng","text":"We study the Undecided-State Dynamics (USD), a fundamental consensus process in which each vertex holds one of k decided opinions or the undecided state. We consider both the gossip model and the population protocol model. Prior work established tight bounds on the consensus time of this process only for the regime \r\nk\r\n=\r\nO\r\n(\r\nn\r\n/\r\n(\r\nlog\r\n⁡\r\nn\r\n)\r\n2\r\n)\r\n (for the population protocol model) and k = O((n/log n)1/3) (for the gossip model), often under restrictive assumptions on the initial configuration.\r\nIn this paper, we obtain the first consensus-time guarantees for USD that hold for arbitrary 2 ≤ k ≤ n and for arbitrary initial configurations in both the gossip model and the population protocol model. In the gossip model, USD reaches consensus within \r\nO\r\n~\r\n(\r\nmin\r\n{\r\nk\r\n,\r\nn\r\n}\r\n)\r\n synchronous rounds with probability 1 - p⊥ - n-c, where p⊥ is the gossip-specific probability of collapsing to the all-undecided state in the first round. In the population protocol model, USD reaches consensus within \r\nO\r\n~\r\n(\r\nmin\r\n{\r\nk\r\nn\r\n,\r\nn\r\n3\r\n/\r\n2\r\n}\r\n)\r\n asynchronous interactions with high probability. We also present lower bounds that match the upper bounds up to polylogarithmic factors for a specific initial configuration and show that our upper bounds are essentially optimal."}],"ddc":["000"],"date_created":"2026-07-19T22:01:47Z","publication":"Proceedings of the Annual ACM Symposium on Principles of Distributed Computing","file":[{"creator":"dernst","relation":"main_file","access_level":"open_access","date_created":"2026-07-21T07:51:58Z","checksum":"9ada61feba1e93fd72867a5ba4ee8bb8","file_size":709077,"file_id":"22380","content_type":"application/pdf","date_updated":"2026-07-21T07:51:58Z","file_name":"2026_ACMPODC_Cooper.pdf","success":1}]},{"year":"2026","corr_author":"1","type":"conference","citation":{"ieee":"T.-L. Breitkopf, J. Dallot, A. El-Hayek, and S. Schmid, “Ranking opinions with few states in population protocols,” in <i>Proceedings of the ACM Symposium on Principles of Distributed Computing</i>, Egham, United Kingdom, 2026, pp. 414–424.","mla":"Breitkopf, Tom-Lukas, et al. “Ranking Opinions with Few States in Population Protocols.” <i>Proceedings of the ACM Symposium on Principles of Distributed Computing</i>, Association for Computing Machinery, 2026, pp. 414–24, doi:<a href=\"https://doi.org/10.1145/3796701.3815913\">10.1145/3796701.3815913</a>.","apa":"Breitkopf, T.-L., Dallot, J., El-Hayek, A., &#38; Schmid, S. (2026). Ranking opinions with few states in population protocols. In <i>Proceedings of the ACM Symposium on Principles of Distributed Computing</i> (pp. 414–424). Egham, United Kingdom: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3796701.3815913\">https://doi.org/10.1145/3796701.3815913</a>","chicago":"Breitkopf, Tom-Lukas, Julien Dallot, Antoine El-Hayek, and Stefan Schmid. “Ranking Opinions with Few States in Population Protocols.” In <i>Proceedings of the ACM Symposium on Principles of Distributed Computing</i>, 414–24. Association for Computing Machinery, 2026. <a href=\"https://doi.org/10.1145/3796701.3815913\">https://doi.org/10.1145/3796701.3815913</a>.","ista":"Breitkopf T-L, Dallot J, El-Hayek A, Schmid S. 2026. Ranking opinions with few states in population protocols. Proceedings of the ACM Symposium on Principles of Distributed Computing. PODC: Symposium on Principles of Distributed Computing, 414–424.","short":"T.-L. Breitkopf, J. Dallot, A. El-Hayek, S. Schmid, in:, Proceedings of the ACM Symposium on Principles of Distributed Computing, Association for Computing Machinery, 2026, pp. 414–424.","ama":"Breitkopf T-L, Dallot J, El-Hayek A, Schmid S. Ranking opinions with few states in population protocols. In: <i>Proceedings of the ACM Symposium on Principles of Distributed Computing</i>. Association for Computing Machinery; 2026:414-424. doi:<a href=\"https://doi.org/10.1145/3796701.3815913\">10.1145/3796701.3815913</a>"},"OA_place":"publisher","has_accepted_license":"1","conference":{"location":"Egham, United Kingdom","start_date":"2026-07-06","name":"PODC: Symposium on Principles of Distributed Computing","end_date":"2026-07-10"},"user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","arxiv":1,"page":"414 - 424","day":"01","scopus_import":"1","doi":"10.1145/3796701.3815913","oa":1,"project":[{"call_identifier":"H2020","_id":"bd9ca328-d553-11ed-ba76-dc4f890cfe62","grant_number":"101019564","name":"The design and evaluation of modern fully dynamic data structures"},{"grant_number":"I05982","name":"Static and Dynamic Hierarchical Graph Decompositions","_id":"bda196b2-d553-11ed-ba76-8e8ee6c21103"}],"abstract":[{"text":"Population protocols are a model of distributed computing where\r\n𝑛 agents, each a simple finite-state machine, interact in pairs to\r\nsolve a common task against a (adversarial) interaction scheduler.\r\nThis model was intensively studied in recent years; in particular,\r\nthe problem of relative majority received much attention: Each\r\nagent starts with an input opinion (or color) out of 𝑘 possibilities,\r\nand the goal is for each agent to eventually output the color with\r\nthe largest support in the population. Before our work, the state\r\ncomplexity (the minimum number of states required per agent) was\r\nonly known to be between Ω(𝑘\r\n2\r\n) and𝑂(𝑘\r\n7\r\n). Our main contribution\r\nis a population protocol that solves the relative majority problem\r\nwith 𝑘\r\n3\r\nstates. We achieve this result with a new protocol called\r\nCircles. While prior approaches in the literature relied on duels of\r\nagents to find the majority color — an approach that proved effective\r\nfor the case with two colors — Circles partitions the agents into\r\ncircular linked lists of decreasing sizes, with the property that no\r\ntwo agents with the same initial color lie in the same circle. We\r\nshow that Circles always correctly computes the desired structure\r\nagainst the most adversarial of schedulers (weakly fair). We then\r\nshow that a trivial extension of Circles solves the relative majority\r\nproblem. We extend our protocol to handle various tie-breaking\r\nmechanisms or to support the case where the agents do not share a\r\nprior ordering of the colors. Finally, we show that a modification of\r\nCircles solves the ranking problem with 2 · 𝑘^4\r\nstates, where each\r\nagent must output the rank of its initial color in the population.","lang":"eng"}],"ddc":["000"],"date_created":"2026-07-14T05:40:17Z","publication":"Proceedings of the ACM Symposium on Principles of Distributed Computing","file":[{"file_size":702140,"checksum":"e56da70c1b2e7e663d2d8106cf07a30a","date_created":"2026-07-16T11:18:44Z","relation":"main_file","access_level":"open_access","creator":"dernst","success":1,"file_name":"2026_ACMPODC_Breitkopf.pdf","date_updated":"2026-07-16T11:18:44Z","content_type":"application/pdf","file_id":"22353"}],"language":[{"iso":"eng"}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"OA_type":"gold","supplementarymaterial":"no","author":[{"last_name":"Breitkopf","full_name":"Breitkopf, Tom-Lukas","first_name":"Tom-Lukas"},{"first_name":"Julien","full_name":"Dallot, Julien","last_name":"Dallot"},{"full_name":"El-Hayek, Antoine","first_name":"Antoine","orcid":"0000-0003-4268-7368","last_name":"El-Hayek","id":"888a098e-fcac-11ee-aff7-d347be57b725"},{"last_name":"Schmid","full_name":"Schmid, Stefan","first_name":"Stefan"}],"file_date_updated":"2026-07-16T11:18:44Z","_id":"22327","das_tickbox":"0","oa_version":"Published Version","publication_identifier":{"isbn":["9798400725128"]},"department":[{"_id":"MoHe"},{"_id":"GradSch"}],"ec_funded":1,"date_published":"2026-07-01T00:00:00Z","publication_status":"published","external_id":{"arxiv":["2605.18707"]},"date_updated":"2026-07-22T07:49:22Z","publisher":"Association for Computing Machinery","title":"Ranking opinions with few states in population protocols","article_processing_charge":"Yes","month":"07","acknowledgement":"Funded by the European union. Views and opinions expressed are\r\nhowever those of the author(s) only and do not necessarily reflect\r\nthose of the European Union or the European Research Council\r\nExecutive Agency. Neither the European Union nor the granting authority can be held responsible for them. This project has received\r\nfunding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme\r\n(MoDynStruct, No. 101019564) and the Austrian Science\r\nFund (FWF) grant DOI 10.55776/I5982. For open access purposes,\r\nthe author has applied a CC BY public copyright license to any\r\nauthor-accepted manuscript version arising from this submission.","researchdata_availability":"no","quality_controlled":"1","status":"public"}]