Brief Announcement: A Time and Space Optimal Stable Population Protocol Solving Exact Majority
| Autor: | Leszek Gąsieniec, Mahsa Eftekhari, Grzegorz Stachowiak, Przemyslaw Uznanski, David Doty, Eric E. Severson |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
Schedule
education.field_of_study Computer science Population Value (computer science) 0102 computer and information sciences 02 engineering and technology Population protocol 16. Peace & justice Binary logarithm 01 natural sciences Majority problem Combinatorics Monotone polygon 010201 computation theory & mathematics 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Pairwise comparison education |
| Zdroj: | PODC |
| DOI: | 10.1145/3465084.3467942 |
| Popis: | We study population protocols, a model of distributed computing where agents exchange information in pairwise interactions, but have no control over their schedule of interaction partners. The well-studied majority problem is that of determining in an initial population of n agents, each with one of two opinions A or B, whether there are more A, more B, or a tie. A stable protocol solves this problem with probability 1 by eventually entering a configuration in which all agents agree on a correct consensus decision of A, B, or T, from which the consensus cannot change. We describe a protocol that solves this problem using O(log n) states (log log n + O(1) bits of memory) and optimal expected time O(log n). The number of states O(log n) is known to be optimal for the class of polylogarithmic time stable protocols that are "output dominant'' and "monotone''. These are two natural constraints satisfied by our protocol, making it simultaneously time- and state-optimal for that class. Our protocol is nonuniform : the transition function has the value log n encoded in it. We show that the protocol can be modified to be uniform, while increasing the state complexity to Θ(log n log log n). |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|