Rendezvous with constant memory
Rendezvous with constant memory
复制标题
与恒定的记忆相会
DOI：
10.1016/j.tcs.2016.01.025
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
M. Yamashita
中科院分区：
文献类型：
--
作者：
P. Flocchini;N. Santoro;G. Viglietta;M. Yamashita
我们研究的影响，持久存储器上的经典会合问题的两个移动的计算实体，称为机器人，在飞机上。众所周知，如果没有额外的假设，即使系统是半同步的（SSynch），如果实体是不经意的（即没有持久记忆），会合也是不可能的。最近已经表明，如果每个机器人被赋予O（1）位的持久存储器，可以在每个周期中传输O（1）位，并且可以记住（即，可以持久存储）最后接收到的传输，即使系统是异步的（ASynch），会合也是可能的。这个设定太强大了。在本文中，我们以两种不同的方式削弱了这种设置：（1）通过保持O（1）位的持久内存，但删除通信能力，我们称之为有限状态（FState）的设置;（2）通过保持O（1）位的传输能力和记住最后收到的消息，但删除代理记住其先前活动的能力，我们称之为有限通信（FComm）的设置。请注意，尽管它的使用非常不同，但在两种设置中，机器人的持久内存量都是恒定的位数。我们调查的会合问题，在这两个较弱的设置。我们将这两种设置都建模为具有可见光的机器人系统，每个机器人都具有恒定数量的颜色：在FState中，机器人只能看到自己的光，而在FComm中，机器人只能看到其他机器人的光。除其他事项外，我们证明，刚性运动，有限状态机器人可以在SSynch会合，有限通信机器人能够会合，即使在ASynch。所有的证据是建设性的：在每一个设置中，我们提出了一个协议，允许两个机器人在有限的时间内会合。
We study the impact that persistent memory has on the classical rendezvous problem of two mobile computational entities, called robots, in the plane. It is well known that, without additional assumptions, rendezvous is impossible if the entities are oblivious (ie, have no persistent memory) even if the system is semi-synchronous (SSynch). It has been recently shown that rendezvous is possible even if the system is asynchronous (ASynch) if each robot is endowed with O (1) bits of persistent memory, can transmit O (1) bits in each cycle, and can remember (ie, can persistently store) the last received transmission. This setting is overly powerful. In this paper we weaken that setting in two different ways:(1) by maintaining the O (1) bits of persistent memory but removing the communication capabilities, a setting we call finite-state (FState); and (2) by maintaining the ability of transmitting O (1) bits and remembering the last received message, but removing the ability of an agent to remember its previous activities, a setting we call finite-communication (FComm). Note that, even though its use is very different, in both settings, the amount of persistent memory of a robot is a constant number of bits. We investigate the rendezvous problem in these two weaker settings. We model both settings as a system of robots endowed with visible lights, each with a constant number of colors: in FState, a robot can only see its own light, while in FComm a robot can only see the other robot's light. Among other things, we prove that, with rigid movements, finite-state robots can rendezvous in SSynch, and that finite-communication robots are able to rendezvous even in ASynch. All proofs are constructive: in each setting, we present a protocol that allows the two robots to rendezvous in finite time.