Asynchronous approach in the plane: A deterministic
polynomial algorithm

arXiv:1612.02168v3 [] 5 May 2017

†

Sébastien Bouchard† , Marjorie Bournat† , Yoann Dieudonné‡ , Swan Dubois† , Franck Petit†
Sorbonne Universités, UPMC Univ Paris 06, CNRS, INRIA, LIP6 UMR 7606, Paris, France
‡
MIS Lab., Université de Picardie Jules Verne, France
May 8, 2017

Abstract
In this paper we study the task of approach of two mobile agents having the same limited range
of vision and moving asynchronously in the plane. This task consists in getting them in finite
time within each other’s range of vision. The agents execute the same deterministic algorithm
and are assumed to have a compass showing the cardinal directions as well as a unit measure. On
the other hand, they do not share any global coordinates system (like GPS), cannot communicate
and have distinct labels. Each agent knows its label but does not know the label of the other
agent or the initial position of the other agent relative to its own. The route of an agent is a
sequence of segments that are subsequently traversed in order to achieve approach. For each
agent, the computation of its route depends only on its algorithm and its label. An adversary
chooses the initial positions of both agents in the plane and controls the way each of them moves
along every segment of the routes, in particular by arbitrarily varying the speeds of the agents.
Roughly speaking, the goal of the adversary is to prevent the agents from solving the task, or at
least to ensure that the agents have covered as much distance as possible before seeing each other.
A deterministic approach algorithm is a deterministic algorithm that always allows two agents
with any distinct labels to solve the task of approach regardless of the choices and the behavior
of the adversary. The cost of a complete execution of an approach algorithm is the length of both
parts of route travelled by the agents until approach is completed.
Let ∆ and l be the initial distance separating the agents and the length of (the binary representation of) the shortest label, respectively. Assuming that ∆ and l are unknown to both agents,
does there exist a deterministic approach algorithm always working at a cost that is polynomial in
∆ and l?
Actually the problem of approach in the plane reduces to the network problem of rendezvous
in an infinite oriented grid, which consists in ensuring that both agents end up meeting at the
same time at a node or on an edge of the grid. By designing such a rendezvous algorithm with
appropriate properties, as we do in this paper, we provide a positive answer to the above question.
Our result turns out to be an important step forward from a computational point of view, as
the other algorithms allowing to solve the same problem either have an exponential cost in the
initial separating distance and in the labels of the agents, or require each agent to know its starting
position in a global system of coordinates, or only work under a much less powerful adversary.
Keywords: mobile agents, asynchronous rendezvous, plane, infinite grid, deterministic algorithm, polynomial cost.

1

1
1.1

Introduction
Model and Problem

The distributed system considered in this paper consists of two mobile agents that are initially placed
by an adversary at arbitrary but distinct positions in the plane. Both agents have a limited sensory
radius (in the sequel also referred to as radius of vision), the value of which is denoted by , allowing
them to sense (or, to see) all their surroundings at distance at most  from their respective current
locations. We assume that the agents know the value of . As stated in [12], when  = 0, if agents
start from arbitrary positions of the plane and can freely move on it, making them occupy the same
location at the same time is impossible in a deterministic way. So, we assume that  > 0 and we
consider the task of approach which consists in bringing them at distance at most  so that they can
see each other. In other words, the agents completed their approach once they mutually sense each
other and they can even get closer. Without loss of generality, we assume in the rest of this paper
that  = 1.
The initial positions of the agents, arbitrarily chosen by the adversary, are separated by a distance
∆ that is initially unknown to both agents and that is greater than  = 1. In addition to the initial
positions, the adversary also assigns a different non-negative integer (called label) to each agent. The
label of an agent is the only input of the deterministic algorithm executed by the agent. While the
labels are distinct, the algorithm is the same for both agents. Each agent is equipped with a compass
showing the cardinal directions and with a unit of length. The cardinal directions and the unit of
length are the same for both agents.
To describe how and where each agent moves, we need to introduce two important notions that
are borrowed from [12]: The route and the walk of an agent. The route of an agent is a sequence
(S1 , S2 , S3 . . .) of segments Si = [ai , ai+1 ] traversed in stages as follows. The route starts from a1 ,
the initial position of the agent. For every i ≥ 1, starting from the position ai , the agent initiates
Stage i by choosing a direction α (using its compass) as well as a distance x. Stage i ends as soon as
the agent either sees the other agent or reaches ai+1 corresponding to the point at distance x from
ai in direction α. Stages are repeated indefinitely (until the approach is completed). Since both
agents never know their positions in a global coordinate system, the directions they choose at each
stage can only depend on their (deterministic) algorithm and their labels. So, the route (the actual
sequence of segments) followed by an agent depends on its algorithm and its label, but also on its
initial position. By contrast, the walk of each agent along every segment of its route is controlled
by the adversary. More precisely, within each stage Si and while the approach is not achieved, the
adversary can arbitrarily vary the speed of the agent, stop it and even move it back and forth as
long as the walk of the agent is continuous, does not leave Si , and ends at ai+1 . Roughly speaking,
the goal of the adversary is to prevent the agents from solving the task, or at least to ensure that
the agents have covered as much distance as possible before seeing each other. We assume that at
any time an agent can remember the route it has followed since the beginning.
A deterministic approach algorithm is a deterministic algorithm that always allows two agents to
solve the task of approach regardless of the choices and the behavior of the adversary. The cost of
an accomplished approach is the length of both parts of route travelled by the agents until they see
each other. An approach algorithm is said to be polynomial in ∆ and in the length of the binary
representation of the shortest label between both agents if it always permits to solve the problem
of approach at a cost that is polynomial in the two aforementioned parameters, no matter what the
adversary does.
It is worth mentioning that the use of distinct labels is not fortuitous. In the absence of a way
2

of distinguishing the agents, the task of approach would have no deterministic solution. This is
especially the case if the adversary handles the agents in a perfect synchronous manner. Indeed, if
the agents act synchronously and have the same label, they will always follow the same deterministic
rules leading to a situation in which the agents will always be exactly at distance ∆ from each other.

1.2

Our Results

In this paper, we prove that the task of approach can be solved deterministically in the above
asynchronous model, at a cost that is polynomial in the unknown initial distance separating the
agents and in the length of the binary representation of the shortest label. To obtain this result, we
go through the design of a deterministic algorithm for a very close problem, that of rendezvous in
an infinite oriented grid which consists in ensuring that both agents end up meeting either at a node
or on an edge of the grid. The tasks of approach and rendezvous are very close as the former can be
reduced to the latter.
It should be noticed that our result turns out to be an important advance, from a computational
point of view, in resolving the task of approach. Indeed, the other existing algorithms allowing to
solve the same problem either have an exponential cost in the initial separating distance and in the
labels of the agents [12], or require each agent to know its starting position in a global system of
coordinates [10], or only work under a much less powerful adversary [18] which initially assigns a
possibly different speed to each agent but cannot vary it afterwards.

1.3

Related Work

The task of approach is closely linked to the task of rendezvous. Historically, the first mention of
the rendezvous problem appeared in [33]. From this publication until now, the problem has been
extensively studied so that there is henceforth a huge literature about this subject. This is mainly
due to the fact that there is a lot of alternatives for the combinations we can make when addressing
the problem, e.g., playing on the environment in which the agents are supposed to evolve, the way
of applying the sequences of instructions (i.e., deterministic or randomized) or the ability to leave
some traces in the visited locations, etc. Naturally, in this paper we focus on work that are related
to deterministic rendezvous. This is why we will mostly dwell on this scenario in the rest of this
subsection. However, for the curious reader wishing to consider the matter in greater depth, regarding
randomized rendezvous, a good starting point is to go through [2, 3, 28]. Concerning deterministic
rendezvous, the literature is divided according to the way of modeling the environnement: Agents
can either move in a graph representing a network, or in the plane.
For the problem of rendezvous in networks, a lot of papers considered synchronous settings, i.e.,
a context where the agents move in the graph in synchronous rounds. This is particularly the case
of [17] in which the authors presented a deterministic protocol for solving the rendezvous problem,
which guarantees a meeting of the two involved agents after a number of rounds that is polynomial
in the size n of the graph, the length l of the shortest of the two labels and the time interval τ
between their wake-up times. As an open problem, the authors asked whether it was possible to
obtain a polynomial solution to this problem which would be independent of τ . A positive answer
to this question was given, independently of each other, in [27] and [35]. While these algorithms
ensure rendezvous in polynomial time (i.e., a polynomial number of rounds), they also ensure it at
polynomial cost because the cost of a rendezvous protocol in a graph is the number of edges traversed
by the agents until they meet—each agent can make at most one edge traversal per round. Note
that despite the fact a polynomial time implies a polynomial cost in this context, the reciprocal
3

is not always true as the agents can have very long waiting periods, sometimes interrupted by a
movement. Thus these parameters of cost and time are not always linked to each other. This was
highlighted in [31] where the authors studied the tradeoffs between cost and time for the deterministic
rendezvous problem. More recently, some efforts have been dedicated to analyse the impact on time
complexity of rendezvous when in every round the agents are brought with some pieces of information
by making a query to some device or some oracle [14, 30]. Along with the work aiming at optimizing
the parameters of time and/or cost of rendezvous, some other work have examined the amount of
required memory to solve the problem, e.g., [24, 25] for tree networks and in [11] for general networks.
In [6], the problem is approached in a fault-prone framework, in which the adversary can delay an
agent for a finite number of rounds, each time it wants to traverse an edge of the network.
Rendezvous is the term that is usually used when the task of meeting is restricted to a team
of exactly two agents. When considering a team of two agents or more, the term of gathering is
commonly used. Still in the context of synchronous networks, we can cite some work about gathering
two or more agents. In [19], the task of gathering is studied for anonymous agents while in [5, 15, 20]
the same task is studied in presence of byzantine agents that are, roughly speaking, malicious agents
with an arbitrary behavior.
Some studies have been also dedicated to the scenario in which the agents move asynchronously
in a network [12, 21, 29], i.e., assuming that the agent speed may vary, controlled by the adversary.
In [29], the authors investigated the cost of rendezvous for both infinite and finite graphs. In the
former case, the graph is reduced to the (infinite) line and bounds are given depending on whether
the agents know the initial distance between them or not. In the latter case (finite graphs), similar
bounds are given for ring shaped networks. They also proposed a rendezvous algorithm for an
arbitrary graph provided the agents initially know an upper bound on the size of the graph. This
assumption was subsequently removed in [12]. However, in both [29] and [12], the cost of rendezvous
was exponential in the size of the graph. The first rendezvous algorithm working for arbitrary finite
connected graphs at cost polynomial in the size of the graph and in the length of the shortest label
was presented in [21]. (It should be stressed that the algorithm from [21] cannot be used to obtain the
solution described in the present paper: this point is fully explained in the end of this subsection).
In all the aforementioned studies, the agents can remember all the actions they have made since
the beginning. A different asynchronous scenario for networks was studied in [13]. In this paper,
the authors assumed that agents are oblivious, but they can observe the whole graph and make
navigation decisions based on these observations.
Concerning rendezvous or gathering in the plane, we also found the same dichotomy of synchronicity vs. asynchronicity. The synchronous case was introduced in [34] and studied from a fault-tolerance
point of view in [1, 16, 22]. In [26], rendezvous in the plane is studied for oblivious agents equipped
with unreliable compasses under synchronous and asynchronous models. Asynchronous gathering
of many agents in the plane has been studied in various settings in [7, 8, 9, 23, 32]. However, the
common feature of all these papers related to rendezvous or gathering in the plane – which is not
present in our model – is that the agents can observe all the positions of the other agents or at least
the global graph of visibility is always connected (i.e., the team cannot be split into two groups so
that no agent of the first group can detect at least one agent of the second group).
Finally, the closest works to ours allowing to solve the problem of approach under an asynchronous
framework are [10, 4, 12, 18]. In [10, 12, 18], the task of approach is solved by reducing it to the
task of rendezvous in an infinite oriented grid. In [4], the authors present a solution to solve the
task of approach in a multidimensional space by reducing it to the task of rendezvous in an infinite
multidimensional grid. Let us give some more details concerning these four works to highlight the
4

