State Complexity of Protocols with Leaders

DOI10.1145/3519270.3538421MaRDI QIDQ6202166zbMATH OpenOpenAlexFDO

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)

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)

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.

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)