论文标题
突破$ω（n）$ - 空间障碍：人口协议决定双指数阈值
Breaking through the $Ω(n)$-space barrier: Population Protocols Decide Double-exponential Thresholds
论文作者
论文摘要
人口协议是一个分布式计算的模型，其中有限状态药物成对随机相互作用。协议决定任何初始配置是否满足固定属性，并在配置集上指定为谓词。如果使用$ \ MATHCAL {O}（|φ_n|）$状态，则决定$φ_n$的协议家族是简洁的，其中$φ_n$被编码为无量词的前汉堡公式，并具有二进制系数。 （所有谓词都可以按这种方式来确定。我们通过$ \ Mathcal {o}构建协议（\ log |φ_n|）$状态的某些阈值谓词$φ_n（x）\ leftrightArrow x \ ge k_n $，带有$ k_1，k_1，k_2，k_2，... （换句话说，具有$ \ MATHCAL {O}（n）$的协议确定$ k \ ge 2^{2^n} $的$ x \ ge k $。）这与已知的下限匹配。此外，我们对阈值谓词的建设是第一个不是$ 1 $的意识，它几乎是自动稳定的。
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.