contrasts with our present contribution. The result from [12] leads to a solution to the problem of
approach in the plane but has the disadvantage of having an exponential cost. The result from [10]
and [4] also implies a solution to the problem of approach in the plane at cost polynomial in the
initial distance of the agents. However, in both these works, the authors use the powerful assumption
that each agent knows its starting position in a global system of coordinates (while in our paper, the
agents are completely ignorant of where they are). Lastly, the result from [18] provides a solution
at cost polynomial in the initial distance between agents and in the length of the shortest label.
However, the authors of this study also used a powerful assumption: The adversary initially assigns
a possibly different and arbitrary speed to each agent but cannot vary it afterwards. Hence, each
agent moves at constant speed and uses clock to achieve approach. By contrast, in our paper, we
assume basic asynchronous settings, i.e., the adversary arbitrarily and permanently controls the
speed of each agent.
To close this subsection, it is worth mentioning that it is unlikely that the algorithm from [21]
that we referred to above, which is especially designed for asynchronous rendez-vous in arbitrary
finite graphs, could be used to obtain our present result. First, in [21] the algorithm has not a
cost polynomial in the initial distance separating the agents and in the length of the smaller label.
Actually, ensuring rendezvous at this cost is even impossible in arbitrary graph, as witnessed by
the case of the clique with two agents labeled 0 and 1: the adversary can hold one agent at a node
and make the other agent traverse Θ(n) edges before rendezvous, in spite of the initial distance 1.
Moreover, the validity of the algorithm given in [21] closely relies on the fact that both agents must
evolve in the same finite graph, which is clearly not the case in our present scenario. In particular even
when considering the task of rendezvous in an infinite oriented grid, the natural attempt consisting
in making each agent apply the algorithm from [21] within bounded grids of increasing size and
centered in its initial position, does not permit to claim that rendezvous ends up occurring. Indeed,
the bounded grid considered by an agent is never exactly the same than the bounded grid considered
by the other one (although they may partly overlap), and thus the agents never evolve in the same
finite graph which is a necessary condition to ensure the validity of the solution of [21] and by
extension of this natural attempt.

1.4

Roadmap

The next section (Section 2) is dedicated to the computational model and basic definitions. We
sketch our solution in Section 3, formally described in Sections 4 and 5. Section 6 presents the
correctness proof and cost analysis of the algorithm. Finally, we make some concluding remarks in
Section 7.

2

Preliminaries

We know from [12, 18] that the problem of approach in the plane can be reduced to that of rendezvous
in an infinite grid specified in the next paragraph.
Consider an infinite square grid in which every node u is adjacent to 4 nodes located North, East,
South, and West from node u. We call such a grid a basic grid. Two agents with distinct labels
(corresponding to non-negative integers) starting from arbitrary and distinct nodes of a basic grid
G have to meet either at some node or inside some edge of G. As for the problem of approach (in
the plane), each agent is equipped with a compass showing the cardinal directions. The agents can
see each other and communicate only when they share the same location in G. In other words, in
5

the basic grid G we assume that the sensory radius (or, radius of vision) of the agents is equal to
zero. In such settings, the only initial input that is given to a rendezvous algorithm is the label of
the executing agent. When occupying a node u, an agent decides (according to its algorithm) to
move to an adjacent node v via one of the four cardinal directions: the movement of the agent along
the edge {u, v} is controlled by the adversary in the same way as in a section of a route (refer to
Subsection 1.1), i.e., the adversary can arbitrarily vary the speed of the agent, stop it and even move
it back and forth as long as the walk of the agent is continuous, does not leave the edge, and ends
at v.
The cost of a rendezvous algorithm in a basic grid is the total number of edge traversals by both
agents until their meeting.
From the reduction described in [18], we have the following theorem.
Theorem 1. If there exists a deterministic algorithm solving the problem of rendezvous between any
two agents in a basic grid at cost polynomial in D and in the length of the binary representation
of the shortest of their labels where D is the distance (in the Manhattan metric) between the two
starting nodes occupied by the agents, then there exists a deterministic algorithm solving the problem
of approach in the plane between any two agents at cost polynomial in ∆ and in the length of the
binary representation of the shortest of their labels where ∆ is the initial Euclidean distance separating
the agents.
For completeness let us now outline the reduction described in [18]. Consider an infinite square
grid with edge length 1. More precisely, for any point v in the plane, we define the basic grid Gv
to be the infinite graph, one of whose nodes is v, and in which every node u is adjacent to 4 nodes
at Euclidean distance 1 from it, and located North, East, South, and West from node u. We now
focus on how to transform any rendezvous algorithm in the grid Gv to an algorithm for the task of
approach in the plane.
Let A be any rendezvous algorithm for any basic grid. Algorithm A can be executed in the grid
Gw , for any point w in the plane. Consider two agents in the plane starting respectively from point
v and from another point w in the plane. Let V 0 be the set of nodes in Gv that are the closest
√ nodes
0
0
0
from w. Let v be a node in V , arbitrarily chosen. Notice that v is at distance at most 2/2 < 1
from w. Let α be the vector v 0 w. Execute algorithm A on the grid Gv with agents starting at nodes v
and v 0 . Let p be the point in Gv (either a node of it or a point inside an edge), in which these agents
meet at some time t. The transformed algorithm A∗ for approach in the plane works as follows:
Execute the same algorithm A but with one agent starting at v and traveling in Gv and the other
agent starting at w and traveling in Gw , so that the starting time of the agent starting at w is the
same as the starting time of the agent starting at v 0 in the execution of A in Gv . The starting time
of the agent starting at v does not change. If approach has not been accomplished before, in time t
the agent starting at v and traveling in Gv will be at point p, as previously. In the same way, the
agent starting at w and traveling in Gw will get to some point q at time t. Clearly, q = p + α. Hence
both agents will be at distance less than 1 at time t, which means that they accomplish approach in
the plane because  = 1 (refer to Subsection 1.1).
Hence in the rest of the paper we will consider rendezvous in a basic grid, instead of the task of
approach. We use N (resp. E, S, W ) to denote the cardinal direction North (resp. East, South,
West) and an instruction like “Perform N S” means that the agent traverses one edge to the North
and then traverses one edge to the South (by the way, coming back to its initial position). We denote
by D the initial (Manhattan) distance separating two agents in a basic grid. A route followed by
an agent in a basic grid corresponds to a path in the grid (i.e., a sequence of edges e1 , e2 , e3 , e4 , . . .)
6

that are consecutively traversed by the agent until rendezvous is done. For any integer k, we define
the reverse path to the path e1 , . . . , ek as the path ek , ek−1 , . . . , e1 = e1 , . . . , ek−1 , ek . We denote by
C(p) the number of edge traversals performed by an agent during the execution of a procedure p.
Consider two distinct nodes u and v. We define a specific path from u to v, denoted P (u, v), as
follows. If there exists a unique shortest path from u to v, this shorthest path is P (u, v). Otherwise,
consider the smallest rectangle R(u,v) such that u and v are two of its corners. P (u, v) is the unique
path among the shortest path from u to v that traverses all the edges on the northern side of R(u,v) .
Note that P (u, v) = P (v, u).
An illustration of P (u, v) is given in Figure 1.

Figure 1: Some different cases for P (u, v)

3
3.1

Idea of the algorithm
Informal Description in a Nutshell. . .

We aim at achieving rendezvous of two asynchronous mobile agents in an infinite grid and in a
deterministic way. It is well known that solving rendezvous deterministically is impossible in some
symmetric graphs (like a basic grid) unless both agents are given distinct identifiers called labels.
We use them to break the symmetry, i.e., in our context, to make the agents follow different routes.
The idea is to make each agent “read” its label binary representation, a bit after another from the
most to the least significant bits, and for each bit it reads, follow a route depending on the read bit.
Our algorithm ensures rendezvous during some of the periods when they follow different routes i.e.,
when the two agents process two different bits.
7

Furthermore, to design the routes that both agents will follow, our approach would require
to know an upper bound on two parameters, namely the initial distance between the agents and
the length (of the binary representation) of the shortest label. As we suppose that the agents
have no knowledge of these parameters, they both perform successive “assumptions”, in the sequel
called phases, in order to find out such an upper bound. Roughly speaking, each agent attempts to
estimate such an upper bound by successive tests, and for each of these tests, acts as if the upper
bound estimation was correct. Both agents first perform Phase 0. When Phase i does not lead to
rendezvous, they perform Phase i + 1, and so on. More precisely, within Phase i, the route of each
agent is built in such a way that it ensures rendezvous if 2i is a good upper bound on the parameters
of the problem. Hence, in our approach two requirements are needed: both agents are assumed (1) to
process two different bits (i.e., 0 and 1) almost concurrently and (2) to perform Phase i = α almost
at the same time—where α is the smallest integer such that the two aforementioned parameters are
upper bounded by 2α .
However, to meet these requirements, we have to face two major issues. First, since the adversary
can vary both agent speeds, the idea described above does not prevent the adversary from making the
agents always process the same type of bit at the same time. Besides, the route cost depends on the
phase number, and thus, if an agent were performing some Phase i with i exponential in the initial
distance and in the length of the binary representation of the smallest label, then our algorithm would
not be polynomial. To tackle these two issues, we use a mechanism that prevents the adversary from
making an agent execute the algorithm arbitrarily faster than the other without meeting. Each of
both these issues is circumvent via a specific “synchronization mechanism”. Roughly speaking, the
first one makes the agents read and process the bits of the binary representation of their labels at
quite the same speed, while the second ensures that they start Phase α at almost the same time. This
is particularly where our feat of strength is: orchestrating in a subtle manner these synchronizations
in a fully asynchronous context while ensuring a polynomial cost. Now that we have described the
very high level idea of our algorithm, let us give more details.

3.2

Under the hood

The approach described above allows us to solve rendezvous when there exists an index for which
the binary representations of both labels differ. However, this is not always the case especially
when a binary representation is a prefix of the other one (e.g., 100 and 1000). Hence, instead of
considering its own label, each agent will consider a transformed label: The transformation borrowed
from [17] will guarantee the existence of the desired difference over the new labels. In the rest of
this description, we assume for convenience that the initial Manhattan distance D separating the
agents is at least the length of the shortest binary representation of the two transformed labels (the
complementary case adds an unnecessary level of complexity to understand the intuition).
As mentioned previously, our solution (cf. Algorithm 5 in Section 5) works in phases numbered
0, 1, 2, 3, 4, . . . During Phase i (cf. Procedure Assumption called at line 3 in Algorithm 5), the agent
supposes that the initial distance D is at most 2i and processes one by one the first 2i bits of its
transformed label: In the case where 2i is greater than the binary representation of its transformed
label, the agent will consider that each of the last “missing” bits is 0. When processing a bit,
the agent executes a particular route which depends on the bit value and the phase number. The
route related to bit 0 (relying in particular on Procedure Berry called at line 9 in Algorithm 6)
and the route related to bit 1 (relying in particular on Procedure Cloudberry called at line 11 in
Algorithm 6) are obviously different and designed in such a way that if both these routes are executed

8

almost simultaneously by two agents within a phase corresponding to a correct upper bound, then
rendezvous occurs by the time any of them has been completed. In the light of this, if we denote by
α the smallest integer such that 2α ≥ D, it turns out that an ideal situation would be that the agents
concurrently start phase α and process the bits at quite the same rate within this phase. Indeed,
we would then obtain the occurrence of rendezvous by the time the agents complete the process
of the jth bit of their transformed label in phase α, where j is the smallest index for which the
binary representations of their transformed labels differ. However, getting such an ideal situation in
presence of a fully asynchronous adversary appears to be really challenging. This is where the two
synchronization mechanisms briefly mentioned above come into the picture.
If the agents start Phase α approximately at the same time, the first synchronization mechanism
(cf. Procedure RepeatSeed called at line 15 in Algorithm 6) permits to force the adversary to make
the agents process their respective bits at similar speed within Phase α, as otherwise rendezvous
would occur prematurely during this phase before the process by any agent of the jth bit. This
constraint is imposed on the adversary by dividing each bit process into some predefined steps and
by ensuring that after each step s of the kth bit process, for any k ≤ 2α , an agent follows a specific
route that forces the other agent to complete the step s of its kth bit process. This route, on which
the first synchronization is based, is constructed by relying on the following simple principle: If an
agent performs a given route X included in a given area S of the basic grid, then the other agent can
“push it” over X. In other words, unless rendezvous occurs, the agent forces the other to complete
its route X by covering S a number of times at least equal to the number of edge traversals involved
in route X (each covering of S allows to traverse all the edges of S at least once). Hence, one of
the major difficulties we have to face lies in the setting up of the second synchronization mechanism
guaranteeing that the agents start Phase α around the same time. At first glance, it might be
tempting to use an analogous principle to the one used for dealing with the first synchronization.
Indeed, if an agent a1 follows a route covering r times an area Y of the grid, such that Y is where
the first α − 1 phases of an agent a2 take place and r is the maximal number of edge traversals an
agent can make during these phases, then agent a1 pushes agent a2 to complete its first α − 1 phases
and to start Phase α. Nevertheless, a strict application of this principle to the case of the second
synchronization directly leads to an algorithm having a cost that is superpolynomial in D and the
length of the smallest label, due to a cumulative effect that does not appear for the case of the first
synchronization. As a consequence, to force an agent to start its Phase α, the second synchronization
mechanism does not depend on the kind of route described above, but on a much more complicated
route that permits an agent to “push” the second one. This works by considering the “pattern” that
is drawn on the grid by the second agent rather than just the number of edges that are traversed (cf.
Procedure Harvest called at line 1 in Algorithm 6). This is the most tricky part of our algorithm,
one of the main idea of which relies in particular on the fact that some routes made of an arbitrarily
large sequence of edge traversals can be pushed at a relative low cost by some other routes that
are of comparatively small length, provided they are judiciously chosen. Let us illustrate this point
through the following example. Consider an agent a1 following from a node v1 an arbitrarily large
sequence of Xi , in which each Xi corresponds either to AA or BB where A and B are any routes
(A and B corresponding to their respective backtrack i.e., the sequence of edge traversals followed
in the reverse order). An agent a2 starting from an initial node v2 located at a distance at most d
from v1 can force agent a1 to finish its sequence of Xi (or otherwise rendezvous occurs), regardless
of the number of Xi , simply by executing AABB from each node at distance at most d from v2 .
To support this claim, let us suppose by contradiction that it does not hold. At some point, agent
a2 necessarily follows AABB from v1 . However, note that if either agent starts following AA (resp.
9

BB) from node v1 while the other is following AA (resp. BB) from node v1 , then the agents meet.
Indeed, this implies that the more ahead agent eventually follows A (resp. B) from a node v3 to
v1 while the other is following A (resp. B) from v1 to v3 , which leads to rendezvous. Hence, when
agent a2 starts following BB from node v1 , agent a1 is following AA, and is not in v1 , so that it
has at least started the first edge traversal of AA. This means that when agent a2 finishes following
AA from v1 , a1 is following AA, which implies, using the same arguments as before, that they meet
before either of them completes this route. Hence, in this example, agent a2 can force a1 to complete
an arbitrarily large sequence of edge traversals with a single and simple route. Actually, our second
synchronization mechanism implements this idea (this point is refined in Section 5). This was way
the most complicated to set up, as each part of each route in every phase had to be orchestrated very
carefully to permit in fine this low cost synchronization while still ensuring rendezvous. However, it
is through this original and novel way of moving that we finally get the polynomial cost.

