Delays Induce an Exponential Memory Gap
for Rendezvous in Trees∗
Pierre Fraigniaud†
Andrzej Pelc‡
Abstract
The aim of rendezvous in a graph is meeting of two mobile agents at some node of an unknown
anonymous connected graph. In this paper, we focus on rendezvous in trees, and, analogously
to the efforts that have been made for solving the exploration problem with compact automata,
we study the size of memory of mobile agents that permits to solve the rendezvous problem
deterministically. We assume that the agents are identical, and move in synchronous rounds.
We first show that if the delay between the starting times of the agents is arbitrary, then
the lower bound on memory required for rendezvous is Ω(log n) bits, even for the line of length
n. This lower bound meets a previously known upper bound of O(log n) bits for rendezvous
in arbitrary graphs of size at most n. Our main result is a proof that the amount of memory
needed for rendezvous with simultaneous start depends essentially on the number ℓof leaves
of the tree, and is exponentially less impacted by the number n of nodes. Indeed, we present
two identical agents with O(log ℓ+ log log n) bits of memory that solve the rendezvous problem
in all trees with at most n nodes and at most ℓleaves.
Hence, for the class of trees with
polylogarithmically many leaves, there is an exponential gap in minimum memory size needed
for rendezvous between the scenario with arbitrary delay and the scenario with delay zero.
Moreover, we show that our upper bound is optimal by proving that Ω(log ℓ+ log log n) bits of
memory are required for rendezvous, even in the class of trees with degrees bounded by 3.
Keywords: rendezvous, exploration, compact data structure.
∗The results of this paper appeared in a preliminary form in papers: P. Fraigniaud, A. Pelc, Deterministic
rendezvous in trees with little memory, Proc.
22nd International Symposium on Distributed Computing (DISC
2008), LNCS 5218, 242-256, and P. Fraigniaud, A. Pelc, Delays induce an exponential memory gap for rendezvous in
trees, Proc. 22nd Ann. ACM Symposium on Parallel Algorithms and Architectures (SPAA 2010), 224-232.
†CNRS, Universit´e Paris Diderot - Paris 7, France. E-mail: Pierre.Fraigniaud@liafa.jussieu.fr. Part of this work
was done during this author’s visit at the Research Chair in Distributed Computing of the Universit´e du Qu´ebec en
Outaouais. Additional supports from ANR projects ALADDIN and PROSE, and INRIA project GANG.
‡D´epartement d’informatique, Universit´e du Qu´ebec en Outaouais, Gatineau, Qu´ebec J8X 3X7, Canada. E-mail:
pelc@uqo.ca. Supported in part by NSERC discovery grant and by the Research Chair in Distributed Computing of
the Universit´e du Qu´ebec en Outaouais.
arXiv:1102.0467v1  [cs.DC]  2 Feb 2011
1
Introduction
The rendezvous in a network [1, 4] is the following task. Two identical mobile agents, initially
located in two nodes of the network, move along links from node to node, and eventually have to
get to the same node at the same time. The network is modeled as an undirected connected graph,
and agents traverse links in synchronous rounds. They cannot leave any marks on visited nodes.
In this paper we consider deterministic rendezvous in trees, and seek rendezvous protocols that do
not rely on the knowledge of node labels, and can work in anonymous trees as well (cf. [3]). This
assumption is motivated by the fact that, even when nodes are equipped with distinct labels, agents
may be unable to perceive them, or nodes may refuse to reveal their labels, e.g., due to security
reasons. (Note also that if nodes of the network are labeled using distinct names, then agents can
meet at some a priori agreed node, and rendezvous reduces to graph exploration). On the other
hand, edges incident to a node v have distinct labels in {0, . . . , d −1}, where d is the degree of v.
Thus every undirected edge {u, v} has two labels, which are called its port numbers at u and at v.
(In the absence of port numbers, rendezvous is usually impossible, as the adversary may prevent
an agent from taking some edge incident to the current node). A function assigning port numbers
to every edge is called a port labeling. Port labeling is local, i.e., there is no relation between port
numbers at u and at v (we do not assume any sense of direction, of any kind).
The aim of the present paper is to determine the space complexity of rendezvous in trees. We
assume that the port labeling is decided by an adversary aiming at preventing two agents from
meeting, or at allowing the agents to meet only after having consumed a lot of resources, e.g.,
memory space. Hence, we adopt the following definition.
Definition 1.1 A pair of agents initially placed at nodes u and v of a tree T solves the rendezvous
problem if, for any port labeling of T, both agents are eventually in the same node of the tree in the
same round.
It is easy to characterize the initial positions u and v of a tree T for which rendezvous is feasible.
Recall that an automorphism of the tree is a bijection f : V →V , where V is the set of nodes of
the tree, such that for any w, w′ ∈V , w is adjacent to w′ if and only if f(w) is adjacent to f(w′).
It preserves a given port labeling µ, if for any w, w′ ∈V , the port number corresponding to edge
{w, w′} at node w is equal to the port number corresponding to edge {f(w), f(w′)} at node f(w).
Nodes u and v of a tree are called topologically symmetric, if there exists an automorphism f of the
tree, such that f(u) = v. Nodes u and v of a tree with labeling µ are called symmetric with respect
to this labeling, if there exists an automorphism f of the tree preserving this port labeling, such
that f(u) = v. It is well known (cf., e.g., [14]) that rendezvous with simultaneous start in a tree T
with a given port labeling µ is feasible, if and only if the initial positions u and v of agents are not
symmetric with respect to this labeling. Thus the following notion is crucial for our considerations.
Definition 1.2 Nodes u and v of a tree T = (V, E) are perfectly symmetrizable if there exists a
port labeling µ of T and an automorphism of the tree preserving µ that carries one node on the
other.
1
Note that two nodes that are perfectly symmetrizable are necessarily topologically symmetric. On
the other hand, two topologically symmetric nodes may not be perfectly symmetrizable. Typi-
cal examples are provided by the paths (or lines) with odd numbers of nodes, and by complete
binary trees. In both cases, two leaves are topologically symmetric while they are not perfectly
symmetrizable.
According to the above definitions, one can reformulate the feasibility of rendezvous as follows.
Fact 1.1 A pair of agents can solve the rendezvous problem in a tree, if and only if their initial
positions are not perfectly symmetrizable.
Consequently, throughout the paper, we consider only non perfectly symmetrizable initial positions
of the agents.
1.1
Our results
We first show that if the delay between the starting times of the agents is arbitrary, then the lower
bound on memory required for rendezvous is Ω(log n) bits, even for the line of length n. This lower
bound matches the upper bound from [14] valid for arbitrary graphs.
Our main positive result is a proof that the amount of memory needed for rendezvous with simulta-
neous start in trees depends essentially on the number ℓof leaves of the tree, and is exponentially less
impacted by the number n of nodes. Indeed, we show two identical agents with O(log ℓ+ log log n)
bits of memory that solve the rendezvous problem in all trees with n nodes and ℓleaves. Hence,
for the class of trees with polylogarithmically many leaves, there is an exponential gap in minimum
memory size needed for rendezvous between the scenario with arbitrary delay and the scenario with
delay zero.
Moreover, we show that the size O(log ℓ+ log log n) of memory needed for rendezvous is optimal,
even in the class of trees with degrees bounded by 3. More precisely, we prove two lower bounds.
First, for infinitely many integers ℓ, we show a class of arbitrarily large trees with maximum
degree 3 and with ℓleaves, for which rendezvous with simultaneous start requires Ω(log ℓ) bits
of memory. Second, we show that Ω(log log n) bits of memory are required for rendezvous with
simultaneous start in the line of length n. These two bounds together imply that our upper bound
O(log ℓ+ log log n) cannot be improved, even for the class of trees with maximum degree 3.
1.2
Bibliographic note
Note that our definition of solving the rendezvous problem is stronger than the definition used in
the conference versions [24, 25] of this paper. Indeed, rendezvous should occur for any port labeling.
As opposed to what is claimed in [25], the exponential gap described in this paper does not carry
over to the case where the ability of achieving rendezvous may depend on the port labeling.
2
More precisely, it was claimed in [25] that the positive result concerning the size O(log ℓ+log log n)
of memory for which rendezvous with simultaneous start is possible, holds for arbitrary initial
positions that are not symmetric with respect to a given port labeling µ of the tree in which agents
operate. This result is in fact incorrect in this formulation. Indeed, it has been recently proved in
[15] that, for some port labeling of a line and some initial positions that are not symmetric with
respect to this labeling, rendezvous with simultaneous start requires a logarithmic number of bits,
while ℓ= 2 for the line. However, our positive result holds for agents starting from arbitrary non
perfectly symmetrizable initial positions. The algorithm and its analysis remain similar as in [25].
(The exact place where the provided arguments do not extend to the case where the ability of
achieving rendezvous may depend on the port labeling will be pointed out to the reader).
On the other hand, all negative results from [24] and [25] hold in the present setting as well.
1.3
Related work
The rendezvous problem was first mentioned in [35]. Authors investigating rendezvous (cf. [3]
for an extensive survey) considered either the geometric scenario (rendezvous in an interval of the
real line, see, e.g., [9, 10, 26], or in the plane, see, e.g., [6, 7]), or rendezvous in networks, see
e.g., [18, 36, 38]. Many papers, e.g., [1, 2, 5, 9, 28] study the probabilistic setting: inputs and/or
rendezvous strategies are random.
A lot of effort has been dedicated to the study of the feasibility of rendezvous, and to the time
required to achieve this task, when feasible. For instance, deterministic rendezvous with agents
equipped with tokens used to mark nodes was considered, e.g., in [32]. Deterministic rendezvous of
agents equipped with unique labels was discussed in [17, 18, 30]. (In this latter scenario, symmetry
is broken by the use of the different labels of agents, and thus rendezvous is sometimes possible
even for strongly symmetric initial positions of the agents). Recently, rendezvous using variants of
Universal Traversal Sequences was investigated in [36]. Surprisingly though, as opposed to what
was done for the graph exploration problem (see, e.g., [12, 23, 29, 34]), or for other tasks such as
routing (see, e.g., [21, 22]), few papers were devoted to study the amount of memory required by
the agents for achieving rendezvous. Up to our knowledge, the only existing results prior to the
conference papers [24, 25] on which the present paper is based were dedicated to rendezvous in rings.
Memory needed for randomized rendezvous in the ring is discussed, e.g., in [31]. In the recent paper
[14] the authors showed that deterministic rendezvous can be solved in arbitrary n-node graphs
using O(log n) memory bits (for arbitrary delay between starting times of the agents) and that
this number of bits is necessary, even in rings and even for simultaneous start. Tradeoffs between
time of rendezvous in trees and the size of memory of the agents are studied in [15]. The impact
of memory size on the feasibility of the related task of tree exploration, for trees with unlabeled
nodes, has been studied in [19, 27].
A natural extension of the rendezvous problem is that of gathering [20, 28, 33, 37], when more than
two agents have to meet in one location. In [38] the authors considered rendezvous of many agents
with unique labels.
3
Apart from the synchronous model used in this paper, several authors have investigated asyn-
chronous rendezvous in the plane [11, 20] and in network environments [8, 16, 17]. In the latter
scenario the agent chooses the edge which it decides to traverse but the adversary controls the
speed of the agent. Under this assumption rendezvous in a node cannot be guaranteed even in very
simple graphs, hence the rendezvous requirement is relaxed to permit the agents to meet inside an
edge.
2
Framework and Preliminaries
2.1
Model
We consider mobile agents traveling in trees with locally labeled ports. The tree and its size are a
priori unknown to the agents. We first define precisely an individual agent. An agent is an abstract
state machine A = (S, π, λ, s0), where S is a set of states among which there is a specified state
s0 called the initial state, π : S × Z2 →S, and λ : S →Z. Initially the agent is at some node u0
in the initial state s0 ∈S. The agent performs actions in rounds measured by its internal clock.
Each action can be either a move to an adjacent node or a null move resulting in remaining in
the currently occupied node. State s0 determines a natural number λ(s0). If λ(s0) = −1 then the
agent makes a null move (i.e., remains at u0). If λ(s0) ≥0 then the agent leaves u0 by port λ(s0)
modulo the degree of u0. When incoming to a node v in state s ∈S, the behavior of the agent is
as follows. It reads the number i of the port through which it entered v and the degree d of v. The
pair (i, d) ∈Z2 is an input symbol that causes the transition from state s to state s′ = π(s, (i, d)).
If the previous move of the agent was null, (i.e., the agent stayed at node v in state s) then the pair
(−1, d) ∈Z2 is the input symbol read by the agent, that causes the transition from state s to state
s′ = π(s, (−1, d)). In both cases s′ determines an integer λ(s′), which is either −1, in which case
the agent makes a null move, or a non negative integer indicating a port number by which the agent
leaves v (this port is λ(s′) mod d). The agent continues moving in this way, possibly infinitely.
Since we consider the rendezvous problem for identical agents, we assume that agents are copies A
and A′ of the same abstract state machine A, starting at two distinct nodes vA and vA′, called the
initial positions. We will refer to such identical machines as a pair of agents. It is assumed that
the internal clocks of a pair of agents tick at the same rate. The clock of each agent starts when
the agent starts executing its actions. Agents start from their initial position with delay θ ≥0,
controlled by an adversary. This means that the later agent starts executing its actions θ rounds
after the first agent. Agents do not know which of them is first and what is the value of θ. We seek
agents with small memory, measured by the number of states of the corresponding automaton, or
equivalently by the number of bits on which these states are encoded. An automaton with K states
requires Θ(log K) bits of memory.
We say that a pair of agents solves the rendezvous problem with arbitrary delay (resp. with simul-
taneous start) in a class of trees, if, for any tree in this class, for any port labeling of this tree,
and for any initial positions that are not perfectly symmetrizable, both agents are eventually in
the same node of the tree in the same round, regardless of the starting rounds of the agents (resp.
4
provided that they start in the same round).
2.2
Preliminary results
Consider any tree T and the following sequence of trees constructed recursively: T0 = T, and Ti+1
is the tree obtained from Ti by removing all its leaves. T ′ = Tj for the smallest j for which Tj has
at most two nodes. If T ′ has one node, then this node is called the central node of T. If T ′ has two
nodes, then the edge joining them is called the central edge of T. A tree T with a port labeling µ
is called symmetric, if there exists a non-trivial automorphism f of the tree (i.e., an automorphism
f such that f(u) ̸= u, for some u ∈V ) preserving this port labeling. If a tree with port numbers
has a central node, then it cannot be symmetric.
We define the “basic walk” starting at node v the walk resulting from an agent performing the
following actions: leave node v by port 0, and, perpetually, whenever entering a degree-d node by
port i ∈{0, . . . , d −1}, leave that node by port (i + 1) mod d. Of course, a basic walk can be
bounded to perform for t steps (instead of perpetually), in which case we refer to a basic walk of
length t. Note that a basic walk of length 2(n −1) in an n-node tree returns to its starting node.
The following statement is an easy consequence of the techniques and results from [27].
Fact 2.1 There exists an agent accomplishing the following task in an arbitrary tree: using O(log m)
bits of memory, it finds the number m of nodes in the tree, returns and stops at its initial position,
and detects whether the tree has a central node, or has a central edge but is not symmetric, or has
a central edge and is symmetric. Moreover,
• if the tree has a central node x, then the agent finds the minimum number of steps of a basic
walk from its initial position to the central node x;
• if the tree has a central edge e = {x, y} but is not symmetric, then, for every initial position,
the agent finds the minimum number of steps of a basic walk from its initial position to
the same extremity x of the central edge; moreover, it knows which port at this extremity
corresponds to the central edge;
• if the tree is symmetric, then the agent finds the minimum number of steps of a basic walk
from its initial position to the farthest extremity1 of the central edge; moreover, it knows which
port at this extremity corresponds to the central edge.
In the sequel, the procedure accomplishing the above task starting at node v will be called Procedure
Explo(v).
1Why the farthest and not the closest is for technical reasons that should appear clear further in the text.
5
3
Rendezvous with arbitrary delay
It was proved in [14] that rendezvous with arbitrary delay can be accomplished in arbitrary n-
node graphs using O(log n) bits of memory. On the other hand, observe that rendezvous requires
Ω(log n) bits of memory in arbitrarily large trees with 2n + 1 nodes and maximum degree n. The
lower bound examples are trees Tn consisting of two nodes u and v of degree n, both linked to a
common node w, and to n −1 leaves. However, these trees have linear degree and the reason for
the logarithmic memory requirement is simply that agents with smaller memory are incapable of
having an output function λ with range of linear size, and thus the adversary can place one agent in
node u, the other in a leaf adjacent to v, and distribute ports in such a way that none of the agents
can ever get to node w, which makes rendezvous infeasible, in spite of non perfectly symmetrizable
initial positions.
This example leaves open the question if rendezvous with sub-logarithmic memory is possible, e.g.,
in all trees with constant maximum degree. It turns out that if the delay is arbitrary, this is not
the case: rendezvous requires logarithmic memory even for the class of lines.
Theorem 3.1 Rendezvous with arbitrary delay in the n-node line requires agents with Ω(log n) bits
of memory.
Proof. Let k be the number of memory bits of the agent and K = 2k be its number of states.
Place one agent at some node u of the infinite line where each edge has the same port number at
its two extremities. In any interval of length K + 1 there exist two nodes at which the agent is in
the same state. Let x1 be the first node of the trajectory of the agent in which this happens and
let s be the state of the agent at x1. Let x2 be the second node of the trajectory of the agent at
which the agent is in state s. Let δ be the distance between u and x1 and let d be the distance
between x1 and x2.
We construct the following instance of the rendezvous problem (see Fig. 1). The line is of length
8(K + 1) + 1. Let e be the central edge of this line. Assign number 0 to ports leading to edge e
from both its extremities, and assign other port labels so that ports leading to any edge at both its
extremities get the same number 0 or 1. (This is equivalent to 2-edge-coloring of the line). Let z be
the endpoint of the line, for which x1 is between z and x2. Let y1 and y2 be symmetric images of
x1 and x2, respectively, according to the axis of symmetry of the line. Let y0 be the node distinct
from y2, at distance d from y1. Let v be the node at distance δ from y0, such that the vectors [x1, u]
and [y0, v] have opposite directions. The other agent is placed at node v.
Let t1 be the number of rounds that the agent starting at u takes to reach2 x1 in state s. Let t2
be the number of rounds that the agent starting at v takes to reach y1 in state s. Let θ = t2 −t1.
The adversary delays the agent starting at u by θ rounds. Hence the agent starting at u reaches
x1 at the same time t and in the same state as the agent starting at v reaches y1. The points x1
and y1 are symmetric positions, hence rendezvous is impossible after time t. Before time t the two
2We say that the agent reaches node v in state s, if s is the state in which the agent leaves v, i.e., it leaves v by
port λ(s).
6
e
v
2(K+1)
2(K+1)
2(K+1)
2(K+1)
u
z
x1
y0
x2
y2
y1
d
d
d
δ
δ
Figure 1: Construction in the proof of Theorem 3.1.
agents were on different sides of edge e, in view of δ + d ≤2(K + 1), hence rendezvous did not
occur, although the initial positions of the agents are not a perfectly symmetrizable pair. The size
of the line is O(K) = O(2k), which concludes the proof.
□
Together with the logarithmic upper bound from [14], the above result completely solves the prob-
lem of determining the minimum memory of the agents permitting rendezvous with arbitrary delay.
Hence in the rest of the paper we concentrate on rendezvous with simultaneous start, thus assuming
that the delay θ = 0.
4
Rendezvous with simultaneous start
4.1
Upper bound
It turns out that the size of memory needed for rendezvous with simultaneous start depends on
two parameters of the tree: the number n of nodes and the number ℓof leaves. In fact we show
that rendezvous in trees with n nodes and ℓleaves can be done using only O(log ℓ+ log log n)
bits of memory. Thus, for trees with polylogarithmically many leaves, O(log log n) bits of memory
are enough. In view of Theorem 3.1, this shows an exponential gap in the minimum memory size
needed for rendezvous between the scenarios with arbitrary delay and with delay zero.
Theorem 4.1 There is a pair of identical agents solving rendezvous with simultaneous start in all
trees, and using, for any integers n and ℓ, O(log ℓ+ log log n) bits of memory in trees with at most
n nodes and at most ℓleaves.
The rest of the section is dedicated to the proof of Theorem 4.1. Let T be any tree, and let v and
v′ be the initial positions of the two agents in T. Let T ′ be the contraction of T, that is the tree
obtained from T by replacing every path3 in T joining two nodes of degree different from 2 by an
edge (the ports of this edge correspond to the ports at both extremities of the contracted path).
Notice that if T has ℓleaves, then its contraction T ′ has at most 2ℓ−1 nodes.
3Here, by path we mean a sequence of adjacent nodes of degree 2, all pairwise distinct.
7
Our rendezvous algorithm uses Procedure Explo, defined in Section 2, as a subroutine.
More
precisely, each of the two agents executes procedure Explo in T, ignoring the degree-2 nodes. That
is, protocol Explo is modified so that whenever an agent enters a degree-2 node through port
i ∈{0, 1} in some state s, it will leave that node in the next round by port (i + 1) mod 2, in the
same state s. In fact, the are some subtle additional details in the modified version of Explo, when
the initial node is of degree different from 2. Specifically, let s0 be the initial state of an agent
executing Explo. Our modified agent starts in an additional state s∗
0. If the initial node v has a
degree different from 2, then it enters state s0 and starts Explo(v), ignoring the degree-2 nodes.
Otherwise, the agent remains in state s∗
0 and leaves the initial node through port 0. The agent then
performs a basic walk, remaining in state s∗
0, until it enters a node of degree 1 (i.e., a leaf of the tree
T). At such a node, denoted by vleaf, the agent enters state s0 and starts Explo(vleaf), ignoring
the degree-2 nodes. We call Explo-bis the procedure Explo modified in this way. Observe that, in
trees with no nodes of degree 2, the two protocols Explo and Explo-bis are executed identically.
Hence, protocols Explo and Explo-bis are executed identically in T ′.
Formally, for an initial
position v, let us define
bv =
 v
