Stable leader election in population protocols requires linear time
Stable leader election in population protocols requires linear time
复制标题
DOI：
10.1007/s00446-016-0281-z
复制
发表时间：
2018-08-01
影响因子：
1.3
通讯作者：
Soloveichik, David
中科院分区：
文献类型：
--
作者：
Doty, David;Soloveichik, David
一个种群协议稳定地选出一个领导者，如果对于所有的n，从一个初始配置开始，n个代理每个都处于相同的状态，概率为1，它达到一个配置是正确的（正好一个代理处于一个特殊的领导者状态）和稳定的（每个可达到的配置也有一个单一的代理状态）。我们表明，任何人口协议，稳定地选出一个领导者需要预期的“并行时间”-预期总成对的相互作用，以达到这样一个稳定的配置。我们的研究结果也通知化学自组织的时间复杂性的理解，显示了一个基本的困难，快速产生精确的分子种类的数量。
A population protocol stably elects a leader if, for all n, starting from an initial configuration with n agents each in an identical state, with probability 1 it reaches a configuration that is correct (exactly one agent is in a special leader state ) and stable (every configuration reachable from also has a single agent in state ). We show that any population protocol that stably elects a leader requires expected "parallel time"- expected total pairwise interactions-to reach such a stable configuration. Our result also informs the understanding of the time complexity of chemical self-organization by showing an essential difficulty in generating exact quantities of molecular species quickly.