4

Basic patterns

In this section we define some sequences of moving instructions, i.e., patterns of moves, that will
serve in turn as building blocks in the construction of our rendezvous algorithm. The main roles of
these patterns are given in the next section when presenting our general solution.

4.1

Pattern Seed

Pattern Seed is involved as a subpattern in the design of all the other patterns presented in this
section. The description of Pattern Seed is given in Algorithm 1. It is made of two periods. For
a given non-negative integer x, the first period of Pattern Seed(x) corresponds to the execution
of x phases, while the second period is a complete backtrack of the path travelled during the first
period. Pattern Seed is designed in such a way that it offers some properties that are shown in
Subsubsection 6.1.2 and that are necessary to conduct the proof of correctness. One of the main
purpose of this pattern is the following: starting from a node v, Pattern Seed(x) allows to visit all
nodes of the grid at distance at most x from v and to traverse all edges of the grid linking two nodes
at distance at most x from v (informally, the procedure permits to cover an area of radius x).
Algorithm 1 Pattern Seed(x)
1: /* First period */
2: for i ← 1; i ≤ x; i ← i + 1 do
3:
/* Phase i */
4:
Perform (N (SE)i (W S)i (N W )i (EN )i )
5: end for
6: /* Second period */
7: L ← the path followed by the agent during the first period
8: Backtrack by following the reverse path L

4.2

Pattern RepeatSeed

Following the high level description of our solution (Section 3), Pattern RepeatSeed is the basic
primitive procedure that implements the first synchronization mechanism (between two consecutive

10

steps of a bit process). An agent a1 executing pattern RepeatSeed(x, n) from a node u processes n
times pattern Seed(x) from node u. All along this execution, a1 stays at distance at most x from u.
Besides, once the execution is over, the agent is back at u.
The description of pattern RepeatSeed is given in Algorithm 2.
Algorithm 2 Pattern RepeatSeed(x, n)
Execute n times Pattern Seed(x)

4.3

Pattern Berry

According to Section 3, Pattern Berry is used in particular to design the specific route that an agent
follows when processing bit 0. The description of Pattern Berry is given in Algorithm 3. It is made
of two periods, the second of which is a backtrack of the first one. Pattern Berry offers several
properties that are proved in Subsubsection 6.1.4 and used in the proof of correctness. Note that,
Pattern Berry(x, y) executed from a node u for any two integers x and y allows an agent to perform
Pattern Seed(x) from each node at distance at most y from u.
Algorithm 3 Pattern Berry(x, y)
1: /* First period */
2: Let u be the current node
3: for i ← 1; i ≤ x + y; i ← i + 1 do
4:
for j ← 0; j ≤ i; j ← j + 1 do
5:
for k ← 0; k ≤ j; k ← k + 1 do
6:
for each node v at distance k from u ordered in the clockwise direction from the North
do
7:
Follow P (u, v)
8:
Execute Seed(i − j)
9:
Follow P (v, u)
10:
end for
11:
end for
12:
end for
13: end for
14: /* Second period */
15: L ← the path followed by the agent during the first period
16: Backtrack by following the reverse path L

4.4

Pattern Cloudberry

Algorithm 4 describes Pattern Cloudberry. According to Section 3, Pattern Cloudberry is used to
design the specific route that an agent follows when processing bit 1. The description of Pattern
Cloudberry is given in Algorithm 4. As for Patterns Seed and Berry, the pattern is made of two
periods, the second of which corresponds to a backtrack of the first one. Properties related to this
pattern are given in Subsubsection 6.1.5. Note that, Pattern Cloudberry(x, y, z, h) executed from a
node u for any integers x, y, z and h allows an agent to perform Pattern Berry(x, y) from each node
at distance at most z from u.
11

Algorithm 4 Pattern Cloudberry(x, y, z, h)
1: /* First period */
2: Let u be the current node
3: Let U be the list of nodes at distance at most z from u ordered in the order of the first visit
when applying Seed(z) from node u
4: for i ← 0; i ≤ 2z(z + 1); i ← i + 1 do
5:
Let v be the node with index h + i (mod 2z(z + 1) + 1) in U
6:
Follow P (u, v)
7:
Execute Seed(x)
8:
Execute Berry(x, y)
9:
Follow P (v, u)
10: end for
11: /* Second period */
12: L ← the path followed by the agent during the first period
13: Backtrack by following the reverse path L

5

Main Algorithm

In this section, we give the formal description of our solution allowing to solve rendezvous in a basic
grid. We also give the main objectives of the involved subroutines and how they work at a high
level. The main algorithm that solves the rendezvous in a basic grid is Algorithm RV (shown in
Algorithm 5). As mentioned in Subsection 3.2, we use the label of an agent only when it has been
transformed. Let us describe this transformation that is borrowed from [17]. Let (b0 b1 . . . bn−1 ) be the
binary representation of the label of an agent. We define its transformed label as the binary sequence
(b0 b0 b1 b1 . . . bn−1 bn−1 01). This transformation permits to obtain the feature that is highlighted by
the following remark.
Remark 2. Given two distinct labels la and lb , their transformed labels are never prefixes of each
other. In other words, there exists an index j such that the jth bit of the transformed label of la is
different from the jth bit of the transformed label of lb .
As explained in Section 3, we need such a feature because our solution requires that at some
point both agents follow different routes by processing different bit values.
Algorithm 5 RV
1: d ← 1
2: while agents have not met yet do
3:
Execute Assumption(d)
4:
d ← 2d
5: end while

Algorithm RV makes use of a subroutine, i.e., Procedure Assumption. When an agent executes
this procedure with a parameter α that is a “good” assumption i.e., that upperbounds the initial
distance D and the value j of the smallest bit position for which both transformed labels differ, we
have the guarantee that rendezvous occurs by the end of this execution. In the rest of this section,
we assume that α is the smallest good assumption that upperbounds D and j.
The code of Procedure Assumption is given in Algorithm 6. It makes use, for technical reasons,
of the sequence r that is defined below.
12

i
3i i i
ρ(1) = 1 and ∀ power of two i ≥ 2, ρ(i) = r( ) + ( (i( + 1) + 1) + 1)
2
2 2 2
∀ power of two i, r(i) = ρ(i) + 3i

Procedure Assumption can be divided into two parts. The first part consists of the execution of
Procedure Harvest (line 1 of Algorithm 6) and corresponds to the second synchronization mechanism
mentioned in Section 3. The main feature of this procedure is the following: when the earlier agent
finishes the execution of Harvest(α) within the execution of Assumption(α), we have the guarantee
that the later agent has at least started to execute Assumption with parameter α (actually, as
explained below, we have even the guarantee that most of Harvest(α) has been executed by the
later agent). Procedure Harvest is presented below. The second part of Procedure Assumption
(cf. lines 2 − 19 of Algorithm 6) consists in processing the bits of the transformed label one by one.
More precisely when processing a given bit in a call to Procedure Assumption(d), the agent acts in
steps 0, 1, . . . , 2d(d + 1): After each of these steps, the agent executes Pattern RepeatSeed whose
role is described below. In each of these steps, the agent executes Berry (resp. Cloudberry) if the
bit it is processing is 0 (resp. 1). These patterns of moves (cf. Algorithms 3 and 4 in Section 4)
are made in such a way that rendezvous occurs by the time any agent finishes the process of its
jth bit in Assumption(α) if we have the following synchronization property. Each time any of both
agents starts executing a step s during the process of its jth bit in Assumption(α), the other agent
has finished the execution of either step s − 1 in the jth bit process of Assumption(α) if s > 0,
or the last step of the (j − 1)th bit process of Assumption(α) if s = 0 (j > 0 in view of the label
transformation given above). To obtain such a synchronization, an agent executes what we called
the first synchronization mechanism in the previous section (cf. line 15 in Algorithm 6) after each
step of a bit process. Actually, this mechanism relies on procedure RepeatSeed, the code of which is
given in Algorithm 1. Note that the total number of steps, and thus of executions of RepeatSeed, in
Assumption(α) is 2α2 (α + 1) + α. For every 0 ≤ i ≤ 2α2 (α + 1) + α, the ith execution of RepeatSeed
in Assumption(α) by an agent permits to force the other agent to finish the execution of its ith
step in Assumption(α) by repeating a pattern Seed (its main purpose is described just above its
code given by Algorithm 2): With the appropriate parameters, this pattern Seed covers any pattern
(Berry or Cloudberry) made in the ith step of Assumption(α) and the number of times it is repeated
is at least the maximal number of edge traversals we can make in the ith step of Assumption(α).
Algorithm 7 gives the code of Procedure Harvest. As in Procedure Assumption, it makes use,
for technical reasons, of two sequences ρ and r that are defined above. Procedure Harvest is made of
two parts: the executions of Procedure P ushP attern (lines 1−3 of Algorithm 7), and the calls to the
patterns Cloudberry and RepeatSeed (lines 4 − 5 of Algorithm 7). When Harvest is executed with
parameter α (which is a good assumption), the first part ensures that the later agent has at least
completed every execution of Assumption with a parameter that is smaller than α, while the second
part ensures that the later agent has completed almost the entire execution of Harvest(α) (more
precisely, when the earlier agent finishes the second part, we have the guarantee that it remains for
the later agent to execute at most the last line before completing its own execution of Harvest(α)).

13

Algorithm 6 Assumption(d)
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:

Execute Harvest(d)
radius ← r(d)
i←1
while i ≤ d do
j←0
while j ≤ 2d(d + 1) do
// Begin of step j
if the length of the transformed label is strictly greater than i, or its ith bit is 0 then
Execute Berry(radius, d)
else
Execute Cloudberry(radius, d, d, j)
end if
// End of step j
radius ← radius + 3d
Execute RepeatSeed(radius, C(Cloudberry(radius − 3d, d, d, j)))
j ←j+1
end while
i←i+1
end while

To give further details on Procedure Harvest, let us first describe Procedure P ushP attern (its
code is given in Algorithm 8). When the earlier agent completes the execution of P ushP attern(2i, d)
with i some power of two, assuming that the later agent had already completed Assumption(i), we
have the guarantee that the later agent has completed its execution of Assumption(2i). To ensure
this, we regard the execution of Assumption(2i) as a sequence of calls to basic patterns (namely
RepeatSeed, Berry and Cloudberry), which is formally defined in Definition 3. This sequence is
what we meant when talking about “the pattern drawn on the grid” in Subsection 3.2. For each
basic pattern p1 in the sequence, the earlier agent executes another pattern p2 at the end of which we
ensure that the later agent has completed p1 . If p1 is either Pattern Berry or Pattern Cloudberry,
then p2 is Pattern RepeatSeed: we use the same idea here as for the first synchronization mechanism.
If p1 is Pattern RepeatSeed, then p2 is Pattern Berry, relying on a property of the route XX (with
X any non-empty route) introduced in the last paragraph of Subsection 3.2: if both agents follow this
route concurrenly from the same node, then they meet. Pattern Seed can be seen as such a route,
and Procedure Berry (whose code is shown in Algorithm 3) consists in executing Pattern Seed from
each node at distance at most α. Hence, unless they meet, the later agent completes its execution
of Pattern RepeatSeed before the earlier one starts executing Seed from the same node. Note that
P ushP attern uses as many patterns as the number of basic patterns in the sequence it is supposed
to push: this and the fact of doubling the value of the input parameter of Procedure Assumption in
Algorithm 5 contribute in particular to keep the polynomiality of our solution.
Thus, once the earlier agent completes the first part of Harvest(α), the later one has at least
started the execution of Assumption(α) (and thus of the first part of Harvest(α)). At this point, we
might think at first glance that we just shifted the problem. Indeed, the number of edge traversals
that has to be made to complete all the executions of Assumption prior to Assumption(α) is quite
the same, if not higher, than the number of edge traversals that has to be made when executing the
first part of Harvest(α). Hence the difference between both agents in terms of edge traversals has not
been improved here. However, a crucial and decisive progress has nonetheless been done: contrary a
priori to the series of Assumption executed before Assumption(d), the first part of Harvest(α) can
be pushed at low cost via the execution of Pattern Cloudberry (line 4 of Algorithm 7) by the earlier