if deg(v) ̸= 2
vleaf
otherwise
Then, the following holds.
Claim 4.1 Once an agent starting from some node v has reached node bv, the states at nodes of
degrees different from 2 of the agent performing Explo-bis in T are identical to the states of an
agent performing Explo in T ′ starting from node bv.
Using this claim, rendezvous in T is achieved as follows.
Stage 1.
Each of the two agents executes procedure Explo-bis from their respective initial
positions v and v′.
After having completed Explo-bis, each agent knows whether the contraction tree T ′ is symmetric
or not. (It is non-symmetric if either there is a central node, or there is a central edge and the
two port-labeled trees obtained by removing the central edge in T ′ are not isomorphic — the
isomorphism must preserve both the structure of the trees, and the port labelings).
Stage 2.
The nature of the second stage differs according to whether T ′ is symmetric or not.
In the non symmetric case, the rendezvous protocol uses Fact 2.1, which states that the two agents
performing Procedure Explo will eventually identify a single node x of T ′. Node x is identified by
the number of steps of the basic walk performed in T ′ to reach that node from the initial position.
Notice that, although Explo ensures (by Fact 2.1) that each agent returns to its initial position
v after completing the procedure, Claim 4.1 guaranties only that the agent applying Explo-bis
returns to a node bv. Nevertheless, this is sufficient, since the length of the basic walk reaching x
is the length of the one starting from node bv, ignoring degree-2 nodes. Note that this length does
not exceed twice the number of edges of T ′, and thus it can be encoded on O(log ℓ) bits.
8
Therefore, each of the agents act as follows:
• If there is a central node x in T ′, then Rendezvous is achieved by waiting for the other agent
at that node.
• Similarly, if there is a central edge in T ′, and the tree T ′ is not symmetric, then let x be the
extremity of the central edge of T ′ identified by protocol Explo-bis; rendezvous is achieved
by waiting for the other agent at that node.
The difficult and more challenging situation is when the contraction tree T ′ has a central edge
with two non distinguishable extremities, in which case the ability to solve the rendezvous problem
depends on the large tree T and on the initial positions of the two agents in T. Achieving rendezvous
is complicated by the constraint that the agents must use sub-logarithmic memory when ℓis small.
The main part of the proof will be dedicated to describing how this task can actually be achieved
in a memory efficient manner.
Sub-stage 2.1.
(for the case when T ′ symmetric) Resynchronization.
Recall that we are in a situation where each of the two agents has performed Explo-bis. An agent
starting from node v ∈T has not necessarily returned to node v, but to node bv ∈T ′. Each agent
executes Procedure Synchro defined as follows. It starts the execution of a basic walk in T, leaving
the current node bv by port 0. This basic walk will end when the agent is back at node bv. This
is simply insured by counting the number of edge-traversals in T ′: the agent stops the basic walk
after 2(ν −1) edge-traversals in T ′, where ν denotes the number of nodes in T ′. Since ν ≤2ℓ−1,
counting up to O(ν) does not require more that O(log ℓ) bits. The basic walk proceeds with the
following insertions: at each visited node w with degree different from 2 (i.e., at each node of T ′),
the agent performs Explo-bis(w), except for the very last node of T ′ visited by the basic walk,
that is except when the agent returns, for the last time, at its initial position bv.
Since agents performing Procedure Synchro starting from different initial positions bv execute iden-
tical actions, only in different order, we have the following:
Claim 4.2 Two agents starting simultaneously at arbitrary initial positions v and v′ in T finish
Procedure Synchro with a delay β = |L −L′| where L (resp., L′) is the length of the basic walk in
T leading from v to bv (resp., from v′ to bv′).
Once the agents are resynchronized (their desynchronization is now precisely β), each of them
proceeds to the second part of Stage 2.
Sub-stage 2.2.
(for the case when T ′ symmetric) Rendezvous in a virtual line.
After the execution of Procedure Synchro, the agent with initial position v is back at bv. In view of
Fact 2.1, since it has applied Explo(bv) at the very beginning of the rendezvous protocol, the agent
9
knows the number of steps of the basic walk from bv to the farthest extremity of the central edge
of T ′. So, its first action in Sub-stage 2.2 is to go to this node, following a basic walk. We denote
by bvfar (resp., bv′
far) the farthest extremity of the central edge of T ′ reached by the agent starting
from v (resp., from v′).
Since the contraction tree T ′ is symmetric, the two agents may end up in two different nodes of
T, i.e., possibly bvfar ̸= bv′
far. For instance, in the n-node path with an odd number of edges, the
two agents may end up in the two extremities of the path. Also, in the binomial tree with n-nodes
(cf.[13]), the two agents may end up in the two roots of the two binomial subtrees of T with n/2
nodes. Still, we prove that rendezvous is possible with little memory assuming that the two initial
positions of the agents were not perfectly symmetrizable in T. Actually, the first of the two key
ingredients in our proof is showing how rendezvous can be achieved in the path (or line) using
agents with O(log log n) bits of memory.
In the lemma below, we consider blind agents in paths, that is agents that ignore port labels. More
precisely, when entering a node, such an agent can just distinguish between the incoming edge and
the other edge (if any). Let P = (v1, . . . , vm) be an m-node path, and consider two identical blind
agents initially located at nodes va and vb, a < b. Rendezvous using blind agents is possible if and
only if m is odd, or m is even and a −1 ̸= m −b. Of course, a standard agent can simulate the
behavior of a blind agent. When applying the lemma below with standard agents, we will make
sure that the starting positions va and vb are such that rendezvous is achievable even with blind
agents.
Lemma 4.1 There exists a pair of identical blind agents accomplishing rendezvous with simultane-
ous start in all paths, whenever it is possible, and using O(log log m) bits of memory in paths with
at most m nodes.
Proof. Let P = (v1, . . . , vm) be an m-node path, and consider two identical blind agents initially
located at nodes va and vb, a < b. To achieve rendezvous, the two agents perform a sequence of
traversals of P, executed at lower and lower speeds, aiming at eventually meeting each other at
some node. More precisely, for an integer s ≥1, a traversal of the path is performed at speed 1/s, if
the agent remains idle s −1 rounds before traversing any edge. For instance, traversing P from v1
to vm at speed 1/s requires (m −1)s rounds. Our rendezvous algorithm for the line, called prime,
performs as follows.
Begin
start in arbitrary direction;
move at speed 1 until reaching one extremity of the path;
p ←2;
While no rendezvous do
traverse the entire path twice, at speed 1/p;
p ←smallest prime larger than p;
End
10
We now prove that, whenever rendezvous is possible for blind agents (i.e., when m odd, or m even
and a −1 ̸= m −b), the two agents meet before the pth iteration of the loop, for p = O(log n).
Let pj be the jth prime number (p1 = 2). Hence the speed of each agent at the jth execution of
the loop is 1/pj. If rendezvous has not occurred during the jth execution of the loop, then the two
agents have crossed the same edge, say e = {vc, vc+1}, at the same time t, in opposite directions.
This can occur if, for instance, the agent initially at va moves to node v1, traverses twice the path
at successive speeds p1, . . . , pj−1, and, c pj rounds after having eventually started walking at speed
pj, traverses the edge e at time t, while the other agent initially at vb moves to vm, traverses twice
the path at successive speeds p1, . . . , pj−1, and, (m −c)pj rounds after having eventually started
walking at speed pj, traverses the same edge e in the other direction at the same time t. In fact,
there are four cases to consider, depending on the two starting directions of the two agents: towards
v1 or towards vm. From these four cases, we get that one of the following four equalities must hold
(the first one corresponds to the previously described scenario: va moves towards v1 while vb moves
towards vm):
• t = (a −1) + 2(m −1) Pj−1
i=1 pi + c pj = (m −b) + 2(m −1) Pj−1
i=1 pi + (m −c)pj
• t = (a −1) + 2(m −1) Pj−1
i=1 pi + (m −1)pj + (m −c)pj = (b −1) + 2(m −1) Pj−1
i=1 pi + c pj
• t = (m −a) + 2(m −1) Pj−1
i=1 pi + (m −c)pj = (m −b) + 2(m −1) Pj−1
i=1 pi + (m −1)pj + c pj
• t = (m −a) + 2(m −1) Pj−1
i=1 pi + (m −c)pj = (b −1) + 2(m −1) Pj−1
i=1 pi + c pj
Therefore we get that pj divides |a −b|, or pj divides |m −(a + b) + 1|. As a consequence, since the
pi’s are primes, we get that if the two agents have not met after the jth execution of the loop, then
Y
i∈I
pi divides |a −b|
and
Y
i∈J
pi divides |m −(a + b) + 1|
where I∪J = {1, . . . , j}. Therefore, since the pi’s are primes, Qj
i=1 pi divides |a−b|·|m−(a+b)+1|.
Hence, if rendezvous is feasible, it must occur at or before the jth execution of the loop, where j
is the largest index such that Qj
i=1 pi divides |a −b| · |m −(a + b) + 1|. Thus it must occur at or
before the jth execution of the loop, where j is the largest index such that Qj
i=1 pi ≤m2.
Let π(x) be the number of prime numbers smaller than or equal to x. On the one hand, we have
Qj
i=1 pi ≥2π(pj). Hence, rendezvous must occur at or before the jth execution of the loop, where j
is the largest index such that 2π(pj) ≤m2, i.e., π(pj) ≤2 log m. On the other hand, from the Prime
Number Theorem we get that π(x) ∼x/ ln(x), i.e., limx→∞
π(x)
x/ ln(x) = 1. Hence, for m large enough,
π(x) ≥x/(2 ln(x)). Thus rendezvous must occur at or before the jth execution of the loop, where
j is the largest index such that pj/ ln pj ≤4 log m.
From the above, we get that (1) rendezvous must occur whenever it is feasible, and (2) it occurs at
or before the jth execution of the loop, where log pj ≤O(log log m). Since the next prime p can be
found using O(log p) bits, e.g., by exhaustive search, we get that prime performs rendezvous using
agents with O(log log m) bits of memory.
□
11
The (blind) agents described in Lemma 4.1 perform a protocol called prime. This protocol uses the
infinite sequence of prime numbers. We denote by prime(i) the protocol prime modified so that it
stops after having considered the ith prime number.
We now come back to our general rendezvous protocol in trees (with port numbers). Let ν = 2x be
the number of nodes in the contraction tree T ′. (We have ν even, since T ′ is symmetric with respect
to its central edge). We define a (non-simple) path called the rendezvous path, denoted by P, that
will be used by the agents to rendezvous using protocol prime. To define P, let u and v be the two
extremities of the path in T corresponding to the central edge in T ′. We have {bvfar, bv′
far} ⊆{u, v}.
The path P is called the central path, and is denoted by C. Abusing notation, C will also be used
as a shortcut for the instruction: “traverse C”.
Let bw (for “basic walk”) be the instruction of performing the following actions: leave by port 0,
and, perpetually, whenever entering a degree-d node by port i ∈{0, . . . , d −1}, leave that node by
port (i + 1) mod d. Similarly, let cbw (for “counter basic walk”), be the instruction of performing
the following: leave by the port used to enter the current node at the previous step, and, perpetually,
whenever entering a degree-d node by port i, leave that node by port (i −1) mod d. For j ≥1,
let bw(j) (resp., cbw(j)) be the instruction to execute bw (resp., cbw) until j nodes of degree
different from 2 have been visited. Let Bu (resp., Bv) be the path corresponding to the execution
of bw
2(ν −1)


