Rendezvous of Two Robots with Constant Memory
P. Flocchini∗
N. Santoro†
G. Viglietta†
M. Yamashita‡
Abstract
We study the impact that persistent memory has on the classical rendezvous problem of two
mobile computational entities, called robots, in the plane. It is well known that, without addi-
tional assumptions, rendezvous is impossible if the entities are oblivious (i.e., have no persistent
memory) even if the system is semi-synchronous (SSynch). It has been recently shown that
rendezvous is possible even if the system is asynchronous (ASynch) if each robot is endowed
with O(1) bits of persistent memory, can transmit O(1) bits in each cycle, and can remember
(i.e., can persistently store) the last received transmission. This setting is overly powerful.
In this paper we weaken that setting in two different ways: (1) by maintaining the O(1) bits
of persistent memory but removing the communication capabilities; and (2) by maintaining the
O(1) transmission capability and the ability to remember the last received transmission, but
removing the ability of an agent to remember its previous activities. We call the former setting
finite-state (FState) and the latter finite-communication (FComm). Note that, even though
its use is very different, in both settings, the amount of persistent memory of a robot is constant.
We investigate the rendezvous problem in these two weaker settings. We model both settings
as a system of robots endowed with visible lights: in FState, a robot can only see its own light,
while in FComm a robot can only see the other robot’s light. We prove, among other things,
that finite-state robots can rendezvous in SSynch, and that finite-communication robots are
able to rendezvous even in ASynch. All proofs are constructive: in each setting, we present a
protocol that allows the two robots to rendezvous in finite time.
1
Introduction
1.1
Framework and Background
Rendezvous is the process of two computational mobile entities, initially dispersed in a spatial
universe, meeting within finite time at a location, non known a priori. When there are more than
two entities, this task is known as Gathering. These two problems are core problems in distributed
computing by mobile entities. They have been intensively and extensively studied when the universe
is a connected region of R2 in which the entities, usually called robots, can freely move; see, for
example, [1, 3, 4, 5, 7, 10, 11, 13, 16, 17, 18, 19, 20].
Each entity is modeled as a point, it has its own local coordinate system of which it perceives
itself as the centre, and has its own unit distance. Each entity operates in cycles of Look, Com-
pute, Move activities. In each cycle, an entity observes the position of the other entities expressed
in its local coordinate system (Look); using that observation as input, it executes a protocol (the
same for all robots) and computes a destination point (Compute); it then moves to the computed
destination point (Move). Depending on the activation schedule and the synchronization level,
three basic types of systems are identified in the literature: a fully synchronous system (FSynch)
∗School of Electrical Engineering and Computer Science, University of Ottawa, Canada.
†School of Computer Science, Carleton University, Canada.
‡Kyushu University, Fukuoka, Japan.
1
arXiv:1306.1956v1  [cs.MA]  8 Jun 2013
is equivalent to a system where there is a common clock and at each clock tick all entities are
activated simultaneously, and Compute and Move are instantaneous; a semi-synchronous system
(SSynch) is like a fully synchronous one except that, at each clock tick, only some entities will be
activated (the choice is made by a fair scheduler); in a fully asynchronous system (ASynch), there
is no common notion of time, each Compute and Move of each robot can take an unpredictable
(but finite) amount of time, and the interval of time between successive activities is finite but un-
predictable. The focus of almost all algorithmic investigations in the continuous setting has been
on oblivious robots, that is when the memory of the robots is erased at the end of each cycle, in
other words the robots have no persistent memory (e.g., for an overview see [12]).
The importance of Rendezvous in the continuous setting derives in part from the fact that
it separates FSynch from SSynch for oblivious robots. Indeed, Rendezvous is trivially solvable
in a fully synchronous system, without any additional assumption. However, without additional
assumptions, Rendezvous is impossible for oblivious robots if the system is semi-synchronous [21].
Interestingly, from a computational point of view, Rendezvous is very different from the Gath-
ering problem of having k ⩾3 robots meet in the same point; in fact, Gathering of oblivious robots
is always possible for any k ⩾3 even in ASynch without any additional assumption other than
multiplicity detection [4]. Furthermore, in SSynch, k ⩾3 robots can gather even in spite of a
certain number of faults [1, 2, 9], and converge in spite of inaccurate measurements [6]; see also
[14].
The Rendezvous problem also shows the impact of certain factors. For example, the problem
has a trivial solution if the robots are endowed with consistent compasses even if the system is fully
asynchronous. The problem is solvable in ASynch even if the local compasses have some degree of
inconsistency (a tilt of an appropriate angle) [15]; the solution is no longer trivial, but does exist.
In this paper, we are concerned with the impact that memory has on the solvability of the
Rendezvous problem. In particular, we are interested in determining what type and how much
persistent memory would allow the robots to rendezvous. What is known in this regard is very little.
On the one hand, it is well known that, in absence of additional assumptions, without persistent
memory rendezvous is impossible even in SSynch [21]. On the other hand, a recent result shows
that rendezvous is indeed possible even in ASynch if each robot has O(1) bits of persistent memory
and can transmit O(1) bits in each cycle and can remember (i.e., can persistently store) the last
received transmission [8] (see also [22] for size-optimal solutions).
The conditions of the latter result are overly powerful. The natural question is whether the
simultaneous presence of these conditions is truly necessary for rendezvous.
1.2
Main Contributions
In this paper we address this question by weakening the setting in two different ways, and investigate
the Rendezvous problem in these weaker settings. Even though its use is very different, in both
settings, the amount of persistent memory of a robot is constant.
We first examine the setting where the two robots have O(1) bits of internal persistent memory
but cannot communicate; this corresponds to the finite-state (FState) robots model. Among other
contributions, we prove that FState robots with rigid movements can rendezvous in SSynch, and
that this can be done using only six internal states. The proof is constructive: we present a protocol
that allows the two robots to rendezvous in finite time under the stated conditions.
We then study the finite-communication (FComm) setting, where a robot can transmit O(1)
bits in each cycle and remembers the last received transmission, but it is otherwise oblivious: it
has no other persistent memory of its previous observations, computations and transmissions. We
prove that two FComm robots with rigid movements are able to rendezvous even in ASynch; this
2
is doable even if the different messages that can be sent are just 12. We also prove that only three
different messages suffice in SSynch. Also for this model all the proofs are constructive.
Finally, we consider the Rendezvous problem when the movement of the robots can be inter-
rupted by an adversary (in the above results, in each cycle a robot reaches its computed destination
point). The only constraint on the adversary is that a robot moves at least a distance δ > 0 (oth-
erwise, rendezvous is clearly impossible). We show that, with knowledge of δ, three internal states
are sufficient to solve Rendezvous by FState robots in SSynch, and three possible messages are
sufficient for FComm robots in ASynch. In other words, we prove that rigidity of the movements
can be traded with knowledge of δ.
These results are obtained modeling both settings as a system of robots endowed with a constant
number of visible lights: a FState robot can see only its own light, while a FComm robot can see
only the other robot’s light. Our results seem to indicate that “it is better to communicate than
to remember”.
In addition to the specific results on the Rendezvous problem, an important contribution of this
paper is the extension of the classical model of oblivious silent robots into two directions: adding
finite memory, and enabling finite communication.
2
Model and Terminology
The general model we employ is the standard one, described in [12]. The two robots are autonomous
computational entities modeled as points moving in R2. Each robot has its own coordinate system
and its own unit distance, which may differ from each other, and it always perceives itself as lying
at the origin of its own local coordinate system. Each robot operates in cycles that consist of
three phases: Look, Compute, and Move. In the Look phase it gets the position (in its local
coordinate system) of the other robot; in the Compute phase, it computes a destination point;
in the Move phase it moves to the computed destination point, along a straight line. Without
loss of generality, the Look phase is assumed to be instantaneous. The robots are anonymous and
oblivious, meaning that they do not have distinct identities, they execute the same algorithm in
each Compute phase, and the input to such algorithm is the snapshot coming from the previous
Look phase.
Here we study two settings; both settings can be described as restrictions of the model of visibile
lights introduced in [8]. In that model, each robot carries a persistent memory of constant size,
called light; the value of the light is called color or state, and it is set by the robot during each
Compute phase. Other than their own light, the robots have no other persistent memory of past
snapshots and computations.
In the first setting, that of silent finite-state (or simply, FState) robots, the light of a robot
is visible only to the robot itself; i.e., the colored light merely encodes an internal state. In the
second setting, of oblivious finite-communication (or simply FComm) robots, the light of a robot
is visible only to the other robot; i.e., they can communicate with the other robot through their
colored light, but by their next cycle they forget even the color of their own light (since they do
not see it). The color a robot sees is used as input during the computation.
In the asynchronous (ASynch) model, the robots are activated independently, and the duration
of each Compute, Move and inactivity is finite but unpredictable. As a result, the robots do not
have a common notion of time, robots can be seen while moving, and computations can be made
based on obsolete observations. In the semi-synchronous (SSynch) models the activations of robots
can be logically divided into global rounds; in each round, one or both robots are activated, obtain
the same snapshot, compute, and perform their move. It is assumed that the activation schedule
3
is fair, i.e., each robot is activated infinitely often.
Depending on whether or not the adversary can stop a robot before it reaches its computed
destination, the movements are called non-rigid and rigid, respectively. In the case of non-rigid
movements, there exists a constant δ > 0 such that if the destination point’s distance is smaller
than δ, the robot will reach it; otherwise, it will move towards it by at least δ. Note that, without
this assumption, an adversary could make it impossible for any robot to ever reach its destination,
following a classical Zenonian argument.
The two robots solve the Rendezvous problem if, within finite time, they move to the same
point and do not move from there; the meeting point is not determined a priori. A rendezvous
algorithm for SSynch (resp., ASynch) is a protocol that allows the robots to solve the Rendezvous
problem under any possible execution schedule in SSynch (resp., ASynch). A particular class of
algorithms, denoted by L, is that where each robot may only compute a destination point of the
form λ · other.position, for some λ ∈R obtained as a function only of the light of which the robot
is aware (i.e., its internal state in the FState model, or the other robot’s color in the FComm
model). The algorithms of this class are of interest because they operate also when the coordinate
system of a robot is not self-consistent (i.e., it can unpredictably rotate, change its scale or undergo
a reflection).
3
Finite-State Robots
We fist consider FState robots and we start by identifying a simple impossibility result for algo-
rithms in L.
Theorem 1. In SSynch, Rendezvous of two FState robots is unsolvable by algorithms in L,
regardless of the amount of their internal memory.
Proof. For each robot, the destination point and the next state are a function of the internal state
only. Assuming that both robots start in the same state, we keep activating them one at a time,
alternately. Hence, every other turn they are in the same state. As soon as the first robot attempts
to move to the other robot’s location, we activate both robots simultaneously, making them switch
positions. By repeating this pattern, the robots never gather.
Thus the computation of the destination must take into account more than just the lights (or states)
of which the robot is aware.
The approach we use to circumvent this impossibility result is to have each robot use its own
unit of distance as a computational tool; recall that the two robots might have different units,
and they are not known to each other. We propose Algorithm 1 for Rendezvous in SSynch, also
illustrated in Figure 1. Each robot has six internal states, namely Sstart, S1, Sleft
2
, Sright
2
, S3, and
Sfinish. Both robots are assumed to begin their execution in Sstart. Each robot lies in the origin of
its own local coordinate system and the two robots have no agreement on axes orientations or unit
distance.
Intuitively, the robots try to reach a configuration in which they both observe the other robot
at distance not lower than 1 (their own unit). From this configuration, they attempt to meet in the
midpoint. If they never meet because they are never activated simultaneously, at some point one
of them notices that its observed distance is lower than 1. This implies a breakdown of symmetry
that enables the robots to finally gather.
In order to reach the desired configuration in which they both observe a distance not lower than
1, the two robots first try to move farther away from each other if they are too close. If they are
far enough, they memorize the side on which they see each other (left or right), and try to switch
4
positions. If only one of them is activated, they gather; otherwise they detect a side switch and
they can finally apply the above protocol. This is complicated by the fact that the robots may
disagree on the distances they observe. To overcome this difficulty, they use their ability to detect
a side switch to understand which distance their partner observed. If the desired configuration is
not reached because of a disagreement, a breakdown of symmetry occurs, which is immediately
exploited to gather anyway. As soon as the two robots coincide at the end of a cycle, they never
move again, and Rendezvous is solved.
start
S
1
S
2
left
S
2
right
S
finish
S
3
S
1
,)
∞
+
,
(left) [1
1
,)
∞
+
,
(right) [1
1
,)
∞
+
,
(right) (1
1
,)
∞
+
,
(left) (1
dist
1
−
1
,
1)
,
[0
2
1
,)
∞
+
,
(left) [1
2
1
,)
∞
+
,
(right) [1
1
,)
∞
+
,
(right) [0
1
,)
∞
+
,
(left) [0
0
,)
2
1
,
(left) [0
0
,)
2
1
,
(right) [0
2
1
,
1)
,
2
1
(right) [
2
1
,
1)
,
2
1
(left) [
0
,
1]
,
[0
1
,)
∞
+
,
(1
0
,)
4
1
,
[0
1
,)
2
1
,
4
1[
0
,
1]
,
[0
Figure 1: Illustration of Algorithm 1. A label of the form (d)I, λ denotes a transition that applies
when the other robot is seen in direction d ∈{left, right} and its observed distance lies in the
interval I ⊂R. The computed destination point is λ · other.position. For example, a robot in state
Sstart perceiving the other at distance ⩾1 on the right will move to the position of the other robot
and will change state to Sright
2
.
To analyze the correctness of Algorithm 1, some terminology is needed. In the following, the
two robots will be called r and s, respectively. An expression of the form (Sr, Ss, Ir, Is) denotes a
configuration in which robot r (resp. s) is in state Sr (resp. Ss), and the distance at which it sees
the other robot lies in the interval Ir (resp. Is), according to its own distance function. Therefore,
the starting configuration of r and s is (Sstart, Sstart, [0, +∞), [0, +∞)).
With abuse of notation, we will say that a robot is in state S=
2 if it is in state Sleft
2
(resp. Sright
2
)
and it sees the other robot on its left (resp. right). Analogously, a robot is said to be in state S̸=
2
if its state is Sleft
2
or Sright
2
and it has detected a switch. For a configuration C, the expression C ↓
means that, whenever the two robots reach C, Rendezvous is eventually solved.
Observation 2. (Sa, Sb, Ia, Ib) ↓if and only if (Sb, Sa, Ib, Ia) ↓.
Observation 3. If (Sr, Ss, Ir, Is) ↓and I′
r ⊆Ir, then (Sr, Ss, I′
r, Is) ↓.
Lemma 4. (Sfinish, S3, [0, 1], [1/4, 1/2)) ↓.
5
Algorithm 1
Rendezvous for rigid SSynch with no unit distance agreement and six internal
states
1: dist ←∥other.position∥
2: if dist = 0 then
3:
terminate
4: if other.position.x > 0 then
5:
dir ←right
6: else if other.position.x < 0 then
7:
dir ←left
8: else if other.position.y > 0 then
▷other.position.x = 0
9:
dir ←right
10: else
11:
dir ←left
12: if me.state = Sstart then
13:
if dist < 1 then
14:
me.state ←S1
15:
me.destination ←other.position · (1 −1/dist)
16:
else
17:
me.state ←Sdir
2
18:
me.destination ←other.position
19: else if me.state = S1 then
20:
if dist ⩽1 then
21:
me.state ←Sfinish
22:
me.destination ←(0, 0)
23:
else
24:
me.state ←Sdir
2
25:
me.destination ←other.position
26: else if me.state = Sd
2 then
27:
if dir = d then
28:
me.state ←Sfinish
29:
me.destination ←other.position
30:
else if dist < 1/2 then
▷side switch detected
31:
me.state ←Sfinish
32:
me.destination ←(0, 0)
33:
else
34:
me.destination ←other.position/2
35:
if dist < 1 then
36:
me.state ←S3
6
37: else if me.state = S3 then
38:
me.state ←Sfinish
39:
if dist < 1/4 then
40:
me.destination ←(0, 0)
41:
else
▷1/4 ⩽d < 1/2
42:
me.destination ←other.position
43: else
▷me.state = Sfinish
44:
if dist ⩽1 then
45:
me.destination ←(0, 0)
46:
else
47:
me.destination ←other.position
Proof. Robot r keeps staying still, while robot s moves to r as soon as it is activated.
Lemma 5. (Sfinish, S̸=
2 , [0, 1], [1/2, +∞)) ↓.
Proof. Robot s keeps moving to the midpoint, while robot r never moves, because it keeps ob-
serving a distance not greater than 1. As soon as s observes a distance smaller than 1 (hence
in [1/2, 1)), its state becomes S3 and it moves to the midpoint again. Now the configuration is
(Sfinish, S3, [0, 1/2], [1/4, 1/2)), and Lemma 4 applies.
Lemma 6. (Sfinish, S=
2 , [0, 1], [0, +∞)) ↓.
Proof. Robot r keeps staying still, while robot s moves to r as soon as it is activated.
Lemma 7. (S3, S̸=
2 , [1/4, 1/2), [0, +∞)) ↓.
Proof. If only robot r is activated, it moves to s, and Rendezvous is solved.
If only robot s is activated, two cases arise.
If the distance observed by s is less than 1/2,
configuration (S3, Sfinish, [1/4, 1/2), [0, 1/2)) is reached, and Lemma 4 applies. Otherwise, if the dis-
tance observed by s is at least 1/2, s moves to the midpoint (and possibly switches to S3). As a
consequence, the distance observed by r becomes less than 1/4, hence it stays still forever (it only
switches to Sfinish as soon as it is activated). On the other hand, s keeps moving to the midpoint,
until it observes a distance lower than 1, switches to S3, and finally moves to r, solving Rendezvous.
If both robots are activated on the first cycle, three cases arise.
• If the distance observed by s is less than 1/2, r moves to s and s stays still, hence Rendezvous
is solved.
• If the distance observed by s lies in [1/2, 1), configuration (Sfinish, S3, [1/8, 1/4), [1/4, 1/2)) is
reached, and Lemma 4 applies.
• If the distance observed by s is at least 1, configuration (Sfinish, S=
2 , [1/8, 1/4), [1/2, +∞)) is
reached (the two robots switch sides), and Lemma 6 applies.
Lemma 8. (S̸=
2 , S̸=
2 , [0, 1/2), [1/2, +∞)) ↓.
7
Proof. If both robots are activated, two cases arise. If the distance observed by s is less than
1, configuration (Sfinish, S3, [0, 1/4), [1/4, 1/2)) is reached, and Lemma 4 applies. Otherwise, if the
distance is at least 1, configuration (Sfinish, S̸=
2 , [0, 1/4), [1/2, +∞)) is reached, and Lemma 5 applies.
If only r is activated, configuration (Sfinish, S̸=
2 , [0, 1/2), [1/2, +∞)) is reached, and Lemma 5
applies.
If only robot s is activated, two cases arise.
If the distance observed by s is less than 1,
configuration (S̸=
2 , S3, [0, 1/4), [1/4, 1/2)) is reached, and Lemma 7 applies. Otherwise, if the distance
is at least 1, the configuration remains (S̸=
2 , S̸=
2 , [0, 1/2), [1/2, +∞)), but the distance between the two
robots has halved. As the execution progresses, this case cannot repeat forever, because eventually
the distance observed by s becomes less than 1, or r is activated.
Lemma 9. (S̸=
2 , S̸=
2 , [1, +∞), [1, +∞)) ↓.
Proof. If both robots are activated, they compute the midpoint and they gather. If only one robot is
activated at each cycle, configuration (S̸=
2 , S̸=
2 , [1, +∞), [1, +∞)) keeps repeating for finitely many
cycles, until the distance observed by some robot, say r, becomes less than 1. The configuration
then becomes (S̸=
2 , S̸=
2 , [1/2, 1), [1/2, +∞)).
Once again, if both robots are activated at the next cycle, they gather in the midpoint. If only
r is activated, configuration (S3, S̸=
2 , [1/4, 1/2), [1/4, +∞)) is reached, and Lemma 7 applies. On the
other hand, if only s is activated, two cases arise. If the distance observed by s is less than 1,
configuration (S̸=
2 , S3, [1/4, 1/2), [1/4, 1/2)) is reached, and Lemma 7 applies again. If the distance is
at least 1, then configuration (S̸=
2 , S̸=
2 , [1/4, 1/2), [1/2, +∞)) is reached, and Lemma 8 applies.
Lemma 10. (S1, Sfinish, [0, 1], (1, +∞)) ↓and (S1, Sstart, [0, 1], [1, +∞)) ↓.
Proof. Robot r switches to Sfinish as soon as it is activated, and keeps staying still. Robot s moves
to r as soon as it is activated.
Lemma 11. (S1, Sstart, {1}, [0, +∞)) ↓.
Proof. If the distance observed by robot s is at least 1, then Lemma 10 applies. Otherwise the
configuration is (S1, Sstart, {1}, [0, 1)). Three cases arise.
• If both robots are activated at the first cycle, they reach configuration (Sfinish, S1, (1, +∞), {1}),
and Lemma 10 applies.
• If only robot r is activated at the first cycle, configuration (Sfinish, Sstart, {1}, [0, 1)) is reached.
Now r keeps staying still and in state Sfinish.
As soon as s is activated, configuration
(Sfinish, S1, (1, +∞), {1}) is reached, and Lemma 10 applies.
• If only robot s is activated at the first cycle, configuration (S1, S1, (1, +∞), {1}) is reached.
From now on, s keeps staying still (possibly switching to Sfinish), whereas r moves to s as
soon as it is activated.
Lemma 12. (S1, S1, (1, +∞), (1, +∞)) ↓.
Proof. If only one robot is activated, it moves to the other robot, and Rendezvous is solved. If
both robots are activated, they turn to Sleft
2
or Sright
2
and switch positions.
Hence they reach
configuration (S̸=
2 , S̸=
2 , (1, +∞), (1, +∞)), and Lemma 9 applies.
8
Theorem 13. In SSynch, Rendezvous of two FState robots is solvable with six internal states.
This result holds even without unit distance agreement.
Proof. We prove that (Sstart, Sstart, [0, +∞), [0, +∞)) ↓. Three cases arise.
• Let the configuration be (Sstart, Sstart, [0, 1), [0, 1)). If only one robot is activated, say r, then
configuration (S1, Sstart, {1}, [0, +∞)) is reached, and Lemma 11 applies. If both robots are
activated, configuration (S1, S1, (1, +∞), (1, +∞)) is reached, and Lemma 12 applies.
• Let the configuration be (Sstart, Sstart, [1, +∞), [0, 1)) (the symmetric case is equivalent, due
to Observation 2). If only robot r is activated, it moves to s and Rendezvous is solved. If
only s is activated, configuration (Sstart, S1, (1, +∞), {1}) is reached, and Lemma 10 applies.
Finally, if both robots are activated, configuration (S=
2 , S1, [0, +∞), [0, 1)) is reached. Next, if
only robot s is activated, configuration (S=
2 , Sfinish, [0, +∞), [0, 1)) is reached, and Lemma 6
applies. In any other case, r moves to s and Rendezvous is solved.
• Let the configuration be (Sstart, Sstart, [1, +∞), [1, +∞)). If only one robot is activated, it
moves to the other robot, and Rendezvous is solved. If both robots move, they switch posi-
tions, and the configuration becomes (S̸=
2 , S̸=
2 , [1, +∞), [1, +∞)). Then Lemma 9 applies.
4
Finite-Communication Robots
We now focus on FComm robots distinguishing the asynchronous and the semi-synchronous cases.
4.1
Asynchronous
It is not difficult to see that algorithms in L are not sufficient to solve the problem.
Theorem 14. In ASynch, Rendezvous of two FComm robots is unsolvable by algorithms in L,
regardless of the amount of colors employed.
Proof. For each robot, the destination point and the next state are a function of the state of the
other robot only. Assuming that both robots start in the same state, we let them perform their
execution synchronously. As soon as both robots compute the midpoint m as a result of seeing
each other in state A, we let only robot r complete its cycle. Meanwhile, s has computed m but
still has not updated its state, nor moved. Therefore, r keeps seeing s set to A, and computes the
new midpoint without changing its own state. We let r complete another cycle, and then we let s
update its state and reach m. As a result, both robots are back in the same state and have not
gathered. By repeating this pattern, the robots never solve Rendezvous.
We now describe an algorithm (which is not in L) that solves the problem. Also this algorithm
uses the local unit distance as a computational tool, but in a rather different way since a robot
cannot remember and has to infer information by observing the other robot’s light.
Intuitively, the two robots try to reach a configuration in which both robots see each other at
distance lower than 1. To do so, they first communicate to the other whether or not the distance
they observe is smaller than 1 (recall that they may disagree, because their unit distances may
differ). If one robot acknowledges that its partner has observed a distance not smaller than 1, it
reduces the distance by moving toward the midpoint.
9
The process goes on until both robots observe a distance smaller than 1. At this point, if they
have not gathered yet, they try to compare their distance functions, in order to break symmetry.
They move away from each other in such a way that their final distance is the sum of their respective
unit distances. Before proceeding, they attempt to switch positions. If, due to asynchrony, they
failed to be in the same state at any time before this step, they end up gathering. Instead, if their
execution has been synchronous up to this point, they finally switch positions. Now, if the robots
have not gathered yet, they know that their distance is actually the sum of their unit distances.
Because each robot knows its own unit, they can tell if one of them is larger. If a robot has a
smaller unit, it moves toward its partner, which waits.
Otherwise, if their units are equal, they apply a simple protocol: as soon as a robot wakes up,
it moves toward the midpoint and orders its partner to stay still. If both robots do so, they gather
in the middle. If one robot is delayed due to asynchrony, it acknowledges the order to stay still and
tells the other robot to come.
>
Moving Away
Test
Me > 1
Approaching
Me < 1
Both < 1
You Moved
Coming
Waiting
Both = 2
Stay
Halted
d=0
d=2
d<2
d>2
>
d>1
>
d>1
d<1
d<1
d>0
d>0
d=0
Figure 2: State transitions in Algorithm 2.
Theorem 15. In ASynch, Rendezvous of two FComm robots is solvable with 12 colors. This
result holds even without unit distance agreement.
Proof. We show that Algorithm 2, also depicted in Figure 2, correctly solves Rendezvous. Both
robots start in state (Test), and then update their state to (Me ⩾1) or (Me < 1), depending if
they see each other at distance greater or lower than 1 (they may disagree, because their distance
functions may be different).
If robot r sees robot s set to (Me ⩾1), it starts approaching it by moving to the midpoint,
in order to reduce the distance. No matter if r approaches s several times before s is activated,
or both robots approach each other at different times, one of them eventually sees the other set to
(Approaching). When this happens, their distance has reduced by at least a half, and at least
one robot turns (Test) again, thus repeating the test on the distances.
At some point, both robots see each other at distance lower than 1 during a test, and at least
one of them turns (Both < 1). If they have not gathered yet, they attempt to break symmetry by
comparing their distance functions. To do so, when a robot sees the other set to (Both < 1), it
turns (Moving Away) and moves away by its own unit distance minus half their current distance.
This move will be performed at most once by each robot, because if one robot sees the other robot
10
Algorithm 2 Rendezvous for rigid ASynch with no unit distance agreement and 12 externally
visible states
1: dist ←∥other.position∥
2: if other.state = (Test) then
▷testing distances
3:
if dist ⩾1 then
4:
me.state ←(Me ⩾1)
5:
else
6:
me.state ←(Me < 1)
7: else if other.state = (Me ⩾1) then
▷reducing distances
8:
me.state ←(Approaching)
9:
me.destination ←other.position/2
10: else if other.state = (Approaching) then
▷test distances again
11:
me.state ←(Test)
12: else if other.state = (Me < 1) then
13:
if dist ⩾1 then
14:
me.state ←(Me ⩾1)
15:
else
16:
me.state ←(Both < 1)
17: else if other.state = (Both < 1) then
18:
if dist = 0 then
▷we have gathered
19:
me.state ←(Halted)
20:
else
21:
me.state ←(Moving Away)
22:
if dist < 1 then
▷moving away by 1 −dist/2
23:
me.destination ←other.position · (1/2 −1/dist)
24: else if other.state = (Moving Away) then
25:
me.state ←(You Moved)
26: else if other.state = (You Moved) then
27:
me.state ←(Coming)
28:
me.destination ←other.position
29: else if other.state = (Coming) then
30:
me.state ←(Waiting)
31: else if other.state = (Waiting) then
32:
if dist > 2 then
▷my unit is smaller
33:
me.state ←(Stay)
34:
me.destination ←other.position
35:
else if dist = 2 then
▷our units are equal
36:
me.state ←(Both = 2)
37:
else
▷my unit is bigger or we have gathered
38:
me.state ←(Halted)
39: else if other.state = (Both = 2) then
40:
me.state ←(Stay)
41:
if dist = 2 then
▷moving to the midpoint
42:
me.destination ←other.position/2
43: else if other.state = (Stay) then
44:
me.state ←(Halted)
11
45: else
▷other.state = (Halted)
46:
if dist = 0 then
▷we have gathered
47:
me.state ←(Halted)
48:
terminate
49:
else
▷maintain position while I come
50:
me.state ←(Stay)
51:
me.destination ←other.position
still set to (Both < 1), but it observes a distance not lower than 1, then it knows that it has
already moved away, and has to wait.
When a robot sees its partner set to (Moving Away), it shares this information by turning
(You Moved). If only one robot turns (You Moved), while the other is still set to (Moving
Away), then the second robot turns (Coming) and reaches the other robot, which just turns
(Waiting) and stays still until they gather.
Otherwise, if both robots see each other set to (You Moved), they both turn (Coming) and
switch positions. At least one of them then turns (Waiting). Now, if a robot sees its partner set
to (Waiting) and they have not gathered yet, it knows that their current distance is the sum of
their unit distances. If such distance is greater than 2, then the robot knows that its partner’s unit
distance is bigger, and it moves toward it, while ordering it to stay still. Vice versa, if the distance
observed is smaller than 2, the observing robot stays still and orders its partner to come.
Finally, if the distance observed is exactly 2, the observing robot knows that the two distance
functions are equal, and turns (Both = 2). In this case, a simple protocol allows them to meet. If
a robot sees the other set to (Both = 2) at distance 2, it turns (Stay) and moves to the midpoint.
If both robots do so, they eventually gather. Indeed, even if the first robot reaches the midpoint
while the other is still set to (Both = 2), it now sees its partner at distance 1, and knows that it
has to wait. On the other hand, whenever a robot sees its partner set to (Stay), it turns (Halted),
which tells its partner to reach it. This guarantees gathering even if only one robot attempts to
move to thee midpoint.
4.2
Semi-synchronous
In SSynch the situation is radically different from the ASynch case. In fact, it is possible to
find a simple solution in L that uses the minimum number of colors possible, and operates cor-
rectly without unit distance agreement, starting from any arbitrary color configuration, and with
interruptable movements (see Algorithm 3 and Figure 3).
Algorithm 3 Rendezvous for non-rigid SSynch with three externally visible states
1: if other.state = A then
2:
me.state ←B
3:
me.destination ←other.position/2
4: else if other.state = B then
5:
me.state ←C
6: else
▷other.state = C
7:
me.state ←A
8:
me.destination ←other.position
12
A
B
C
/
0
1 2
1
Figure 3: State transitions in Algorithm 3.
Theorem 16. In SSynch, Rendezvous of two FComm robots is solvable by an algorithm in L with
only three distinct colors. This result holds even if starting from an arbitrary color configuration,
without unit distance agreement, and with non-rigid movements.
Proof. We show that Algorithm 3 (see also Figure 3) correctly solves Rendezvous from any initial
configuration. Assume first that both robots start in the same state and both are activated at each
turn. Then they keep having equal states, and they cycle through states A, B, and C forever.
Every time they are both set to A, they move toward the midpoint and their distance reduces by
at least 2δ, until it becomes so small that they actually gather.
Otherwise, if at some point the two robots are in different states, they will keep staying in
different states forever. In this case their distance will never increase, and they will periodically be
found in states B and C, respectively. Whenever this happens, the robot set to C retains its state
and stays still until the other robot is activated and moves toward it by at least δ. As soon as their
distance becomes not greater than δ and they turn again B and C, they finally gather.
Note that the number of colors used by the algorithm is optimal. This follows as a corollary of
the impossibility result when lights are visible to both robots:
Lemma 17. [22] In SSynch, Rendezvous of two robots with persistent memory visible by both of
them is unsolvable by algorithms in L that use only two colors.
5
Movements: Knowledge vs. Rigidity
In this section, we consider the Rendezvous problem when the movement of the robots can be inter-
rupted by an adversary; previously, unless otherwise stated, we have considered rigid movements,
i.e., in each cycle a robot reaches its computed destination point. Now, the only constraint on the
adversary is that a robot, if interrupted before reaching its destination, moves by at least δ > 0
(otherwise, rendezvous is clearly impossible). We prove that, for rendezvous with lights, knowledge
of δ has the same power as rigidity of the movements. Note that knowing δ implies also that the
robots can agree on a unit distance.
5.1
FState Robots
Theorem 18. In non-rigid SSynch, Rendezvous of two FState robots with knowledge of δ is
solvable with three colors.
Proof. We show that Algorithm 4 correctly solves Rendezvous. Both robots start in state A. If a
robot sees its partner at distance lower than δ/2, it moves in the opposite direction, to the point
at distance δ/2 from its partner. On the other hand, if the distance observed is not lower than δ,
it moves toward the point located δ/4 before the midpoint.
13
After sufficiently many turns, the robots are found at a distance in the interval [δ/2, δ), and
both in state A. From now on, all their movements are rigid. If only one robot is activated, it
reaches its partner and Rendezvous is solved. Otherwise, they both turn B and switch positions.
Then, if both robots are activated, they gather in the midpoint. Otherwise, one of them turns
C and moves to the midpoint. Now, the robot still in B keeps staying still because it observes a
distance lower than δ/2. On the other hand, the robot set to C moves to its partner as soon as it
is activated.
Algorithm 4 Rendezvous for non-rigid SSynch with knowledge of δ and three internal states
1: dist ←∥other.position∥
2: if dist = 0 then
3:
terminate
4: if me.state = A then
5:
if dist < δ/2 then
▷reach the point at distance δ/2 from the other
6:
me.destination ←other.position · (1 −δ/(2 · dist))
7:
else if δ/2 ⩽dist < δ then
▷gather or switch positions
8:
me.state ←B
9:
me.destination ←other.position
10:
else
▷dist ⩾δ, reach the point at distance δ/4 from the midpoint
11:
me.destination ←other.position · (1/2 −δ/(4 · dist))
12: else if me.state = B then
13:
if δ/2 ⩽dist < δ then
14:
me.state ←C
15:
me.destination ←other.position/2
16: else
▷me.state = C
17:
me.destination ←other.position
5.2
FComm Robots
Theorem 19. In non-rigid ASynch, Rendezvous of two FComm robots with knowledge of δ is
solvable with three colors.
Proof. We show that Algorithm 5 correctly solves Rendezvous. Both robots begin their execution
in state Start, and attempt to position themselves at a distance in the interval (δ, 2δ]. To do so,
they adjust their position by moving by δ/2 at each step. When a robot sees its partner at the
desired distance, it turns Ready and stops. It is easy to prove that, even if its partner is still
moving, it will end its move at a distance in the interval (δ, 2δ].
When a robot sees its partner set to Ready, it turns Come and moves to the midpoint. The
midpoint is eventually reached, because the distance traveled is not greater than δ. Assume that
both robots turn Ready, both see each other, and move toward the midpoint. If robot r reaches
the midpoint and sees its partner s still on its way and set to Come, r turns Ready and keeps
chasing s. When s reaches its destination and sees r set to Ready and at distance at most δ, it
stays still and waits until Rendezvous is solved.
Similarly, assume that r sees s set to Ready and turns Come before s sees r set to Ready. r will
reach the midpoint and stay there, while s will start chasing r until they meet in the midpoint.
14
Algorithm 5 Rendezvous for non-rigid ASynch with knowledge of δ and three externally visible
states
1: dist ←∥other.position∥
2: if other.state = Start then
3:
if dist = 0 then
▷we have already gathered
4:
me.state ←Come
5:
else if dist ⩽δ then
▷moving δ/2 away
6:
me.state ←Start
7:
me.destination ←−other.position · δ/(2 · dist)
8:
else if dist > 2δ then
▷moving δ/2 in
9:
me.state ←Start
10:
me.destination ←other.position · δ/(2 · dist)
11:
else
▷δ < dist ⩽2δ, ready to gather
12:
me.state ←Ready
13: else if other.state = Ready then
14:
me.state ←Come
15:
if δ < dist ⩽2δ then
▷reaching the midpoint
16:
me.destination ←other.position/2
17: else
▷other.state = Come
18:
if dist = 0 then
▷we have gathered
19:
me.state ←Come
20:
terminate
21:
else
22:
me.state ←Ready
23:
me.destination ←other.position
15
6
Open Problems
We have shown that rendezvous can be obtained both in FState and FComm, two models sub-
stantially weaker than the one of [8], where both internal memory and communication memory
capabilities are present. Our results open several new problems and research questions.
Our results, showing that rendezvous is possible in SSynch for FState robots and in ASynch
for FComm robots, seem to indicate that “it is better to communicate than to remember”. How-
ever, determining the precise computational relationship between FState and FComm is an open
problem. To settle it, it must be determined whether or not it is possible for FState robots to
rendezvous in ASynch.
Although minimizing the amount of constant memory was not the primary focus of this paper,
the number of states employed by our algorithms is rather small. An interesting research ques-
tion is to determine the smallest amount of memory necessary for the robots to rendezvous when
rendezvous is possible, and devise optimal solution protocols.
The knowledge of δ in non-rigid scenarios is quite powerful and allows for simple solutions. It
is an open problem to study the Rendezvous problem for FState and FComm robots when δ is
unknown or not known precisely.
This paper has extended the classical models of oblivious silent robots into two directions:
adding finite memory, and enabling finite communication. It thus opens the investigation in the
FState and FComm models of other classical robots problems (e.g., Pattern Formation, Flocking,
etc.); an exception is Gathering because, as mentioned in the introduction, it is already solvable
without persistent memory and without communication [4].
References
[1] N. Agmon and D. Peleg. Fault-tolerant gathering algorithms for autonomous mobile robots.
SIAM Journal on Computing, 36:56–82, 2006.
[2] Z. Bouzid, S. Das, and S. Tixeuil.
Gathering of Mobile Robots Tolerating Multiple Crash
Faults. In Proceedings of 33rd IEEE International Conference on Distributed Computing Systems
(ICDCS), 2013.
[3] Z. Bouzid, M. Gradinariu Potop-Butucaru, and S. Tixeuil. Byzantine convergence in robot
networks: The price of asynchrony. In Proceedings of 13th International Conference Principles
of Distributed Systems (OPODIS), pages 54–70, 2009.
[4] M. Cieliebak, P. Flocchini, G. Prencipe, and N. Santoro. Distributed computing by mobile
robots: Gathering. SIAM Journal on Computing, 41(4): 829-879, 2012.
[5] R. Cohen and D. Peleg. Convergence properties of the gravitational algorithm in asynchronous
robot systems. SIAM Journal on Computing, 34:1516–1528, 2005.
[6] R. Cohen and D. Peleg. Convergence of autonomous mobile robots with inaccurate sensors
and movements.
In Proceedings of 23rd International Symposium on Theoretical Aspects of
Computer Science (STACS), pages 549—560, 2006.
[7] A. Cord-Landwehr, B. Degener, M. Fischer, M. H¨ullmann, B. Kempkes, A. Klaas, P. Kling,
S. Kurras, M. Mrtens, F. Meyer auf der Heide, C. Raupach, K. Swierkot, D. Warner, C. Wed-
demann, and D. Wonisch. A new approach for analyzing convergence algorithms for mobile
16
robots. In Proceedings of 38th International Colloquium on Automata, Languages and Program-
ming (ICALP), pages 650–661. Springer, 2011.
[8] S. Das, P. Flocchini, G. Prencipe, N. Santoro, and M. Yamashita. The power of lights: syn-
chronizing asynchronous robots using visible bits. In Proceedings of the 32nd International
Conference on Distributed Computing Systems (ICDCS), pages 506–515, 2012.
[9] X. D´efago, M. Gradinariu, S. Messika, and P. Raipin-Parv´edy. Fault-tolerant and self-stabilizing
mobile robots gathering. In Proc. 20th Intl. Symp. on Distributed Computing (DISC), pages
46–60, 2006.
[10] B. Degener, B. Kempkes, T. Langner, F. Meyer auf der Heide, P. Pietrzyk, and R. Wattenhofer.
A tight runtime bound for synchronous gathering of autonomous robots with limited visibility.
In Proceedings of 23rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA),
pages 139–148, 2011.
[11] Y. Dieudonn´e and F. Petit. Self-stabilizing gathering with strong multiplicity detection. The-
oretical Computer Science, 428(13), 2012.
[12] P. Flocchini, G. Prencipe, and N. Santoro. Distributed Computing by Oblivious Mobile Robots.
Morgan & Claypool, 2012.
[13] P. Flocchini, G. Prencipe, N. Santoro, and P. Widmayer. Gathering of asynchronous robots
with limited visibility. Theoretical Computer Science, 337(1-3):147–168, 2005.
[14] T. Izumi, Z. Bouzid, S. Tixeuil, and K. Wada. Brief Announcement: The BG-simulation for
Byzantine mobile robots. Proceedings od 25-th Intl. Symp. on Distributed Computing (DISC),
pages 330–331, 2011.
[15] T. Izumi, S. Souissi, Y. Katayama, N. Inuzuka, X. Defago, K. Wada, and M. Yamashita.
The gathering problem for two oblivious robots with unreliable compasses. SIAM Journal on
Computing, 41(1):26–46, 2012.
[16] S. Kamei, A. Lamani, F. Ooshita, and S. Tixeuil.
Asynchronous mobile robot gathering
from symmetric configurations without global multiplicity detection. In Proceedings of 18th
Int. Colloquium on Structural Information and Communication Complexity (SIROCCO), pages
150–161, 2011.
[17] J. Lin, A.S. Morse, and B.D.O. Anderson. The multi-agent rendezvous problem. parts 1 and
2. SIAM Journal on Control and Optimization, 46(6):2096–2147, 2007.
[18] L. Pagli, G. Prencipe, and G. Viglietta. Getting close without touching. In Proceedings of 19th
Int. Colloquium on Structural Information and Communication Complexity (SIROCCO), pages
315–326, 2012.
[19] G. Prencipe. Impossibility of gathering by a set of autonomous mobile robots. Theoretical
Computer Science, 384(2-3):222–231, 2007.
[20] S. Souissi, X. D´efago, and M. Yamashita. Using eventually consistent compasses to gather
memory-less mobile robots with limited visibility.
ACM Transactions on Autonomous and
Adaptive Systems, 4(1):1–27, 2009.
17
[21] I. Suzuki and M. Yamashita. Distributed anonymous mobile robots: Formation of geometric
patterns. SIAM Journal on Computing, vol. 28, pp. 1347–1363, 1999.
[22] G. Viglietta. Rendezvous of two robots with visible bits. Technical Report arXiv:1211.6039,
2012.
18
Rendezvous of Two Robots with Constant Memory
P. Flocchini∗
N. Santoro†
G. Viglietta†
M. Yamashita‡
Abstract
We study the impact that persistent memory has on the classical rendezvous problem of two
mobile computational entities, called robots, in the plane. It is well known that, without addi-
tional assumptions, rendezvous is impossible if the entities are oblivious (i.e., have no persistent
memory) even if the system is semi-synchronous (SSynch). It has been recently shown that
rendezvous is possible even if the system is asynchronous (ASynch) if each robot is endowed
with O(1) bits of persistent memory, can transmit O(1) bits in each cycle, and can remember
(i.e., can persistently store) the last received transmission. This setting is overly powerful.
In this paper we weaken that setting in two different ways: (1) by maintaining the O(1) bits
of persistent memory but removing the communication capabilities; and (2) by maintaining the
O(1) transmission capability and the ability to remember the last received transmission, but
removing the ability of an agent to remember its previous activities. We call the former setting
finite-state (FState) and the latter finite-communication (FComm). Note that, even though
its use is very different, in both settings, the amount of persistent memory of a robot is constant.
We investigate the rendezvous problem in these two weaker settings. We model both settings
as a system of robots endowed with visible lights: in FState, a robot can only see its own light,
while in FComm a robot can only see the other robot’s light. We prove, among other things,
that finite-state robots can rendezvous in SSynch, and that finite-communication robots are
able to rendezvous even in ASynch. All proofs are constructive: in each setting, we present a
protocol that allows the two robots to rendezvous in finite time.
1
Introduction
1.1
Framework and Background
Rendezvous is the process of two computational mobile entities, initially dispersed in a spatial
universe, meeting within finite time at a location, non known a priori. When there are more than
two entities, this task is known as Gathering. These two problems are core problems in distributed
computing by mobile entities. They have been intensively and extensively studied when the universe
is a connected region of R2 in which the entities, usually called robots, can freely move; see, for
example, [1, 3, 4, 5, 7, 10, 11, 13, 16, 17, 18, 19, 20].
Each entity is modeled as a point, it has its own local coordinate system of which it perceives
itself as the centre, and has its own unit distance. Each entity operates in cycles of Look, Com-
pute, Move activities. In each cycle, an entity observes the position of the other entities expressed
in its local coordinate system (Look); using that observation as input, it executes a protocol (the
same for all robots) and computes a destination point (Compute); it then moves to the computed
destination point (Move). Depending on the activation schedule and the synchronization level,
three basic types of systems are identified in the literature: a fully synchronous system (FSynch)
∗School of Electrical Engineering and Computer Science, University of Ottawa, Canada.
†School of Computer Science, Carleton University, Canada.
‡Kyushu University, Fukuoka, Japan.
1
arXiv:1306.1956v1  [cs.MA]  8 Jun 2013
is equivalent to a system where there is a common clock and at each clock tick all entities are
activated simultaneously, and Compute and Move are instantaneous; a semi-synchronous system
(SSynch) is like a fully synchronous one except that, at each clock tick, only some entities will be
activated (the choice is made by a fair scheduler); in a fully asynchronous system (ASynch), there
is no common notion of time, each Compute and Move of each robot can take an unpredictable
(but finite) amount of time, and the interval of time between successive activities is finite but un-
predictable. The focus of almost all algorithmic investigations in the continuous setting has been
on oblivious robots, that is when the memory of the robots is erased at the end of each cycle, in
other words the robots have no persistent memory (e.g., for an overview see [12]).
The importance of Rendezvous in the continuous setting derives in part from the fact that
it separates FSynch from SSynch for oblivious robots. Indeed, Rendezvous is trivially solvable
in a fully synchronous system, without any additional assumption. However, without additional
assumptions, Rendezvous is impossible for oblivious robots if the system is semi-synchronous [21].
Interestingly, from a computational point of view, Rendezvous is very different from the Gath-
ering problem of having k ⩾3 robots meet in the same point; in fact, Gathering of oblivious robots
is always possible for any k ⩾3 even in ASynch without any additional assumption other than
multiplicity detection [4]. Furthermore, in SSynch, k ⩾3 robots can gather even in spite of a
certain number of faults [1, 2, 9], and converge in spite of inaccurate measurements [6]; see also
[14].
The Rendezvous problem also shows the impact of certain factors. For example, the problem
has a trivial solution if the robots are endowed with consistent compasses even if the system is fully
asynchronous. The problem is solvable in ASynch even if the local compasses have some degree of
inconsistency (a tilt of an appropriate angle) [15]; the solution is no longer trivial, but does exist.
In this paper, we are concerned with the impact that memory has on the solvability of the
Rendezvous problem. In particular, we are interested in determining what type and how much
persistent memory would allow the robots to rendezvous. What is known in this regard is very little.
On the one hand, it is well known that, in absence of additional assumptions, without persistent
memory rendezvous is impossible even in SSynch [21]. On the other hand, a recent result shows
that rendezvous is indeed possible even in ASynch if each robot has O(1) bits of persistent memory
and can transmit O(1) bits in each cycle and can remember (i.e., can persistently store) the last
received transmission [8] (see also [22] for size-optimal solutions).
The conditions of the latter result are overly powerful. The natural question is whether the
simultaneous presence of these conditions is truly necessary for rendezvous.
1.2
Main Contributions
In this paper we address this question by weakening the setting in two different ways, and investigate
the Rendezvous problem in these weaker settings. Even though its use is very different, in both
settings, the amount of persistent memory of a robot is constant.
We first examine the setting where the two robots have O(1) bits of internal persistent memory
but cannot communicate; this corresponds to the finite-state (FState) robots model. Among other
contributions, we prove that FState robots with rigid movements can rendezvous in SSynch, and
that this can be done using only six internal states. The proof is constructive: we present a protocol
that allows the two robots to rendezvous in finite time under the stated conditions.
We then study the finite-communication (FComm) setting, where a robot can transmit O(1)
bits in each cycle and remembers the last received transmission, but it is otherwise oblivious: it
has no other persistent memory of its previous observations, computations and transmissions. We
prove that two FComm robots with rigid movements are able to rendezvous even in ASynch; this
2
is doable even if the different messages that can be sent are just 12. We also prove that only three
different messages suffice in SSynch. Also for this model all the proofs are constructive.
Finally, we consider the Rendezvous problem when the movement of the robots can be inter-
rupted by an adversary (in the above results, in each cycle a robot reaches its computed destination
point). The only constraint on the adversary is that a robot moves at least a distance δ > 0 (oth-
erwise, rendezvous is clearly impossible). We show that, with knowledge of δ, three internal states
are sufficient to solve Rendezvous by FState robots in SSynch, and three possible messages are
sufficient for FComm robots in ASynch. In other words, we prove that rigidity of the movements
can be traded with knowledge of δ.
These results are obtained modeling both settings as a system of robots endowed with a constant
number of visible lights: a FState robot can see only its own light, while a FComm robot can see
only the other robot’s light. Our results seem to indicate that “it is better to communicate than
to remember”.
In addition to the specific results on the Rendezvous problem, an important contribution of this
paper is the extension of the classical model of oblivious silent robots into two directions: adding
finite memory, and enabling finite communication.
2
Model and Terminology
The general model we employ is the standard one, described in [12]. The two robots are autonomous
computational entities modeled as points moving in R2. Each robot has its own coordinate system
and its own unit distance, which may differ from each other, and it always perceives itself as lying
at the origin of its own local coordinate system. Each robot operates in cycles that consist of
three phases: Look, Compute, and Move. In the Look phase it gets the position (in its local
coordinate system) of the other robot; in the Compute phase, it computes a destination point;
in the Move phase it moves to the computed destination point, along a straight line. Without
loss of generality, the Look phase is assumed to be instantaneous. The robots are anonymous and
oblivious, meaning that they do not have distinct identities, they execute the same algorithm in
each Compute phase, and the input to such algorithm is the snapshot coming from the previous
Look phase.
Here we study two settings; both settings can be described as restrictions of the model of visibile
lights introduced in [8]. In that model, each robot carries a persistent memory of constant size,
called light; the value of the light is called color or state, and it is set by the robot during each
Compute phase. Other than their own light, the robots have no other persistent memory of past
snapshots and computations.
In the first setting, that of silent finite-state (or simply, FState) robots, the light of a robot
is visible only to the robot itself; i.e., the colored light merely encodes an internal state. In the
second setting, of oblivious finite-communication (or simply FComm) robots, the light of a robot
is visible only to the other robot; i.e., they can communicate with the other robot through their
colored light, but by their next cycle they forget even the color of their own light (since they do
not see it). The color a robot sees is used as input during the computation.
In the asynchronous (ASynch) model, the robots are activated independently, and the duration
of each Compute, Move and inactivity is finite but unpredictable. As a result, the robots do not
have a common notion of time, robots can be seen while moving, and computations can be made
based on obsolete observations. In the semi-synchronous (SSynch) models the activations of robots
can be logically divided into global rounds; in each round, one or both robots are activated, obtain
the same snapshot, compute, and perform their move. It is assumed that the activation schedule
3
is fair, i.e., each robot is activated infinitely often.
Depending on whether or not the adversary can stop a robot before it reaches its computed
destination, the movements are called non-rigid and rigid, respectively. In the case of non-rigid
movements, there exists a constant δ > 0 such that if the destination point’s distance is smaller
than δ, the robot will reach it; otherwise, it will move towards it by at least δ. Note that, without
this assumption, an adversary could make it impossible for any robot to ever reach its destination,
following a classical Zenonian argument.
The two robots solve the Rendezvous problem if, within finite time, they move to the same
point and do not move from there; the meeting point is not determined a priori. A rendezvous
algorithm for SSynch (resp., ASynch) is a protocol that allows the robots to solve the Rendezvous
problem under any possible execution schedule in SSynch (resp., ASynch). A particular class of
algorithms, denoted by L, is that where each robot may only compute a destination point of the
form λ · other.position, for some λ ∈R obtained as a function only of the light of which the robot
is aware (i.e., its internal state in the FState model, or the other robot’s color in the FComm
model). The algorithms of this class are of interest because they operate also when the coordinate
system of a robot is not self-consistent (i.e., it can unpredictably rotate, change its scale or undergo
a reflection).
3
Finite-State Robots
We fist consider FState robots and we start by identifying a simple impossibility result for algo-
rithms in L.
Theorem 1. In SSynch, Rendezvous of two FState robots is unsolvable by algorithms in L,
regardless of the amount of their internal memory.
Proof. For each robot, the destination point and the next state are a function of the internal state
only. Assuming that both robots start in the same state, we keep activating them one at a time,
alternately. Hence, every other turn they are in the same state. As soon as the first robot attempts
to move to the other robot’s location, we activate both robots simultaneously, making them switch
positions. By repeating this pattern, the robots never gather.
Thus the computation of the destination must take into account more than just the lights (or states)
of which the robot is aware.
The approach we use to circumvent this impossibility result is to have each robot use its own
unit of distance as a computational tool; recall that the two robots might have different units,
and they are not known to each other. We propose Algorithm 1 for Rendezvous in SSynch, also
illustrated in Figure 1. Each robot has six internal states, namely Sstart, S1, Sleft
2
, Sright
2
, S3, and
Sfinish. Both robots are assumed to begin their execution in Sstart. Each robot lies in the origin of
its own local coordinate system and the two robots have no agreement on axes orientations or unit
distance.
Intuitively, the robots try to reach a configuration in which they both observe the other robot
at distance not lower than 1 (their own unit). From this configuration, they attempt to meet in the
midpoint. If they never meet because they are never activated simultaneously, at some point one
of them notices that its observed distance is lower than 1. This implies a breakdown of symmetry
that enables the robots to finally gather.
In order to reach the desired configuration in which they both observe a distance not lower than
1, the two robots first try to move farther away from each other if they are too close. If they are
far enough, they memorize the side on which they see each other (left or right), and try to switch
4
positions. If only one of them is activated, they gather; otherwise they detect a side switch and
they can finally apply the above protocol. This is complicated by the fact that the robots may
disagree on the distances they observe. To overcome this difficulty, they use their ability to detect
a side switch to understand which distance their partner observed. If the desired configuration is
not reached because of a disagreement, a breakdown of symmetry occurs, which is immediately
exploited to gather anyway. As soon as the two robots coincide at the end of a cycle, they never
move again, and Rendezvous is solved.
start
S
1
S
2
left
S
2
right
S
finish
S
3
S
1
,)
∞
+
,
(left) [1
1
,)
∞
+
,
(right) [1
1
,)
∞
+
,
(right) (1
1
,)
∞
+
,
(left) (1
dist
1
−
1
,
1)
,
[0
2
1
,)
∞
+
,
(left) [1
2
1
,)
∞
+
,
(right) [1
1
,)
∞
+
,
(right) [0
1
,)
∞
+
,
(left) [0
0
,)
2
1
,
(left) [0
0
,)
2
1
,
(right) [0
2
1
,
1)
,
2
1
(right) [
2
1
,
1)
,
2
1
(left) [
0
,
1]
,
[0
1
,)
∞
+
,
(1
0
,)
4
1
,
[0
1
,)
2
1
,
4
1[
0
,
1]
,
[0
Figure 1: Illustration of Algorithm 1. A label of the form (d)I, λ denotes a transition that applies
when the other robot is seen in direction d ∈{left, right} and its observed distance lies in the
interval I ⊂R. The computed destination point is λ · other.position. For example, a robot in state
Sstart perceiving the other at distance ⩾1 on the right will move to the position of the other robot
and will change state to Sright
2
.
To analyze the correctness of Algorithm 1, some terminology is needed. In the following, the
two robots will be called r and s, respectively. An expression of the form (Sr, Ss, Ir, Is) denotes a
configuration in which robot r (resp. s) is in state Sr (resp. Ss), and the distance at which it sees
the other robot lies in the interval Ir (resp. Is), according to its own distance function. Therefore,
the starting configuration of r and s is (Sstart, Sstart, [0, +∞), [0, +∞)).
With abuse of notation, we will say that a robot is in state S=
2 if it is in state Sleft
2
(resp. Sright
2
)
and it sees the other robot on its left (resp. right). Analogously, a robot is said to be in state S̸=
2
if its state is Sleft
2
or Sright
2
and it has detected a switch. For a configuration C, the expression C ↓
means that, whenever the two robots reach C, Rendezvous is eventually solved.
Observation 2. (Sa, Sb, Ia, Ib) ↓if and only if (Sb, Sa, Ib, Ia) ↓.
Observation 3. If (Sr, Ss, Ir, Is) ↓and I′
r ⊆Ir, then (Sr, Ss, I′
r, Is) ↓.
Lemma 4. (Sfinish, S3, [0, 1], [1/4, 1/2)) ↓.
5
Algorithm 1
Rendezvous for rigid SSynch with no unit distance agreement and six internal
states
1: dist ←∥other.position∥
2: if dist = 0 then
3:
terminate
4: if other.position.x > 0 then
5:
dir ←right
6: else if other.position.x < 0 then
7:
dir ←left
8: else if other.position.y > 0 then
▷other.position.x = 0
9:
dir ←right
10: else
11:
dir ←left
12: if me.state = Sstart then
13:
if dist < 1 then
14:
me.state ←S1
15:
me.destination ←other.position · (1 −1/dist)
16:
else
17:
me.state ←Sdir
2
18:
me.destination ←other.position
19: else if me.state = S1 then
20:
if dist ⩽1 then
21:
me.state ←Sfinish
22:
me.destination ←(0, 0)
23:
else
24:
me.state ←Sdir
2
25:
me.destination ←other.position
26: else if me.state = Sd
2 then
27:
if dir = d then
28:
me.state ←Sfinish
29:
me.destination ←other.position
30:
else if dist < 1/2 then
▷side switch detected
31:
me.state ←Sfinish
32:
me.destination ←(0, 0)
33:
else
34:
me.destination ←other.position/2
35:
if dist < 1 then
36:
me.state ←S3
6
37: else if me.state = S3 then
38:
me.state ←Sfinish
39:
if dist < 1/4 then
40:
me.destination ←(0, 0)
41:
else
▷1/4 ⩽d < 1/2
42:
me.destination ←other.position
43: else
▷me.state = Sfinish
44:
if dist ⩽1 then
45:
me.destination ←(0, 0)
46:
else
47:
me.destination ←other.position
Proof. Robot r keeps staying still, while robot s moves to r as soon as it is activated.
Lemma 5. (Sfinish, S̸=
2 , [0, 1], [1/2, +∞)) ↓.
Proof. Robot s keeps moving to the midpoint, while robot r never moves, because it keeps ob-
serving a distance not greater than 1. As soon as s observes a distance smaller than 1 (hence
in [1/2, 1)), its state becomes S3 and it moves to the midpoint again. Now the configuration is
(Sfinish, S3, [0, 1/2], [1/4, 1/2)), and Lemma 4 applies.
Lemma 6. (Sfinish, S=
2 , [0, 1], [0, +∞)) ↓.
Proof. Robot r keeps staying still, while robot s moves to r as soon as it is activated.
Lemma 7. (S3, S̸=
2 , [1/4, 1/2), [0, +∞)) ↓.
Proof. If only robot r is activated, it moves to s, and Rendezvous is solved.
If only robot s is activated, two cases arise.
If the distance observed by s is less than 1/2,
configuration (S3, Sfinish, [1/4, 1/2), [0, 1/2)) is reached, and Lemma 4 applies. Otherwise, if the dis-
tance observed by s is at least 1/2, s moves to the midpoint (and possibly switches to S3). As a
consequence, the distance observed by r becomes less than 1/4, hence it stays still forever (it only
switches to Sfinish as soon as it is activated). On the other hand, s keeps moving to the midpoint,
until it observes a distance lower than 1, switches to S3, and finally moves to r, solving Rendezvous.
If both robots are activated on the first cycle, three cases arise.
• If the distance observed by s is less than 1/2, r moves to s and s stays still, hence Rendezvous
is solved.
• If the distance observed by s lies in [1/2, 1), configuration (Sfinish, S3, [1/8, 1/4), [1/4, 1/2)) is
reached, and Lemma 4 applies.
• If the distance observed by s is at least 1, configuration (Sfinish, S=
2 , [1/8, 1/4), [1/2, +∞)) is
reached (the two robots switch sides), and Lemma 6 applies.
Lemma 8. (S̸=
2 , S̸=
2 , [0, 1/2), [1/2, +∞)) ↓.
7
Proof. If both robots are activated, two cases arise. If the distance observed by s is less than
1, configuration (Sfinish, S3, [0, 1/4), [1/4, 1/2)) is reached, and Lemma 4 applies. Otherwise, if the
distance is at least 1, configuration (Sfinish, S̸=
2 , [0, 1/4), [1/2, +∞)) is reached, and Lemma 5 applies.
If only r is activated, configuration (Sfinish, S̸=
2 , [0, 1/2), [1/2, +∞)) is reached, and Lemma 5
applies.
If only robot s is activated, two cases arise.
If the distance observed by s is less than 1,
configuration (S̸=
2 , S3, [0, 1/4), [1/4, 1/2)) is reached, and Lemma 7 applies. Otherwise, if the distance
is at least 1, the configuration remains (S̸=
2 , S̸=
2 , [0, 1/2), [1/2, +∞)), but the distance between the two
robots has halved. As the execution progresses, this case cannot repeat forever, because eventually
the distance observed by s becomes less than 1, or r is activated.
Lemma 9. (S̸=
2 , S̸=
2 , [1, +∞), [1, +∞)) ↓.
Proof. If both robots are activated, they compute the midpoint and they gather. If only one robot is
activated at each cycle, configuration (S̸=
2 , S̸=
2 , [1, +∞), [1, +∞)) keeps repeating for finitely many
cycles, until the distance observed by some robot, say r, becomes less than 1. The configuration
then becomes (S̸=
2 , S̸=
2 , [1/2, 1), [1/2, +∞)).
Once again, if both robots are activated at the next cycle, they gather in the midpoint. If only
r is activated, configuration (S3, S̸=
2 , [1/4, 1/2), [1/4, +∞)) is reached, and Lemma 7 applies. On the
other hand, if only s is activated, two cases arise. If the distance observed by s is less than 1,
configuration (S̸=
2 , S3, [1/4, 1/2), [1/4, 1/2)) is reached, and Lemma 7 applies again. If the distance is
at least 1, then configuration (S̸=
2 , S̸=
2 , [1/4, 1/2), [1/2, +∞)) is reached, and Lemma 8 applies.
Lemma 10. (S1, Sfinish, [0, 1], (1, +∞)) ↓and (S1, Sstart, [0, 1], [1, +∞)) ↓.
Proof. Robot r switches to Sfinish as soon as it is activated, and keeps staying still. Robot s moves
to r as soon as it is activated.
Lemma 11. (S1, Sstart, {1}, [0, +∞)) ↓.
Proof. If the distance observed by robot s is at least 1, then Lemma 10 applies. Otherwise the
configuration is (S1, Sstart, {1}, [0, 1)). Three cases arise.
• If both robots are activated at the first cycle, they reach configuration (Sfinish, S1, (1, +∞), {1}),
and Lemma 10 applies.
• If only robot r is activated at the first cycle, configuration (Sfinish, Sstart, {1}, [0, 1)) is reached.
Now r keeps staying still and in state Sfinish.
As soon as s is activated, configuration
(Sfinish, S1, (1, +∞), {1}) is reached, and Lemma 10 applies.
• If only robot s is activated at the first cycle, configuration (S1, S1, (1, +∞), {1}) is reached.
From now on, s keeps staying still (possibly switching to Sfinish), whereas r moves to s as
soon as it is activated.
Lemma 12. (S1, S1, (1, +∞), (1, +∞)) ↓.
Proof. If only one robot is activated, it moves to the other robot, and Rendezvous is solved. If
both robots are activated, they turn to Sleft
2
or Sright
2
and switch positions.
Hence they reach
configuration (S̸=
2 , S̸=
2 , (1, +∞), (1, +∞)), and Lemma 9 applies.
8
Theorem 13. In SSynch, Rendezvous of two FState robots is solvable with six internal states.
This result holds even without unit distance agreement.
Proof. We prove that (Sstart, Sstart, [0, +∞), [0, +∞)) ↓. Three cases arise.
• Let the configuration be (Sstart, Sstart, [0, 1), [0, 1)). If only one robot is activated, say r, then
configuration (S1, Sstart, {1}, [0, +∞)) is reached, and Lemma 11 applies. If both robots are
activated, configuration (S1, S1, (1, +∞), (1, +∞)) is reached, and Lemma 12 applies.
• Let the configuration be (Sstart, Sstart, [1, +∞), [0, 1)) (the symmetric case is equivalent, due
to Observation 2). If only robot r is activated, it moves to s and Rendezvous is solved. If
only s is activated, configuration (Sstart, S1, (1, +∞), {1}) is reached, and Lemma 10 applies.
Finally, if both robots are activated, configuration (S=
2 , S1, [0, +∞), [0, 1)) is reached. Next, if
only robot s is activated, configuration (S=
2 , Sfinish, [0, +∞), [0, 1)) is reached, and Lemma 6
applies. In any other case, r moves to s and Rendezvous is solved.
• Let the configuration be (Sstart, Sstart, [1, +∞), [1, +∞)). If only one robot is activated, it
moves to the other robot, and Rendezvous is solved. If both robots move, they switch posi-
tions, and the configuration becomes (S̸=
2 , S̸=
2 , [1, +∞), [1, +∞)). Then Lemma 9 applies.
4
Finite-Communication Robots
We now focus on FComm robots distinguishing the asynchronous and the semi-synchronous cases.
4.1
Asynchronous
It is not difficult to see that algorithms in L are not sufficient to solve the problem.
Theorem 14. In ASynch, Rendezvous of two FComm robots is unsolvable by algorithms in L,
regardless of the amount of colors employed.
Proof. For each robot, the destination point and the next state are a function of the state of the
other robot only. Assuming that both robots start in the same state, we let them perform their
execution synchronously. As soon as both robots compute the midpoint m as a result of seeing
each other in state A, we let only robot r complete its cycle. Meanwhile, s has computed m but
still has not updated its state, nor moved. Therefore, r keeps seeing s set to A, and computes the
new midpoint without changing its own state. We let r complete another cycle, and then we let s
update its state and reach m. As a result, both robots are back in the same state and have not
gathered. By repeating this pattern, the robots never solve Rendezvous.
We now describe an algorithm (which is not in L) that solves the problem. Also this algorithm
uses the local unit distance as a computational tool, but in a rather different way since a robot
cannot remember and has to infer information by observing the other robot’s light.
Intuitively, the two robots try to reach a configuration in which both robots see each other at
distance lower than 1. To do so, they first communicate to the other whether or not the distance
they observe is smaller than 1 (recall that they may disagree, because their unit distances may
differ). If one robot acknowledges that its partner has observed a distance not smaller than 1, it
reduces the distance by moving toward the midpoint.
9
The process goes on until both robots observe a distance smaller than 1. At this point, if they
have not gathered yet, they try to compare their distance functions, in order to break symmetry.
They move away from each other in such a way that their final distance is the sum of their respective
unit distances. Before proceeding, they attempt to switch positions. If, due to asynchrony, they
failed to be in the same state at any time before this step, they end up gathering. Instead, if their
execution has been synchronous up to this point, they finally switch positions. Now, if the robots
have not gathered yet, they know that their distance is actually the sum of their unit distances.
Because each robot knows its own unit, they can tell if one of them is larger. If a robot has a
smaller unit, it moves toward its partner, which waits.
Otherwise, if their units are equal, they apply a simple protocol: as soon as a robot wakes up,
it moves toward the midpoint and orders its partner to stay still. If both robots do so, they gather
in the middle. If one robot is delayed due to asynchrony, it acknowledges the order to stay still and
tells the other robot to come.
>
Moving Away
Test
Me > 1
Approaching
Me < 1
Both < 1
You Moved
Coming
Waiting
Both = 2
Stay
Halted
d=0
d=2
d<2
d>2
>
d>1
>
d>1
d<1
d<1
d>0
d>0
d=0
Figure 2: State transitions in Algorithm 2.
Theorem 15. In ASynch, Rendezvous of two FComm robots is solvable with 12 colors. This
result holds even without unit distance agreement.
Proof. We show that Algorithm 2, also depicted in Figure 2, correctly solves Rendezvous. Both
robots start in state (Test), and then update their state to (Me ⩾1) or (Me < 1), depending if
they see each other at distance greater or lower than 1 (they may disagree, because their distance
functions may be different).
If robot r sees robot s set to (Me ⩾1), it starts approaching it by moving to the midpoint,
in order to reduce the distance. No matter if r approaches s several times before s is activated,
or both robots approach each other at different times, one of them eventually sees the other set to
(Approaching). When this happens, their distance has reduced by at least a half, and at least
one robot turns (Test) again, thus repeating the test on the distances.
At some point, both robots see each other at distance lower than 1 during a test, and at least
one of them turns (Both < 1). If they have not gathered yet, they attempt to break symmetry by
comparing their distance functions. To do so, when a robot sees the other set to (Both < 1), it
turns (Moving Away) and moves away by its own unit distance minus half their current distance.
This move will be performed at most once by each robot, because if one robot sees the other robot
10
Algorithm 2 Rendezvous for rigid ASynch with no unit distance agreement and 12 externally
visible states
1: dist ←∥other.position∥
2: if other.state = (Test) then
▷testing distances
3:
if dist ⩾1 then
4:
me.state ←(Me ⩾1)
5:
else
6:
me.state ←(Me < 1)
7: else if other.state = (Me ⩾1) then
▷reducing distances
8:
me.state ←(Approaching)
9:
me.destination ←other.position/2
10: else if other.state = (Approaching) then
▷test distances again
11:
me.state ←(Test)
12: else if other.state = (Me < 1) then
13:
if dist ⩾1 then
14:
me.state ←(Me ⩾1)
15:
else
16:
me.state ←(Both < 1)
17: else if other.state = (Both < 1) then
18:
if dist = 0 then
▷we have gathered
19:
me.state ←(Halted)
20:
else
21:
me.state ←(Moving Away)
22:
if dist < 1 then
▷moving away by 1 −dist/2
23:
me.destination ←other.position · (1/2 −1/dist)
24: else if other.state = (Moving Away) then
25:
me.state ←(You Moved)
26: else if other.state = (You Moved) then
27:
me.state ←(Coming)
28:
me.destination ←other.position
29: else if other.state = (Coming) then
30:
me.state ←(Waiting)
31: else if other.state = (Waiting) then
32:
if dist > 2 then
▷my unit is smaller
33:
me.state ←(Stay)
34:
me.destination ←other.position
35:
else if dist = 2 then
▷our units are equal
36:
me.state ←(Both = 2)
37:
else
▷my unit is bigger or we have gathered
38:
me.state ←(Halted)
39: else if other.state = (Both = 2) then
40:
me.state ←(Stay)
41:
if dist = 2 then
▷moving to the midpoint
42:
me.destination ←other.position/2
43: else if other.state = (Stay) then
44:
me.state ←(Halted)
11
45: else
▷other.state = (Halted)
46:
if dist = 0 then
▷we have gathered
47:
me.state ←(Halted)
48:
terminate
49:
else
▷maintain position while I come
50:
me.state ←(Stay)
51:
me.destination ←other.position
still set to (Both < 1), but it observes a distance not lower than 1, then it knows that it has
already moved away, and has to wait.
When a robot sees its partner set to (Moving Away), it shares this information by turning
(You Moved). If only one robot turns (You Moved), while the other is still set to (Moving
Away), then the second robot turns (Coming) and reaches the other robot, which just turns
(Waiting) and stays still until they gather.
Otherwise, if both robots see each other set to (You Moved), they both turn (Coming) and
switch positions. At least one of them then turns (Waiting). Now, if a robot sees its partner set
to (Waiting) and they have not gathered yet, it knows that their current distance is the sum of
their unit distances. If such distance is greater than 2, then the robot knows that its partner’s unit
distance is bigger, and it moves toward it, while ordering it to stay still. Vice versa, if the distance
observed is smaller than 2, the observing robot stays still and orders its partner to come.
Finally, if the distance observed is exactly 2, the observing robot knows that the two distance
functions are equal, and turns (Both = 2). In this case, a simple protocol allows them to meet. If
a robot sees the other set to (Both = 2) at distance 2, it turns (Stay) and moves to the midpoint.
If both robots do so, they eventually gather. Indeed, even if the first robot reaches the midpoint
while the other is still set to (Both = 2), it now sees its partner at distance 1, and knows that it
has to wait. On the other hand, whenever a robot sees its partner set to (Stay), it turns (Halted),
which tells its partner to reach it. This guarantees gathering even if only one robot attempts to
move to thee midpoint.
4.2
Semi-synchronous
In SSynch the situation is radically different from the ASynch case. In fact, it is possible to
find a simple solution in L that uses the minimum number of colors possible, and operates cor-
rectly without unit distance agreement, starting from any arbitrary color configuration, and with
interruptable movements (see Algorithm 3 and Figure 3).
Algorithm 3 Rendezvous for non-rigid SSynch with three externally visible states
1: if other.state = A then
2:
me.state ←B
3:
me.destination ←other.position/2
4: else if other.state = B then
5:
me.state ←C
6: else
▷other.state = C
7:
me.state ←A
8:
me.destination ←other.position
12
A
B
C
/
0
1 2
1
Figure 3: State transitions in Algorithm 3.
Theorem 16. In SSynch, Rendezvous of two FComm robots is solvable by an algorithm in L with
only three distinct colors. This result holds even if starting from an arbitrary color configuration,
without unit distance agreement, and with non-rigid movements.
Proof. We show that Algorithm 3 (see also Figure 3) correctly solves Rendezvous from any initial
configuration. Assume first that both robots start in the same state and both are activated at each
turn. Then they keep having equal states, and they cycle through states A, B, and C forever.
Every time they are both set to A, they move toward the midpoint and their distance reduces by
at least 2δ, until it becomes so small that they actually gather.
Otherwise, if at some point the two robots are in different states, they will keep staying in
different states forever. In this case their distance will never increase, and they will periodically be
found in states B and C, respectively. Whenever this happens, the robot set to C retains its state
and stays still until the other robot is activated and moves toward it by at least δ. As soon as their
distance becomes not greater than δ and they turn again B and C, they finally gather.
Note that the number of colors used by the algorithm is optimal. This follows as a corollary of
the impossibility result when lights are visible to both robots:
Lemma 17. [22] In SSynch, Rendezvous of two robots with persistent memory visible by both of
them is unsolvable by algorithms in L that use only two colors.
5
Movements: Knowledge vs. Rigidity
In this section, we consider the Rendezvous problem when the movement of the robots can be inter-
rupted by an adversary; previously, unless otherwise stated, we have considered rigid movements,
i.e., in each cycle a robot reaches its computed destination point. Now, the only constraint on the
adversary is that a robot, if interrupted before reaching its destination, moves by at least δ > 0
(otherwise, rendezvous is clearly impossible). We prove that, for rendezvous with lights, knowledge
of δ has the same power as rigidity of the movements. Note that knowing δ implies also that the
robots can agree on a unit distance.
5.1
FState Robots
Theorem 18. In non-rigid SSynch, Rendezvous of two FState robots with knowledge of δ is
solvable with three colors.
Proof. We show that Algorithm 4 correctly solves Rendezvous. Both robots start in state A. If a
robot sees its partner at distance lower than δ/2, it moves in the opposite direction, to the point
at distance δ/2 from its partner. On the other hand, if the distance observed is not lower than δ,
it moves toward the point located δ/4 before the midpoint.
13
After sufficiently many turns, the robots are found at a distance in the interval [δ/2, δ), and
both in state A. From now on, all their movements are rigid. If only one robot is activated, it
reaches its partner and Rendezvous is solved. Otherwise, they both turn B and switch positions.
Then, if both robots are activated, they gather in the midpoint. Otherwise, one of them turns
C and moves to the midpoint. Now, the robot still in B keeps staying still because it observes a
distance lower than δ/2. On the other hand, the robot set to C moves to its partner as soon as it
is activated.
Algorithm 4 Rendezvous for non-rigid SSynch with knowledge of δ and three internal states
1: dist ←∥other.position∥
2: if dist = 0 then
3:
terminate
4: if me.state = A then
5:
if dist < δ/2 then
▷reach the point at distance δ/2 from the other
6:
me.destination ←other.position · (1 −δ/(2 · dist))
7:
else if δ/2 ⩽dist < δ then
▷gather or switch positions
8:
me.state ←B
9:
me.destination ←other.position
10:
else
▷dist ⩾δ, reach the point at distance δ/4 from the midpoint
11:
me.destination ←other.position · (1/2 −δ/(4 · dist))
12: else if me.state = B then
13:
if δ/2 ⩽dist < δ then
14:
me.state ←C
15:
me.destination ←other.position/2
16: else
▷me.state = C
17:
me.destination ←other.position
5.2
FComm Robots
Theorem 19. In non-rigid ASynch, Rendezvous of two FComm robots with knowledge of δ is
solvable with three colors.
Proof. We show that Algorithm 5 correctly solves Rendezvous. Both robots begin their execution
in state Start, and attempt to position themselves at a distance in the interval (δ, 2δ]. To do so,
they adjust their position by moving by δ/2 at each step. When a robot sees its partner at the
desired distance, it turns Ready and stops. It is easy to prove that, even if its partner is still
moving, it will end its move at a distance in the interval (δ, 2δ].
When a robot sees its partner set to Ready, it turns Come and moves to the midpoint. The
midpoint is eventually reached, because the distance traveled is not greater than δ. Assume that
both robots turn Ready, both see each other, and move toward the midpoint. If robot r reaches
the midpoint and sees its partner s still on its way and set to Come, r turns Ready and keeps
chasing s. When s reaches its destination and sees r set to Ready and at distance at most δ, it
stays still and waits until Rendezvous is solved.
Similarly, assume that r sees s set to Ready and turns Come before s sees r set to Ready. r will
reach the midpoint and stay there, while s will start chasing r until they meet in the midpoint.
14
Algorithm 5 Rendezvous for non-rigid ASynch with knowledge of δ and three externally visible
states
1: dist ←∥other.position∥
2: if other.state = Start then
3:
if dist = 0 then
▷we have already gathered
4:
me.state ←Come
5:
else if dist ⩽δ then
▷moving δ/2 away
6:
me.state ←Start
7:
me.destination ←−other.position · δ/(2 · dist)
8:
else if dist > 2δ then
▷moving δ/2 in
9:
me.state ←Start
10:
me.destination ←other.position · δ/(2 · dist)
11:
else
▷δ < dist ⩽2δ, ready to gather
12:
me.state ←Ready
13: else if other.state = Ready then
14:
me.state ←Come
15:
if δ < dist ⩽2δ then
▷reaching the midpoint
16:
me.destination ←other.position/2
17: else
▷other.state = Come
18:
if dist = 0 then
▷we have gathered
19:
me.state ←Come
20:
terminate
21:
else
22:
me.state ←Ready
23:
me.destination ←other.position
15
6
Open Problems
We have shown that rendezvous can be obtained both in FState and FComm, two models sub-
stantially weaker than the one of [8], where both internal memory and communication memory
capabilities are present. Our results open several new problems and research questions.
Our results, showing that rendezvous is possible in SSynch for FState robots and in ASynch
for FComm robots, seem to indicate that “it is better to communicate than to remember”. How-
ever, determining the precise computational relationship between FState and FComm is an open
problem. To settle it, it must be determined whether or not it is possible for FState robots to
rendezvous in ASynch.
Although minimizing the amount of constant memory was not the primary focus of this paper,
the number of states employed by our algorithms is rather small. An interesting research ques-
tion is to determine the smallest amount of memory necessary for the robots to rendezvous when
rendezvous is possible, and devise optimal solution protocols.
The knowledge of δ in non-rigid scenarios is quite powerful and allows for simple solutions. It
is an open problem to study the Rendezvous problem for FState and FComm robots when δ is
unknown or not known precisely.
This paper has extended the classical models of oblivious silent robots into two directions:
adding finite memory, and enabling finite communication. It thus opens the investigation in the
FState and FComm models of other classical robots problems (e.g., Pattern Formation, Flocking,
etc.); an exception is Gathering because, as mentioned in the introduction, it is already solvable
without persistent memory and without communication [4].
References
[1] N. Agmon and D. Peleg. Fault-tolerant gathering algorithms for autonomous mobile robots.
SIAM Journal on Computing, 36:56–82, 2006.
[2] Z. Bouzid, S. Das, and S. Tixeuil.
Gathering of Mobile Robots Tolerating Multiple Crash
Faults. In Proceedings of 33rd IEEE International Conference on Distributed Computing Systems
(ICDCS), 2013.
[3] Z. Bouzid, M. Gradinariu Potop-Butucaru, and S. Tixeuil. Byzantine convergence in robot
networks: The price of asynchrony. In Proceedings of 13th International Conference Principles
of Distributed Systems (OPODIS), pages 54–70, 2009.
[4] M. Cieliebak, P. Flocchini, G. Prencipe, and N. Santoro. Distributed computing by mobile
robots: Gathering. SIAM Journal on Computing, 41(4): 829-879, 2012.
[5] R. Cohen and D. Peleg. Convergence properties of the gravitational algorithm in asynchronous
robot systems. SIAM Journal on Computing, 34:1516–1528, 2005.
[6] R. Cohen and D. Peleg. Convergence of autonomous mobile robots with inaccurate sensors
and movements.
In Proceedings of 23rd International Symposium on Theoretical Aspects of
Computer Science (STACS), pages 549—560, 2006.
[7] A. Cord-Landwehr, B. Degener, M. Fischer, M. H¨ullmann, B. Kempkes, A. Klaas, P. Kling,
S. Kurras, M. Mrtens, F. Meyer auf der Heide, C. Raupach, K. Swierkot, D. Warner, C. Wed-
demann, and D. Wonisch. A new approach for analyzing convergence algorithms for mobile
16
robots. In Proceedings of 38th International Colloquium on Automata, Languages and Program-
ming (ICALP), pages 650–661. Springer, 2011.
[8] S. Das, P. Flocchini, G. Prencipe, N. Santoro, and M. Yamashita. The power of lights: syn-
chronizing asynchronous robots using visible bits. In Proceedings of the 32nd International
Conference on Distributed Computing Systems (ICDCS), pages 506–515, 2012.
[9] X. D´efago, M. Gradinariu, S. Messika, and P. Raipin-Parv´edy. Fault-tolerant and self-stabilizing
mobile robots gathering. In Proc. 20th Intl. Symp. on Distributed Computing (DISC), pages
46–60, 2006.
[10] B. Degener, B. Kempkes, T. Langner, F. Meyer auf der Heide, P. Pietrzyk, and R. Wattenhofer.
A tight runtime bound for synchronous gathering of autonomous robots with limited visibility.
In Proceedings of 23rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA),
pages 139–148, 2011.
[11] Y. Dieudonn´e and F. Petit. Self-stabilizing gathering with strong multiplicity detection. The-
oretical Computer Science, 428(13), 2012.
[12] P. Flocchini, G. Prencipe, and N. Santoro. Distributed Computing by Oblivious Mobile Robots.
Morgan & Claypool, 2012.
[13] P. Flocchini, G. Prencipe, N. Santoro, and P. Widmayer. Gathering of asynchronous robots
with limited visibility. Theoretical Computer Science, 337(1-3):147–168, 2005.
[14] T. Izumi, Z. Bouzid, S. Tixeuil, and K. Wada. Brief Announcement: The BG-simulation for
Byzantine mobile robots. Proceedings od 25-th Intl. Symp. on Distributed Computing (DISC),
pages 330–331, 2011.
[15] T. Izumi, S. Souissi, Y. Katayama, N. Inuzuka, X. Defago, K. Wada, and M. Yamashita.
The gathering problem for two oblivious robots with unreliable compasses. SIAM Journal on
Computing, 41(1):26–46, 2012.
[16] S. Kamei, A. Lamani, F. Ooshita, and S. Tixeuil.
Asynchronous mobile robot gathering
from symmetric configurations without global multiplicity detection. In Proceedings of 18th
Int. Colloquium on Structural Information and Communication Complexity (SIROCCO), pages
150–161, 2011.
[17] J. Lin, A.S. Morse, and B.D.O. Anderson. The multi-agent rendezvous problem. parts 1 and
2. SIAM Journal on Control and Optimization, 46(6):2096–2147, 2007.
[18] L. Pagli, G. Prencipe, and G. Viglietta. Getting close without touching. In Proceedings of 19th
Int. Colloquium on Structural Information and Communication Complexity (SIROCCO), pages
315–326, 2012.
[19] G. Prencipe. Impossibility of gathering by a set of autonomous mobile robots. Theoretical
Computer Science, 384(2-3):222–231, 2007.
[20] S. Souissi, X. D´efago, and M. Yamashita. Using eventually consistent compasses to gather
memory-less mobile robots with limited visibility.
ACM Transactions on Autonomous and
Adaptive Systems, 4(1):1–27, 2009.
17
[21] I. Suzuki and M. Yamashita. Distributed anonymous mobile robots: Formation of geometric
patterns. SIAM Journal on Computing, vol. 28, pp. 1347–1363, 1999.
[22] G. Viglietta. Rendezvous of two robots with visible bits. Technical Report arXiv:1211.6039,
2012.
18