Optimal Deterministic Rendezvous in Labeled Lines

To get some intuition on how rendezvous algorithms typically work, it is instructive to consider one of the simplest variants of the problem: the asymmetric setting with simultaneous startup. Asymmetry means that each agent can execute its own strategy, or equivalently, one agent receives label $1$ while the other receives label $2$. Simultaneous startup means that the two agents wake up in the same round.

These assumptions allow for the following strategy: one agent goes through successive phases exploring increasingly bigger intervals centered on its initial node, while the other agent waits at its initial node. Having the active agent explore intervals doubling in size between phases, the strategy achieves rendezvous in $O(D)$ rounds, which is optimal up to the hidden constant and lower order terms. Rendezvous reduces to treasure hunt in that scenario.

While this algorithm cannot be used as is in harder settings, our goal will be to somehow reduce to this simple strategy. In the symmetric setting but with access to randomness, for example, the agents can flip coins to decide whether to search or stay put during some time intervals. In all likelihood, the agents should regularly sample opposite roles. Similarly, if the agents are given distinct labels (but importantly, not restricted to the set $\{1,2\}$), distinct behaviors can still be constructed from the given identifiers. The agents might for example alternate searching and inactive phases according to the binary representations of their labels. More generally, we need the agents to break symmetry between themselves, so that at some point during the execution, one of the two agents does a search while the other agent stays idle. Given that one agent’s idle phase overlaps sufficiently with the other agent’s searching phase, the two agents will achieve rendezvous.

Having the agents know the initial distance $D$ between them drastically reduces the space of possibilities. For instance, from the perspective of either agent, there are only two possibilities for the starting location of the other agent: the two nodes at distance exactly $D$ from its own initial node. If each agent spends its first $3D$ rounds to go to these two nodes, the first awake agent always finds the other agent in these $3D$ rounds, granted that the delay $\tau$ between the agents’ wake-up times is at least $3D$. Not meeting the other agent in these initial $3D$ rounds thus immediately implies a bound on the delay, .

On the infinite labeled line, consider now the subset of nodes whose distances to the starting location of one of the agents are divisible by $D$. The resulting set of nodes is the same whether we measure the distances from either of the two starting locations, as well as contains them. Connecting each member of this set to the two other members closest to it on the original line, we obtain another infinite labeled line. A possible strategy for the two agents to break symmetry is to agree on a coloring of this sub-line, and to act according to the colors of their starting nodes. As the agents perform searching phases interspersed with waiting phases according to these colors, knowing $D$ allows the agents to limit their phases to intervals of $O(D)$ rounds.

Without additional assumptions, the agents cannot truly agree on a coloring of the whole sub-line. Indeed, the agents can only base the coloring of the sub-line on the labels of the nodes of the infinite line. In order for the agents to be able to compute the color of a node, said color should only depend on a finite set of labels. As the agents cannot explore more than $T$ nodes in $T$ rounds, for the sake of speed, the colors given to the agents’ starting nodes should ideally be computable from labels in relative proximity to them.

At a high level, we want a mapping from some universe of possible local neighborhoods to colors, such that if applying this mapping to the infinite line, a valid coloring is obtained. This idea of constructing a mapping between local neighborhoods and a node’s local output almost corresponds to the LOCAL model of distributed computing. A key difference, however, is that the standard LOCAL model assumes a finite graph.