from u (resp., from v). Note that a node can be visited several times by the walk,
and thus neither Bu nor Bv are simple. Note also that since T ′ has ν nodes, it has ν −1 edges,
and thus both Bu and Bv are closed paths, i.e., their extremities are u and v, respectively. Let Bu
(resp., Bv) be the path corresponding to the execution of cbw
2(ν −1)


from u (resp., from v).
We define
P = (Bu | Cu→v | Bv | Cv→u)5ℓ| (Bu | Cu→v | Bv)
where “ | ” denotes the concatenation of paths, Cu→v (resp., Cv→u) denotes the path C traversed
from u to v (resp., from v to u), and, for a closed path Q, Qα denotes Q concatenated with itself
α times.
The path P is well defined. Indeed, the sequence Bu | Cu→v | Bv | Cv→u leads back to node u. Also,
the two extremities of the path are u and v. Now, the agents have no clue whether they are standing
at u or at v. Nevertheless, we have the following.
Claim 4.3 Starting from an extremity u or v of the central path C, an agent performing the
sequence of instructions

bw
2(ν −1)


, C, cbw
2(ν −1)


, C
5ℓ
, bw
2(ν −1)


, C, cbw
2(ν −1)


traverses the path P from one of its extremities to the other.
Before establishing the claim, note that instructions bw
2(ν−1)


