论文标题
早期适应趋势：使用被动沟通的自动化信息传播
Early Adapting to Trends: Self-Stabilizing Information Spread using Passive Communication
论文作者
论文摘要
如何在系统中有效，可靠地传播信息是分布式计算中最根本的问题之一。最近，受生物方案的启发，几项工作着重于确定在错误条件下传播信息所需的最小通信资源。在这里，我们研究了Boczkowski，Korman和Natale在[Soda 2017]中提出的自我稳定的位渗透问题。该问题考虑了一个完全连接的n个代理网络，并具有二进制的意见世界，其中一个被称为正确。在任何给定时间，每个代理商都将意见作为其公共产出。人口包含一个来源的代理，知道哪种意见是正确的。该代理人采用了正确的意见，并在整个执行过程中仍然存在。我们考虑了基本的通信模型，在该模型中，每个代理在每个回合中都观察到相对较少的随机选择代理。非源代理人的目标是快速汇聚正确的意见，尽管具有任意的初始配置，即以自动化的方式。一旦人口以正确的意见汇聚，它应该永远存在。受到动物观察和反应他人行为的生物学情景的动机，我们专注于极度约束的被动通信模型，该模型假设当观察另一个代理时，唯一可以提取的信息是该剂的观点。我们证明，可以在n个弹药数中以高概率的n次数量来解决此问题，同时在每个回合中对对数数量的代理进行采样。以前的工作更快地解决了这个问题，并使用较少的样本解决了这一问题，但是他们通过将代理商从其输出意见中发送的消息解开，因此不符合被动通信的框架。此外，这些作品将复杂的递归算法与精制时钟使用，这些算法不太可能被生物实体使用。相比之下，我们提出的算法具有自然的吸引力，因为它基于让代理估计动力学的当前趋势方向，然后适应新兴趋势。
How to efficiently and reliably spread information in a system is one of the most fundamental problems in distributed computing. Recently, inspired by biological scenarios, several works focused on identifying the minimal communication resources necessary to spread information under faulty conditions. Here we study the self-stabilizing bit-dissemination problem, introduced by Boczkowski, Korman, and Natale in [SODA 2017]. The problem considers a fully-connected network of n agents, with a binary world of opinions, one of which is called correct. At any given time, each agent holds an opinion bit as its public output. The population contains a source agent which knows which opinion is correct. This agent adopts the correct opinion and remains with it throughout the execution. We consider the basic PULL model of communication, in which each agent observes relatively few randomly chosen agents in each round. The goal of the non-source agents is to quickly converge on the correct opinion, despite having an arbitrary initial configuration, i.e., in a self-stabilizing manner. Once the population converges on the correct opinion, it should remain with it forever. Motivated by biological scenarios in which animals observe and react to the behavior of others, we focus on the extremely constrained model of passive communication, which assumes that when observing another agent the only information that can be extracted is the opinion bit of that agent. We prove that this problem can be solved in a poly-logarithmic in n number of rounds with high probability, while sampling a logarithmic number of agents at each round. Previous works solved this problem faster and using fewer samples, but they did that by decoupling the messages sent by agents from their output opinion, and hence do not fit the framework of passive communication. Moreover, these works use complex recursive algorithms with refined clocks that are unlikely to be used by biological entities. In contrast, our proposed algorithm has a natural appeal as it is based on letting agents estimate the current tendency direction of the dynamics, and then adapt to the emerging trend.
