State Complexity of Protocols with Leaders

DOI10.1145/3519270.3538421arXiv2109.15171OpenAlexW4286210572MaRDI QIDQ6202166FDOQ6202166

Authors: Jérôme Leroux 

Publication date: 26 March 2024

Published in: Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Abstract: Population protocols are a model of computation in which an arbitrary number of anonymous finite-memory agents are interacting in order to decide by stable consensus a predicate. In this paper, we focus on the counting predicates that asks, given an initial configuration, whether the number of agents in some initial state $i$ is at least $n$. In 2018, Blondin, Esparza, and Jaax shown that with a fix number of leaders and interaction-width, there exists infinitely many $n$ for which the counting predicate is stably computable by a protocol with at most $O(loglog(n))$ states. We provide in this paper a matching lower-bound (up to a square root) that improves the inverse-Ackermannian lower-bound presented at PODC in 2021.

Full work available at URL: https://arxiv.org/abs/2109.15171

zbMATH Keywords

Petri netspopulation protocolsstate complexitycounting predicates

Mathematics Subject Classification ID

Distributed algorithms (68W15) Distributed systems (68M14)

This page was built for publication: State Complexity of Protocols with Leaders

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6202166)