14

agent. Actually this pattern corresponds to the kind of route, described at the end of Subsection 3.2
for the second synchronization mechanism, which is of small length compared to the sequence of
patterns it can push. Indeed, the first part of Harvest(α) can be viewed as a “large” sequence of
Patterns Seed and Berry: however Seed and Berry can be seen (by analogy with Subsection 3.2)
as routes of the form AA and BB respectively, while Pattern Cloudberry executes Seed and Berry
(i.e., AABB) once from at least each node at distance at most α.
Note that when the earlier agent has completed the execution of Pattern Cloudberry in Harvest(α),
the later agent has at least started the execution of Pattern Cloudberry in Harvest(α). Hence, there
is still a difference between both agents, but it has been considerably reduced: it is now relatively
small so that we can handle it pretty easily afterwards.
Algorithm 7 Harvest(d)
1:
2:
3:
4:
5:

for i ← 1; i < d; i ← 2i do
Execute P ushP attern(i, d)
end for
Execute Cloudberry(ρ(d), d, d, 0)
Execute RepeatSeed(r(d), C(Cloudberry(ρ(d), d, d, 0)))

Definition 3 (Basic and Perfect Decomposition). Given a call P to an algorithm, we say that the
basic decomposition of P , denoted by BD(P ), is P itself if P corresponds to a basic pattern, the
type of which belongs to {RepeatSeed; Berry; Cloudberry}. Otherwise, if during its execution P
makes no call then BD(P ) =⊥, else BD(P ) = BD(x1 ), BD(x2 ), . . . , BD(xn ) where x1 , x2 , . . . , xn is
the sequence (in the order of execution) of all the calls in P that are children of P . We say that
BD(P ) is a perfect decomposition if it does not contain any ⊥.
Remark 4. The basic decomposition of every call to Procedure Assumption is perfect.
Algorithm 8 P ushP attern(i, d)
1: for each p in BD(Assumption(i)) do
2:
if p is a call to pattern RepeatSeed with value x as first parameter then
3:
Execute Berry(x, d)
4:
else
5:
/* pattern p is either a call to pattern Berry or a call to pattern Cloudberry (in view of the above remark)
and has at least two parameters */
6:
Let x (resp. y) be the first (resp. the second) parameter of p
7:
Execute RepeatSeed(d + x + 2y, C(Cloudberry(x, y, y, 0)))
8:
end if
9: end for

6

Proof of correctness and cost analysis

The purpose of this section is to prove that Algorithm RV ensures rendezvous in the basic grid at
cost polynomial in D (the initial distance between the agents), and l, the length of the shortest
label. To this end, the section is made of four subsections. The first two subsections are dedicated
to technical results about the basic patterns presented in Section 4 and synchronization properties
of Algorithm RV, which are used in turn to carry out the proof of correctness and the cost analysis
of Algorithm RV that are presented in the last two subsections.

15

6.1

Properties of the basic patterns

This subsection is dedicated to the presentation of some technical materials about the basic patterns
described in Section 4, which will be used in the proof of correctness of Algorithm 5 solving rendezvous
in a basic grid.
6.1.1

Vocabulary

Before going any further, we need to introduce some extra vocabulary in order to facilitate the
presentation of the next properties and lemmas.
Definition 5. A pattern execution A precedes another pattern execution B if the beginning of A
occurs before the beginning of B.
Definition 6. Two pattern executions A and B are concurrent iff:
• pattern execution A does not finish before pattern execution B starts
• pattern execution B does not finish before pattern execution A starts
By misuse of langage, in the rest of this paper we will sometimes say “a pattern” instead of “a
pattern execution”.
Hereafter we say that a pattern A concurrently precedes a pattern B, iff A and B are concurrent,
and A precedes B.
Definition 7. A pattern A pushes a pattern B in a set of executions E, if for every execution of E
in which B concurrently precedes A, agents meet before the end of the execution of B, or B finishes
before A.
In the sequel, given two sequences of moving instructions X and Y , we will say that X is a prefix
of Y if Y can be viewed as the execution of the sequence X followed by another sequence possibly
empty.
6.1.2

Pattern Seed

In this subsubsection, we show some properties related to Pattern Seed.
Proposition 8 follows by induction on the input parameter of Pattern Seed and Proposition 9
follows from the description of Algorithm 1.
Proposition 8. Let x be an integer. Starting from a node v, Pattern Seed(x) guarantees the following properties:
1. it allows to visit all nodes of the grid at distance at most x from v
2. it allows to traverse all edges of the grid linking two nodes at distance at most x from v
Proposition 9. Given two integers x1 ≤ x2 , the first period of Pattern Seed(x1 ) is a prefix of the
first period of Pattern Seed(x2 ).
Lemma 10. Let x1 and x2 be two integers such that x1 ≤ x2 . Let a1 and a2 be two agents executing
respectively Patterns Seed(x1 ) and Seed(x2 ) both from the same node such that the execution of
Pattern Seed(x1 ) concurrently precedes the execution of Pattern Seed(x2 ). Let t1 (resp. t2 ) be the
time when agent a1 (resp. a2 ) completes the execution of Pattern Seed(x1 ) (resp. Seed(x2 )). Agents
a1 and a2 meet by time min(t1 , t2 ).
16

Proof. Consider a node u and a first agent a1 executing Pattern Seed(x1 ) from u with x1 any integer.
Suppose that the execution of Seed(x1 ) by a1 concurrently precedes the execution of Pattern Seed(x2 )
by another agent a2 still from node u with x1 ≤ x2 .
According to Proposition 9, the first period of Seed(x1 ) is a prefix of the first period of Pattern Seed(x2 ). If the path followed by agent a1 during its execution of Seed(x1 ) is e1 , e2 , . . . , en ,
e1 , e2 , . . . , en (the overlined part of the path corresponds to the backtrack), then the path followed
by agent a2 during the execution of Pattern Seed(x2 ) is e1 , e2 , . . . , en , s, e1 , e2 , . . . , en , s where s corresponds to the edges traversed at a distance ∈ {x1 + 1; . . . ; x2 }. When a2 starts executing the path
e1 , e2 , . . . , en , a1 is on the path e1 , e2 , . . . , en , e1 , e2 , . . . , en . Thus, either a2 catches a1 when the latter
is following e1 , e2 , . . . , en , or they meet while a1 follows e1 , e2 , . . . , en .
Thus, if the execution of Seed(x1 ) by a1 concurrently precedes the execution of Seed(x2 ) by agent
a2 both executed from the same node, agents meet by the end of these executions.
6.1.3

Pattern RepeatSeed

This subsubsection is dedicated to some properties of Pattern RepeatSeed. Informally speaking,
Lemmas 11 and 12 describe the fact that Pattern RepeatSeed pushes respectively Pattern Berry
and Cloudberry when it is given appropriate parameters.
Lemma 11. Consider two nodes u and v separated by a distance δ. If Pattern Berry(x1 , y) is
executed from node v and Pattern RepeatSeed(x2 , n) is executed from node u with x1 , x2 , y and n
integers such that x2 ≥ x1 + y + δ and n ≥ C(Berry(x1 , y)) then Pattern RepeatSeed(x2 , x) pushes
Pattern Berry(x1 , y).
Proof. Assume that, in the grid, there are two agents a1 and a2 . Denote by u and v their respective initial positions. Suppose that u and v are separated by a distance δ. Assume that
agent a1 starts executing Pattern RepeatSeed(x2 , n) from node u and agent a2 performs Pattern
Berry(x1 , y) on node v (with n ≥ C(Berry(x1 , y)) and x2 ≥ x1 + y + δ). Also suppose that Pattern
Berry(x1 , y) concurrently precedes Pattern RepeatSeed(x2 , n). Let us suppose by contradiction,
that RepeatSeed(x2 , n) does not push Berry(x1 , y), which means, by Definition 7 that at the end of
the execution of RepeatSeed(x2 , n) by a1 , agents have not met and a2 has not finished executing its
Berry(x1 , y).
When executing its Berry(x1 , y) agent a2 can not be at a distance greater than x1 + y from its
initial position, and can not be at a distance greater than δ + x1 + y from node u. Besides, in view
of Proposition 8, each Pattern Seed(x2 ) (which composes Pattern RepeatSeed(x2 , n)) from node u
allows to visit all nodes and to traverse all edges at distance at most x2 from node u. Thus, each
Pattern Seed(x2 ) executed from node u allows to visit all nodes and to traverse all edges (although
not necessarily in the same order) that are traversed during the execution of Pattern Berry(x1 , y)
from node v.
Consider the position of agent a2 when a1 starts executing any of the Seed(x2 ) which compose
Pattern RepeatSeed(x2 , n), and when a1 has completed it. If a2 has not completed a single edge
traversal, then whether it was in a node or traversing an edge, it has met a1 which traverses every
edge a2 traverses during its execution of Pattern Berry(x1 , y). As this contradicts our hypothesis,
each time a1 completes one of its executions of Pattern Seed(x2 ), a2 has completed at least an edge
traversal. As agent a1 executes n ≥ C(Berry(x1 , y)) times Pattern Seed(x2 ) then a2 traverses at
least C(Berry(x1 , y)) edges before a1 finishes executing its RepeatSeed(x2 , n). As C(Berry(x1 , y)) is
the number of edge traversals in Berry(x1 , y), when a1 finishes executing Pattern RepeatSeed(x2 , n),
17

a2 has finished executing its Pattern Berry(x1 , y), which contradicts our assumption and proves the
lemma.
Lemma 12. Consider two nodes u and v separated by a distance δ. If Pattern Cloudberry(x1 , y, z, h)
is executed from node v (with x1 , y, z and h integers) and Pattern RepeatSeed(x2 , n) is executed from
u such that x2 ≥ x1 + y + z + δ and n ≥ C(Cloudberry(x1 , y, z, h)) then Pattern RepeatSeed(x2 , n)
pushes Pattern Cloudberry(x1 , y, z, h).
Proof. Using similar arguments to those used in the proof of Lemma 11, we can prove Lemma 12.
6.1.4

Pattern Berry

This subsubsection is dedicated to the properties of Pattern Berry. Informally speaking, Lemma 14
describes the fact that Pattern Berry permits to push Pattern RepeatSeed when it is given appropriate parameters. Proposition 13 and Lemma 15 are respectively analogous to Proposition 9 and
Lemma 10.
According to Algorithm 3, we have the following proposition.
Proposition 13. Given four integers x1 + y1 ≤ x2 + y2 , the first period of Pattern Berry(x1 , y1 ) is
a prefix of the first period of Pattern Berry(x2 , y2 ).
Lemma 14. Consider two nodes u and v separated by a distance δ. Let RepeatSeed(x1 , n) and
Berry(x2 , y) be two patterns respectively executed from nodes u and v with x1 , x2 , y and n integers.
If y ≥ δ and x1 ≤ x2 then Pattern Berry(x2 , y) pushes Pattern RepeatSeed(x1 , n).
Proof. Assume that there are two agents a1 and a2 initially separated by a distance δ. Assume that
their respective initial positions are node u and node v. Agent a2 executes Pattern RepeatSeed(x1 , n)
centered on v with x1 and n any integers. This execution of Pattern RepeatSeed(x1 , n) concurrently
precedes the execution of Pattern Berry(x2 , y) by a1 with y ≥ δ and x1 ≤ x2 . When executing
this Pattern, agent a1 performs Pattern Seed(x2 ) from each node at distance at most y from u with
y ≥ δ. So, at some point a1 executes Pattern Seed(x2 ) centered on node v. Since x2 ≥ x1 , by
Lemma 10, if a2 has not finished executing its RepeatSeed(x1 , n) when a1 starts executing Pattern
Seed(x2 ) from v, then agents meet by the end of the latter.
Hence, to avoid rendezvous the adversary must choose an execution in which the speed of agent
a2 is such that it completes all executions of Patterns Seed(x1 ) inside RepeatSeed(x1 , n) before a1
starts the execution of Pattern Seed(x2 ) centered on v.
Let t1 (resp. t2 ) be the time when agent a1 (resp. a2 ) completes its execution of Pattern
Berry(x2 , y) (resp. RepeatSeed(x1 , n)). Thus, if the execution of Pattern RepeatSeed(x1 , n) by a2
concurrently precedes the execution of Pattern Berry(x2 , y) by agent a1 , either t2 ≤ t1 or the agents
meet by time min(t1 , t2 ).
Lemma 15. Consider two agents a1 and a2 executing respectively Patterns Berry(x1 , y1 ) and
Berry(x2 , y2 ) both from node u with x1 , x2 , y1 and y2 integers such that x2 + y2 ≥ x1 + y1 . Suppose that the execution of Berry(x1 , y1 ) by a1 concurrently precedes the execution of Berry(x2 , y2 )
by a2 . Let t1 (resp. t2 ) be the time when agent a1 (resp. a2 ) completes its execution of Pattern
Berry(x1 , y1 ) (resp. Berry(x2 , y2 )). Agents a1 and a2 meet by time min(t1 , t2 ).
Proof. Consider a node u and a first agent a1 executing Pattern Berry(x1 , y1 ) from u with x1 and
y1 two integers. Suppose that the execution of Pattern Berry(x1 , y1 ) by a1 concurrently precedes
an execution of Pattern Berry(x2 , y2 ) by another agent a2 still from node u with x2 + y2 ≥ x1 + y1 .
18

