Gąsieniec, Leszek, Stachowiak, Grzegorz and Uznański, Przemysław
(2020)
Time and Space Optimal Exact Majority Population Protocols.
|
Text
2011.07392v1.pdf - Published Version Download (1MB) | Preview |
Abstract
In this paper we study population protocols governed by the {\em random scheduler}, which uniformly at random selects pairwise interactions between $n$ agents. The main result of this paper is the first time and space optimal {\em exact majority population protocol} which also works with high probability. The new protocol operates in the optimal {\em parallel time} $O(\log n),$ which is equivalent to $O(n\log n)$ sequential {\em pairwise interactions}, where each agent utilises the optimal number of $O(\log n)$ states. The time optimality of the new majority protocol is possible thanks to the novel concept of fixed-resolution phase clocks introduced and analysed in this paper. The new phase clock allows to count approximately constant parallel time in population protocols.
| Item Type: | Article |
|---|---|
| Additional Information: | We combined this paper with arXiv:2012.15800 and have a new updated version at arXiv:2106.10201 |
| Uncontrolled Keywords: | cs.DC, cs.DC, cs.DS |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 07 Dec 2020 08:51 |
| Last Modified: | 30 Apr 2022 20:10 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3109201 |
Share
Share
