TY - GEN

T1 - Lower Bounds on the State Complexity of Population Protocols

AU - Czerner, Philipp

AU - Esparza, Javier

N1 - Publisher Copyright:
© 2021 ACM.

PY - 2021/7/21

Y1 - 2021/7/21

N2 - 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 Ø(log •) for leaderless protocols and Ο(log log •) for protocols with leaders. We obtain the first non-trivial lower bounds: the state complexity of x ≥ • is ω(log log log •) for leaderless protocols, and the inverse of a non-elementary function for protocols with leaders.

AB - 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 Ø(log •) for leaderless protocols and Ο(log log •) for protocols with leaders. We obtain the first non-trivial lower bounds: the state complexity of x ≥ • is ω(log log log •) for leaderless protocols, and the inverse of a non-elementary function for protocols with leaders.

KW - distributed computing

KW - population protocols

KW - state complexity

UR - http://www.scopus.com/inward/record.url?scp=85112378441&partnerID=8YFLogxK

U2 - 10.1145/3465084.3467912

DO - 10.1145/3465084.3467912

M3 - Conference contribution

AN - SCOPUS:85112378441

T3 - Proceedings of the Annual ACM Symposium on Principles of Distributed Computing

SP - 45

EP - 54

BT - PODC 2021 - Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing

PB - Association for Computing Machinery

T2 - 40th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC 2021

Y2 - 26 July 2021 through 30 July 2021

ER -