This proof is similar to the proof of Lemma 10. According to Proposition 13, if the path followed
by agent a1 during its execution of Berry(x1 , y1 ) is e1 , e2 , . . . , en , e1 , e2 , . . . , en (the overlined part of
the path corresponds to the backtrack), then the path followed by agent a2 during the execution of
Pattern Berry(x2 , y2 ) is e1 , e2 , . . . , en , s, e1 , e2 , . . . , en , s where s corresponds to the edges traversed
from the x1 + y1 + 1-th iteration of the main loop of Pattern Berry to its x2 + y2 -th iteration.
Thus, either a2 catches a1 when the latter is following e1 , e2 , . . . , en , or they meet while a2 follows
e1 , e2 , . . . , en .
Let t1 (resp. t2 ) be the time when agent a1 (resp. a2 ) completes its execution of Pattern
Berry(x1 , y1 ) (resp. Berry(x2 , y2 )). In the same way as in the proof of Lemma 10, if the execution
of Berry(x1 , y1 ) by a1 concurrently precedes the execution of Berry(x2 , y2 ) by agent a1 both executed
from the same node, the agents meet by time min(t1 , t2 ).
6.1.5

Pattern Cloudberry

Informally speaking, the following lemma highlights the fact that Pattern Cloudberry can push “a
lot of basic patterns” under some conditions. In other words, we can force an agent to make a lot of
edge traversals “at relative low cost”.
Lemma 16. Consider two nodes u and v separated by a distance δ. Consider a sequence S of Patterns
RepeatSeed and Berry executed from u, and a Pattern Cloudberry(x, y, z, h) executed from v (with
x, y, z and h four integers) such that z ≥ δ and the execution of S concurrently precedes the execution
of Pattern Cloudberry(x, y, z, h). If for each Pattern RepeatSeed R and Pattern Berry B belonging
to S, x + y is greater than or equal to the sum of the parameters of B, and x is greater than or equal
to the first parameter of R, then the execution of Pattern Cloudberry(x1 , y1 , z, h) from v pushes S.
Proof. Let a2 be an agent executing a sequence S of Patterns RepeatSeed and Berry from a node u.
Suppose that there exist two integers x1 and y1 such that each Pattern Berry B inside the sequence
is assigned parameters the sum of which is at most x1 + y1 , and such that each Pattern RepeatSeed
R of the sequence is assigned a first parameter which is at most x1 . Let v be another node separated
from u by a distance δ. Suppose that another agent a1 executes Pattern Cloudberry(x1 , y1 , z, h)
from v with z ≥ δ and h two integers.
In order to prove that the execution of Pattern Cloudberry(x1 , y1 , z, h) by a1 pushes the sequence
of Patterns S, let us suppose by contradiction that there exists an execution in which S concurrently
precedes Cloudberry(x1 , y1 , z, h), and that by the end of the execution of Cloudberry(x1 , y2 , z, h) by
a1 , a2 neither has met a1 nor has finished executing its whole sequence of patterns.
According to Algorithm Cloudberry, when executing Cloudberry(x1 , y1 , z, h), a1 executes Pattern
Seed(x) followed by Pattern Berry(x, y) on each node at distance at most z from v. As z ≥ δ, during
its execution of Cloudberry(x1 , y1 , z, h), a1 follows P (v, u), executes Pattern Seed(x1 ) (denoted by
p1 ) and then Pattern Berry(x1 , y1 ) (denoted by p2 ) both from node u. In order to prove that the
execution of Cloudberry(x1 , y1 , z, h) by a1 pushes the execution of S by a2 , we are going to prove
that if a2 has not finished executing S when a1 starts executing p1 and p2 , agents meet. This will
imply that the adversary has to make a2 complete S before a1 starts executing p1 and p2 in order
to prevent the agents from meeting, and will thus prove the lemma.
By assumption, a2 has not finished executing S when a1 arrives on u to execute p1 and p2 . Let
us consider what it can be executing at this moment. If it is executing Pattern Seed(x2 ) with x2 any
integer, then by assumption, x2 ≤ x1 and by Lemma 10, agents meet by the end of the execution of
p1 , which contradicts the assumption that agents do not meet by the end of Cloudberry(x1 , y1 , z, h).
19

It means that when a1 starts executing p1 , a2 is executing Pattern Berry(x2 , y2 ) for any integers x2
and y2 such that x2 + y2 ≤ x1 + y1 . After p1 , a1 executes p2 . By Lemma 15, if a2 is still executing
Pattern Berry(x2 , y2 ) for any integers x2 and y2 such that x2 + y2 ≤ x1 + y1 (the same as above, or
another) then the agents meet by the end of the execution of p2 which contradicts our assumption
once again. As a consequence, when a1 starts executing p2 , a2 is executing Pattern Seed(x3 ) for an
integer x3 ≤ x1 . Denote by p3 this pattern, and remember that a2 can not have started it before
a1 starts executing p1 . Moreover, when a1 starts executing p2 , a2 can not be in u as it is the node
where a1 starts p2 , thus it has at least started traversing the first edge of p3 . Hence, p1 concurrently
precedes p3 , and p1 ends up before p3 .
By Algorithm Seed, like in the proof of Lemma 10, we can denote by e1 , . . . , en , e1 , . . . , en the
route followed by a2 when executing p3 and by e1 , . . . , en , s, e1 , . . . , en , s the route followed by a1 when
executing p1 where s corresponds to edges traversed at a distance belonging to {x2 + y2 + 1; . . . ; x1 +
y1 }. Remark that according to the definition of a backtrack, e1 , . . . , en , s = s, e1 , . . . , en . Consider
the moment t1 when a2 finishes the first period of p3 and begins the second one. It has just traversed
e1 , . . . , en , and is about to execute e1 , . . . , en . At this moment, a1 can not have traversed the edges
e1 , . . . , en , or else agents have met by t1 , which would contradict our assumption. However, as p1
is completed before p3 , a1 must finish executing s, e1 , . . . , en before a2 finishes executing e1 , . . . , en
which implies that agents meet by the end of the execution of p1 and contradicts once again the
hypothesis that they do not meet by the end of p2 .
So, in every case, it contradicts the assumption that by the end of the execution of Pattern
Cloudberry(x1 , y1 , z, h), a2 neither has met a1 nor has finished executing S. Hence, the execution of
Pattern Cloudberry(x1 , y1 , z, h) by a1 pushes the execution of S by a2 , and the lemma holds.

6.2

Agents synchronizations

We recall the reader that D is the initial distance separating the two agents in the basic grid.
The aim of this subsection is to introduce and prove several synchronization properties our
algorithms offer (cf., Lemmas 20 and 21). By “synchronization” we mean that if one agent has
completed some part of its rendezvous algorithm, then either it must have met the other agent or
this other agent has also completed some part (not necessarily the same one) of its algorithm i.e., it
must have made progress.
To prove Lemmas 20 and 21, we first need to show some more technical results—Lemmas 17, 18,
and 19.
Lemma 17. Let u and v be the two nodes initially occupied by the agents a1 and a2 . Let d1 and
d2 ≥ D be two powers of two not necessarily different from each other. If agent a2 executes Procedure
Assumption(d1 ) from node u and agent a1 executes Procedure P ushP attern(d1 , d2 ) from node v, then
Procedure P ushP attern(d1 , d2 ) pushes Procedure Assumption(d1 ).
Proof. Consider two agents a1 and a2 . Their respective initial nodes are u and v, which are separated
by a distance D. Assume that a2 executes Procedure Assumption(d1 ) with d1 any power of two, and
that a1 executes P ushP attern(d1 , d2 ) with d2 ≥ D any other power of two. Assume by contradiction
that the execution of Assumption(d1 ) by agent a2 concurrently precedes the execution of Procedure
P ushP attern(d1 , d2 ) by a1 , and that by the end of the execution of the latter, neither agents have
met, nor the execution of Procedure Assumption(d1 ) is completed.
According to Algorithm 8, there are as many basic patterns (from {RepeatSeed; Berry; Cloudberry})
in BD(P ushP attern(d1 , d2 )) as in BD(Assumption(d1 )). We denote by n this number of basic patterns. Each basic pattern inside BD(P ushP attern(d1 , d2 )) and BD(Assumption(d1 )) is
20

given an index between 1 and n according to their order of appearance. According to Remark 4,
BD(Assumption(d1 )) is perfect. This means that when agent a2 starts the execution of Assumption(d1 ),
this agent starts the execution of the first basic pattern in BD(Assumption(d1 )), that when agent a2
completes the execution of Assumption(d1 ), it completes the execution of the n-th basic pattern in
BD(Assumption(d1 )), and that, for any integer i between 1 and n − 1, agent a2 does not make any
edge traversal between the i-th and the (i + 1)-th basic pattern in BD(Assumption(d1 )). Every edge
traversal agent a2 makes during the execution of Procedure Assumption(d1 ) is performed during one
of the basic patterns inside BD(Assumption(d1 )). Remark that BD(P ushP attern(d1 , d2 )) is also
perfect.
Suppose that for any integer i between 1 and n, by the end of the execution of the i-th pattern
inside BD(P ushP attern(d1 , d2 )), agents have met or the execution by a2 of the i-th pattern inside
BD(Assumption(d1 )) is over. We get a contradiction, as it means that, by the end of the execution
of Procedure P ushP attern(d1 , d2 ) by a1 (and thus by the end of the n-th pattern of BD(P ushP attern(d1 , d2 ))), agents have met or the execution of the n-th pattern inside BD(Assumption(d1 ))
(and thus Assumption(d1 ) itself) by a2 is over. As a consequence, there exists an integer i between
1 and n, such that by the end of the execution of the i-th pattern inside BD(P ushP attern(d1 , d2 ))
by a1 , agents have not met, and the execution by a2 of the i-th pattern inside BD(Assumption(d1 ))
is not over. Without loss of generality, let us make the assumption that i is the smallest positive
integer, such that by the end of the execution of the i-th pattern inside BD(P ushP attern(d1 , d2 ))
by a1 , agents have not met, and the execution by a2 of the i-th pattern inside BD(Assumption(d1 ))
is not over.
Let us first show that the execution of the i-th pattern inside BD(Assumption(d1 )) concurrently precedes the execution of the i-th pattern inside BD(P ushP attern(d1 , d2 )). If i = 1, since
Assumption(d1 ) concurrently precedes P ushP attern(d1 , d2 ), the i-th pattern inside BD(Assumption(d1 ))
concurrently precedes the i-th pattern inside BD(P ushP attern(d1 , d2 )). If i > 1 and the i-th pattern inside BD(Assumption(d1 )) does not concurrently precede the i-th pattern inside BD(P ushP attern(d1 , d2 )), then the i-th pattern inside BD(Assumption(d1 )) does not begin before the i-th
pattern inside BD(P ushP attern(d1 , d2 )), which implies that the (i−1)-th pattern inside BD(Assumption(d1 ))
ends after the (i − 1)-th pattern inside BD(P ushP attern(d1 , d2 )), which contradicts the hypothesis
that i is the smallest positive integer, such that by the end of the i-th pattern inside BD(P ushP attern(d1 , d2 )), agents have not met, and the i-th pattern inside BD(Assumption(d1 )) is not over.
This means that the i-th pattern inside BD(Assumption(d1 )) concurrently precedes the i-th pattern
inside BD(P ushP attern(d1 , d2 )).
According to Lemmas 11, 12 and 14, Algorithm P ushP attern and the fact that d2 ≥ D, whatever
the type of the i-th pattern inside BD(Assumption(d1 )) (Berry, Cloudberry or RepeatSeed), the
i-th pattern inside BD(P ushP attern(d1 , d2 )) pushes it. In particular, if the i-th pattern inside
BD(Assumption(d1 )) is a Berry or a Cloudberry called after the test at Line 8, at Line 9 or 11,
the i-th pattern inside BD(P ushP attern(d1 , d2 )) pushes it regardless of which of the two patterns it
is. Indeed, for any integers x and h, Cloudberry(x, d1 , d1 , h) is composed of several Berry(x, d1 ) so
that C(Cloudberry(x, d1 , d1 , h)) ≥ C(Berry(x, d1 )). As the i-th pattern inside BD(Assumption(d1 ))
concurrently precedes the i-th pattern inside BD(P ushP attern(d1 , d2 )), this contradicts the fact that
by the end of the i-th pattern inside BD(P ushP attern(d1 , d2 )), agents have not met, and the i-th
pattern inside BD(Assumption(d1 )) is not over.
We then get a contradiction regardless of the case, which proves the lemma.
Lemma 18. Let d1 be any power of two, and x be any integer such that the first parameter of each

