Book ; Online: Leaderless Population Protocols Decide Double-exponential Thresholds
2022
Abstract: Population protocols are a model of distributed computation in which finite-state agents interact randomly in pairs. A protocol decides for any initial configuration whether it satisfies a fixed property, specified as a predicate on the set of ... ...
Abstract | Population protocols are a model of distributed computation in which finite-state agents interact randomly in pairs. A protocol decides for any initial configuration whether it satisfies a fixed property, specified as a predicate on the set of configurations. The state complexity of a predicate is smallest number of states of any protocol deciding that predicate. For threshold predicates of the form $x\ge k$, with $k$ constant, prior work has shown that they have state complexity $\Theta(\log\log k)$ if the protocol is extended with leaders. For ordinary protocols it is only known to be in $\Omega(\log\log k)\cap \mathcal{O}(\log k)$. We close this remaining gap by showing that it is $\Theta(\log\log k)$ as well, i.e. we construct protocols with $\mathcal{O}(n)$ states deciding $x\ge k$ with $k\ge2^{2^n}$. |
---|---|
Keywords | Computer Science - Distributed ; Parallel ; and Cluster Computing |
Publishing date | 2022-04-05 |
Publishing country | us |
Document type | Book ; Online |
Database | BASE - Bielefeld Academic Search Engine (life sciences selection) |
Full text online
More links
Kategorien
Inter-library loan at ZB MED
Your chosen title can be delivered directly to ZB MED Cologne location if you are registered as a user at ZB MED Cologne.