Lower Bounds on the State Complexity of Population Protocols

Philipp Czerner; Javier Esparza

doi:10.1145/3465084.3467912

Lower Bounds on the State Complexity of Population Protocols

Philipp Czerner, Javier Esparza

Informatics 7 - Chair of Theoretical Computer Science

Technical University of Munich

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

7 Scopus citations

Abstract

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.

Original language	English
Title of host publication	PODC 2021 - Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing
Publisher	Association for Computing Machinery
Pages	45-54
Number of pages	10
ISBN (Electronic)	9781450385480
DOIs	https://doi.org/10.1145/3465084.3467912
State	Published - 21 Jul 2021
Event	40th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC 2021 - Virtual, Online, Italy Duration: 26 Jul 2021 → 30 Jul 2021

Publication series

Name	Proceedings of the Annual ACM Symposium on Principles of Distributed Computing

Conference

Conference	40th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC 2021
Country/Territory	Italy
City	Virtual, Online
Period	26/07/21 → 30/07/21

Keywords

distributed computing
population protocols
state complexity

Access to Document

10.1145/3465084.3467912

Cite this

@inproceedings{d3407df13def4d769890bfd598a4a0b1,

title = "Lower Bounds on the State Complexity of Population Protocols",

abstract = "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 Ο(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.",

keywords = "distributed computing, population protocols, state complexity",

author = "Philipp Czerner and Javier Esparza",

note = "Publisher Copyright: {\textcopyright} 2021 ACM.; 40th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC 2021 ; Conference date: 26-07-2021 Through 30-07-2021",

year = "2021",

month = jul,

day = "21",

doi = "10.1145/3465084.3467912",

language = "English",

series = "Proceedings of the Annual ACM Symposium on Principles of Distributed Computing",

publisher = "Association for Computing Machinery",

pages = "45--54",

booktitle = "PODC 2021 - Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing",

}

Czerner, P & Esparza, J 2021, Lower Bounds on the State Complexity of Population Protocols. in PODC 2021 - Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing. Proceedings of the Annual ACM Symposium on Principles of Distributed Computing, Association for Computing Machinery, pp. 45-54, 40th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC 2021, Virtual, Online, Italy, 26/07/21. https://doi.org/10.1145/3465084.3467912

Lower Bounds on the State Complexity of Population Protocols. / Czerner, Philipp; Esparza, Javier.
PODC 2021 - Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing. Association for Computing Machinery, 2021. p. 45-54 (Proceedings of the Annual ACM Symposium on Principles of Distributed Computing).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Lower Bounds on the State Complexity of Population Protocols

AU - Czerner, Philipp

AU - Esparza, Javier

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 -

Lower Bounds on the State Complexity of Population Protocols

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this