Still, it is easy to adapt a seminal LOCAL algorithm for $3$-coloring paths and cycles to obtain a useful mapping. To do so, the algorithm is transformed into an early-stopping one, which has nodes terminate earlier depending on their given labels. While the classic LOCAL algorithm for $3$-coloring paths and cycles completes in $O({\log }^{\ast }n)$ rounds, assuming that the nodes are given unique identifiers between $1$ and $\mathrm{poly}(n)$, the early-stopping version instead guarantees that a node $v$ of label $\mathrm{\ell }(v)$ permanently commits to a color after $O({\log }^{\ast }\mathrm{\ell }(v))$ rounds. From the point of view of mapping local views to colors, this means that there exists a mapping that infers the color of a node of label $\mathrm{\ell }(v)$ from its distance-$O({\log }^{\ast }\mathrm{\ell }(v))$-neighborhood. Used on the infinite sub-line obtained by taking one out of every $D$ nodes, this allows the two agents to assign distinct colors to their starting nodes after $O(D{\log }^{\ast }{\mathrm{\ell }}_{\max })$ rounds of exploration, where ${\mathrm{\ell }}_{\max }$ is the largest of the starting locations’ labels. This roughly summarizes the approach of Miller and Pelc [18].

The approach sketched in previous paragraphs is very dependent on the assumption that the agents have knowledge of $D$, as it has the agents essentially ignore all but a specific $1/D$ fraction of the line. If the agents run the same algorithm with a wrong “guess” for $D$, the two agents are effectively not synchronizing in any way, as the sub-lines they each construct are only the same if the agents’ guess for $D$ is a divisor of the actual distance $D$. Even when their guess divides $D$, the agents’ starting nodes are only adjacent in the sub-line if the guess is exactly $D$.

As a result, to tackle the setting without knowledge of $D$ by using the previous algorithm with different guesses for $D$ basically requires to test every possible value for $D$. This is true even if the agents are given an upper bound on $D$. This difficulty is the source of the $O(D^2)$ dependency in the earlier algorithm by Miller and Pelc [18].

For simplicity, let us assume for now that the agents are given an upper bound on $D$. In the paper, we will see that handling a fully unknown $D$ can be handled relatively easily by essentially considering geometrically increasing bounds on $D$. As a first try, let us aim for the agents to agree on a common coloring of the line that ensures that their starting locations receive distinct colors.

With only an upper bound on $D$, the agents now need to break symmetry with $2D$ nodes instead of just $2$. Guaranteeing that any two nodes within distance $D$ from one another are colored differently cannot be done with $3$ colors. Pushing forward with this approach, one could color the line with $O(D)$ colors. But now, the increased number of colors necessitates to design the same number of distinct behaviors of alternating searching and waiting phases guaranteeing rendezvous. This higher number of behaviors is likely to lead to a $D\log D$ dependency in the distance, similar to how in anonymous networks with labeled agents, larger labels lead to higher complexity in this fashion²²2For instance, with $\mathrm{\ell }$ the smallest of the two agents’ labels, $D$ their initial distance, and simultaneous startup, the complexity of rendezvous is $\mathrm{\Theta }(D\log \mathrm{\ell })$ in the anonymous ring [8].. This would be far from the $\mathrm{\Omega }(D{\log }^{\ast }\mathrm{\ell })$ lower bound.

To reduce the number of behaviors we have to design, and thus, improve on the complexity that would follow from an approach based on computing a distance-$D$ coloring, we have the agents agree on a $1/\mathrm{\Theta }(D)$ fraction of the nodes that act as common milestones, or landmarks. One way to understand our algorithm is that we have the agents build their common sparse sub-line instead of receiving it from the get-go as when they know $D$. Formally, the agents compute a ruling set over the line: a set of nodes such that every two of its members are at least at some minimum distance $\mathrm{\Theta }(D)$ from one another, and every node in the graph is within some maximum distance $\mathrm{\Theta }(D)$ from the nearest member. Computation of this ruling set by the agents corresponds, again, to a computation in the early-stopping LOCAL model.

To achieve rendezvous, each agent effectively substitutes its starting position with the nearest node on the sub-line. By having the agents agree on a common coloring of this sub-line, as before, the agents can now find each other by performing some waiting and searching phases based on the colors of their location in the sub-line. Even if our new sub-line is less structured than the one considered in the setting with knowledge of $D$, its properties are sufficient to be able to give distinct colors to members of the sub-line at distance $O(D)$ in the original line, while only using $O(1)$ colors.

