论文标题
人口协议中的动态大小计数
Dynamic size counting in population protocols
论文作者
论文摘要
人口协议模型描述了一个匿名代理网络，该网络以随机选择的成对异步相互作用。每个代理以相同的初始状态$ S $开始。我们介绍了 *动态尺寸计数 *问题：大约在对手的存在下计算代理的数量，他们在任何时候都可以删除任何数量的代理或在状态$ s $中添加任何数量的新代理。一个有效的解决方案要求，在每个添加/删除事件之后，导致人口大小$ n $，每个代理“快速”计算值$ \ log_2 n $的恒定因素估计值（被称为 *收敛 *时间的速度如何），这是每个代理商的输出，尽可能长时间（ *持有 *持有 *时间 *时间）。由于对手可以去除代理，因此固定时间必然是有限的：即使对手停止改变人口，也不可能 *稳定 *到永远不会改变的输出。 我们首先表明，当且仅当它解决 *固定大小 *人群中估算$ \ log n $的问题时，协议就解决了动态大小计数问题，但在对手可以在任意状态下初始化每个代理，并以相同的融合时间和持有时间初始化每个代理。 We then show a protocol solving the loosely-stabilizing counting problem with the following guarantees: if the population size is $n$, $M$ is the largest initial estimate of $\log n$, and s is the maximum integer initially stored in any field of the agents' memory, we have expected convergence time $O(\log n + \log M)$, expected polynomial holding time, and expected memory usage of $O(\log^2 （s） +（\ log \ log n）^2）$位。被解释为动态大小计数协议，当从总体大小$ n_ {prev} $更改为$ n_ {next} $时，收敛时间为$ o（\ log n_ {next} + \ log \ log \ log \ log n_ {prev}）$。
The population protocol model describes a network of anonymous agents that interact asynchronously in pairs chosen at random. Each agent starts in the same initial state $s$. We introduce the *dynamic size counting* problem: approximately counting the number of agents in the presence of an adversary who at any time can remove any number of agents or add any number of new agents in state $s$. A valid solution requires that after each addition/removal event, resulting in population size $n$, with high probability each agent "quickly" computes the same constant-factor estimate of the value $\log_2 n$ (how quickly is called the *convergence* time), which remains the output of every agent for as long as possible (the *holding* time). Since the adversary can remove agents, the holding time is necessarily finite: even after the adversary stops altering the population, it is impossible to *stabilize* to an output that never again changes. We first show that a protocol solves the dynamic size counting problem if and only if it solves the *loosely-stabilizing counting* problem: that of estimating $\log n$ in a *fixed-size* population, but where the adversary can initialize each agent in an arbitrary state, with the same convergence time and holding time. We then show a protocol solving the loosely-stabilizing counting problem with the following guarantees: if the population size is $n$, $M$ is the largest initial estimate of $\log n$, and s is the maximum integer initially stored in any field of the agents' memory, we have expected convergence time $O(\log n + \log M)$, expected polynomial holding time, and expected memory usage of $O(\log^2 (s) + (\log \log n)^2)$ bits. Interpreted as a dynamic size counting protocol, when changing from population size $n_{prev}$ to $n_{next}$, the convergence time is $O(\log n_{next} + \log \log n_{prev})$.