and cbw
2(ν−1)


are meaningful,
since agents can have counters of size O(log ℓ) bits, and they know ν in view of Fact 2.1. To establish
the claim, it suffices to notice that the path P reverse to P is given by
P = (Bv | Cv→u | Bu) | (Cu→v | Bv | Cv→u | Bu)5ℓ= (Bv | Cv→u | Bu | Cu→v)5ℓ| (Bv | Cv→u | Bu).
12
Begin
for consecutive values i ≥1 do
/* outer loop */
/* try rendezvous */
for j = 0, 1, . . . , 2(ν −1) do
/* first inner loop */
perform bw(j);
perform cbw(j);
/* back to the original position */
perform prime(i) on the rendezvous path P;
/* reset */
go to the other extremity of the central path C;
for j = 0, 1, . . . , 2(ν −1) do
/* second inner loop */
perform bw(j);
perform cbw(j);
/* back to the original position */
return to the original extremity of the central path C;
End
Figure 2: Second phase of the rendezvous (performed when the contraction tree is symmetric).
The two agents will use protocol prime along the path P to achieve rendezvous.
However, to
make sure that rendezvous succeeds, the two agents must not start prime simultaneously at the
two extremities of P, in order to break symmetry. Unfortunately, this requirement is not trivial to
satisfy. Indeed, one can guarantee some upper bound on the delay between the times the two agents
reach the two extremities of C (and thus of P as well) that does not exceed n, but no guarantee can
be given for the minimum delay, which could be zero. This is because the delay does not depend
on the tree T ′, but on the tree T. Hence two agents starting simultaneously in T may actually
finish Stage 2.1 of our protocol (i.e., the execution of Synchro) at the same time, even if T is not
symmetric, and even if T is symmetric but the starting positions were not perfectly symmetrizable.
The second key ingredient in our proof is a technique guaranteeing eventual desynchronization of
the two agents. A high level description of this technique is summarized in Figure 2. We describe
this technique in detail below.
The outer loop of the protocol in Figure 2 states how many consecutive prime numbers the protocol
will test while performing prime along the path P. Performing prime(i) for successive values of
i, instead of just prime, is for avoiding a perpetual execution of prime in the case when the two
agents started the execution of phase 2 at the same time from the two extremities of P. For every
number i ≥1 of primes to be used in prime, the protocol performs two inner loops. The first one is
an attempt to achieve rendezvous along P, while the second one is used to upper bound the delay
between the two agents at the end of the outer loop, in order to guarantee that the next execution
of the outer loop will start with a delay between the two agents that does not exceed n.
During the first inner loop, an agent executing the protocol performs a series of basic walks, of
different lengths. For j = 0, the agent performs nothing. In this case, prime(i) is performed on P
directly. For j > 0, the agent performs a basic walk in T to the jth node of degree different from 2
that it encounters along its walk. When j = 2(ν −1), the basic walk is a complete one, traversing
each edge of T twice. Each bw(j) is followed by a cbw(j), so as to come back to the original
position at the same extremity of the path P. Once this is done, the agent performs prime(i) on
13
P.
The second inner loop aims at resetting the two agents. For this purpose, each agent goes to the
other extremity of C, performs the same sequence of actions as the other agent had performed
during its execution of the first inner loop, and returns to its original extremity of C. This enables
resetting the two agents in the following sense.
Claim 4.4 Let t and t′ be the times of arrival of the two agents at bvfar and bv′
far after the execution
of Synchro, respectively. Then the difference between the times the two agents enter each execution
of the outer loop of the protocol in Figure 2 remains identical, equal to |t −t′|.
To establish the claim, just notice that, during every execution of the outer loop, the sets of actions
performed by the two agents inside the loop are identical, differing only by their orders.
Note that we can express |t −t′| = |(L + bL) −(L′ + bL′)| where L and L′ are defined in Claim 4.2,
and bL (resp., bL′) denotes the length of the basic walk leading from bv (resp., bv′) to bvfar (resp.,
to bv′
far). A consequence of Claim 4.4 is the following lemma.
Lemma 4.2 Let t and t′ be the times of arrival of the two agents at bvfar and bv′
far after the
execution of Synchro, respectively. For every i, the delay between the two agents at the beginning
of each execution of prime(i) cannot exceed |t −t′| + 16nℓ.
Proof. For j ≥1, let lj and l′
j be the lengths (i.e., numbers of edges) of the paths in T between the
(j −1)th and the jth node of degree different from 2 that is met by the two agents, respectively,
during their basic walk from their positions at the two extremities of C. At the jth iteration of
the inner loop, one agent has traversed 2 Pj
a=1
Pa
b=1 lb edges during bw(a) and cbw(a) for all
a = 1, . . . , j. The other agent has traversed 2 Pj
a=1
Pa
b=1 l′
b edges during the same bw(a) and
cbw(a). Since the number of rounds of prime(i) is the same for both agents, we get that their
delay is at most:
|t −t′| + 2
j
X
a=1
a
X
b=1
|lb −l′
b|
≤
|t −t′| + 4(ν −1)
2(ν−1)
X
b=1
|lb −l′
b|
≤
|t −t′| + 4(ν −1)
2(ν−1)
X
b=1
max{lb, l′
b}
≤
|t −t′| + 8(ν −1)n
≤
|t −t′| + 8νn
≤
|t −t′| + 16nℓ.
This completes the proof of the lemma.
□
14
Lemma 4.3 Assume that the two agents have not met when they arrive at bvfar and bv′
far after
the execution of Synchro. For every i, if at the beginning of each execution of prime(i) the delay
between the two agents is zero, then their initial positions were perfectly symmetrizable in T.
Proof. Fix i ≥1, and assume that, at the beginning of each of the 2ν −1 executions of prime(i)
in the outer loop, the delay between the two agents is zero. This implies that, using the same
notations as in the proof of Lemma 4.2, for every j = 0, . . . , 2(ν −1) we have
t + 2
j
X
a=1
a
X
b=1
lb = t′ + 2
j
X
a=1
a
X
b=1
l′
b .
Therefore,
t = t′
and
lj = l′
j for every j = 0, . . . , 2(ν −1).
These equalities imply that the tree T is topologically symmetric: there is an automorphism f which
extends the port preserving automorphism f′ of T ′ mapping the two symmetric subtrees T ′
1 and T ′
2
of T ′ hanging at the two extremities of the central edge of T ′ (f′ induces an isomorphism between
T ′
1 and T ′
2 preserving port labels). Indeed, since the two agents have not met when both of them
arrive at bvfar and bv′
far, the fact that t = t′ implies that bvfar ̸= bv′
far. We have bv′
far = f′(bvfar).
More generally, if xj (resp., x′
j) denotes the jth node of T ′ reached by the basic walk starting at
bvfar (resp., bv′
far), we have x′
j = f′(xj). By definition, lj (resp., l′
j) is the length of the path in
T between xj−1 and xj (resp., between x′
j−1 and x′
j). Since lj = l′
j, we get that the number of
degree-2 nodes in T between xj−1 and xj is the same as the number of degree-2 nodes in T between
x′
j−1 and x′
j. Thus f′ can be extended to match nodes of these two paths, preserving adjacencies.
Since this holds for every j, we get that T is topologically symmetric4.
To sum up, the tree T is topologically symmetric (by automorphism f), and its contraction tree
T ′ is symmetric (by automorphism f′, which preserves port labels). A consequence of this fact is
the following crucial observation. Let us consider the following port labeling µ. The port numbers
at nodes of degree larger than 2 are the same as in T ′. The port labeling is completed arbitrarily
at nodes of degree 2, preserving the following condition: if {z, z′} is an edge in T with at least
one extremity z of degree 2, then the port number at z corresponding to {z, z′} is equal to the
port number at f(z) corresponding to {f(z), f(z′)}. Two basic walks starting from two symmetric
positions in T ′ generate two sequences of nodes such that the ith nodes of the two sequences are
symmetric in T with respect to µ. Indeed, the “branching” nodes, i.e., the nodes of degree at
least 3, are symmetric, and basic walks are oblivious of the port numbers at nodes of degree at
most 2. The same observation holds for counter basic walks. It also holds if the port number of the
outgoing edge from the starting nodes are not 0, under the simple assumption that they are equal.
4The automorphism f does not necessarily preserve the port numbers in T along the paths between nodes with
degree different from 2. This is the reason why, as opposed to what is claimed in [25], the initial positions of the
agents are not necessarily symmetric in T. We show however that they are perfectly symmetrizable in T.
15
We use the above observation to show that the two nodes v and v′ are perfectly symmetrizable.
Since T ′ is symmetric, it is sufficient to show that v and v′ are topologically symmetric. The two
agents have reached nodes bvfar and bv′
far after procedure Synchro, entering these nodes from the
central path. Indeed, on the one hand, bvfar and bv′
far are the farthest extremity of the central edge
of T ′ coming from bv and bv′, respectively, and, on the other hand, the basic walks reaching these
nodes are of minimum length (cf., Fact 2.1). Since bvfar and bv′
far are symmetric in T ′, the port
numbers of the edges incident to these nodes on the central path are identical. Let i be this port
number. Consider two counter basic walks of length t = t′ starting from bvfar and bv′
far, leaving the
starting node by port number i. These counter basic walks proceed backwards, first along the basic
walk from bv to bvfar for bL steps, and next along the basic walk from v to bv for L steps. If bv = v
then L = 0. If bv ̸= v, then the articulation between the two basic walks v →bv and bv →bvfar
occurs at bv = vleaf. Since we have chosen this latter node as a leaf, the sequence of basic walks
v →bv and bv →bvfar is actually equal to a basic walk v →bvfar of length t = L + bL. Hence the
counter basic walk of length t starting from bvfar by port i leads to the initial position v. The same
holds for the other walk of length t′ = t. Therefore, v and v′ are topologically symmetric, and thus
they are perfectly symmetrizable.
□
In view of the previous lemma, since v and v′ are not perfectly symmetrizable, at each execution
i of the outer loop, there is an execution j of prime(i) for which the two agents do not start the
second phase at the same time from their respective extremities of P. Moreover, by Lemma 4.2,
during this jth execution of prime(i), the delay δ between the two agents is at most |t −t′| + 16nℓ.
We have |t −t′| = |(L + bL) −(L′ + bL′)|, where the four parameters are lengths of basic walks.
These four basic walks have lengths at most 2(n −1). Hence, |t −t′| ≤4n. Therefore, δ ≤20nℓ.
The length of the rendezvous path P is larger than 20nℓbecause Bu and Bv are each of length
at least 2n. Therefore, at the first time when both agents are simultaneously in the jth execution
of prime(i), they occupy two non perfectly symmetrizable positions in P: one is at one extremity
of P, and the other is at some node of P at distance δ > 0 along P from the other extremity of
P. Moreover, since the delay δ between the two agents is smaller than the length of the path P,
the agent first executing prime(i) has not yet completed the first traversal of P when the other
agent starts prime(i). As a consequence, the two agents act as if prime(i) were executed with
both agents starting simultaneously at non perfectly symmetrizable positions in the path. Now, for
small values of i, prime(i) may not achieve rendezvous in P. However, in view of Lemma 4.1, for
some i = O(log n), rendezvous will be completed whenever the initial positions of the agents were
not perfectly symmetrizable in T.
We complete the proof by checking that each agent uses O(log ℓ+log log n) bits of memory. Protocol
Explo-bis executed in T consumes the same amount of memory as Protocol Explo executed
in T ′.
Since T ′ has at most 2ℓ−1 nodes, Explo-bis uses O(log ℓ) bits of memory.
During
the second stage of the rendezvous, a counter is used for identifying the index j of the inner
loop.
Since j ≤2ν ≤4ℓ, this counter uses O(log ℓ) bits of memory.
All executions of prime
are independent, and performed one after the other.
Thus, in view of Lemma 4.1, a total of
O(log log n) bits suffice to implement these executions. The index i of the outer loop grows until it
is large enough so that prime(i) achieves rendezvous in a path of length O(nℓ). Thus, i ≤log(nℓ),
16
and thus O(log log(nℓ)) = O(log log n) bits suffice to encode this index. This completes the proof
of Theorem 4.1.
4.2
The lower bound Ω(log log n)
In this section we prove the lower bound Ω(log log n) on the size of memory required for rendezvous
with simultaneous start in a n-node line.
Theorem 4.2 Rendezvous with simultaneous start in the n-node line requires agents with Ω(log log n)
bits of memory.
The rest of the section is dedicated to the proof of Theorem 4.2. For proving the theorem, note
that we can restrict ourselves to lines whose edges are properly colored 1 and 2, so that the port
numbers at the two extremities of an edge colored i are set to i. In this setting, the transition
function of an agent in a line is π : S × {1, 2} →S that describes the transition that occurs when
an agent enters a node of degree d ∈{1, 2} in state s ∈S. In this situation, the agent changes its
state to state s′ = π(s, d), and performs the action λ(s′). The fact that one does not need to specify
the incoming port number is a consequence of the edge-coloring, which implies that whenever an
agent leaves a node by port i, it enters the next node by port i too.
Let us fix two identical agents A and A′, with finite state set S, and transition function π. Let
π′ : S →S be the transition function applied at nodes of degree 2 of the edge-colored line, i.e.,
π′(s) = π(s, 2) for any s ∈S. To π′ is associated its transition digraph, whose nodes are the states
in S, and there is an arc from s to s′ if and only if s′ = π′(s). This digraph is composed of a certain
number of connected components, say r, each of them of a similar shape, that is a circuit with
inward trees rooted at the nodes of the circuit. Let C1, . . . , Cr be the r circuits corresponding to
the r connected components of the transition digraph, and let γ be the least common multiple of
the number of arcs of these circuits, i.e., γ = lcm(|C1|, . . . , |Cr|). We prove that there is a line of
length proportional to 2γ + |S| in which A and A′ do not rendezvous.
First, observe that if A and A′ cannot go at arbitrarily large distance from their starting positions,
say they go at maximum distance D, then they cannot rendezvous in a line of length 4D + 4.
Indeed, if the initial positions are two nodes at distance 2D +1, and at distance at least D +1 from
the extremities of the line, then the ranges of activity of the two agents are disjoint, and thus they
cannot meet (one edge is added at one extremity of the line to break the symmetry of the initial
configuration).
Thus from now on, we assume that both agents can go at arbitrarily large distance from their
starting positions.
For the purpose of establishing our result, place the two agents A and A′ on two adjacent nodes
vA and vA′ of an infinite line (whose edges are properly colored). Let e = {vA, vA′} be the edge
linking these two nodes.
17
• Let t0 be large enough so that A is at distance at least 2γ + |S| from its starting position
after t0 steps.
Since t0 > |S|, agent A at time t0 is in some state si ∈Ci for some i ∈{1, . . . , r}. In fact, since
|Ci| divides γ, agent A has fully executed Ci at least twice.
We define the notion of extreme position for a circuit C. Let s, π′(s), . . . , π′(k)(s) be a circuit, with
s = π′(k)(s). Assume that agent A starts in state s from node u0 at distance at least k + 1 from
both extremities of the line. After having performed C exactly once, i.e., after k steps, agent A
is at some node uk, back in state s. Let u0, u1, u2, . . . , uk be the k + 1 non necessarily distinct
nodes visited by A while executing C. The extreme position for C starting in state s is the node
uj satisfying
dist(u0, uj) = dist(u0, uk) + dist(uk, uj),
and
dist(u0, uj) = max
0≤ℓ≤k dist(u0, uℓ).
Let ui be the extreme position for Ci starting in si, and let us define the following parameters:
• τ is the first time step among the |Ci| steps after step t0 at which A reaches ui.
• x is the distance of agent A at time τ from its original position, i.e., x = dist(ui, vA);
• τ ′ = τ + 2γ;
• x′ is the distance of agent A′ at time τ ′ from its original position vA′.
Note that, by symmetry of the port labeling, and from the fact that A and A′ are identical and
operate in an infinite line, the two agents are on the two different sides of edge e at time τ. Note
also that, between times τ and τ ′, agent A′ keeps on going further away from its original position,
by repeating the sequence of actions determined by the circuit Ci. Hence x′ ̸= x. Actually, we have
x′ > x. We can therefore consider the following construction.
Initial configuration of the agents.
Let L be the properly 2-edge-colored line of length x +
x′ + 1, formed by x edges, followed by one edge called e, and followed by x′ edges. The two agents
A and A′ are placed at the two extremities vA and vA′ of e, the same way they were placed at the
two extremities of e in the infinite line used to define x and x′.
Since x ̸= x′, the initial positions of agents are not perfectly symmetrizable. Nevertheless, we prove
that the two agents never meet in L, and thus rendezvous is not accomplished. The adversary
imposes no delay between the starting times of the agents, i.e., they both start acting simultaneously
from their respective initial positions.
One ingredient used for proving that the two agents do not rendezvous is the following general
result, that we state as a lemma for further reference.
Lemma 4.4 (Parity Lemma)Consider two (not necessarily identical) agents initially at odd dis-
tance in a tree T, that start acting simultaneously in T. Let t ≥1. Assume that one agent stays
18
idle q times in the time interval [1, t], while the other one stays idle q′ times in the same time
interval. If |q −q′| is even, then the two agents are at odd distance at step t.
Proof. At any step, if one agent moves while the other one stays idle, then the parity of their
distance changes. On the other hand, if both agents move or both stay idle, then the parity of
their distance remains unchanged. Let a be the number of steps in [1, t] when both agents were
idle simultaneously. Then the parity of the inter-agent distance changes exactly (q −a) + (q′ −a)
times in the time interval [1, t]. Since |q −q′| is even, q + q′ is also even, and thus (q −a) + (q′ −a)
is even too. Thus the parity of the inter-agent distance is the same at time 1 and at time t.
□
The Parity Lemma enables us to establish the following.
Lemma 4.5 The two agents A and A′ do not meet during the first τ steps.
Proof. Since the agents perform the same sequence of actions in the time interval [1, τ], we get
that, for any t ≤τ, the two agents have remained idle the same mumber of times in the time
interval [1, t], and thus, by the Parity Lemma (with q = q′), they are at odd distance at step t,
since they originally started at distance 1. In other words, the two agents remain permanently at
odd distance during the time interval [1, τ]. Thus they cannot meet during this time interval.
□
At step τ, the behavior of the two agents becomes different.
Indeed, agent A is reaching one
extremity of L, while A′ is visiting a degree-2 node.
We analyze the states of the two agents when they reach extremities of L during the execution of
their protocol. Assume that agent A reaches the extremities of L at least k ≥1 times. Let σj be
the state of agent A when it reaches any of the two extremities of L for the jth time, 1 ≤j ≤k.
Lemma 4.6 Agent A′ reaches the extremities of L at least k times. Moreover, if σ′
j is the state of
agent A′ when it reaches any of the two extremities of L for the jth time, 1 ≤j ≤k, then σ′
j = σj.
Proof. First, let us consider the case k = 1. After time τ (i.e., after the time when A reaches one
extremity of L, in state σ1), agent A′ keeps on repeating the execution of circuit Ci. This leads
A′ to eventually reach the other extremity of L. Recall that we have considered the behavior of
A after time t0 when A was in state si ∈Ci, and that τ was defined as the first time step among
the |Ci| steps after step t0 at which A reaches the extreme position ui of Ci starting at si. Since
τ ′ = τ + 2γ, and since |Ci| divides γ, we get that agent A′ is in state σ1 at time τ ′. Moreover, since
|Ci| divides γ, A′ reaches the extreme position ui of Ci at time τ ′, and therefore time τ ′ is the first
time when A′ is at distance x′ from e. Therefore σ′
1 = σ1, and the lemma holds for k = 1.
For k > 1, the proof is by induction on the number of times j agent A reaches an extremity of L,
j = 1, . . . , k. By the previous arguments, the result holds for j = 1. When agent A reaches an
extremity of L for the jth time, it is in state σj. By the induction hypothesis, when agent A′ reaches
19
an extremity of L for the jth time, it is also in state σ′
j = σj. Therefore, the configuration for A
and A′ between two consecutive hits of an extremity of L is actually symmetric. As a consequence,
σ′
j+1 = σj+1, and the lemma holds.
□
After time τ the walks of the agents can be decomposed in two different types of subwalks. A
traversal period for an agent is the subwalk between two consecutive hits of two different extremities
of L by this agent. A bouncing period for an agent is a subwalk (possibly empty) performed between
two consecutive traversal periods. Roughly, a bouncing period for an agent is a walk during which
the agent starts from one extremity of L and repeats bouncing (i.e., leaving and going back) that
extremity until it eventually starts the next traversal period.
Globally, an agent starts from its original position, performs some initial steps (τ for A, and τ ′ for
A′), and then alternates between bouncing periods and traversal periods. These periods are not
synchronous between the two agents because there is a delay of 2γ between them. Nevertheless,
by Lemma 4.6, if one agent bounces at one extremity of L during its kth bouncing period, then
the other agent bounces at the other extremity of L during its kth bouncing period. Similarly,
if one agent traverses L during its kth traversal period, then the other agent traverses L in the
opposite direction during its kth traversal period. In fact, Lemma 4.6 guarantees that the two
agents perform symmetric actions with a delay of 2γ, alternating bouncing at the two different
extremities of L, and traversing L in two opposite directions.
The following lemma holds, by establishing that whenever one agent is in a bouncing period, the
two agents are far apart.
Lemma 4.7 The two agents A and A′ do not meet whenever one of them is in a bouncing period.
Proof. There is a delay of 2γ between the two agents. During such a period of time, an agent can
travel a distance at most 2γ. Also, during its bouncing period, an agent cannot go at distance more
than |S| from the extremity of the line where it is bouncing. On the other hand, by the definitions
of t0 and τ > t0, we have x > 2γ + |S|, and thus x′ > 2γ + |S| as well. Therefore, when one of the
agents is in a bouncing period, the distance between the two agents is at least 2γ + |S|, and thus
they cannot meet.
□
The following lemma holds, by using the fact that γ is the least common multiple of the circuit
lengths in the transition digraph of the agents, and by applying the Parity Lemma.
Lemma 4.8 The two agents A and A′ do not meet when both of them are in a traversal period.
Proof. When both agents are in a traversal period, they started their period in the same state,
from Lemma 4.6. Hence, they are eventually both performing the same circuit of states Ci. This
occurs after the same initial time of duration at most |S|. This time corresponds to the time it
takes to reach the circuit Ci from the initial state at which the agents started their traversal period.
20
As we already observed in the proof of Lemma 4.7, since x′ > x > 2γ + |S|, the two agents are
far apart during the transition period before both of them have entered the circuit Ci executed
during the considered traversal. Thus we can now assume that the two agents are performing Ci,
traversing the line in two opposite directions. We prove that they cross along an edge, and hence
they do not meet. Since the delay between the two agents is 2γ and since γ is a multiple of |Ci|
for any i ∈{1, . . . , r}, the delay is an even multiple of the length of the circuit |Ci| performed at
this traversal. As a consequence, at any step of their traversal periods, the number of times one
agent was idle when the other was not, is even. The Parity Lemma with |q −q′| = 2γ/|Ci| then
insures that the distance between the two agents remains odd during the whole traversal period.
Thus they do not meet.
□
Proof of Theorem 4.2. The two agents start an initial period that lasts τ steps. By Lemma 4.5
they do not meet during this period. Then the two agents alternate between bouncing periods and
traversal periods. By Lemma 4.7, they do not meet when one of the two agents is in a bouncing
period. When the two agents are in a traversal period, Lemma 4.8 guarantees that they do not
meet. Hence the two agents never meet, in spite of starting from non perfectly symmetrizable
positions, and thus they do not rendezvous in L. By the construction of the line L and the setting
of γ, we get that L is of length O(|S||S|). Therefore, rendezvous with simultaneous start in lines of
size at most n requires agents with at least Ω(log log n) memory bits.
□
4.3
The lower bound Ω(log ℓ)
In this section we prove that rendezvous with simultaneous start in trees with ℓleaves requires
Ω(log ℓ) bits of memory, even in the class of trees with maximum degree 3. Together with the
lower bound of Ω(log log n) on memory size needed for rendezvous in the n-node line5 established
in Theorem 4.2, this result proves that our upper bound O(log ℓ+log log n) from Section 4.1 cannot
be improved even for trees of maximum degree 3.
Theorem 4.3 For infinitely many integers ℓ, there exists an infinite family of trees with ℓleaves,
for which rendezvous with simultaneous start requires Ω(log ℓ) bits of memory.
Proof. Consider an integer ℓ= 2i, for any even i. Consider an (i+1)-node path with a distinguished
endpoint called the root. To every internal node x of the path attach either a new leaf, or a new
node y of degree 2 with a new leaf z attached to it. There are 2i−1 = 2ℓ/2−1 possible resulting
non-isomorphic rooted trees. Call them side trees. Note that non-isomorphic is meant here without
the port-preserving clause: there are so many rooted trees which cannot be mapped to each other
by any isomorphism, not only by any isomorphism preserving port numbering. Fix an arbitrary
port labeling in every side tree.
5Notice that the lower bound Ω(log log n) holds for n-node trees of maximum degree 3 with many leaves as well:
it suffices to attach identical binary trees on each extremity of the line, and the argument from the previous section
goes through.
21
For any pair of side trees T ′ and T ′′ and for any positive even integer m, consider the tree T
consisting of side trees T ′ and T ′′ whose roots are joined by a path of length m + 1 (i.e., there are
m added nodes of degree two). Ports at the added nodes of degree two are labeled as follows: both
ports at the central edge have label 0, and ports at both ends of any other edge of the line have
the same label 0 or 1. (This corresponds to a 2-edge-coloring of the line). Call any tree resulting
from this construction a two-sided tree. Any such tree has ℓleaves and maximum degree 3. For any
two-sided tree consider initial positions of the agents at nodes u and v of the joining path adjacent
to roots of its side trees.
Consider agents with k bits of memory (thus with K = 2k states). A tour of a side tree associated
with an initial position (u or v) is the part of the trajectory of the agent in this side tree between
consecutive visits of the associated initial position. Observe that the maximum duration D of a
tour is smaller than K · (3i). Indeed, the number of nodes in a side tree is at most 3i −1, hence
the number of possible pairs (state, node of the side tree) is at most K · (3i −1). A tour of longer
duration than this value would cause the agent to leave the same node twice in the same state,
implying an infinite loop. Such a tour could not come back to the initial position.
For a fixed agent with the set S of states and a fixed side tree, we define the function p : S →S
as follows. Let s be the state in which the agent starts a tour. Then p(s) is the state in which the
agent finishes the tour. Now we define the function q : S →S × {1, . . . , D}, called the behavior
function, by the formula q(s) = (p(s), t), where t is the number of rounds to complete the tour
when starting in state s. The number of possible behavior functions is at most F = (KD)K. A
behavior function depends on the side tree for which it is constructed.
Suppose that k ≤
1
3 log ℓ.
We have D < 3Ki =
3
2Kℓ, hence KD <
3
2K2ℓ.
Hence we have
log K + log log(KD) ≤k + log log(3
2K2ℓ) ≤k + 2 + log k + log log ℓ, which is smaller than 2
3 log ℓfor
sufficiently large k. It follows that K log(KD) < ℓ2/3 < ℓ/2−1, which implies F = (KD)K < 2ℓ/2−1.
Thus the number of possible behavior functions is strictly smaller than the total number of side
trees. It follows that there are two side trees T1 and T2 for which the corresponding behavior
functions are equal.
Consider two instances of the rendezvous problem for any length m+1 of the joining line, where m
is a positive even integer: one in which both side trees are equal to T1, and the other for which one
side tree is T1 and the other is T2. Rendezvous is impossible in the first instance because in this
instance initial positions of the agents form a symmetric pair of nodes with respect to the given
port labeling. Consider the second instance, in which the initial positions of the agents do not form
a perfectly symmetrizable pair. Because of the symmetry of labeling of the joining line, agents
cannot meet inside any of the side trees. Indeed, when one of them is in one tree, the other one is
in the other tree. Since the behavior function associated with side trees T1 and T2 is the same, the
agents leave these trees always at the same time and in the same state. Hence they cannot meet on
the line, in view of its odd length and symmetric port labeling. This implies that they never meet,
in spite of initial positions that are not perfectly symmetrizable. Hence rendezvous in the second
instance requires Ω(log ℓ) bits of memory.
□
22
References
[1] S. Alpern, The rendezvous search problem, SIAM J. on Control and Optimization 33 (1995),
673-683.
[2] S. Alpern, Rendezvous search on labelled networks, Naval Reaserch Logistics 49 (2002), 256-
274.
[3] S. Alpern and S. Gal, The theory of search games and rendezvous. Int. Series in Operations
research and Management Science, Kluwer Academic Publisher, 2002.
[4] J. Alpern, V. Baston, and S. Essegaier, Rendezvous search on a graph, Journal of Applied
Probability 36 (1999), 223-231.
[5] E. Anderson and R. Weber, The rendezvous problem on discrete locations, Journal of Applied
Probability 28 (1990), 839-851.
[6] E. Anderson and S. Fekete, Asymmetric rendezvous on the plane, Proc. 14th Annual ACM
Symp. on Computational Geometry (1998), 365-373.
[7] E. Anderson and S. Fekete, Two-dimensional rendezvous search, Operations Research 49
(2001), 107-118.
[8] D. Baba, T. Izumi, F. Ooshita, H. Kakugawa, T. Masuzawa, Space-optimal rendezvous of
mobile agents in asynchronous trees. Proc. 17th Int. Colloquium on Structural Information
and Comm. Complexity, (SIROCCO 2010), Springer LNCS 6058, 86-100.
[9] V. Baston and S. Gal, Rendezvous on the line when the players’ initial distance is given by an
unknown probability distribution, SIAM J. on Control and Opt. 36 (1998), 1880-1889.
[10] V. Baston and S. Gal, Rendezvous search when marks are left at the starting points, Naval
Reaserch Logistics 48 (2001), 722-731.
[11] M. Cieliebak, P. Flocchini, G. Prencipe, N. Santoro, Solving the robots gathering problem,
Proc. 30th International Colloquium on Automata, Languages and Programming (ICALP
2003), 1181-1196.
[12] S. A. Cook and C. Rackoff. Space Lower Bounds for Maze Threadability on Restricted Ma-
chines. SIAM J. Comput. 9 (1980), 636-652.
[13] T.H. Cormen, C.E. Leiserson, R.L. Rivest, Introduction to Algorithms, McGraw-Hill 1990.
[14] J. Czyzowicz, A. Kosowski, A. Pelc, How to meet when you forget: Log-space rendezvous in
arbitrary graphs, Proc. 29th Annual ACM Symposium on Principles of Distributed Computing
(PODC 2010), 450-459.
[15] J. Czyzowicz, A. Kosowski, A. Pelc, Time vs. space trade-offs for rendezvous in trees. Submit-
ted for publication.
23
[16] J. Czyzowicz, A. Labourel, A. Pelc, How to meet asynchronously (almost) everywhere, Proc.
21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010), 22-30.
[17] G. De Marco, L. Gargano, E. Kranakis, D. Krizanc, A. Pelc, U. Vaccaro, Asynchronous deter-
ministic rendezvous in graphs, Theoretical Computer Science 355 (2006), 315-326.
[18] A. Dessmark, P. Fraigniaud, D. Kowalski, A. Pelc. Deterministic rendezvous in graphs. Algo-
rithmica 46 (2006), 69-96.
[19] K. Diks, P. Fraigniaud, E. Kranakis, A. Pelc, Tree exploration with little memory, Journal of
Algorithms 51 (2004), 38-63.
[20] P. Flocchini, G. Prencipe, N. Santoro, P. Widmayer, Gathering of asynchronous oblivious
robots with limited visibility, Proc. 18th Annual Symposium on Theoretical Aspects of Com-
puter Science (STACS 2001), Springer LNCS 2010, 247-258.
[21] P. Fraigniaud and C. Gavoille. A Space Lower Bound for Routing in Trees. In 19th Annual
Symp. on Theoretical Aspects of Computer Science (STACS 2002), Springer LNCS 2285, 65-75.
[22] P. Fraigniaud and C. Gavoille. Routing in Trees. In 28th Int. Colloquium on Automata, Lan-
guages and Programming (ICALP 2001), Springer LNCS 2076, 757-772.
[23] P. Fraigniaud and D. Ilcinkas. Digraphs Exploration with Little Memory. 21st Symp. on The-
oretical Aspects of Comp. Science (STACS 2004), Springer LNCS 2996, 246-257.
[24] P. Fraigniaud, A. Pelc, Deterministic rendezvous in trees with little memory, Proc. 22nd Inter-
national Symposium on Distributed Computing (DISC 2008), Springer LNCS 5218, 242-256.
[25] P. Fraigniaud, A. Pelc, Delays induce an exponential memory gap for rendezvous in trees,
Proc. 22nd Ann. ACM Symposium on Parallel Algorithms and Architectures (SPAA 2010),
224-232.
[26] S. Gal, Rendezvous search on the line, Operations Research 47 (1999), 974-976.
[27] L. Gasieniec, A. Pelc, T. Radzik, X. Zhang, Tree exploration with logarithmic memory, Proc.
18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2007), 585-594.
[28] A. Israeli and M. Jalfon, Token management schemes and random walks yield self stabilizing
mutual exclusion, Proc. 9th Annual ACM Symposium on Principles of Distributed Computing
(PODC 1990), 119-131.
[29] M. Kouck`y, Universal Traversal Sequences with Backtracking, Proc. 16th IEEE Conference on
Computational Complexity (2001), 21-26.
[30] D. Kowalski, A. Malinowski, How to meet in anonymous network, in 13th Int. Colloquium
on Structural Information and Comm. Complexity, (SIROCCO 2006), Springer LNCS 4056,
44-58.
24
[31] E. Kranakis, D. Krizanc, and P. Morin, Randomized Rendez-Vous with Limited Memory, Proc.
8th Latin American Theoretical Informatics (LATIN 2008), Springer LNCS 4957, 605-616.
[32] E. Kranakis, D. Krizanc, N. Santoro and C. Sawchuk, Mobile agent rendezvous in a ring, Proc.
23rd Int. Conference on Distributed Computing Systems (ICDCS 2003), IEEE, 592-599.
[33] W. Lim and S. Alpern, Minimax rendezvous on the line, SIAM J. on Control and Optimization
34 (1996), 1650-1665.
[34] O. Reingold. Undirected connectivity in log-space. Journal of the ACM 55(2008), 1-24.
[35] T. Schelling, The strategy of conflict, Oxford University Press, Oxford, 1960.
[36] A. Ta-Shma and U. Zwick. Deterministic rendezvous, treasure hunts and strongly universal
exploration sequences. Proc. 18th ACM-SIAM Symposium on Discrete Algorithms (SODA
2007), 599-608.
[37] L. Thomas, Finding your kids when they are lost, Journal on Operational Res. Soc. 43 (1992),
637-639.
[38] X. Yu and M. Yung, Agent rendezvous: a dynamic symmetry-breaking problem, Proc. In-
ternational Colloquium on Automata, Languages, and Programming (ICALP 1996), Springer
LNCS 1099, 610-621.
25