Breaking through the $Ω(n)$-space barrier: Population Protocols Decide Double-exponential Thresholds
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2022
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911986818744320 |
|---|---|
| author | Czerner, Philipp |
| author_facet | Czerner, Philipp |
| contents | 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. A family of protocols deciding predicates $φ_n$ is succinct if it uses $\mathcal{O}(|φ_n|)$ states, where $φ_n$ is encoded as quantifier-free Presburger formula with coefficients in binary. (All predicates decidable by population protocols can be encoded in this manner.) While it is known that succinct protocols exist for all predicates, it is open whether protocols with $o(|φ_n|)$ states exist for \emph{any} family of predicates $φ_n$. We answer this affirmatively, by constructing protocols with $\mathcal{O}(\log|φ_n|)$ states for some family of threshold predicates $φ_n(x)\Leftrightarrow x\ge k_n$, with $k_1,k_2,...\in\mathbb{N}$. (In other words, protocols with $\mathcal{O}(n)$ states that decide $x\ge k$ for a $k\ge 2^{2^n}$.) This matches a known lower bound. Moreover, our construction for threshold predicates is the first that is not $1$-aware, and it is almost self-stabilising. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2204_02115 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Breaking through the $Ω(n)$-space barrier: Population Protocols Decide Double-exponential Thresholds Czerner, Philipp Distributed, Parallel, and Cluster Computing 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. A family of protocols deciding predicates $φ_n$ is succinct if it uses $\mathcal{O}(|φ_n|)$ states, where $φ_n$ is encoded as quantifier-free Presburger formula with coefficients in binary. (All predicates decidable by population protocols can be encoded in this manner.) While it is known that succinct protocols exist for all predicates, it is open whether protocols with $o(|φ_n|)$ states exist for \emph{any} family of predicates $φ_n$. We answer this affirmatively, by constructing protocols with $\mathcal{O}(\log|φ_n|)$ states for some family of threshold predicates $φ_n(x)\Leftrightarrow x\ge k_n$, with $k_1,k_2,...\in\mathbb{N}$. (In other words, protocols with $\mathcal{O}(n)$ states that decide $x\ge k$ for a $k\ge 2^{2^n}$.) This matches a known lower bound. Moreover, our construction for threshold predicates is the first that is not $1$-aware, and it is almost self-stabilising. |
| title | Breaking through the $Ω(n)$-space barrier: Population Protocols Decide Double-exponential Thresholds |
| topic | Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2204.02115 |