21

basic pattern inside BD(Assumption(d1 )) is assigned a value which is at most x. For every power
of two d2 ≥ d1 , the first parameter of each basic pattern inside BD(P ushP attern(d1 , d2 )) is lower
than or equal to x + 3d2 .
Proof. We prove this lemma by contradiction. Make the assumption that there exists a power of two
d1 and an integer x1 such that the first parameter of each basic pattern inside BD(Assumption(d1 ))
is given a value lower than or equal to x1 . Also suppose that there exists a call to a basic pattern
inside BD(P ushP attern(d1 , d2 )) for some power of two d2 ≥ d1 in which the first parameter is given
a value greater than x1 + 3d2 . According to Algorithm P ushP attern, in BD(P ushP attern(d1 , d2 ))
there cannot be any call to basic Pattern Cloudberry, and each basic pattern inside BD(P ushP attern(d1 , d2 )) and BD(Assumption(d1 )) is given an index between 1 and n according to their
order of appearance, with n the number of basic patterns in either of these decompositions. Thus,
for any integer i between 1 and n, there is a pair of patterns (p1 , p2 ) such that p1 is the i-th basic
pattern inside BD(Assumption(d1 )), and p2 is the i-th pattern inside BD(P ushP attern(d1 , d2 )). We
consider any pair (p1 , p2 ) such that the first parameter of p2 is given a value greater than x1 + 3d2 ,
and we analyse three cases depending on the type of pattern p1 . By assumption, the first parameter
of p1 is x1 .
Let us first consider the case in which p1 is Pattern RepeatSeed(x2 , n1 ) with x2 and n1 any two
integers. According to Algorithm 8, since p1 is Pattern RepeatSeed(x2 , n1 ), p2 is Berry(x2 , d2 ). By
assumption, the first parameter of p2 is greater than x1 +3d2 , which contradicts our other assumption
that the first parameter of p1 is at most x1 .
Thus, p1 is either Pattern Berry or Pattern Cloudberry. In BD(Assumption(d1 )), whether it
is called directly by Procedure Assumption(d1 ), or inside its call to Harvest(d1 ), or inside the call
of the latter to P ushP attern(d3 , d1 ) with a power of two d3 < d1 , the second parameter of Pattern
Berry is always d1 , and the second and third parameters of Pattern Cloudberry are always d1 as
well. Let p1 be Pattern Berry(x2 , d1 ) with any integer x2 ≤ x1 . According to Algorithm 8, p2 is
RepeatSeed(d1 + d2 + x2 , C(Berry(x2 , d1 ))). This implies that the first parameter of Pattern p2 i.e.,
d1 + d2 + x2 is greater than x1 + 3d2 . This means that x2 > x1 − d1 + 2d2 > x1 which contradicts
the assumption that the first parameter of p1 is at most x1 .
At last, according to Algorithm 8, if p1 is Pattern Cloudberry(x2 , d1 , d1 , h) with two integers
h and x2 ≤ x1 , p2 is RepeatSeed(d2 + 2d1 + x2 , C(Cloudberry(x2 , d1 , d1 , h))). This implies that
the first parameter of Pattern p2 i.e., d2 + 2d1 + x2 is greater than x1 + 3d2 . This means that
x2 > x1 + 2d2 − 2d1 > x1 which also contradicts the assumption that the first parameter of p1 is at
most x1 .
Hence, within BD(P ushP attern(d1 , d2 )), there cannot be a call to a basic pattern in which the
first parameter is assigned a value greater than x1 + 3d2 , which proves the lemma.
Lemma 19. Let d1 be a power of two. The first parameter of each basic pattern inside BD(Assumption(d1 ))
is at most ρ(2d1 ) − 3d1 .
Proof. We prove this lemma by induction on d1 .
Let us first consider that d1 = 1, and prove that the first parameter of each basic pattern inside
BD(Assumption(1)) is at most ρ(2) − 3. Let us assume by contradiction that there exists a basic
pattern inside BD(Assumption(1)) for which the first parameter is given a value greater than ρ(2)−3.
Denote by p such a pattern. Procedure Assumption(1) begins with Harvest(1) which is composed
of calls to Cloudberry(ρ(1), 1, 1, 0) and RepeatSeed(r(1), C(Cloudberry(1, 1, ρ(1), 0))). As ρ(1) and
r(1) are lower than ρ(2) − 3, pattern p does not belong to BD(Harvest(1)). As a consequence,
22

pattern p is called after Harvest(1). After Harvest(1), the first parameter that is given to the
patterns called in Procedure Assumption(1) is always at most ρ(2) − 3. Indeed, the first parameter
is assigned its maximal value when j = 2d1 (d1 + 1) = 4 and i = d1 = 1 in the while loop i.e., when
3d1 = 3 has been added i(j + 1) = 5 times to r(d1 ) = r(1), which gives a maximal value equal to
r(d1 ) + 3d21 (2d1 (d1 + 1) + 1) = r(1) + 15 = ρ(2d1 ) − 3d1 = ρ(2) − 3. We then get a contradiction with
the existence of p since its first parameter is lower than or equal to ρ(2) − 3.
Let us now assume that there exists a power of two d2 such that for each power of two d3 ≤ d2 , the
first parameter of each basic pattern inside BD(Assumption(d3 )) is at most ρ(2d2 ) − 3d2 , and prove
that the first parameter of each basic pattern inside BD(Assumption(2d2 )) is at most ρ(4d2 ) − 6d2 .
Let us assume by contradiction that there exists a basic pattern p inside BD(Assumption(2d2 )) which
is assigned a first parameter that is greater than ρ(4d2 ) − 6d2 . Procedure Assumption(2d2 ) begins
with Harvest(2d2 ) which in turn, begins with P ushP attern(1, 2d2 ), . . . , P ushP attern(d2 , 2d2 ).
According to the definition of a basic decomposition, if p is called by P ushP attern(1, 2d2 ), . . . ,
P ushP attern(d2 , 2d2 ), it belongs to BD(P ushP attern(1, 2d2 )), . . . , BD(P ushP attern(d2 , 2d2 )).
By induction hypothesis, inside BD(Assumption(1)), . . . , BD(Assumption(d2 )), the first parameter of each basic pattern is at most ρ(d2 ) − 3d2 . According to Lemma 18, inside BD(P ushP attern(1, 2d2 )), . . . , BD(P ushP attern(d2 , 2d2 )), the first parameter of each basic pattern is at
most ρ(d2 ) + 3d2 = r(d2 ) ≤ ρ(2d2 ) − 6d2 . Moreover, after P ushP attern(1, 2d2 ), . . . , P ushP attern(d2 , 2d2 ), Harvest(2d2 ) executes Pattern Cloudberry(ρ(2d2 ), 2d2 , 2d2 , 0) followed by Pattern RepeatSeed(r(2d2 ), C(Cloudberry(2d2 , 2d2 , ρ(2d2 ), 0))). Inside these calls, the first parameter
is respectively given the values ρ(2d2 ) and r(2d2 ) which are both lower than ρ(4d2 ) − 6d2 . As a
consequence, p does not belong to BD(Harvest(2d2 )). This means that this pattern is called after
Harvest(2d2 ). However, in the same way as when d1 = 1, we can show that the first parameter
keeps increasing and reaches a maximal value equal to r(2d2 ) + 12d22 (4d2 (2d2 + 1) + 1) = ρ(4d2 ) − 6d2
which contradicts the existence of a basic pattern inside BD(Assumption(2d2 )) which is assigned a
first parameter that is greater than ρ(4d2 ) − 6d2 , and then proves the lemma.
Before presenting the next lemma, we need to introduce the following notions. We say that the
first four lines of Algorithm Harvest are its first part, and that the last line is the second part.
Procedure Assumption begins with a call to Procedure Harvest: We will consider that the first
part of Procedure Assumption is the first part of this call, and that the second part of Procedure
Assumption is the second part of this call. After these two parts, there is a third part in Procedure
Assumption which consists of calls to basic patterns. Moreover, note that the execution of Algorithm
RV can be viewed as a sequence of consecutive calls to Procedure Assumption with an increasing
parameter. We will say that the (i + 1)-th call to Procedure Assumption (i.e., the call to Procedure
Assumption(2i ) by an agent executing Algorithm RV is Phase i.
Lemma 20. Consider two agents executing Algorithm RV. Let i be an integer such that 2i ≥ D. If
rendezvous has not occurred before, at the end of the execution by any of both agents of the second
part of Phase i, the other agent has finished executing the first part of Phase i.
Proof. Let a1 and a2 be two agents executing Algorithm RV. Let i1 and d1 be two integers such
that 2i1 = d1 ≥ D. Assume by contradiction that at the end of the execution of the second part
of Phase i1 by a1 , agents have not met and a2 has not completed its execution of the first part of
Phase i1 .
By assumption, when a1 finishes executing the second part of Phase i1 , a2 is either executing
Phase i2 for an integer i2 < i1 , or the first part of Phase i1 .
23

First of all, let us show that when a1 finishes executing the sequence P ushP attern(1, d1 ),
. . . , P ushP attern(2i1 −1 , d1 ) (i.e., the loop at the beginning of procedure Harvest(d1 )), a2 cannot be executing Phase i2 for an integer i2 < i1 . Indeed, in view of Lemma 17 and the fact that
d1 ≥ D, we know that the sequence P ushP attern(1, d1 ), . . . , P ushP attern(2i1 −1 , d1 ) pushes the
sequence Assumption(1), . . . , Assumption(2i1 −1 ). This means that by the time a1 finishes P ushP attern(2i1 −1 , d1 ), the agents have met or a2 has finished executing Procedure Assumption(2i1 −1 )
i.e., Phase (i1 − 1). Given that by assumption, agents do not meet before a1 completes its execution of the first part of Phase i1 , when a1 finishes executing the loop at the beginning of procedure
Harvest(d1 ), a2 is executing the first part of Phase i1 .
Let us now show that when a1 finishes executing Cloudberry(ρ(d1 ), d1 , d1 , 0), a2 has finished
executing the loop at the beginning of Procedure Harvest(d1 ). According to Lemmas 18 and 19,
inside this loop, the first parameter which is assigned to Patterns RepeatSeed and Berry is at
most ρ(d1 ). Besides, while executing this loop, a2 executes a sequence of Patterns RepeatSeed and
Berry called by Procedure P ushP attern. Since d1 ≥ D, according to Lemma 16, the execution of
Cloudberry(ρ(d1 ), d1 , d1 , 0) by a1 pushes the execution by a2 of the loop at the beginning of Procedure
Harvest(d1 ). By assumption, when a1 finishes executing Cloudberry(ρ(d1 ), d1 , d1 , 0), agents have
not met which implies that a2 has finished executing the loop.
After executing Pattern Cloudberry(ρ(d1 ), d1 , d1 , 0) but before completing Procedure Harvest(d1 ),
a1 performs RepeatSeed(r(d1 ), C(Cloudberry(ρ(d1 ), d1 , d1 , 0))). According to Lemma 12, as r(d1 ) =
ρ(d1 ) + 3d1 , the execution of RepeatSeed(r(d1 ), C(Cloudberry(ρ(d1 ), d1 , d1 , 0))) by a1 pushes the
execution of Cloudberry(ρ(d1 ), d1 , d1 , 0) by a2 . Still by assumption, when a1 finishes executing
RepeatSeed(r(d1 ), C(Cloudberry(ρ(d1 ), d1 , d1 , 0))), agents have not met, and thus a2 has finished
executing Cloudberry(ρ(d1 ), d1 , d1 , 0). This means that when a1 finishes executing Harvest(d1 ) and
thus the second part of Phase i1 , a2 has completed the execution of the first part of Phase i1 , which
proves the lemma.
In the hereafter lemma, we focus on the calls to Pattern RepeatSeed in the second and in the
third part of Procedure Assumption(d1 ) for any power of two d1 . In the statement and proof of this
lemma, they are called “synchronization RepeatSeed”, and indexed from 1 to d1 (2d1 (d1 +1)+1)+1) in
their ascending execution order in these two parts of the procedure. The call to Pattern RepeatSeed
in the second part of Procedure Assumption is the first (indexed by 1) synchronization RepeatSeed
during an execution of Procedure Assumption(d1 ) for any power of two d1 .
Lemma 21. Let a1 and a2 be two agents executing Algorithm RV. Let u and v be their respective
initial nodes separated by a distance D. For every power of two d1 ≥ D and every positive integer i, if
agents have not met yet, then when one agent finishes executing the i-th synchronization RepeatSeed
of Assumption(d1 ), the other agent has at least started executing the i-th synchronization RepeatSeed
of Assumption(d1 ).
Proof. Consider two nodes u and v separated by a distance D, and two agents a1 and a2 respectively
located on u and v. Suppose that agent a1 has just finished executing the i-th synchronization
RepeatSeed inside Procedure Assumption(d1 ) with any power of two d1 ≥ D and any positive
integer i. Let us prove by induction on i that if rendezvous has not occurred yet a2 has at least
started executing this i-th synchronization RepeatSeed.
Let us first consider the case in which i = 1. The synchronization RepeatSeed a1 has just
finished executing is called at the end of the execution of Procedure Harvest(d1 ) called at Line 1
of Procedure Assumption(d1 ). As d1 ≥ D, by Lemma 20, when a1 finishes executing Pattern
24