Computing the ruling set we need in the early-stopping LOCAL model follows relatively straightforwardly from standard results in distributed computing. We perform this computation by repeated applications of an algorithm for Maximal Independent Set (MIS). At a high level, we start from a set containing all nodes of the lines and gradually remove nodes from it. Each call to the MIS subroutine roughly doubles the minimum distance between members of the set, while maintaining that the maximum distance of any node on the graph to the nearest member of the set increases only moderately. A small subtlety is that we have each node mostly coordinate with other nodes whose labels are of the same order of magnitude.

Contributing to the overall simplicity of our algorithm is a subroutine for crossing edges that prevents the agents from exchanging positions on the line without achieving rendezvous. The idea behind it is very simple: on the labeled line, every edge can be given a canonical orientation, for example, from lower to higher ID. By having the agents perform a different set of moves to cross an edge depending on the direction in which they take it, we can make sure that the agents must be at the same node at some point during the crossing. The first few moves are the same for both orientations of the edge, which enables an agent to discover the orientation of the edge while crossing it – e.g., on the labeled line, through learning the identifier of the other endpoint. Replacing every one-round edge crossing by this procedure only incurs a multiplicative factor of $4$ in the complexity of the algorithm. We believe that this observation might be useful to the design of future rendezvous algorithms on graphs whose edges can easily be given an orientation.

We write $G=(V,E)$ for a graph over vertices $V$ and edges $E$. Each node $v\in V$ is equipped with a unique label or identifier $\mathrm{\ell }(v)\in ℒ$. We identify the set of labels with the positive integers, $ℒ={\mathbb{N}}^{\ast }$. We partition the nodes according to their labels and the ${\log }^{\ast }$ function, defining $V_i=\{v\in V:{\log }^{\ast }(\mathrm{\ell }(v))=i\}$, so that $V={⨆}_{i\ge 1}{V}_i$. We also define $V_{\le i}={⨆}_{j=1}^i{V}_j$ and . The degree of a node $v\in V$ is denoted by $\mathrm{deg}(v)$, the distance $\mathrm{dist}(v,v^{\prime })$ between two nodes corresponds to the (edge-)length of a shortest path between them, and $N(v)$ is the set of neighbors of $v$. For every integer $k$, $N^k(v)=\{u\in V:\mathrm{dist}(u,v)\in [1,k]\}$ is the $k$-hop neighborhood of $v$.

For $U\subseteq V$ a subset of the nodes of a graph $G=(V,E)$, the graph $G[U]=(U,E^{\prime })$ is the graph induced by $U$, whose set of nodes is $U$ and whose set of edges is $E^{\prime }=\{v{v}^{\prime }\in E:v\in U\wedge v^{\prime }\in U\}$. For a positive integer $k\ge 1$, the power graph of order $k$ is the graph $G^k=(V,E^{\prime \prime })$ with the same set of nodes as $G$ and whose set of edges is $E^{\prime \prime }=\{v{v}^{\prime }:{\mathrm{dist}}_G(v,v^{\prime })\in [1,k]\}$. Note that $G^k[U]=(G^k)[U]$ rather than ${(G[U])}^k$, i.e., $G^k[U]$ is an induced subgraph of a power graph of $G$, rather than a power graph of an induced subgraph of $G$.

An infinite labeled line is a $2$-regular connected graph $G=(V,E)$ over a countably infinite set of nodes.

For the analysis’ sake, it is sometimes convenient to consider a canonical orientation and naming for the line. When we do so, we refer to nodes on the infinite line as relative integers, s.t. for any $i\in \mathbb{Z}$, node $v_i$ is adjacent to nodes $v_{i-1}$ and $v_{i+1}$ on the line.

The agents are placed and move in a network modeled by a graph $G=(V,E)$. $G$ can be finite or countably infinite. Each node $v\in V$ of the graph has $\mathrm{deg}(v)$ ports, and each edge is the graph is matched to exactly one port of each of its two endpoints. The ports of a node $v$ are labeled $0$ to $\mathrm{deg}(v)-1$. At a node $v$, an agent can read the node’s label $\mathrm{\ell }(v)$ if the graph is labeled, see the node’s degree $\mathrm{deg}(v)$, and distinguish the $\mathrm{deg}(v)$ ports leading out of the node.

