Lower bounds on the state complexity of population protocols

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...

Full description

Saved in:
Bibliographic Details
Published in:Distributed computing 2023-09, Vol.36 (3), p.209-218
Main Authors: Czerner, Philipp, Esparza, Javier, Leroux, Jérôme
Format: Article
Language:English
Subjects:
Complexity
Computer Communication Networks
Computer Hardware
Computer Science
Computer Systems Organization and Communication Networks
Configurations
Lower bounds
Software Engineering/Programming and Operating Systems
Theory of Computation
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 Ω ( log log η ) for leaderless protocols, and the inverse of a non-elementary function for protocols with leaders.
ISSN:0178-2770
1432-0452
DOI:10.1007/s00446-023-00450-4