RepeatSeed, and thus Harvest(d1 ), agents have met or a2 has completed the execution of the
first part of Procedure Assumption(d1 ). This means that when a1 has finished executing the first
synchronization RepeatSeed, either agents have met or a2 has at least begun the execution of the
first synchronization RepeatSeed.
Let us now make the assumption that, for every power of two d1 ≥ D, during an execution of
Procedure Assumption(d1 ), there exists an integer j between 1 and d1 (2d1 (d1 + 1) + 1) such that
when agent a1 has finished executing the j-th synchronization RepeatSeed, either agents have met
or a2 has at least begun the execution of the j-th synchronization RepeatSeed, and prove that when
a1 has finished executing the (j + 1)-th synchronization RepeatSeed, either agents have met or a2
has at least begun the execution of the (j + 1)-th synchronization RepeatSeed. Let us assume by
contradiction that when a1 has finished executing the (j + 1)-th synchronization RepeatSeed, a2 has
neither met a1 nor started executing the (j + 1)-th synchronization RepeatSeed.
After executing the j-th synchronization RepeatSeed, a1 executes Line 9 or Line 11 of Algorithm
Assumption(d1 ) and thus either Pattern Berry or Pattern Cloudberry, depending on the bits of its
transformed label. By Lemmas 14 and 16, as d1 ≥ D, if a2 is still executing the j-th synchronization
RepeatSeed, whichever pattern a1 executes, it pushes the execution of the j-th synchronization
RepeatSeed by a2 . By assumption, when a1 finishes executing Line 9 or Line 11 of Algorithm
Assumption(d1 ) after the j-th synchronization RepeatSeed, agents have not met which implies that
a2 has finished executing the j-th synchronization RepeatSeed.
The next pattern that a1 executes is the (j + 1)-th synchronization RepeatSeed. Given the above
assumptions and statements, when a1 starts executing this synchronization RepeatSeed, a2 has finished executing the j-th synchronization RepeatSeed and has started executing Line 9 or Line 11 of
Algorithm Assumption(d1 ). By Lemmas 11 and 12, as d1 ≥ D, whichever pattern a2 executes, it is
pushed by the execution of the (j + 1)-th synchronization RepeatSeed by a1 . Given that, still by assumption, agents do not meet before a1 finishes executing the (j +1)-th synchronization RepeatSeed,
when this occurs, a2 has finished the execution of Line 9 or 11 of Algorithm Assumption(d1 ), just
after the j-th, and just before the (j + 1)-th synchronization RepeatSeed. Hence, when a1 finishes
executing the (j + 1)-th synchronization RepeatSeed, a2 has at least started executing the (j + 1)-th
synchronization RepeatSeed, which contradicts the hypothesis that when a1 has finished executing
the (j + 1)-th synchronization RepeatSeed, a2 has neither met a1 nor started executing the (j + 1)-th
synchronization RepeatSeed, and proves the lemma.

6.3

Correctness of Algorithm RV

Theorem 22. Algorithm RV solves the problem of rendezvous in the basic grid.
Proof. To prove this theorem, it is enough to prove the following claim.
Claim 23. Let d1 be the smallest power of two such that d1 ≥ max(D, l0 ) with l0 the index of the
first bit which differs in the transformed labels of the agents. Algorithm RV ensures rendezvous by
the time one of both agents completes an execution of Procedure Assumption(d1 ).
This proof is made by contradiction. Suppose that the agents a1 and a2 executing Algorithm RV
never meet. First, in view of Remark 2, l0 exists. Respectively denote by u and v, the initial nodes
of a1 and a2 .
Consider an agent that eventually starts executing Assumption(d1 ) where d1 is the smallest
power of two such that d1 ≥ max(D, l0 ). As d1 ≥ D, by Lemma 20, we know that as soon as this
agent finishes executing Procedure Harvest(d1 ), both agents have started executing Assumption(d1 ).
25

Otherwise, agents have met which contradicts our assumption. Without loss of generality, suppose
that the bits in the transformed labels of agents a1 and a2 with the index l0 are respectively 1
and 0. We are going to prove that the agents meet before one of them finishes the execution of
Assumption(d1 ).
To achieve this, we first show that there exists an iteration of the loop at Line 6 of Algorithm 6
during which the two following properties are satisfied:
1. the value of the variable i is equal to l0
2. the value of the variable j is such that when executing Pattern Cloudberry at Line 11, the first
pair of Patterns Seed and Berry executed inside this Cloudberry by a1 starts from the initial
node of a2
As, d1 ≥ l0 , there is an iteration of the loop at Line 4 during which the first property is verified.
We now show that the second property is also satisfied. Let U be a list of all the nodes at distance
at most d1 from u and ordered in the order of the first visit when executing Seed(d1 ) from node u.
The same list is considered in the algorithm of Pattern Cloudberry(x, d1 , d1 , h) for any integers x
and h. First of all, there are 2d1 (d1 + 1) + 1 nodes at distance at most d1 from u, and thus in U .
Since the distance between u and v is D ≤ d1 , v belongs to U . Let j1 an integer lower than or equal
to 2d1 (d1 + 1) be its index in U . According to Procedure Assumption, the value of the variable j
is incremented at each iteration of the loop at Line 6 and takes one after another each value lower
than or equal to 2d1 (d1 + 1). Consider the iteration when it is equal to j1 . According to Algorithm
Cloudberry, the first node from which a1 executes Seed and Berry is the node which has index
j1 + 0 (mod 2d1 (d1 + 1) + 1) = j1 . This node is v, which proves that there exists an iteration of the
loop at Line 6 (and thus of the loop at Line 4) during which the second property is verified too. Let
us denote by I the iteration of the loop at Line 4 which satisfies the two aforementioned properties.
It is the iteration after the (1 + (l0 − 1)(2d1 (d1 + 1) + 1) + j1 )-th synchronization RepeatSeed.
According to Lemma 21, we know that when an agent finishes executing the i-th synchronization
RepeatSeed inside the second and the third part of any execution of Procedure Assumption(d1 ) (for
any positive integer i lower than or equal to d1 (2d1 (d1 +1)+1)+1), the other agent has at least begun
the execution of this synchronization RepeatSeed. Thus, when an agent is the first one which starts
executing I, it has just finished executing the (1 + (l0 − 1)(2d1 (d1 + 1) + 1) + j1 )-th synchronization
RepeatSeed and the other agent is executing (or finishing executing) the same RepeatSeed. Let us
prove that rendezvous occurs before any of the agents starts the (2 + (l0 − 1)(2d1 (d1 + 1) + 1) + j1 )-th
synchronization RepeatSeed.
Let us consider the patterns both agents execute between the beginning of the (1+(l0 −1)(2d1 (d1 +
1) + 1) + j1 )-th synchronization RepeatSeed, and the beginning of the next one. Agent a1 executes
Pattern RepeatSeed(x, n) with x an integer and n a positive integer (call this pattern, p1 ) and
Pattern Cloudberry(x, d1 , d1 , j1 ) from node u while a2 executes RepeatSeed(x, n) (let us call it p2 )
and Berry(x, d1 ) (p3 ) from node v. During its execution of Pattern Cloudberry(x, d1 , d1 , j1 ) from
node u, a1 first follows P (u, v), and then executes Pattern Seed(x) followed by Pattern Berry(x, d1 )
both from node v (call them respectively p4 and p5 ). Recall that during any execution of Pattern
Berry(x, d1 ) from node v, there are two periods, the second one consisting in backtracking every
edge traversal made during the first one. During the first period, in particular, an agent executes
a Pattern Seed(x) from every node at distance at most d1 . Those patterns include an execution of
Pattern Seed(x) from node u and another from v. Since backtracking Seed(x) allows to perform
exactly the same edge traversals as Seed(x), during the second period of Pattern Berry(x, d1 ), there
is also an execution of Pattern Seed(x) from node u and another from v.
26

Let us consider two different cases. In the first one, when a1 starts executing p4 from v, inside
p3 , a2 has not yet started following P (v, u) to go executing Seed(x) from u. In the second one, when
a1 starts executing p4 from v, a2 has at least started following P (v, u) to go executing Seed(x) from
u. In the following, we analyse both these cases.
Concerning the first case, we get a contradiction. Consider what a2 can be executing when
a1 starts executing p4 from node v, after following P (u, v). First, it can still be executing the
synchronization RepeatSeed p2 from node v. Then, by Lemma 10, rendezvous occurs. The only
other pattern that a2 can be executing at this moment is p3 . However, in this case, we know that
a2 will have finished its execution of p3 before a1 starts p5 , just after p4 . Otherwise, by Lemma 15,
rendezvous occurs.
We have just reminded the reader that during any execution of Pattern Berry(x, d1 ) from v,
agent a2 performs, among the Patterns Seed(x) from every node at distance at most d1 from v,
Patterns Seed(x) from v. If it executes one of these Patterns Seed(x) while a1 is executing its p4
from node v after following P (u, v), by Lemma 10, rendezvous occurs. This implies that before
a1 finishes following P (u, v), a2 has completed each execution of Pattern Seed(x) from v inside its
execution of Berry(x, d1 ).
It means that, each execution of Pattern Seed(x) from node v during the second period of p3
has already been completed by a2 when a1 starts executing its own Seed(x) from v. Since inside the
second period of p3 , a2 executes Pattern Seed(x) from node v, a2 has already executed the whole
first period of p3 when a1 starts executing p4 from v including Pattern Seed(x) performed from node
u, as u is at distance at most d1 from v. This contradicts the definition of this first case: according
to this definition, when a1 starts executing p4 from v, inside p3 , a2 has not followed P (v, u) yet, and
thus has not executed Seed(x) from u.
Concerning the second case, we prove that rendezvous occurs, which is also a contradiction.
Recall that in this case, when a1 starts executing p4 from v, a2 has at least started following P (v, u)
to go executing Seed(x) from u. If a2 has not finished following P (v, u) when a1 starts executing
P (u, v), then if we denote by t1 (resp. t2 ) the time when a1 (resp. a2 ) finishes following P (u, v)
(resp. P (v, u)), agents meet by time min(t1 , t2 ) as P (u, v) = P (v, u). If a2 has finished following
P (v, u) before a1 starts executing P (u, v), then it has begun executing Seed(x) from u before a1
finishes executing p1 (before it executes Cloudberry(x, d1 , d1 , j1 )), which means by Lemma 10 that
agents achieve rendezvous.
So, whatever the execution chosen by the adversary, rendezvous occurs in the worst case by the
time any agent completes Assumption(d1 ), which contradicts the assumption that rendezvous never
happens. This proves the claim, and by extension the theorem.

6.4

Cost analysis

Theorem 24. The cost of Algorithm RV is polynomial in D and l.
Proof. In order to prove this theorem, we first need to show the following two claims.
Claim 25. Let d1 be any power of two. The cost of each basic pattern inside BD(Assumption(d1 ))
is polynomial in d1 .
Let us prove this claim. First, the costs of these basic patterns are polynomial in d1 if the values of
their parameters are polynomial in d1 . Indeed, C(Seed(x)) ∈ O(x2 ), C(RepeatSeed(x, n)) ∈ O(n ×
C(Seed(x))), C(Berry(x, y)) ∈ O((x + y)6 ), and C(Cloudberry(x, y, z, h)) ∈ O(z 2 × (C(Seed(x)) +
C(Berry(x, y)))).
27