The agents execute the same deterministic algorithm, as in, when put in the same configuration, agents $\alpha$ and $\beta$ perform the same set of moves. Time is divided into discrete rounds. The agents are initially asleep, and upon wake-up (or startup), they have no notion of how much time has elapsed before. Formally, the agents have an internal clock that is initialized at $0$ upon waking-up, and from there on keeps track of how many rounds passed since wake-up. We denote by $\tau$ the delay between the wake-up times of the two agents. The agents can be thought of as waking up in rounds $0$ and $\tau$. The initial distance between the two agents is denoted by $D$.

In each round, an awake agent at a node $v$ chooses one of $\mathrm{deg}(v)+1$ possible moves. One of these moves is staying at $v$ for one round, the other moves being to take one of the ports leading out of $v$. When an agent takes a port, in the next round, it arrives at the other endpoint of the edge behind that port. When entering a node, an agent knows the port it enters it from. We put no limit on the memory of the agents, and they can base each of their decisions on everything they have experienced in previous rounds: the labels of all the nodes they were at in previous rounds, and from which port they were all entered from.

The agents can detect each other if they are at the same node in the same round, in which case they achieve rendezvous. This is also the case if one of the agents is asleep, i.e., agents exist in the network before waking up. They have no other means of communication. By default, the agents do not detect each other if they cross the same edge in opposite directions in the same round. We consider agents able to detect simultaneous edge-crossing in some parts of the paper.

The agents have no shared notion of orientation of the line, no idea of their position on the line with respect to some shared point of origin, and have no knowledge of both $D$ and $\tau$.

The standard LOCAL model is a model of distributed computation in which a network is represented as a graph $G=(V,E)$ whose nodes possess computational power. Every node has a unique identifier, typically assumed to be an integer between $1$ and $\mathrm{poly}(n)$, where $n$ is the number of nodes in the graph. The time is measured in rounds, in which a node can receive the messages sent by its neighbors in the previous round, do some internal computation, and send a message to each of its neighbors for them to receive in the next round. Computation starts at the same time for all nodes and is done synchronously. An algorithm’s complexity on instances of size $n$ is the maximum number of rounds before all nodes in the graph have terminated executing the algorithm and permanently committed to an output. The complexity of a problem on instances of size $n$ is the minimum complexity over all possible algorithms solving the problem over instances of size $n$. Messages sent in the LOCAL model can be arbitrarily large. As a result, without loss of generality, each node learns its entire $T$-hop neighborhood in $T$ rounds of LOCAL. This makes a $T$-round algorithm for a problem in the LOCAL model equivalent to a map from possible $T$-hop neighborhoods to possible node outputs.

In infinite graphs, it is nonsensical to consider the complexity of most problems as the time needed for the last node to terminate. The complexity also cannot be measured with respect to the number of nodes or the value of the largest identifier. To tame the infinite, we instead aim to bound the time it takes a node to finish with respect to some local parameters, for example, its identifier. To have nodes terminate at different times, the problems we consider must be inherently quite local. We refer to this model, where nodes commit to an output in a time that is a function of a local parameter, and thus algorithms make sense on both finite and infinite graphs, as the EarlyStop-LOCAL model (ES-LOCAL for short). This model was also used in the work by Miller and Pelc [18] and appeared previously in other sources [11, Exercise 1.7].

To prove Theorem 1, we first bound in Section 4.3 how out-of-sync the two agents can be without trivially achieving rendezvous. Knowing that a delay $\tau$ that exceeds some threshold $\mathrm{\Theta }(D)$ necessarily implies that the agents achieve rendezvous in $O(D)$ rounds, the rest of the analysis can assume some degree of synchronization between the agents.

