论文标题
概率人口协议模型
Probabilistic Population Protocol Models
论文作者
论文摘要
人口协议是一个相对新颖的计算模型，其中非常有限的匿名代理与计算谓词的目标成对相互作用。我们考虑了该模型的概率版本，该版本自然允许考虑容忍不正确输出概率的设置。本论文的主要重点是自信领导人选举的问题，这是对常规领导人选举问题的扩展，最终的领导者可以发现其独特性。拥有自信的领导者允许人口协议确定其计算的收敛性。该模型的这种行为非常有益，并且在以各种方式扩展原始模型时被证明是可行的。 我们表明，概率种群协议的人口相互作用的人口大小数量需要线性，以在所有可触及状态下具有非零的代理分数，从与同一状态的所有试剂的配置开始。这使我们得出一个结论，即即使是模型的概率版本，自信的领导者选举也无法实现。
Population protocols are a relatively novel computational model in which very resource-limited anonymous agents interact in pairs with the goal of computing predicates. We consider the probabilistic version of this model, which naturally allows to consider the setup in which a small probability of an incorrect output is tolerated. The main focus of this thesis is the question of confident leader election, which is an extension of the regular leader election problem with an extra requirement for the eventual leader to detect its uniqueness. Having a confident leader allows the population protocols to determine the convergence of its computations. This behaviour of the model is highly beneficial and was shown to be feasible when the original model is extended in various ways. We show that it takes a linear in terms of the population size number of interactions for a probabilistic population protocol to have a non-zero fraction of agents in all reachable states, starting from a configuration with all agents in the same state. This leads us to a conclusion that confident leader election is out of reach even with the probabilistic version of the model.