Pattern Seed does not belong to BD(Assumption(d1 )). It is called when executing the other
basic patterns, which give it a parameter which is polynomial in their own parameters. Hence, we
focus on the parameters of Pattern RepeatSeed, Berry, and Cloudberry, and prove that their values
are polynomial in d1 .
For each basic Pattern Berry or Cloudberry inside BD(Assumption(d1 )), the value given to its
second parameter is always d1 . For each basic Pattern Cloudberry inside BD(Assumption(d1 )), the
value assigned to the third parameter of Pattern Cloudberry, is always d1 . The fourth parameter of
Pattern Cloudberry does not have any impact on its cost since it only modifies the order in which
the edge traversals are made, and not their number.
The first parameter of these three basic patterns can take various complicated values, but
they are still polynomial in d1 . Indeed, according to Lemma 19, for any power of two d1 , inside
BD(Assumption(d1 )), the value of this first parameter is at most ρ(2d1 ) − 3d1 , which is polynomial
in d1 .
At last, the second parameter of Pattern RepeatSeed, is always equal to C(p) where p is one of
the other patterns, either Berry or Cloudberry. Besides, since the parameters given to this pattern
p are polynomial in d1 , this is also the case for the second parameter of Pattern RepeatSeed. Hence
the claim is proven.
Claim 26. Let d1 be a power of two. The cost of Procedure Assumption(d1 ) is polynomial in d1 .
Let us prove this claim. According to the definition of a basic decomposition, and of Remark 4, for any power of two d1 , each edge traversal performed during an execution of Procedure
Assumption(d1 ) is performed by one of the basic patterns inside BD(Assumption(d1 )). The cost
of Procedure Assumption(d1 ) is the same as the sum of the costs of all the basic patterns inside BD(Assumption(d1 )). According to Claim 25, we know that for any power of two d1 , inside
BD(Assumption(d1 )), each basic pattern is polynomial in d1 . Thus, to prove this claim it is enough
to show that BD(Assumption(d1 )) contains a number of basic patterns which is polynomial in d1 .
For any power of two d1 , Procedure Assumption(d1 ) is composed of a call to Procedure Harvest(d1 )
and the nested loops. These loops consist in 2d1 (2d1 (d1 + 1) + 1) calls to basic patterns. Half of them
are made to RepeatSeed and the others either to Berry or to Cloudberry. In its turn, Harvest(d1 )
is composed of two parts: a loop calling Procedure P ushP attern and two basic patterns. For any
power of two d2 , in view of Algorithm 8, and since they are both perfect, the number of basic patterns
inside BD(P ushP attern(d2 , d1 )) or BD(Assumption(d2 )) is the same. As a consequence, if d1 ≥ 2,
BD(P ushP attern(1, d1 )), . . . , BD(P ushP attern( d21 , d1 )) is composed of as many basic patterns as
there are in BD(Assumption(1)), . . . , BD(Assumption( d21 )).
For any power of two i, let us denote by L1 (i) (resp. L2 (i)) the number of calls to basic patterns
inside BD(Assumption(i)) (resp. BD(Harvest(i))). We then have the following equations:
L1 (i) = L2 (i) + 2i(2i(i + 1) + 1)
log2 (i)−1

L2 (i) =

X

(L1 (2j )) + 2

j=0

They imply the following:

if i ≥ 2

L2 (1) = 2 and
i
i
i
i
then L2 (i) = L2 ( ) + L1 ( ) = 2L2 ( ) + i(i( + 1) + 1)
2
2
2
2
28

Hence, L2 (i) ∈ O(i5 ). Both L2 (i) and L1 (i) are polynomial in i, which means that for any power
of two d1 , BD(Assumption(d1 )) is composed of number of basic patterns which is polynomial in d1 .
Hence, in view of Claim 25, the cost of Assumption(d1 ) is indeed polynomial in d1 , which proves the
claim.
Now, it remains to conclude the proof of the theorem. According to Claim 23, rendezvous
is achieved by the end of the execution of Assumption(δ) by any of both agents, where δ is the
smallest power of two such that δ ≥ max(D, l0 ) and l0 is the index of the first bit which differs in the
transformed labels of the agents. So, according to Claim 26, the cost of Assumption(δ) is polynomial
in D and l0 , and by extension polynomial in D and l as by construction we have l0 ≤ 2l +2. Moreover,
before executing Assumption(δ), all the calls to Procedure Assumption use an input parameter lower
than δ and thus, each of these calls is also polynomial in D and l. Hence, in view of the fact that
the number of calls to procedure Assumption before executing Assumption(δ) belongs to Θ(log δ)
(the input parameter of Assumption doubles after each call), the theorem follows.

7

Conclusion

From Theorems 1, 22 and 24, we obtain the following result concerning the task of approach in the
plane.
Theorem 27. The task of approach can be solved at cost polynomial in the unknown initial distance
∆ separating the agents and in the length of (the binary representation) of the shortest of their labels.
Throughout the paper, we made no attempt at optimizing the cost. Actually, as the acute reader
will have noticed, our main concern was only to prove the polynomiality. Hence, a natural open
problem is to find out the optimal cost to solve the task of approach. This would be all the more
important as in turn we could compare this optimal cost with the cost of solving the same task with
agents that can position themselves in a global system of coordinates (the almost optimal cost for
this case is given in [10]) in order to determine whether the use of such a system (e.g., GPS) is finally
relevant to minimize the travelled distance.

References
[1] Noa Agmon and David Peleg. Fault-tolerant gathering algorithms for autonomous mobile robots.
SIAM J. Comput., 36(1):56–82, 2006.
[2] Steve Alpern. Rendezvous search: A personal perspective. Operations Research, 50(5):772–795,
2002.
[3] Steve Alpern. The theory of search games and rendezvous. International Series in Operations
Research and Management Science, Kluwer Academic Publishers, 2003.
[4] Evangelos Bampas, Jurek Czyzowicz, Leszek Gasieniec, David Ilcinkas, and Arnaud Labourel.
Almost optimal asynchronous rendezvous in infinite multidimensional grids. In Distributed
Computing, 24th International Symposium, DISC 2010, Cambridge, MA, USA, September 1315, 2010. Proceedings, pages 297–311, 2010.

29

[5] Sébastien Bouchard, Yoann Dieudonné, and Bertrand Ducourthial. Byzantine gathering in
networks. Distributed Computing, 29(6):435–457, 2016.
[6] Jérémie Chalopin, Yoann Dieudonné, Arnaud Labourel, and Andrzej Pelc. Rendezvous in networks in spite of delay faults. Distributed Computing, 29(3):187–205, 2016.
[7] Mark Cieliebak, Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro. Distributed computing
by mobile robots: Gathering. SIAM J. Comput., 41(4):829–879, 2012.
[8] Reuven Cohen and David Peleg. Convergence properties of the gravitational algorithm in asynchronous robot systems. SIAM J. Comput., 34(6):1516–1528, 2005.
[9] Reuven Cohen and David Peleg. Convergence of autonomous mobile robots with inaccurate
sensors and movements. SIAM J. Comput., 38(1):276–302, 2008.
[10] Andrew Collins, Jurek Czyzowicz, Leszek Gasieniec, and Arnaud Labourel. Tell me where I
am so I can meet you sooner. In Automata, Languages and Programming, 37th International
Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010, Proceedings, Part II, pages 502–
514, 2010.
[11] Jurek Czyzowicz, Adrian Kosowski, and Andrzej Pelc. How to meet when you forget: log-space
rendezvous in arbitrary graphs. Distributed Computing, 25(2):165–178, 2012.
[12] Jurek Czyzowicz, Andrzej Pelc, and Arnaud Labourel. How to meet asynchronously (almost)
everywhere. ACM Transactions on Algorithms, 8(4):37, 2012.
[13] Gianlorenzo D’Angelo, Gabriele Di Stefano, and Alfredo Navarra. Gathering on rings under the
look-compute-move model. Distributed Computing, 27(4):255–285, 2014.
[14] Shantanu Das, Dariusz Dereniowski, Adrian Kosowski, and Przemyslaw Uznanski. Rendezvous
of distance-aware mobile agents in unknown graphs. In Structural Information and Communication Complexity - 21st International Colloquium, SIROCCO 2014, Takayama, Japan, July
23-25, 2014. Proceedings, pages 295–310, 2014.
[15] Shantanu Das, Flaminia L. Luccio, and Euripides Markou. Mobile agents rendezvous in spite
of a malicious agent. In Algorithms for Sensor Systems - 11th International Symposium on
Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2015, Patras,
Greece, September 17-18, 2015, Revised Selected Papers, pages 211–224, 2015.
[16] Xavier Défago, Maria Gradinariu, Stéphane Messika, and Philippe Raipin Parvédy. Faulttolerant and self-stabilizing mobile robots gathering. In Distributed Computing, 20th International Symposium, DISC 2006, Stockholm, Sweden, September 18-20, 2006, Proceedings, pages
46–60, 2006.
[17] Anders Dessmark, Pierre Fraigniaud, Dariusz R. Kowalski, and Andrzej Pelc. Deterministic
rendezvous in graphs. Algorithmica, 46(1):69–96, 2006.
[18] Yoann Dieudonné and Andrzej Pelc. Deterministic polynomial approach in the plane. Distributed
Computing, 28(2):111–129, 2015.
[19] Yoann Dieudonné and Andrzej Pelc. Anonymous meeting in networks. Algorithmica, 74(2):908–
946, 2016.
30

[20] Yoann Dieudonné, Andrzej Pelc, and David Peleg. Gathering despite mischief. ACM Transactions on Algorithms, 11(1):1, 2014.
[21] Yoann Dieudonné, Andrzej Pelc, and Vincent Villain. How to meet asynchronously at polynomial cost. SIAM J. Comput., 44(3):844–867, 2015.
[22] Yoann Dieudonné and Franck Petit. Self-stabilizing gathering with strong multiplicity detection.
Theor. Comput. Sci., 428:47–57, 2012.
[23] Paola Flocchini, Giuseppe Prencipe, Nicola Santoro, and Peter Widmayer. Gathering of asynchronous robots with limited visibility. Theor. Comput. Sci., 337(1-3):147–168, 2005.
[24] Pierre Fraigniaud and Andrzej Pelc. Deterministic rendezvous in trees with little memory. In
Distributed Computing, 22nd International Symposium, DISC 2008, Arcachon, France, September 22-24, 2008. Proceedings, pages 242–256, 2008.
[25] Pierre Fraigniaud and Andrzej Pelc. Delays induce an exponential memory gap for rendezvous
in trees. ACM Transactions on Algorithms, 9(2):17, 2013.
[26] Taisuke Izumi, Samia Souissi, Yoshiaki Katayama, Nobuhiro Inuzuka, Xavier Défago, Koichi
Wada, and Masafumi Yamashita. The gathering problem for two oblivious robots with unreliable
compasses. SIAM J. Comput., 41(1):26–46, 2012.
[27] Dariusz R. Kowalski and Adam Malinowski. How to meet in anonymous network. Theor.
Comput. Sci., 399(1-2):141–156, 2008.
[28] Evangelos Kranakis, Danny Krizanc, and Sergio Rajsbaum. Mobile agent rendezvous: A survey. In Structural Information and Communication Complexity, 13th International Colloquium,
SIROCCO 2006, Chester, UK, July 2-5, 2006, Proceedings, pages 1–9, 2006.
[29] Gianluca De Marco, Luisa Gargano, Evangelos Kranakis, Danny Krizanc, Andrzej Pelc, and Ugo
Vaccaro. Asynchronous deterministic rendezvous in graphs. Theor. Comput. Sci., 355(3):315–
326, 2006.
[30] Avery Miller and Andrzej Pelc. Fast rendezvous with advice. In Algorithms for Sensor Systems
- 10th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless
Networks and Distributed Robotics, ALGOSENSORS 2014, Wroclaw, Poland, September 12,
2014, Revised Selected Papers, pages 75–87, 2014.
[31] Avery Miller and Andrzej Pelc. Time versus cost tradeoffs for deterministic rendezvous in
networks. Distributed Computing, 29(1):51–64, 2016.
[32] Linda Pagli, Giuseppe Prencipe, and Giovanni Viglietta. Getting close without touching: neargathering for autonomous mobile robots. Distributed Computing, 28(5):333–349, 2015.
[33] Thomas Schelling. The Strategy of Conflict. Oxford University Press, Oxford, 1960.
[34] Ichiro Suzuki and Masafumi Yamashita. Distributed anonymous mobile robots: Formation of
geometric patterns. SIAM J. Comput., 28(4):1347–1363, 1999.
[35] Amnon Ta-Shma and Uri Zwick. Deterministic rendezvous, treasure hunts, and strongly universal exploration sequences. ACM Transactions on Algorithms, 10(3):12, 2014.

31