We then argue that as the agents reach a large enough value of $L$ (of order $\mathrm{\Theta }(D{\log }^{\ast }{\mathrm{\ell }}_{\min })$) in their executions of Algorithm 5, they compute nodes from colored ruling sets parameterized by distances of order at least $\mathrm{\Omega }(D)$. When using such ruling set nodes in their executions of SearchingWalk (Algorithm 6), the agents can achieve rendezvous in two different ways. If the two agents have computed nodes from distinct ruling sets (i.e., the distance parameters of their ruling sets do not match), the agent with the larger distance is guaranteed to find the other agent. This follows from the agent with the smaller distance parameter being constrained to some interval on the line, which we show gets fully explored by the agent with the larger parameter. We show this in Section 4.4.1. The analysis for when the two agents computed nodes from the same ruling set (i.e., with the same distance parameter) is in Section 4.4.2. There, we argue that rendezvous is easily achieved if the two agents decided to go to the same node of the ruling set, and if not, they find each other from the fact that they perform SearchingWalk from nodes that are both close enough to one another, and are colored with distinct colors. The various arguments are put together in Section 4.5.

We use the following notation:

• $\mathrm{■}$

  For each $L\in \{2^i\mid i\in \mathbb{N}\}$, $T_{\alpha ,L}$ is the round in which agent $\alpha$ starts its discovery phase with parameter $L$ (line $3$ in Algorithm 5). $T_{\beta ,L}$ is the equivalent for agent $\beta$.

• $\mathrm{■}$

  $T_{\mathrm{𝗋𝖽𝗏}}\in \mathbb{N}\cup \{\mathrm{\infty }\}$ is the round in which the agents first achieve rendezvous ($\mathrm{\infty }$ if the agents never do so).

• $\mathrm{■}$

  As previously in the paper, we identify the infinite line with the relative integers. For each $t\in \mathbb{N}$, let $x(t)$ (resp. $y(t)$) be the position of agent $\alpha$ (resp. $\beta$) in round $t$. We assume $\alpha$ to be the first agent to wake up, so that $y(t)=y(0)=v_{\beta }$ for all $t\le \tau$.

• $\mathrm{■}$

  For each $L\in \{2^i\mid i\in \mathbb{N}\}$, let $R_{\alpha ,L}\in (\{4^i\mid i\in \mathbb{N}\}\cap [1,L/16])\cup \{\perp \}$ be the value of $R^{\ast }$ for agent $\alpha$ for the loop iteration of parameter $L$. $R_{\beta ,L}$ represents the same quantity for $\beta$, and the value $\perp$ represents the fact that no valid $R^{\ast }$ was found for this loop iteration.

A useful remark about our algorithm is that the discovery and searching phases of our agents have fixed runtimes.

The loop iteration of Algorithm 5 with a given value of $L$ takes $28L$ rounds. Indeed, the discovery phase is a ZWalk of parameter $L$, taking $4L$ rounds. Whether some $R^{\ast }=4^j$ is found such that $\exists u\in N^{R^{\ast }}(v_{\alpha }),N^{{\kappa }_{\text{<a href="\#alg3" title="Algorithm 3 ‣ 3.3 Computing Colored Ruling Sets on Paths, and Stopping Early ‣ 3 Our Main Methods ‣ Optimal Deterministic Rendezvous in Labeled Lines" class="ltx\_ref ltx\_font\_italic" style="font-size:50\%;"><span class="ltx\_text ltx\_ref\_tag">3</span></a>}}{R}^{\ast }{\log }^{\ast }(u)}(u)\subseteq N^L(v_{\alpha })$ or not, the rest of the loop always takes $24L$ rounds. Either these rounds are spent waiting at $v_{\alpha }$, or they are spent executing SearchingWalk (Algorithm 6). SearchingWalk has this complexity that is a function of $L$ only because each of its actions whose runtime increases with $R$ is compensated by a waiting period whose time decreases with $R$ by the exact same amount. $2\times L$ rounds are spent traveling and waiting between $v_{\alpha }$ and $r$, and $11\times 2L$ are spent in $11$ calls to $\text{ZWalk}(8R)$ and/or waiting periods, for a total of $24L$ rounds.

