Deterministic Rendezvous in Infinite Trees

We consider infinite trees. They can be either unoriented or oriented. An unoriented tree does not have labels of nodes and the port labelings at each node are arbitrary. In oriented trees, one node, called the root, has label $R$, all other nodes do not have labels, and at each node different from $R$ the port 0 is on the simple path toward $R$.

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. An agent makes a move by choosing a port number at its current node. When entering the adjacent node corresponding to the chosen edge the agent learns the port of entry and the degree of this node. We assume that the memory of the agents is unlimited: from the computational point of view they are modeled as Turing machines. We consider deterministic rendezvous algorithms. Both agents execute the same algorithm, each agent starting in its wakeup round. Each agent knows its label which is a parameter of the algorithm but does not know the label of the other agent. The execution time of such an algorithm is the number of rounds since the wakeup of the earlier agent till the meeting. This time depends on values of the initial distance $D$ between the agents and of the size $L$ of the space of labels. These values may be known or unknown to the agents, depending on the scenario. By saying that the time of an algorithm is $f(D,L)$ we mean that this is the worst case time of the execution of this algorithm, over all pairs of starting nodes of agents at distance $D$, over all pairs of agents’ labels from $\{1,\dots,L\}$, and over all possible delays between waking times of agents, if the algorithm works for arbitrary delay.

