2021/02/23 by Philipp Czerner, Javier Esparza, Czerner, Philipp +3
Computer Science · Social Sciences · #Access Control and Trust #Distributed #Distributed systems and fault tolerance #FOS: Computer and information sciences #Logic, Reasoning, and Knowledge #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2102.11619
openalex publication_date 2021/02/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Population protocols are a model of computation in which an arbitrary number of indistinguishable finite-state agents interact in pairs. The goal of the agents is to decide by stable consensus whether their initial global configuration satisfies a given property, specified as a predicate on the set of configurations. The state complexity of a predicate is the number of states of a smallest protocol that computes it. Previous work by Blondin et al. has shown that the counting predicates x ≥ η have state complexity O(log η) for leaderless protocols and O(log log η) for protocols with leaders. We obtain the first non-trivial lower bounds: the state complexity of x ≥ η is Ω(loglog η) for leaderless protocols, and the inverse of a non-elementary function for protocols with leaders.