Rendezvous and Election of Mobile Agents: Impact of Sense of Direction
Rendezvous and Election of Mobile Agents: Impact of Sense of Direction
复制标题
移动代理的交会和选择：方向感的影响
DOI：
--
复制
发表时间：
2007
影响因子：
0.5
通讯作者：
N. Santoro
中科院分区：
文献类型：
--
作者：
Lali Barrière;P. Flocchini;P. Fraigniaud;N. Santoro
抽象考虑r个相同的异步移动代理的集合
分散在大小为n的任意匿名网络上。代理
所有节点都执行相同的协议并从一个节点移动到另一个邻居
节点。在每个节点上都有一个白板，代理可以在白板上编写
并从中阅读。代理不知道网络的拓扑。
我们研究了会合的问题(即，让代理人
聚集在同一节点)和选举(即选择领导人
在这些代理中)。这两个问题在计算上是
在这里考察的上下文中的等价物。我们研究的条件是
确定性一般解的存在性，即算法
解决这两个问题，而不考虑网络拓扑和
代理的初始安置。特别是，我们研究了
关于这种解的存在性的边标记法。会合地点和
选举是不可解的(即，不存在确定性的类属
解决方案)如果gcd(r，n)>；1，无论是否
边缘标记具有方向感。另一方面，
如果gcd(r，n)=1，则机器人在
网络创造了可以利用的拓扑不对称性
来解决这些问题。我们证明了这些
如果边标注具有以下意义，则可以利用不对称性
方向，但如果边标签是任意的，则不能。这个
可能性证明是建设性的：我们提出了一个解决方案协议
并证明其正确性。除了其他功能外，该协议还使用
一种基于方向感的动态命名机制
系统的完全匿名性。
Abstract Consider a collection of r identical asynchronous mobile agents
dispersed on an arbitrary anonymous network of size n. The agents
all execute the same protocol and move from node to neighboring
node. At each node there is a whiteboard where the agents can write
and read from. The topology of the network is unknown to the agents.
We examine the problems of rendezvous (i.e., having the agents
gather in the same node) and election (i.e., selecting a leader
among those agents). These two problems are computationally
equivalent in the context examined here. We study conditions for the
existence of deterministic generic solutions, i.e., algorithms that
solve the two problems regardless of the network topology and the
initial placement of the agents. In particular, we study the impact
of edge-labeling on the existence of such solutions. Rendezvous and
election are unsolvable (i.e., there are no deterministic generic
solutions) if gcd(r,n) > 1, regardless of whether or not the
edge-labeling has sense of direction. On the other hand,
if gcd(r,n) = 1 then the initial placement of the robots in
the network creates topological asymmetries that could be exploited
to solve the problems. We prove that these
asymmetries can be exploited if the edge-labeling has sense of
direction, but cannot if the edge-labeling is arbitrary. The
possibility proof is constructive: we present a solution protocol
and prove its correctness. The protocol, among other features, uses
a dynamic naming mechanism based on sense of direction to overcome
the complete anonymity of the system.