We first design a rendezvous algorithm working for unoriented regular^***The discussion of the assumption of regularity is deferred to the Conclusion. trees of degree $d\geq 2$. These are infinite trees all of whose nodes have degree $d$. (For $d=2$ this is the infinite line). The time of our algorithm 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$. We prove that this high complexity is inevitable: $\Omega(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 $\Omega(z(D))$ still holds, for simultaneous start the time of rendezvous can be dramatically shortened. Our algorithms for oriented trees do not assume regularity of the tree. 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 in view of [14]. If no such extra knowledge is available, a significant speedup is still possible: in this case we design an algorithm working in time $O(D^{2}+\log^{2}L)$.

The task of rendezvous has been studied in the literature both in the randomized and deterministic settings. Randomized rendezvous is surveyed in [2], cf. also [1, 5]. Deterministic rendezvous in networks is surveyed in [23, 24]. Several authors considered geometric settings (rendezvous in an interval of the real line, e.g., [5, 6], or in the plane, e.g., [3, 8, 11]). Rendezvous of more than two agents, also called gathering, was studied, e.g., in [15, 17, 22].

In the deterministic setting, feasibility and time complexity of synchronous rendezvous in networks is one of the main topics of investigation. Deterministic rendezvous of agents equipped with tokens used to mark nodes was considered, e.g., in [21]. In most of the papers concerning rendezvous in networks, nodes of the network are assumed to be unlabeled and marking nodes by agents is not allowed. In this case, anonymous agents cannot meet in many highly symmetric networks, e.g., in oriented rings. Hence symmetry is usually broken by assigning the agents distinct labels and assuming that each agent knows its own label but not the label of the other agent. Deterministic rendezvous of labeled agents in rings was investigated, e.g., in [14, 19] and in arbitrary graphs in [14, 19, 25]. Gathering many anonymous agents in unlabeled networks was studied in [15]. In this weak scenario, not all initial configurations of agents are possible to gather, and the authors of [15] characterized all such configurations and provided universal gathering algorithms for them. In [10], the authors studied rendezvous under a very strong assumption that each agent has a map of the network and knows its position in it. Using this assumption they designed optimal algorithms for several classes of networks, including the infinite line and finite trees.

Another measure of efficiency of rendezvous algorithms is the amount of memory needed to execute this task. Memory of the agents required to achieve deterministic rendezvous was studied in [18] for trees and in [12] for arbitrary graphs. Memory needed for randomized rendezvous in the ring was investigated, e.g., in [20].

A scenario significantly differing from the above was discussed by several authors. The difference is in dropping the assumption that agents navigate in synchronous rounds. Asynchronous rendezvous and approach in the plane was studied in [7, 9, 17] and asynchronous rendezvous in networks modeled as graphs was investigated in [4, 13, 16]. In the latter scenario, the agent chooses the edge to traverse, but the adversary controls the speed of the agent. Under this assumption, rendezvous at a node cannot be guaranteed even in the two-node graph. Hence the rendezvous requirement is relaxed to permit the agents to meet inside an edge. In [4], the authors designed almost optimal algorithms for asynchronous rendezvous in infinite multidimensional grids, under a strong assumption that the agent knows its position in the grid. In [16], the authors designed a polynomial-cost algorithm for asynchronous rendezvous in arbitrary finite graphs, without this assumption.

For any node $v$ and any positive integer $r$, we define the following procedures.

Procedure $ACT(v,r)$

Explore the ball $B(v,r)$ by DFS, in increasing order of port numbers at each node,
         starting and finishing at node $v$.

Procedure $PASS(v,t)$

Stay at node $v$ for $t$ rounds.

The following procedure takes as parameters the degree $d$ of the infinite regular tree, a bit $b$ of the transformed label, and a positive integer $i$. For $d=2$, i.e., for the infinite line, and for any integer $i\geq 0$, the procedure consists of two DFS explorations of the ball $B(v,2^{2i})$, if the bit $b$ is 1, and of staying at node $v$ for the duration of these two explorations, if the bit $b$ is 0. (Exploration of a ball of radius 0 takes time 0.) For $d>2$, the procedure consists of two DFS explorations of the ball $B(v,2i)$, if the bit $b$ is 1, and of staying at node $v$ for the duration of these two explorations, if the bit $b$ is 0.

Procedure $Exec(d,b,i)$

if $d=2$ then $r_{i}=2^{2i}$
         else $r_{i}=2i$
         if $b=1$ then
                 $ACT(v,r_{i})$
                 $ACT(v,r_{i})$
         else
                 $PASS(v,2a(r_{i}))$

We first present the high-level idea of the rendezvous algorithm and its challenges. The algorithm exploits the fact that agents have different labels and guarantees that at some point one of the agents stays idle at its starting node while the other one fully explores a sufficiently large ball centered at its own starting node and thus meets the waiting agent. Exploration and waiting periods depend on bits of the transformed label of the agent. Since agents do not know the distance between them, the algorithm is divided into stages with increasing radii of explored balls and increasing waiting times. The main challenge is due to the fact that agents may start with some delay and that, due to possibly different label lengths, they complete the same stage at different speeds. Hence the whole process may become significantly desynchronized and the difficulty is to hold one agent idle at its starting node for a sufficiently long time to allow the other agent to meet it.

Now we are ready to succinctly describe Algorithm URT (for unoriented regular trees). The algorithm is executed by an agent with label $\ell$, starting at a node $v$ of an infinite regular tree of degree $d$. The algorithm works in stages $i=0,1,2,\dots$. In a stage $i$ it “executes” consecutive bits $b_{j}$ of $Trans(\ell)$ by performing procedure $Exec(d,b_{j},i)$. Notice that for $d=2$, $Exec(d,b_{j},i)$ explores balls $B(v,2^{2i})$ if $b_{j}=1$ and instructs the agent to wait a corresponding time if $b_{j}=0$, while for $d>2$, $Exec(d,b_{j},i)$ explores balls $B(v,2i)$ if $b_{j}=1$ and instructs the agent to wait a corresponding time if $b_{j}=0$. This is because for $d=2$ the size of a ball is linear in its radius, while for $d>2$ it is exponential in it. Stages are organized so that their durations telescope. For technical reasons we want the size of the balls treated in stage $i+1$ to be at least 4 times larger (and not only 2 times larger) than those in stage $i$. The algorithm is interrupted as soon as the agents meet.

Algorithm URT

$Trans(\ell):=(b_{1},b_{2},\dots,b_{k})$
         for $i=0,1,2,\dots$ do
                 for $j=1$ to $k$ do
                          $Exec(d,b_{j},i)$

In this section we prove the correctness of Algorithm URT and analyze its time complexity. We start with the definition of the critical stage. Intuitively, it is the first stage such that the radius $r_{i}$ of the balls explored in this stage is at least the initial distance $D$ between the agents. Thus, more formally, the critical stage is the smallest integer $i$ such that:

• •

  $D\leq 2^{2i}$, if $d=2$

• •

  $D\leq 2i$, if $d>2$.

This smallest integer $i$ is denoted by $i^{*}$. Hence $r_{i^{*}}$ is the radius of balls explored in the critical stage.

According to the algorithm, during an execution of bit $1$ in stage $i$, an agent explores a ball of radius $r_{i}$ twice. We refer to each of these explorations as one activity cycle. Thus, during an execution of a single bit $1$, an agent performs two activity cycles. Similarly, during an execution of a bit $0$ in stage $i$, an agent waits for two consecutive periods each of duration of one such exploration. We refer to each of these waiting periods as one passivity cycle. Thus, during an execution of a single bit $0$, an agent waits for two passivity cycles.

For a given $d$, let $\pi_{i}=2a(r_{i})$ be the duration of the execution of a bit in stage $i$, using procedure $Exec(d,b,i)$. Let $y$ be the length of the transformed label of an agent. Let $S_{i}=y\pi_{i}$ denote the duration of stage $i$. The time $\alpha$ taken by the agent to reach its critical stage is the sum of durations of all previous stages. Thus this time is $\sum_{i=0}^{i^{*}-1}S_{i}$.

In the following lemma we compute the duration $S_{i}$ of stage $i$, depending on $d$ and $y$.

Proof. First consider the case when $d=2$. In stage $i$, an agent explores a ball of radius $r_{i}=2^{2i}$. We first compute $z(r_{i})$, the number of nodes in the ball of radius $r_{i}$. Since in this case the graph is a line, $z(r_{i})=2\cdot 2^{2i}+1$. Recall that, $a(r_{i})=2(z(r_{i})-1)$ is the number of edge traversals of a DFS exploration of the ball $B(v,r_{i})$, starting and finishing at the same node. Thus, $a(r_{i})=2\cdot 2\cdot 2^{2i}$. By definition, $\pi_{i}=2a(r_{i})$ i.e., $\pi_{i}=8\cdot 4^{i}$. Hence, $S_{i}=8y4^{i}$.

Next suppose $d\geq 3$. In this case, in stage $i$, an agent explores a ball of radius $r_{i}=2i$. The value of $z(r_{i})$ is as follows:

Thus, in this case, $a(r_{i})=2d\frac{(d-1)^{2i}-1}{d-2}$ and $\pi_{i}=4d\frac{(d-1)^{2i}-1}{d-2}$. Hence, $S_{i}=y4d\frac{(d-1)^{2i}-1}{d-2}$. $\Box$

Proof. When $d=2$, by Lemma 2.1, we have

Next suppose $d\geq 3$. In this case, by Lemma 2.1, we have,

$\Box$

The next lemma estimates the duration of any stage in terms of the duration of the preceding and of the following stage.

Proof. We consider two cases:

• •

  $\boldsymbol{d=2}$ In this case, by Lemma 2.2, $S_{i+p}=4S_{i+p-1}<5S_{i+p-1}$.

• •

  $\boldsymbol{d\geq 3}$ By Lemma 2.2, we have $S_{i+p}=(d-1)^{2}S_{i+p-1}+S_{1}$. This implies $S_{i+p}>(d-1)^{2}S_{i+p-1}$. Since $d\geq 3$, we can conclude that $4S_{i+p-1}\leq S_{i+p}$. Finally consider the following:

  		$\displaystyle S_{i+p-1}$	$\displaystyle=(d-1)^{2i+2p-4}S_{1}+S_{i+p-2}$
  		$\displaystyle(d-1)^{2}S_{i+p-1}$	$\displaystyle\geq(d-1)^{2i+2p-2}S_{1}$		(1)

  Again, we have

  		$\displaystyle S_{i+p}$	$\displaystyle=(d-1)^{2i+2p-2}S_{1}+S_{i+p-1}$
  		$\displaystyle S_{i+p}$	$\displaystyle\leq(d-1)^{2}S_{i+p-1}+S_{i+p-1}\qquad(\text{by (1)})$
  		$\displaystyle S_{i+p}$	$\displaystyle\leq((d-1)^{2}+1)S_{i+p-1}$		(2)

  Since $d\geq 3$, (2) implies $S_{i+p}\leq 5S_{i+p-1}$. This concludes the proof.

$\Box$

Lemma 2.3 implies

In the next lemma we compute the value $\alpha$ of the time taken by an agent to reach its critical stage.

Proof. When $d=2$, we have

Suppose $d\geq 3$. Then we have

$\Box$

Since $\frac{1}{(d-1)^{2}-1}\leq\frac{1}{3}$ for $d\geq 3$, Lemmas 2.1 and 2.4 imply

Denote by $A_{1}$ the agent that starts earlier, and by $A_{2}$ the agent that starts later. (In the case of simultaneous start, names $A_{1}$ and $A_{2}$ are given arbitrarily). Let $\delta\geq 0$ denote the delay of the start of $A_{2}$ w.r.t the start of $A_{1}$.

The next lemma shows that if the delay is sufficiently large then agents meet during the critical stage of the earlier agent.

Proof. Agent $A_{1}$ takes time $\alpha$ to reach its critical stage. Since each transformed label starts with bits 01, during its critical stage agent $A_{1}$ first executes two consecutive passivity cycles, i.e., for a time $2a(r_{i}^{*})$ it does not moves and then it starts executing its two consecutive activity cycles and each activity cycle takes time $a(r_{i}^{*})$. Hence, in time at most $\alpha+3a(r_{i}^{*})$ since its start agent $A_{1}$ reaches the node initially occupied by agent $A_{2}$. Thus, if $\delta\geq\alpha+3a(r_{i}^{*})$, i.e., if agent $A_{2}$ remains inactive till that time, agent $A_{1}$ meets $A_{2}$ at its initial position. This happens during the critical stage of $A_{1}$. $\Box$