The results follow from the just established formulas $T_{\alpha ,2L}=T_{\alpha ,L}+28L$ and $T_{\beta ,2L}=T_{\beta ,L}+28L$, together with the base case $T_{\beta ,1}=T_{\alpha ,1}+\tau$. $◀$

For the first inequality, first note that by definition $x(T_{\alpha ,L})=x(0)=v_{\alpha }$ since the agent always returns at $v_{\alpha }$ before starting a new loop iteration. This immediately implies that $|x(t)-x(0)|\le L/2$ for $t\in [T_{\alpha ,L},T_{\alpha ,L}+L/2]$, as agents can only cross one edge per round. For smaller $t$ ($t\in [0,T_{\alpha ,L}]$, let us consider the movements done in loop iterations for smaller values of $L$. As an agent executes a ZWalk with some parameter $d$, it stays at distance $\le d$ from the node where it started its execution. As a results, all calls to ZWalk as part of previous discovery phases have kept the agent at distance $\le L/2$ from $x(0)=v_{\alpha }$. As for the movements done in the searching phase, the agent moves at distance at most from $v_{\alpha }$. Indeed, at most $2R^{\ast }-1$ are done to go to a nearby ruling set node, from which ZWalk is called with parameter $8R^{\ast }$, and $R^{\ast }\le L/16$.

The second item simply follows from the fact that a ZWalk of parameter $L$ consists of going $L$ steps away from the starting position, then taking $2L$ steps in the other direction. Therefore, either $x(T_{\alpha ,L}+L)=v_{\alpha }-L$ and $x(T_{\alpha ,L}+3L)=v_{\alpha }+L$, or $x(T_{\alpha ,L}+L)=v_{\alpha }+L$ and $x(T_{\alpha ,L}+3L)=v_{\alpha }-L$. In either case, the entire interval $[v_{\alpha }-L,v_{\alpha }+L]$ is swept. $◀$

Note that $L\in [2D,4D-1]$. If $\tau \ge 5L/2$, then for all $t\le T_{\alpha ,L}+3L\le T_{\alpha ,L}+\tau +L/2=T_{\beta ,L}+L/2$, $|y(t)-v_{\beta }|\le L/2$ by Proposition 10. Because $|v_{\alpha }-v_{\beta }|=D$, this also implies that $|y(t)-v_{\alpha }|\le D+L/2\le L$ for all $t\le T_{\alpha ,L}+3L$. Since $\alpha$ explores the entire distance-$L$ neighborhood of $v_{\alpha }$ between $T_{\alpha ,L}+L$ and $T_{\alpha ,L}+3L$ by Proposition 10, the two agents achieve rendezvous before round $T_{\alpha ,L}+3L$ by Proposition 5. $◀$

Let $v_{\min }\in N^D(v_{\alpha })\cup N^D(v_{\beta })$ be the node s.t. $\mathrm{\ell }(v_{\min })={\mathrm{\ell }}_{\min }$ and $R_D=4^{\lceil {\log }_4(2D)\rceil }$. Note that , $\mathrm{dist}(v_{\min },v_{\alpha })\le 2D\le R_D$, and $\mathrm{dist}(v_{\min },v_{\beta })\le 2D\le R_D$.

Consider lines 5 and 6 in Algorithm 5. $R_{\alpha ,L}$ is the largest value that satisfies the following three properties: $R_{\alpha ,L}$ is a power of $4$, $R_{\alpha ,L}\le L/16$, and agent $\alpha$ has discovered enough of the line in its discovery phase of parameter $L$ to compute the output of at least one node within distance $R_{\alpha ,L}$ from $v_{\alpha }$ in an execution of $\text{ES-ColPathRulingSet}(R_{\alpha ,L})$. $R_{\beta ,L}$ is defined similarly for agent $\beta$. We show that all these properties hold for $R_D=4^{\lceil {\log }_4(2D)\rceil }$ with the lower bound on $L$ given as hypothesis, which implies the lemma.

$R_D$ is a power of $4$ by definition. Also, since $L\ge 128D$ and , we have $R_D\le L/16$. Node $v_{\min }$ is at distance at most $2D\le R_D$ from $v_{\alpha }$. Finally, consider the distance-$({\kappa }_{\text{<a href="\#alg3" title="Algorithm 3 ‣ 3.3 Computing Colored Ruling Sets on Paths, and Stopping Early ‣ 3 Our Main Methods ‣ Optimal Deterministic Rendezvous in Labeled Lines" class="ltx\_ref ltx\_font\_italic" style="font-size:70\%;"><span class="ltx\_text ltx\_ref\_tag">3</span></a>}}{R}_D{\log }^{\ast }{\mathrm{\ell }}_{\min })$ neighborhood of $v_{\min }$. From the bound on the distance between $v_{\min }$ and $v_{\alpha }$, and , it holds that $N^{{\kappa }_{\text{<a href="\#alg3" title="Algorithm 3 ‣ 3.3 Computing Colored Ruling Sets on Paths, and Stopping Early ‣ 3 Our Main Methods ‣ Optimal Deterministic Rendezvous in Labeled Lines" class="ltx\_ref ltx\_font\_italic" style="font-size:50\%;"><span class="ltx\_text ltx\_ref\_tag">3</span></a>}}{R}_D{\log }^{\ast }{\mathrm{\ell }}_{\min }}(v_{\min })\subseteq N^{8{\kappa }_{\text{<a href="\#alg3" title="Algorithm 3 ‣ 3.3 Computing Colored Ruling Sets on Paths, and Stopping Early ‣ 3 Our Main Methods ‣ Optimal Deterministic Rendezvous in Labeled Lines" class="ltx\_ref ltx\_font\_italic" style="font-size:50\%;"><span class="ltx\_text ltx\_ref\_tag">3</span></a>}}D{\log }^{\ast }{\mathrm{\ell }}_{\min }+2D}(v_{\alpha })\subseteq N^L(v_{\alpha })$. This implies that $S_{R_D}\ne \mathrm{\varnothing }$ for $S_{R_D}$ defined as in lines 5 and 6 of Algorithm 5, and therefore, $R_{\alpha ,L}\ge R_D\ge 2D$. The same holds for agent $\beta$. $◀$

Recall that $T_{\alpha ,L}\in O(L)$ (Proposition 9). If the delay $\tau$ between the startup times of the two agents is $10D$ or larger, by Lemma 11, the agents reach rendezvous in $T_{\alpha ,O(D)}+O(D)\in O(D)$ rounds ($T_{\mathrm{𝗋𝖽𝗏}}\in O(D)$). We assume a smaller delay $\tau$ in what follows.

By Lemma 12, we know that $R_{\alpha ,L}\ge D$ and $R_{\beta ,L}\ge D$ for $L>\mathrm{\Theta }(D{\log }^{\ast }{\mathrm{\ell }}_{\min })$. For $L$ a large enough $\mathrm{\Theta }(D{\log }^{\ast }{\mathrm{\ell }}_{\min })$, if during the loop iteration of parameter $L$ the agents settle on different values $R_{\alpha ,L}\ne R_{\beta ,L}$ for their ruling sets’ distances, they achieve rendezvous before round $T_{\alpha ,L}+O(L)=O(L)=O(D{\log }^{\ast }{\mathrm{\ell }}_{\min })$ by Lemma 13. If they have the same value $R_{\alpha ,L}=R_{\beta ,L}$, then they also achieve rendezvous before round $T_{\alpha ,L}+O(L)=O(L)=O(D{\log }^{\ast }{\mathrm{\ell }}_{\min })$, whether they go to the same ruling set node (Lemma 14) or different ones (Lemma 15). $◀$