论文标题
无限树的确定性会合
Deterministic Rendezvous in Infinite Trees
论文作者
论文摘要
集合任务需要两个移动代理，从建模为图形的网络的不同节点开始，以在同一节点上满足。代理具有不同的标签，这些标签是集合$ \ {1，\ dots，l \} $的整数。他们可能在不同的时间醒来，并在同步回合中移动。在每个回合中，代理可以保持空闲或移动到相邻节点。我们考虑确定的会合算法。这种算法的时间是自早期特工唤醒之前的回合数。在本文中，我们考虑在无限树中进行会合。我们的主要目的是研究树对聚会时期的影响。 我们首先设计了一种为无定向的普通树工作的集合算法，其时间为$ o（z（d）\ log l）$，其中$ z（d）$是半径$ d $的球的大小，即，从给定节点$ d $的距离最多$ d $。该算法在代理的清醒时间之间进行任意延迟，并且不需要有关参数$ l $或$ d $的任何初始信息。它的缺点是它的复杂性：$ z（d）$在$ d $中的指数为$ d $ d> 2 $ 2 $。我们证明，这种高复杂性是不可避免的：$ω（z（d））$被证明是在无指导的普通树中的会合时间的下限，即使是同时起步，甚至当代理商知道$ l $和$ d $时。然后，我们将注意力转向定向的树木。尽管代理商的醒来时间在任意延迟时，下限$ω（z（d））$仍然保持不变，同时启动会合时间的时间可以大大缩短。我们表明，如果代理商知道$ l $上的多项式上限或$ d $上的线性上限，则可以在时间$ o（d \ log l）$的定向树中完成crendezvous，这是最佳的。如果没有此类知识，我们会设计一种在时间$ O（d ^2+\ log ^2l）$中工作的算法。
The rendezvous task calls for two mobile agents, starting from different nodes of a network modeled as a graph to meet at the same node. Agents have different labels which are integers from a set $\{1,\dots,L\}$. They wake up at possibly different times and move in synchronous rounds. In each round, an agent can either stay idle or move to an adjacent node. We consider deterministic rendezvous algorithms. The time of such an algorithm is the number of rounds since the wakeup of the earlier agent till the meeting. In this paper we consider rendezvous in infinite trees. Our main goal is to study the impact of orientation of a tree on the time of rendezvous. We first design a rendezvous algorithm working for unoriented regular trees, whose time is in $O(z(D) \log L)$, where $z(D)$ is the size of the ball of radius $D$, i.e, the number of nodes at distance at most $D$ from a given node. The algorithm works for arbitrary delay between waking times of agents and does not require any initial information about parameters $L$ or $D$. Its disadvantage is its complexity: $z(D)$ is exponential in $D$ for any degree $d>2$ of the tree. We prove that this high complexity is inevitable: $Ω(z(D))$ turns out to be a lower bound on rendezvous time in unoriented regular trees, even for simultaneous start and even when agents know $L$ and $D$. Then we turn attention to oriented trees. While for arbitrary delay between waking times of agents the lower bound $Ω(z(D))$ still holds, for simultaneous start the time of rendezvous can be dramatically shortened. We show that if agents know either a polynomial upper bound on $L$ or a linear upper bound on $D$, then rendezvous can be accomplished in oriented trees in time $O(D\log L)$, which is optimal. When no such extra knowledge is available, we design an algorithm working in time $O(D^2+\log ^2L)$.
