=Paper=
{{Paper
|id=Vol-1720/full9
|storemode=property
|title=Gathering of Robots in a Ring with Mobile Faults
|pdfUrl=https://ceur-ws.org/Vol-1720/full9.pdf
|volume=Vol-1720
|authors=Shantanu Das,Riccardo Focardi,Flaminia L. Luccio,Euripides Markou,Davide Moro,Marco Squarcina
|dblpUrl=https://dblp.org/rec/conf/ictcs/0001FLMMS16
}}
==Gathering of Robots in a Ring with Mobile Faults==
https://ceur-ws.org/Vol-1720/full9.pdf
Gathering of Robots in a Ring with Mobile
Faults
Shantanu Das1 , Riccardo Focardi2 , Flaminia L. Luccio2 ,
Euripides Markou3 , Davide Moro2 , and Marco Squarcina2
1
Aix Marseille Univ, CNRS, LIF, Marseille, France
2
DAIS, Università Ca’ Foscari Venezia, Venezia, Italy
3
DCSBI, University of Thessaly, Lamia, Greece
Abstract. In this paper, we consider the problem of gathering mobile
agents in a graph in the presence of mobile faults that can appear any-
where in the graph. Faults are modeled as a malicious mobile agent that
attempts to block the path of the honest agents and prevents them from
gathering. The problem has been previously studied by a subset of the
authors for asynchronous agents in the ring and in the grid graphs. Here,
we consider synchronous agents and we present new algorithms for the un-
oriented ring graphs that solve strictly more cases than the ones solvable
with asynchronous agents. We also show that previously known solutions
for asynchronous agents in the oriented ring can be improved when agents
are synchronous. We finally provide a proof-of-concept implementation
of the synchronous algorithms using real Lego Mindstorms EV3 robots.
1 Introduction
An important problem in the area of distributed computing with mobile agents
(or robots) is the rendezvous problem, i.e., the gathering of all agents at the same
location. Gathering is a crucial task for teams of autonomous mobile robots, since
they may need to meet in order to share information or coordinate. This problem
has been widely studied when the environment is modelled as an undirected
graph and the mobile agents can move along the edges of the graph. Most of the
studies are restricted to fault-free environments and very little is known about
gathering in the presence of faults. Possible faults can be a permanent failure
of a node, like for example the so called black hole that destroys agents arriving
at a node, or, transient faults that can appear anywhere in the graph, such as a
mobile hostile entity (an intruder) that behaves maliciously. Some work has been
done to locate a malicious node in a graph (see, e.g., [8,10]), whereas protecting
the network against a malicious entity that is mobile and moves from node to
Copyright c by the paper’s authors. Copying permitted for private and academic pur-
poses.
V. Biló, A. Caruso (Eds.): ICTCS 2016, Proceedings of the 17th Italian Conference on
Theoretical Computer Science, 73100 Lecce, Italy, September 7–9 2016, pp. 122–135
published in CEUR Workshop Proceedins Vol-1720 at http://ceur-ws.org/Vol-1720
Gathering of Robots in a Ring with Mobile Faults 123
node of the graph, is a more difficult problem. An example of this kind is the
so-called network decontamination or intruder capture problem (see, e.g., [9,11]).
In this paper we consider a new type of malicious agent that was introduced
in [5]. This agent can block the movement of an honest agent to the node it
occupies, it can move arbitrarily fast along the edges of the graph, it has full
information about the graph and the location of the agents, and it even has full
knowledge of the actions that will be taken by the honest agents. On the other
hand, the honest agents are relatively weak: they are independent and identical
anonymous processes with some internal memory, they move synchronously and
use face to face communication when they are in the same node. We investigate
the feasibility of rendezvous in oriented and unoriented ring networks in the
presence of such a powerful adversary, that blocks other agents from having
access to parts of the network.
We consider an oriented and an unoriented ring network modelled as a con-
nected undirected graph with a set of mobile honest agents located at distinct
nodes of the graph, and a malicious agent that cannot harm the honest agents but
can prevent them from visiting a node. As in [5] we are interested in solving the
rendezvous of all honest agents in this hostile environment. However, differently
from [5], we consider synchronous mobile honest agents. These agents have local
communication capability, and no prior knowledge of their number k (except for
the protocol for k = 2) and of the ring size n. Our objective is to study the
feasibility of rendezvous with minimal assumptions.
Contributions. (i) We prove that in an unoriented ring network of n nodes the
problem is not solvable for n odd and k even, and we then present an algorithm
that solves the problem in all the other cases for k > 2 synchronous agents,
also in the case n odd and k odd which is unsolvable with asynchronous agents;
(ii) we briefly discuss how to solve the problem for k = 2 agents and n even,
not solvable in the asynchronous setting, and how to solve the problem in the
oriented ring by improving the known algorithm for asynchronous agents; (iii)
we show that the proposed algorithms and underlying assumptions are realistic
through a proof-of-concept implementation using Lego Mindstorms EV3 robots.
Related work. In this paper we consider the rendezvous problem, which has
been previously studied for robots moving on the plane [3], or for agents moving on
graphs [1]. This problem can be easily solved, in synchronous and asynchronous
settings, when the system is not symmetric, e.g., when there is a distinguished
node. In symmetric settings (e.g., in the anonymous ring) the problem is non-
trivial and symmetry has to be broken, e.g., by using tokens [6], by adding distinct
identifiers to agents [4], etc.
Some recent work [7] also considers the problem of rendezvous in the presence
of Byzantine agents, which are indistinguishable from the honest agents, but may
behave in an arbitrary manner, and may also provide false information to the
honest agents so to prevent their gathering. Other related work includes gathering
in networks with delay faults [2]. The model used in [2] is somehow similar to ours
in the sense that the adversary may delay for an arbitrary, but finite time, the
124 Authors Suppressed Due to Excessive Length
movements of the agents. However, contrary to the model of [2], in our setting,
one of the agents may be blocked forever.
From a practical point of view, the work that is more closely related to our
model is [13], where the author proposes an example of a simulation of a known
distributed fault-free gathering algorithm, using real NXT robots. Differently
from our setting, in [13] robots are moving on a plane (not in a graph), do not
use direct communication, but only indirect one, i.e., can only detect the position
and the movement of the other robots but cannot communicate any information.
Paper structure. The paper is organized as follows: In Section 2 we illustrate
the formal model; in Section 3 we first present some impossibility results, and
then the algorithm for the unoriented ring network for k > 2 agents. For lack of
space we only discuss the solution for k = 2 and for the oriented ring network.
In Section 4 we present the implementation of the algorithms on programmable
robots, and we discuss the usefulness of the study of the real model in the
development of the theoretical models. We conclude in Section 5.
2 A Model of Synchronous Agents in a Ring
We consider a distributed network modeled by an undirected, connected graph
G = (V, E) where V are the anonymous and identical nodes or hosts, and E the
edges or connections between nodes. We assume that in the network there are k
honest anonymous identical synchronous agents A1 , A2 , . . . Ak , and one malicious
agent M which is trying to prevent the gathering of honest agents. More precisely,
the network, and the capabilities and behavior of honest and malicious agents
are the following.
The network: We consider either oriented or unoriented ring networks R =
(V, E), with |V | = n nodes. The links incident to a host are distinctly labeled. In
the oriented ring, the links are labelled consistently to allow all agents agree on
a common sense of direction. In the unoriented ring there is no such agreement
and the labels on the links are arbitrary. The edges of the network are FIFO
links, meaning that all agents, including the malicious one, that move in the
same link respect a FIFO ordering. We call a node v occupied when one or more
honest agents are in v, and we call v free or unoccupied otherwise. Moreover, for
solvability reasons, we will have to assume that the ring contains a special node
marked ⊗, otherwise gathering is impossible (see [5]).
Honest agents: The agents are independent and identical, anonymous processes
with some internal constant memory, except for the case k = 2 in the unoriented
ring that requires O(log n) bits. These agents are initially scattered in the graph,
i.e., at most one agent at a node, start the protocol at the same time, and can
move along the edges of G. An agent located at a node v can see how many other
agents are at v, and it can access their states. An agent cannot see or communicate
with any agent that is not located at the same node, i.e., communication is face
to face. Moreover an agent cannot mark the node or leave any information on the
node that it visits. An agent arriving at a node v, learns the label of the incoming
Gathering of Robots in a Ring with Mobile Faults 125
port and the label of the outgoing port. Two agents traveling on the same edge
in different directions do not notice each other, and cannot meet on the edge.
Their goal is to rendezvous at a node. The agents neither have knowledge of the
size n of the ring, nor of the number k of agents present in the network.
The moves of honest agents are synchronized as follows: (a) all agents start
executing the protocols at the same time; (b) time is discretized into atomic time
units; (c) all agents start in the same initial state, and the set of agent states is
finite and independent of the graph size or the number of agents; (d) During each
time unit, an agent arriving at a node v through a port q takes the following three
actions: (d.1) it reads its own state, counts the number of agents at v and reads
their states; (d.2) based on the above information it performs some computation
to decide its next destination; the output of the computation is a new state and
the port number p of an edge incident to v, or p = 0 if the agent decides to stay
in v; (d.3) the agent changes its state and either moves using the computed port
number (p > 0), or waits at the current node (p = 0). If the agent decided to
move on edge (v, z), and the node z is not occupied by the malicious agent then
the agent is located at the node z in the next time unit. Otherwise, the agent
is still located at node v in the next time unit, with a flag set in its memory
notifying the agent that the move was unsuccessful. In the next time unit, the
agent repeats the above three actions.
Malicious agent: We consider a worst case scenario in which the malicious
agent M is a very powerful entity compared to honest agents: It has unlimited
memory; at any time has full knowledge of the graph, the locations of the honest
agents and their states, and the algorithm followed by the agents. Based on the
above information, M can either stay at its current node y or decide to move to
another node w, if there is a path from y to w, such that no node on this path,
including w, is occupied by any honest agent. The speed of the malicious agent
is unbounded, thus M can move arbitrarily fast inside the network, but must
move along the edges of the graph, and it also obeys the FIFO property of the
links. When it resides at a node u it prevents any honest agent A from visiting u,
i.e., it “blocks" A: If an agent A attempts to visit u, the agent receives a signal
that M is in u. M can neither visit a node which is already occupied by some
honest agent, nor cross some honest agent in a link.
3 Rendezvous in Rings with Synchronous Agents
In this section we first study the rendezvous problem with synchronous agents
having constant memory, in an unoriented ring with one malicious agent. In [5]
the authors have analyzed the same problem with asynchronous agents and have
proved that the problem is solvable in any unoriented ring if and only if the
number of honest agents k is odd. We prove here that with k > 2 synchronous
agents having constant memory, the problem can be solved in an unoriented ring
consisting of n nodes, when n is even or k is odd. We also prove that for k even
and n odd numbers, the problem is unsolvable. We discuss also the case k = 2
in unoriented rings, and the problem in oriented rings.
126 Authors Suppressed Due to Excessive Length
Let us first show the impossibility result in the unoriented ring. The technique
of the proof is similar to the one presented in Lemma 5 of [5], where it was
proved that an even number of agents with constant memory cannot gather in
an unoriented ring with a malicious agent. We can show that when n is odd
and k is even, an adversary can initially place the agents in a configuration that
is symmetric with respect to a line passing through the special node ⊗, and
can place itself in ⊗. Hence, the agents are distributed into two groups of equal
size. Moreover, the agents belonging to the same group, agree on the clockwise
(CW ) orientation but they do not agree with the agents of the other group. In
other words, what is considered clockwise direction for any agent of one group is
considered counter-clockwise direction for every agent of the other group. Each
two symmetrically placed agents which belong to different groups should behave
identically under any algorithm. Moreover, recall that n − 1, the number of free
positions is even, i.e., there is no meeting point in the middle opposite to ⊗, and
therefore the agents of the two groups can never meet at a node. We thus have:
Lemma 1 (Impossibility when n is odd and k is even). In an unoriented
ring with a specially marked node ⊗ and a malicious agent having arbitrary speed,
k ≥ 2 mobile synchronous agents starting from arbitrary symmetric locations,
cannot gather at a node if n is odd and k is even.
3.1 Unoriented Ring with more than two Agents
We now propose an algorithm for k > 2 synchronous agents with constant memory,
and that do not know n and k. Moreover, agents do not agree on a common sense
of direction given that the ring is unoriented. Algorithm 1, called CollectAgents,
works as follows. Each agent has a state and some local variables that keep track
of the execution. Agents wake up in state INITIAL. We illustrate the algorithm
distinguishing the case in which all agents have the same orientation, from the
case in which the agents are split in two groups, those that move in one direction
and those that move in the opposite direction. Note that the agents are not aware
of this information so they cannot adapt their behaviour accordingly.
If an agent continues moving in the same direction and eventually reaches ⊗
for the second time, then the agent can be sure that all agents are moving in the
same direction. In this case, one of the agents - the first agent to reach ⊗ twice
- will stop at ⊗. The other agents continue moving in the same direction until
they are blocked by M . The first agent to be blocked stops (in state STOPPED)
and all other agents gather at this node, except one of the agents (the first one
to meet the STOPPED agent) which changes to state MSG (“messenger") and
goes around the ring in the other direction until it is blocked by M . At this point
M is surrounded by the stopped agent (now in state HEAD) and the messenger
agent. The messenger agent (changing to state R_MSG) returns back, collecting
the STAR agent on the way, and rendezvous is achieved when these two agents
reach the other agents who are waiting at the HEAD agent.
When the agents do not have the same orientation then the situation is
different. In this case there are two groups of agents, G1 and G2 , moving in
Gathering of Robots in a Ring with Mobile Faults 127
opposite directions. One agent from each group will eventually be blocked by
M and become the “leader" (HEAD) agent for their group. The two groups of
agents will start gathering in two distinct locations. To bring the two groups
together, we use the fact that either k is odd or n is even. In the former case,
one of the groups is of odd size, and agents of this group turn back and go to
the other group. Otherwise if k is even and both groups are of even size, then
the leader (HEAD) agents of the two groups try to push M from two sides until
M is cornered in one node of the network. The segment of the ring containing
the other nodes is of odd size and the two groups of agents can meet at the
center of this segment. Let agent A for G1 , and agent B for G2 , be the agents
that are blocked by M and become STOPPED (line 6). When two other agents,
say C and D, meet A and B respectively then A and B will become HEAD and
will start moving, trying to surround M , while C and D become MSG, reverse
direction and move towards B and A, respectively. When agents C and D meet
the two HEAD agents B and A (line 67), they reverse direction and become
R_MSG delivering some information and joining all the agents of their own
group. If either G1 or G2 is of odd size and all the agents of the odd group move
towards even group (line 23), and rendezvous is achieved. If k is even, and both
G1 and G2 are of even size, then agents C and D go back and forth, until when
they find that M has been surrounded, i.e., when HEAD agents cannot move
anymore (line 24). At this point G1 and G2 move towards the middle point and
gather there if n is even or the algorithm fails if n is odd (line 38).
128 Authors Suppressed Due to Excessive Length
Algorithm 1 CollectAgents
# Gathering k > 2 agents in an Unoriented Ring.
# Local variables: sync = parity = s_reached = 0, moved = -1, first_clock = 1,
State = INITIAL
1: sync := (sync + 1) mod 2
2: if State = INITIAL then
3: dir := CW
4: if first_clock = 1 and Reached ⊗ then s_reached = s_reached +1
5: end if
6: if Blocked then State := STOPPED
7: else
8: Move to the next node
9: if Reached ⊗ then s_reached = s_reached +1
10: end if
11: if meet a STOPPED agent then State := MSG
12: else if meet a HEAD agent h then State := FOLLOWER of h
13: else if Blocked then State := STOPPED
14: else if s_reached = 2 and not found a STAR agent then
15: State := STAR
16: end if
17: end if
18: else if State = HEAD then
19: if meet a INITIAL agent then parity:= (parity + 1) mod 2
20: else if meet a R_MSG agent r then
21: if r.moved = -1 then State := RENDEZVOUS
22: else if parity = 1 and r.parity = 0 then State := WAIT
23: else if parity = 0 and r.parity = 1 then State := R_HEAD
24: else if moved = 0 and r.moved = 0 then
25: State := R_HEAD
26: Wait (sync)
27: end if
28: moved:= 0
29: else if not blocked and s_reached < 2 then
30: moved:= 1
31: Move to the next node
32: if Reached ⊗ then s_reached = s_reached +1
33: end if
34: else Wait (1)
35: end if
36: else if State = R_HEAD then
37: dir:= CCW
38: if Blocked then State := FAILURE
39: else if meet a R_HEAD agent then State := RENDEZVOUS
40: else
41: Move to the next node
42: if meet a R_HEAD or WAIT agent then State := RENDEZVOUS
43: end if
44: end if
Gathering of Robots in a Ring with Mobile Faults 129
CollectAgents algorithm - Continue
45: else if State = STOPPED then
46: if meet a INITIAL agent then
47: State := HEAD
48: moved:= 0
49: parity:= (parity + 1) mod 2
50: else if meet a MSG agent m then State := FOLLOWER of m
51: else Wait (1)
52: end if
53: else if State = STAR then
54: if meet a R_MSG agent r then State := FOLLOWER of r
55: else Wait (1)
56: end if
57: else if State = FOLLOWER then
58: if leader state is RENDEZVOUS then State := RENDEZVOUS
59: else follow the leader
60: end if
61: else if State = MSG then
62: dir:= CCW
63: if Blocked then
64: State := R_MSG
65: else
66: Move to the next node
67: if meet a HEAD agent h then
68: state := R_MSG
69: moved:= h.moved
70: parity:= h.parity
71: else if Blocked or meet a STOPPED agent then state := R_MSG
72: end if
73: end if
74: else if State = R_MSG then
75: dir:= CW
76: Move to the next node
77: if meet a HEAD agent h then
78: if moved = -1 then State := RENDEZVOUS
79: else if (parity!= h.parity) or (moved = 0 and h.moved = 0) then
80: State := FOLLOWER
81: else State := MSG
82: end if
83: end if
84: else if State = WAIT then
85: if meet a R_HEAD agent then
86: State := RENDEZVOUS
87: Change state of FOLLOWER agents to RENDEZVOUS
88: else Wait (1)
89: end if
90: end if
91: first_clock:= 0
130 Authors Suppressed Due to Excessive Length
Theorem 1. Algorithm CollectAgents solves the rendezvous problem for k > 2
agents in an unoriented ring of size n with a special node ⊗, and with one
malicious agent M . It returns a failure message when n is odd, k is even and
there are at least two agents for each of the two possible orientations.
Proof. All the agents start moving at the same time in their CW direction,
but there is no common sense of direction thus some agents could move in one
direction while some others are moving in the opposite one. We have three
possible cases: (1 ) all the agents move in the same direction; (2 ) all the agents
except one move in the same direction; (3 ) at least two agents move in one
direction and at least two move in the opposite one.
(1 ) We want to prove that in this case exactly one agent becomes STOPPED.
Let us first assume by contradiction that no agent becomes STOPPED. There
are two cases: a) Either M stops or moves in a direction opposite to the other
agents, but in this case it blocks one agent that becomes STOPPED, thus a
contradiction; b) or M keeps on moving in the same direction chosen by the
agents, but in this case one agent will cross ⊗ twice and will stop, thus blocking
M . Therefore, at least another agent will eventually be blocked by M (no other
agent stops at ⊗), and will become STOPPED, thus a contradiction also in
this case. Let us now prove that the STOPPED agent is unique. Given that
by hypothesis there are k > 2 agents that move in the same direction, and at
most one agent becomes STAR, then one agent C has to meet A, the STOPPED
one, becomes MSG, while A changes its state to HEAD. Note that, all the other
agents in state INITIAL cannot become STOPPED, but become FOLLOWER,
given that they meet A before being blocked by M . The agents A and C move in
opposite directions. C reaches M in the opposite side because there are no other
STOPPED or HEAD agents, given that C is the first agent that moves in this
direction. Thus, the STOPPED agent is A and is unique. Let us now prove that
C will coordinate the gathering. When C comes back in state R_MSG has the
default moved value equal to −1. Agent A in the opposite side continues to move
in the same direction, with some agents in state FOLLOWER. However, the two
agents C and A eventually meet, in fact either A is stopped by M , or after it has
reached ⊗ for the second time, it will remain stopped, together with the agents
in state FOLLOWER, waiting for the arrival of C to rendezvous. Note that, if
one agent had previously stopped in ⊗, then it has to be in the path followed
by R_MSG, thus it will become a FOLLOWER of R_MSG and will rendezvous
with the other agents. Thus, if all agents initially move in the same direction
rendezvous is achieved.
(2 ) Let us assume that all the agents except one, called B, move in the same
direction. The agent M cannot escape both from B and from the agents going in
the opposite direction, let us call this group G1 , thus M has to block both B and
another agent A of G1 . B becomes STOPPED but not HEAD because no other
agent can reach it in state INITIAL, whereas A, becomes STOPPED, and once
it is reached by an INITIAL agent C, A becomes HEAD, and C starts moving in
the opposite direction, i.e. towards B, in state MSG. All the remaining agents of
G1 become FOLLOWER of A. When C and B meet, B becomes a FOLLOWER
Gathering of Robots in a Ring with Mobile Faults 131
of C, and C moves in state R_MSG towards A with the default moved value
equal to −1. The agent A and its FOLLOWER agents continue to move in CW
direction, however A is either blocked by M , or it stops after reaching ⊗ twice.
When C and B reach A, all the other possible agents already reached A, and
since moved = −1 the agents terminate in state RENDEZVOUS.
(3 ) At least two agents have an orientation in one direction, and another
two in the other direction. Thus, exactly 2 agents become HEAD and 2 agents
become MSG. Let us call them A and C - the HEAD and the MSG on one side,
and B and D, those on the other side, respectively. All the other agents become
FOLLOWER of the HEAD they meet. C and D perform a tour in opposite
directions: they reverses direction, reach B and A, respectively, and come back
to A and B in state R_MSG, delivering the moved and the parity information
related to the other HEAD agent.
We now have to show that the two groups of agents are able to meet. First
observe that since agents are synchronous and links are FIFO D (C) meets A
(B) in state MSG before that C (D) comes back in state R_MSG delivering
the information on the parity or oddness (computed using the parity bit) of the
opposite group of agents, and the information on the possible movement of the
opposite HEAD, stored in a variable moved. Note that, when M is surrounded,
A and B are not able to move. We have two cases:
- k is odd: If k is odd, the HEAD agent of a group with parity = 1, remains
stopped in state WAIT , whereas the other HEAD agent, with parity = 0, starts
moving in opposite direction in state R_HEAD with all the other agents of its
group in state FOLLOWER. This group of agents will reach the other stopped
group -regardless of the value n- and all agents will rendezvous.
- k is even: This case is more complicated and rendezvous can be achieved
only when M has been surrounded, i.e., when A and B cannot move anymore.
This is possible since even if M is very fast, due to the synchronicity of the agents,
M can block only A or B in one time step. Note also that none of the HEAD
agents can meet ⊗ twice since M is surrounded before either of them could visit
all the nodes of the ring.
Thus, we have now to prove that C and D perform a same number of turns and
they eventually meet, together with their FOLLOWER agents. Given that C
and D collect both the moved value of their HEAD and the one of the opposite
HEAD agent, if at least one of the moved values is not 0 (which means at least
one of the HEAD agents moved) they start a new round, otherwise they try to
rendezvous. Observe that collecting both values and having FIFO links implies
a synchronization of the rounds.
Let G1 and G2 be the two groups of agents surrounding M that will eventually
be formed at the node of A and of B respectively. The sync variable changes at
each clock (line 1), and is used to synchronize the movements. In case n is even,
A and B are separated by an odd number of nodes. If one HEAD agent changes
direction at an even clock tick and the other at an odd clock tick (defined by the
sync variable), only one of the groups waits one clock cycle (line 26), and so the
two groups move at an instant of time that preserves the odd distance and thus,
132 Authors Suppressed Due to Excessive Length
they rendezvous. Without this synchronization, the agents may cross on an edge
without meeting.
Conversely, if n is odd A and B do not meet along the path and are blocked again
by M , thus they move to the state FAILURE since they did not rendezvous. t u
The complexity of the algorithm is as follows.
Theorem 2. Algorithm CollectAgents in an unoriented ring of size n requires
constant memory and it converges in O(n) time steps and with O(kn) total moves.
Strategy for M . We now very briefly illustrate the best strategy for the malicious
agent M , in order to delay as much as possible the gathering of the honest agents.
Thus, we will be considering time constraints. If k − 1 agents have the same CW
orientation, M moves CW up to when it is blocked by an agent and stops. If
all k agents have the same orientation, M moves in that direction up to when it
is blocked by an agent, then it waits until the agent moves (as it has become a
FOLLOWER of an R_MSG), and M follows the agent until it is blocked again
and stops. This happens after a HEAD has crossed twice the node ⊗ and has
become STOPPED. Finally, if agents are split in two groups, and k is odd, M
moves in the direction of the group of even size; if k is even M alternatively
blocks HEAD agents from one or the other side, so that both HEAD agents start
a round as soon as possible with the effect of maximizing the number of rounds.
Let us call this algorithm BlockAgents for M .
Lemma 2. Algorithm BlockAgents provides the best strategy for the malicious
agent to delay as much as possible the gathering of the honest agents.
Results for the oriented rings, and for the case k = 2 in unoriented
rings. For lack of space, we just very shortly illustrate two new cases, more details
may be found in [12]. Let us first consider the case of the oriented ring. First note
that there are no unsolvable cases, given that the symmetric configurations of
Lemma 1 never arise when agents move in the same direction. One solution for
k ≥ 2 would be to apply Algorithm 1 of [5] which might require that the agents
reverse direction three times when they are blocked by M . Moreover agents will
terminate but do not know when there is global termination. Another solution
for k ≥ 3 would be to apply Algorithm CollectAgents in the case in which all the
agents move in the same direction. This solution could even be improved: After
an agent has become HEAD it just stops and waits, since if all the agents move
in the same direction, then HEAD will not need to surround M . We have devised
another simpler algorithm that requires less rounds, assures global termination,
works for k ≥ 2 agents, and uses only constant memory. The general idea is
as follows: Suppose all the agents start moving in the CW direction, then the
first agent that is blocked by M , let us call it A, becomes the leader and starts
moving in the CCW direction. Then, when A meets an agent that is moving in
the CW direction, let us call it B, B stops, while A continues to move until it is
blocked again by M . Then, A reverses direction and moves back. The rendezvous
Gathering of Robots in a Ring with Mobile Faults 133
is achieved at the node of B. Note that, also in this case, an agent that arrives in
⊗ stops to block M . Finally, to assure that when A moves in the CCW direction
it meets any other agent, e.g. B, that is moving in the CW direction, we assume
that A waits at the even clock ticks and moves at the odd clock ticks, while B
moves at the even clock ticks and wait at the odd clock ticks.
Let us now consider the case k = 2 in the unoriented ring. Note that, in the
unoriented ring with asynchronous agents the problem is unsolvable for any even
number k ≥ 2, of honest agents, even if the agents know k [5]. With synchronous
agents we have the following. For n odd Lemma 1 proves that the problem is
not solvable, for n even we now briefly discuss a solution that requires O(log n)
bits of memory, and assumes that the agents know that k = 2. The algorithm
works as follows. It uses the general idea of the Controlled Distance algorithm
in a ring [14]. The agents move back and forth for a certain distance x which
increases at each round, in particular we choose x = 2i , for i = 0, 1, 2, . . .. At
each round i both agents, that we call A and B, try to move for x steps in the
CW direction, i.e., for x cycles of clock either they move, or they wait if they
are blocked by M . Then, they move back in the CCW direction for x steps, or
they wait if they are blocked by M in the opposite direction. During this walk
if they meet each other they gather. Note that, if they have waited some time
moving CW , then they might go back passing the starting position. It is possible
to prove that eventually the two agents will either meet at some intermediate
node, or they will eventually surround M and, since they are synchronized, and
they start moving in CCW direction at the same time step, they will meet at the
middle node, opposite to M in the ring. To prevent agents to infinitely increase
value x when they start in the same direction, an agent stops when it reaches ⊗
twice so that the other agent will meet it at the node ⊗.
4 Implementation
In this section we illustrate a proof-of-concept implementation based on the Lego
Mindstorms EV3 platform,4 which is widely adopted in robotic courses.
We have represented each undirected edge of the ring as two parallel links, so
that robots moving in two opposite directions on the same edge do not collide.
The nodes are all identical, and they have been represented as circles that can be
traversed by the agents moving around the border. The special node is labeled
with a yellow marker. The honest robots are all identical, whereas the malicious
agent has been physically modified to be easily noticeable.
To built our robots we have used standard Lego EV3 components. We have
used the EV3 Color Sensor to detect the lines representing the edges of the
graph so to let the robots move along them. We have used the EV3 Infrared
Seeking Sensor and EV3 Ultrasonic Sensor to detect the other honest agents in
the same node, and to avoid collisions when robots are following each other. By
4
Lego mindstorms ev3, 2016. http://www.lego.com/en-us/mindstorms/products/
31313-mindstorms-ev3
134 Authors Suppressed Due to Excessive Length
rotating the sensors on top of the EV3 Servo Motors we are also able to detect
robots placed crosswise.
Face to face communication is implemented using the built-in Bluetooth
adapters. However, given the small physical dimension of the ring we could not
use the Received Signal Strength Indicator (RSSI) of the Bluetooth devices to
connect to the robots in the same node, since all devices were showing very
similar signal strengths. We have then used a centralized server that mediates
connections and only enables face to face communication in the same node. We
claim that on a bigger network the strength indicator would work more reliably
and local communication might be implemented without resorting to a centralized
server.
The software platform used for the implementation is ev3dev,5 an open-source
Linux-based operating system fully compatible with Lego Mindstorm robots.
EV3 hardware can be controlled from a wide range of common programming
languages providing bindings for the ev3dev device API. We decided to implement
our algorithms in Python3 since it offers high code readability and enables rapid
prototyping of applications. The source code written to evaluate the protocols
consists of around 600 lines and is publicly available at our github repository
page,6 together with some exemplifying videos.7
5 Conclusions
In this paper we have presented the problem of gathering a set of mobile agents
in presence of mobile transient faults, represented by a mobile malicious agent.
We have studied the problem in oriented and unoriented ring networks, and we
have shown that the proposed solutions are realistic by giving a proof-of-concept
implementation of the algorithms with real Lego Mindstorms EV3 robots. We
are presently studying the problem of gathering in an unoriented ring with k = 2
agents and constant memory, and the gathering of synchronous agents in other
topologies.
References
1. S. Alpern and S. Gal. Searching for an agent who may or may not want to be
found. Operations Research, 50(2):311–323, 2002.
2. J. Chalopin, Y. Dieudonne, A. Labourel, and A. Pelc. Rendezvous in networks in
spite of delay faults. Distributed Computing, 29:187–205, 2016.
3. R. Cohen and D. Peleg. Convergence of autonomous mobile robots with inaccurate
sensors and movements. SIAM J. on Computing, 38:276–302, 2008.
4. J. Czyzowicz, A. Labourel, and A. Pelc. How to meet asynchronously (almost)
everywhere. In Proc. of 21st Annual ACM-SIAM Symp. on Discrete Algorithms,
2010.
5
Lego EV3 compatible operating system, http://www.ev3dev.org/
6
Source code https://github.com/secgroup/MTFGatheRing
7
Video of the rendezvous in an unoriented ring, https://github.com/secgroup/
MTFGatheRing/raw/master/videos/robots_unoriented.mp4
Gathering of Robots in a Ring with Mobile Faults 135
5. S. Das, F.L. Luccio, and E. Markou. Mobile agents rendezvous in spite of a mali-
cious agent. In 11th International Symposium on Algorithms and Experiments for
Wireless Sensor Networks (Algosensors 2015), LNCS 9536, pages 211–224. Springer,
Patras, Greece 2015.
6. S. Das, M. Mihalak, R. Sramek, E. Vicari, and P. Widmayer. Rendezvous of mobile
agents when tokens fail anytime. In OPODIS, LNCS 5401, pages 463–480, 2008.
7. Y. Dieudonne, A. Pelc, and D. Peleg. Gathering despite mischief. ACM Transactions
on Algorithms, 11(1):1, 2014.
8. S. Dobrev, P. Flocchini, G. Prencipe, and N. Santoro. Mobile search for a black
hole in an anonymous ring. Algorithmica, 48(1):67–90, 2007.
9. P. Flocchini and N. Santoro. Distributed security algorithms for mobile agents.
In Jiannong Cao and Sajal K. Das, editors, Mobile Agents in Networking and
Distributed Computing, chapter 3, pages 41–70. John Wiley & Sons, Inc., Hoboken,
NJ, USA, 2012.
10. R. Klasing, E. Markou, T. Radzik, and F. Sarracco. Hardness and approximation
results for black hole search in arbitrary graphs. TCS, 384(2-3):201–221, 2007.
11. F. L. Luccio. Contiguous search problem in sierpinski graphs. Theory of Comp.
Sys., (44):186–204, 2009.
12. Davide Moro. From theory to practice: Solving the rendezvous problem using real
robots. Master’s thesis, DAIS, Università Ca’ Foscari, Venezia, June 2016.
13. A. Pásztor. Gathering simulation of real robot swarm. Tehnicki vjesnik, 21(5):1073–
1080, 2014.
14. Nicola Santoro. Design and analysis of distributed algorithms, volume 56. John
Wiley & Sons, 2006.