arXiv:1801.07656v1 [cs.DS] 23 Jan 2018

Byzantine Gathering in Polynomial Time∗
Sébastien Bouchard1 , Yoann Dieudonné2 , Anissa Lamani2
1
Sorbonne Universités, UPMC Univ Paris 06, CNRS, INRIA, LIP6 UMR 7606, Paris, France
E-mail: sebastien.bouchard@lip6.fr
2
Laboratoire MIS & Université de Picardie Jules Verne, Amiens, France.
E-mails: {yoann.dieudonne,anissa.lamani}@u-picardie.fr
Abstract
Gathering a group of mobile agents is a fundamental task in the field of distributed and mobile
systems. This can be made drastically more difficult to achieve when some agents are subject to faults,
especially the Byzantine ones that are known as being the worst faults to handle. In this paper we study,
from a deterministic point of view, the task of Byzantine gathering in a network modeled as a graph. In
other words, despite the presence of Byzantine agents, all the other (good) agents, starting from possibly
different nodes and applying the same deterministic algorithm, have to meet at the same node in finite
time and stop moving. An adversary chooses the initial nodes of the agents (the number of agents may
be larger than the number of nodes) and assigns a different positive integer (called label) to each of them.
Initially, each agent knows its label. The agents move in synchronous rounds and can communicate with
each other only when located at the same node. Within the team, f of the agents are Byzantine. A
Byzantine agent acts in an unpredictable and arbitrary way. For example, it can choose an arbitrary port
when it moves, can convey arbitrary information to other agents and can change its label in every round,
in particular by forging the label of another agent or by creating a completely new one.
Besides its label, which corresponds to a local knowledge, an agent is assigned some global knowledge denoted by GK that is common to all agents. In literature, the Byzantine gathering problem has
been analyzed in arbitrary n-node graphs by considering the scenario when GK = (n, f ) and the scenario when GK = f . In the first (resp. second) scenario, it has been shown that the minimum number
of good agents guaranteeing deterministic gathering of all of them is f + 1 (resp. f + 2). However, for
both these scenarios, all the existing deterministic algorithms, whether or not they are optimal in terms
of required number of good agents, have the major disadvantage of having a time complexity that is
exponential in n and L, where L is the value of the largest label belonging to a good agent.
In this paper, we seek to design a deterministic solution for Byzantine gathering that makes a concession on the proportion of Byzantine agents within the team, but that offers a significantly lower
complexity. We also seek to use a global knowledge whose the length of the binary representation (that
we also call size) is small. In this respect, assuming that the agents are in a strong team i.e., a team in
which the number of good agents is at least some prescribed value that is quadratic in f , we give positive
and negative results. On the positive side, we show an algorithm that solves Byzantine gathering with
strong teams in all graphs of size at most n, for any integers n and f , in a time polynomial in n and the
length |lmin | of the binary representation of the smallest label of a good agent. The algorithm works
using a global knowledge of size O(log log log n), which is of optimal order of magnitude in our context
to reach a time complexity that is polynomial in n and |lmin |. Indeed, on the negative side, we show that
there is no deterministic algorithm solving Byzantine gathering with strong teams, in all graphs of size
at most n, in a time polynomial in n and |lmin | and using a global knowledge of size o(log log log n).
∗
This work was performed within Project ESTATE (Ref. ANR-16-CE25-0009-03) and Project TOREDY. The first project is
supported by French state funds managed by the ANR (Agence Nationale de la Recherche), while the second project is supported
by the European Regional Development Fund (ERDF) and the Hauts-de-France region.

1

Keywords: gathering, deterministic algorithm, mobile agent, Byzantine fault, polynomial time.

1 Introduction
1.1

Context

Gathering a group of mobile agents is a basic problem that has been widely studied in literature dedicated
to mobile and distributed systems. One of the main reasons for this popularity stems from the fact that this
task turns out to be an essential prerequisite to achieve more complex cooperative works. In other words,
getting fundamental results on the problem of gathering implies de facto getting fundamental results on a
large set of problems whose resolution needs to use gathering as a building block.
The scale-up when considering numerous agents is inevitably tied to the occurrence of faults among them,
the most emblematic of which is the Byzantine one. Byzantine faults are very interesting under multiple
aspects, especially because the Byzantine case is the most general one, as it subsumes all the others kind of
faults. In fact, in the field of fault tolerance they are considered as the worst faults that can occur.
In this paper, we consider the problem of gathering in a deterministic way in a network modeled as a graph,
wherein some agents are Byzantine. A Byzantine agent acts in an unpredictable and arbitrary manner. For
instance it may choose to never stop or to never move. It may also convey arbitrary information to the
other agents, impersonate the identity of another agent, and so on. In such a context, gathering is very
challenging, and so far the power of such Byzantine agents has been offset by a huge complexity when
solving this problem. In what follows, we seek a solution allowing to withstand Byzantine agents while
keeping a “reasonable” complexity.
1.2

Model and problem

A team of mobile agents are initially placed by an adversary at arbitrary nodes of a network modeled as a
finite, connected, undirected graph G = (V, E). We assume that |V | ≤ n. Several agents may initially share
the same node and the size of the team may be larger than n. Two assumptions are made about the labelling
of the two main components of the graph that are nodes and edges. The first assumption is that nodes are
anonymous i.e., they do not have any kind of labels or identifiers allowing them to be distinguished from
one another. The second assumption is that edges incident to a node v are locally ordered with a fixed port
numbering ranging from 0 to deg(v) − 1 where deg(v) is the degree of v. Therefore, each edge has exactly
two port numbers, one for each of both nodes it links. The port numbering is not supposed to be consistent: a
given edge (u, v) ∈ E may be the i-th edge of u but the j-th edge of v, where i 6= j. These two assumptions
are not fortuitous. The primary motivation of the first one is that if each node could be identified by a
label, gathering would become quite easy to solve as it would be tantamount to explore the graph (via e.g.
a breadth-first search) and then meet in the node having the smallest label. While the first assumption is
made so as to avoid making the problem trivial, the second assumption is made in order to avoid making the
problem impossible to solve. Indeed, in the absence of a way allowing an agent to distinguish locally the
edges incident to a node, gathering could be proven as impossible to solve deterministically in view of the
fact that some agents could be precluded from traversing some edges and visit some parts of the graph.
Time is discretized into an infinite sequence of rounds. In each round, every agent, which has been previ2

ously woken up (this notion is detailed in the next paragraph), is allowed to stay in place at its current node
or to traverse an edge according to a deterministic algorithm. The algorithm is the same for all agents: only
the input, whose nature is specified further in the subsection, varies among agents.
Before being woken up, an agent is said to be dormant. A dormant agent may be woken up only in two
different ways: either by the adversary that wakes some of the agents at possibly different rounds, or as soon
as a non-dormant agent is at the starting node of the dormant agent. We assume that the adversary wakes up
at least one agent. Note that, when the adversary chooses to wake up in round r a dormant agent located at
a node v, all the dormant agents that are at node v wake up in round r.
When an agent is woken up in a round r, it is told the degree of its starting node. As mentioned above, in
each round r ′ ≥ r, the executed algorithm can ask the agent to stay idle or to traverse an edge. In the latter
case, this takes the following form: the algorithm asks the agent, located at node u, to traverse the edge
having port number i, where 0 ≤ i < deg(u) − 1. Let us denote by (u, v) ∈ E this traversed edge. In round
r ′ + 1, the agent enters node v: it then learns the degree deg(v) as well as the local port number j of (u, v)
at node v (recall that in general i 6= j). An agent cannot leave any kind of tokens or markers at the nodes it
visits or the edges it traverses.
In the beginning, the adversary also assigns a different positive integer (called label) to each agent. Each
agent knows its label but does not know a priori the labels of the other agents (except if some or all of them
are inserted in the global knowledge GK that is introduced below). When several agents are at the same node
v in the same round t, they see, for each agent x at node v, the label of agent x and all information it wants
to share with the others in round t. This transmission of information is done in a “shouting” mode in one
round: all the transmitted information by all agents at node v in round t becomes common knowledge for
agents that are currently at node v in round t. On the other hand when two agents are not at the same node
in the same round they cannot see or talk to each other: in particular, two agents traversing simultaneously
the same edge but in opposite directions, and thus crossing each other on the same edge, do not notice this
fact. In every round, the input of the algorithm executed by an agent a is made up of the label of agent a,
the up-to-date memory of what agent a has seen and learnt since its waking up and some global knowledge
denoted by GK. Parameter GK is a piece of information that is initially given to all agents and common to
all of them (i.e., GK is the same for all agents): its nature is precised at the end of this subsection. Note
that in the absence of a way of distinguishing the agents, the gathering problem would have no deterministic
solution in some graphs, regardless of the nature of GK. This is especially the case in a ring in which at
each node the edge going clockwise has port number 0 and the edge going anti-clockwise has port 1: if all
agents are woken up in the same round and start from different nodes, they will always have the same input
and will always follow the same deterministic rules leading to a situation where the agents will always be at
distinct nodes no matter what they do.
Within the team, it is assumed that f of the agents are Byzantine. A Byzantine agent has a high capacity
of nuisance: it can choose an arbitrary port when it moves, can convey arbitrary information to other agents
and can change its label in every round, in particular by forging the label of another agent or by creating
a completely new one. All the agents that are not Byzantine are called good. We consider the task of f Byzantine gathering which is stated as follows. The adversary wakes up at least one good agent and all
good agents must eventually be in the same node in the same round, simultaneously declare termination
and stop, despite the fact there are f Byzantine agents. Regarding this task, it is worth mentioning that we
3

cannot require the Byzantine agents to cooperate as they may always refuse to be with some agents. Thus,
gathering all good agents with termination is the strongest requirement we can make in such a context. The
time complexity of an algorithm solving f -Byzantine gathering is the number of rounds counted from the
start of the earliest good agent until the task is accomplished.
We end this subsection by explaining what we mean by global knowledge, that can be viewed as a kind of
advice given to all agents. Following the paradigm of algorithms with advice [1, 25, 38, 9, 20, 19, 33], GK
is actually a piece of information that is initially provided to the agents at the start, by an oracle knowing the
initial instance of the problem. By instance, we precisely mean: the entire graph with its port numbering,
the initial positions of the agents with their labels, the f agents that are Byzantine, and for each agent the
round, if any, when the adversary wakes it up in case it has not been woken up before by another agent. So,
for example, GK might correspond to the size of the network, the number of Byzantine agents, or a complete
map of the network, etc. As mentionned earlier, we assume that GK is the same for all agents. The size of
GK is the length of its binary representation.
1.3

Related works

When reviewing the chronology of the works that are related to the gathering problem, it can be seen that
this problem has been first studied in the particular case in which the team is made of exactly two agents.
Under such a limitation, gathering is generally referred to as rendezvous. From the first mention of the
rendezvous problem in [36], this problem and its generalization, gathering, have been extensively studied
in a great variety of ways. Indeed, there is a lot of alternatives for the combinations we can make when
addressing the problem, e.g., by playing on the environment in which the agents are supposed to evolve, the
way of applying the sequences of instructions (i.e., deterministic or randomized) or the ability to leave some
traces in the visited locations, etc. In this paper, we are naturally closer to the research works that are related
to deterministic gathering in networks modeled as graphs. Hence, we will mostly dwell on this scenario in
the rest of this subsection. However, for the curious reader wishing to consider the matter in greater depth,
we invite him to consult [8, 2, 24] that address the problem in the plane via various scenarios, especially
in a system affected by the occurrence of faults or inaccuracies for the last two references. Regarding
randomized rendezvous, a good starting point is to go through [3, 4, 28].
Now, let us focus on the area that concerns the present paper most directly, namely deterministic rendezvous
and/or gathering in graphs. In most papers on rendezvous in networks, a synchronous scenario was assumed,
in which agents navigate in the network in synchronous rounds. Under this context, a lot of effort has been
dedicated to the study of the feasibility and to the time (i.e., number of rounds) required to achieve the task,
when feasible. For instance, in [16] the authors show a rendezvous algorithm polynomial in the size of the
graph, in the length of the shorter label and in the delay between the starting time of the agents. In [26]
and [37] solutions are given for rendezvous, which are polynomial in the first two of these parameters and
independent of the delay. While these algorithms ensure rendezvous in polynomial time (i.e., a polynomial
number of rounds), they also ensure it at polynomial cost where the cost corresponds here to the total number
of edge traversals made by both agents until meeting. Indeed, since each agent can make at most one edge
traversal per round, a polynomial time always implies a polynomial cost. However, the reciprocal may be
not true, for instance when using an algorithm relying on a technique similar to “coding by silence” in the
time-slice algorithm for leader election [29]: “most of the time” both agents stay idle, in order to guarantee

4

that agents rarely move simultaneously. Thus these parameters of cost and time are not always linked to
each other. This was recently highlighted in [32] where the authors studied the tradeoffs between cost and
time for the deterministic rendezvous problem. Some other efforts have been also dedicated to analyse the
impact on time complexity of rendezvous when in every round the agents are brought with some pieces of
information by making a query to some device or some oracle, see, e.g., [14, 31]. Along with the works
aiming at optimizing the parameters of time and/or cost of rendezvous, some other works have examined the
amount of memory that is required to achieve deterministic rendezvous e.g., in [21, 22] for tree networks
and in [12] for general networks.
Apart from the synchronous scenario, the academic literature also contains several studies focusing on a
scenario in which the agents move at constant speed, which are different from each other, or even move
asynchronously: in this latter case the speed of agents may then vary and is controlled by the adversary.
For more details about rendezvous under such a context, the reader is referred to [30, 13, 23, 18, 27] for
rendezvous in finite graphs and [5, 10] for rendezvous in infinite grids.
As stated in the previous subsection, our paper is also related to the field of fault tolerance since some agents
may be prone to Byzantine faults. First introduced in [34], a Byzantine fault is an arbitrary fault occurring
in an unpredictable way during the execution of a protocol. Due to its arbitrary nature, such a fault is
considered as the worst fault that can occur. Byzantine faults have been extensively studied for “classical”
networks i.e., in which the entities are fixed nodes of the graph (cf., e.g., the book [29] or the survey [6]).
To a lesser extend, the occurrence of Byzantine faults has been also studied in the context of mobile entities
evolving on a one-dimensional or two-dimensional space, cf. [2, 15, 11].
Gathering in arbitrary graphs in presence of many Byzantine agents was considered in [17, 7]. Actually, our
model is borrowed from both these papers, and thus they are naturally the closest works to ours. In [17],
the problem is introduced via the following question: what is the minimum number M of good agents that
guarantees f-Byzantine gathering in all graphs of size n? In [17], the authors provided several answers to
this problem by firstly considering a relaxed variant, in which the Byzantine agents cannot lie about their
labels, and then by considering a harsher form (the same as in our present paper) in which Byzantine agents
can lie about their identities. For the relaxed variant, it has been proven that the minimum number M
of good agents that guarantees f -Byzantine gathering is precisely 1 when GK = (n, f ) and f + 2 when
GK is reduced to f only. The proof that both these values are enough, relies on polynomial algorithms
using a mechanism of blacklists that are, informally speaking, lists of labels corresponding to agents having
exhibited an “inconsistent” behavior. Of course, such blacklists cannot be used when the Byzantine agents
can change their labels and in particular steal the identities of good agents. Still in [17], the authors give for
the harsher form of f -byzantine gathering a lower bound of f + 1 (resp. f + 2) on M and a deterministic
gathering algorithm requiring at least 2f +1 (resp. 4f +2) good agents, when GK = (n, f ) (resp. GK = f ).
Both these algorithms have a huge complexity as they are exponential in n and L, where L is the largest label
of a good agent evolving in the graph. Some advances are made in [7], via the design of an algorithm for
the case GK = (n, f ) (resp. GK = f ) that works with a number of good agents that perfectly matches the
lower bound of f + 1 (resp. f + 2) shown in [17]. However, these algorithms also suffer from a complexity
that is exponential in n and L.

5

1.4

Our results

As mentioned just above, the existing deterministic algorithms dedicated to f -Byzantine gathering all have
the major disadvantage of having a time complexity that is exponential in n and L, when Byzantine agents
are allowed to change their labels. Actually, these solutions are all based on a common strategy that consists
in enumerating the possible initial configurations, and successively testing them one by one. Once the
testing reaches the correct initial configuration, the gathering can be achieved. However, in order to get a
significantly more efficient algorithm, such a costly strategy must be abandoned in favor of a completely
new one.
In this paper, we seek to design a deterministic solution for Byzantine gathering that makes a concession
on the proportion of Byzantine agents within the team, but that offers a significantly lower complexity. We
also seek to use a global knowledge whose the length of the binary representation (that we also call size)
is small. In this respect, assuming that the agents are in a strong team i.e., a team in which the number
of good agents is at least the quadratic value 5f 2 + 6f + 2, we give positive and negative results. On the
positive side, we show an algorithm that solves f -Byzantine gathering with strong teams in all graphs of
size at most n, for any integers n and f , in a time polynomial in n and |lmin |. The algorithm works using a
global knowledge of size O(log log log n), which is of optimal order of magnitude in our context to reach a
time complexity that is polynomial in n and |lmin |. Indeed, on the negative side, we show that there is no
deterministic algorithm solving f -Byzantine gathering with strong teams, in all graphs of size at most n, in
a time polynomial in n and |lmin | and using a global knowledge of size o(log log log n).
1.5

Roadmap

The next section is dedicated to the presentation of some basic definitions and routines that we need in the
rest of this paper. In Section 3, we describe two building blocks that are used in turn in Section 4 to establish
our positive result. In Section 5, we prove our negative result. Finally we make some concluding remarks in
Section 6.

2 Preliminaries
Throughout the paper, log denotes the binary logarithm. An agent will be designated by a capitalized letter,
and the label of an agent X will be denoted by ℓX . The length of the binary representation of ℓX will be
denoted by |ℓX |. The length of the binary representation of the smallest label of a good agent in a given
team will be denoted by |lmin |.
Several routines given in this paper will use a procedure whose aim is graph exploration, i.e., visiting all
nodes of the graph. This procedure, based on universal exploration sequences (UXS), is a corollary of the
result of Reingold [35]. Given any positive integer n, this procedure, called EXPLO(n), allows the executing
agent to traverse all nodes of any graph of size at most n, starting from any node of this graph, using P (n)
edge traversals, where P is some polynomial. After entering a node of degree d by some port p, the agent can
compute the port q by which it has to exit; more precisely q = (p+xi ) mod d, where xi is the corresponding
term of the UXS of length P (n). We denote by Xn the execution time of procedure EXPLO with parameter
n (note that Xn = P (n) + 1).

6

Besides this exploration procedure, we will use a label transformation derived from [16]. Let ℓB be the
label of an agent B and b1 . . . bc its binary representation with c its length. The binary representation of the
corresponding transformed label ℓ∗B is 10b1 b1 . . . bc bc 0110b1 b1 . . . bc bc 01. This transformation is made to
ensure the following property that is used in the proof of correctness of our algorithm in Section 4.
Proposition 2.1 Let ℓB and ℓX be two labels such that ℓB < ℓX . Let b∗1 b∗2 . . . b∗4c+8 and x∗1 x∗2 . . . x∗4y+8 be
the respective binary representations of ℓ∗B and ℓ∗X , with c and y the lengths of the binary representations
of ℓB and ℓX respectively. There exist two positive integers i ≤ 2c + 4 and 2c + 4 < j ≤ 4c + 8 such that
b∗i 6= x∗i and b∗j 6= x∗j .
Proof. Let b1 b2 . . . bc (resp. x1 x2 . . . xy ) the binary representation of ℓB (resp. ℓX ). There are two cases to
consider: either c = y or c < y. In the first case, since ℓB 6= ℓX , there exists a positive integer i ≤ c such
that bi 6= xi . This implies in particular that x∗2i+1 6= b∗2i+1 and x∗2c+2i+5 6= b∗2c+2i+5 . In the second case,
either x∗2c+3 6= b∗2c+3 or x∗2c+4 6= b∗2c+4 , and if x∗2c+5 = b∗2c+5 then x∗2c+6 6= b∗2c+6 . Hence, in each case the
proposition holds.

Throughout the paper, we will recurrently design some routines in the form of a description of several
states, where an agent has to apply specific rules, along with how to transit among them. In each round
spent executing such a routine, we assume that a good agent will tell its current state to the other agents
sharing the same node. Sometimes, we will require that an agent also tells extra information other than only
its state: when such a situation arises, we will obviously precise this point. Moreover, in the description of
our states, we will use different expressions that are as follows. When we say “agent A enters state W”, we
precisely mean that at the previous round, agent A was in some state U 6= W and at the current round, it is
in state W. When we say “agent A exits state X”, we mean agent A remains in state X until the end of the
current round and is in some state V 6= X at the following round. Lastly, when we say “agent A transits from
state Y to state Z”, we mean agent A exits state Y at the current round and enters state Z at the following
one. Thus, in each round, agent A is always exactly in at most one state.

3 Building blocks
To design our solution that is given in Section 4, we need to describe two prior subroutines that will be used
as building blocks.
In the rest of this section, for each of both building blocks, we first explain the high level idea that is behind it.
Then, we give a detailed description of it. Finally, we show its correctness and analyze its time complexity.
3.1

Procedure GROUP

The first building block called GROUP takes as input three integers T , n and bin such that bin ∈ {0; 1}.
Let x be an integer that is at least f + 2. Roughly speaking, subroutine GROUP(T , n, bin) ensures that
(x − f ) good agents finish the execution of the subroutine at the same round and in the same node in a
graph of size at most n provided the following two conditions are verified: the number of agents is at least
(x − 1)(f + 1) + 1, and all good agents start executing the subroutine in some interval lasting at most T
7

rounds, with the same parameters except for the last one that has to be 0 (resp. 1) for at least one good agent.
The time complexity of the procedure is polynomial in the first two parameters T and n.
3.1.1

High level idea

As mentioned previously, subroutine GROUP aims at ensuring that x − f good agents finish the execution of
the subroutine at the same round and in the same node. To achieve this, we have to face several difficulties,
especially the fact that the agents know neither x nor f , and also the fact that agents have a priori no mean to
detect whether an agent is good or not. Indeed, we cannot have instructions like “If there are at least x − f
good agents in my current node, then. . . ”. We cannot even have “If there are at least x or f agents in my
current node, then...” no matter whether there are some Byzantine agents or not in the current node. So,
to circumvent these problems, procedure GROUP is made of two phases. The first phase aims at ensuring
that at least x agents executing the first phase meet in the same node (even though the involved agents do
not detect this event). This phase lasts exactly the same time for each good agent and when it finishes it, a
good agent is at the node from which it started executing it. The second phase consists, for a good agent, in
replaying in the same order the same edge traversals and waiting periods made during the first i rounds of
its first phase started at round t, such that t + i is the round when the agent was with the maximal number
of agents executing the first phase (if there are several such rounds, we choose the latest one). Once this
is done, the agent stops executing GROUP. By doing so, we have the guarantee that x − f good agents
(those involved in the last maximal meeting of the first phase) will stop executing the second phase (and
thus procedure GROUP) in the same node and at the same round, as all the meetings involving the maximal
number of agents in the first phase, necessarily involve at least x agents. Hence, the key of the procedure is
to make x agents meet in the first phase.
During the execution of the first phase, the agents are partitioned into two distinct groups, namely followers
and searchers. The first group corresponds to agents executing the subroutine with bin = 0 and the second
group corresponds to those executing it with bin = 1.
The first phase works in steps 1, 2, . . . , S where S is some polynomial in T and n. At a very high level, in
each step, the main role of followers is to remain idle in their initial starting nodes in order to “mark” possible
positions on which x agents could meet, while the main role of searchers is to look for these positions. To
this end, each searcher will make use of a kind of map that it initially computes during the first step by
making an entire traversal of the graph, using procedure EXPLO(n). Actually, this map corresponds to a
sequence P of objects symbolizing every visited node v along with the list of labels of the agents that are
(or pretend to be) followers present in node v at the time of the visit by the searcher. More precisely, the
length of P is equal to the number of visited nodes in EXPLO(n), and the i-th object of P contains, among
other information, the set of all followers’ labels present in the i-th visited node of the traversal. Note that
such a map will be called imperfect map as some nodes can be represented several times in the sequence
P . Indeed EXPLO(n) guarantees that each node is visited at least once but some nodes may be visited more
than once. The use of the qualifying term “imperfect” also stems from the fact that the list of followers’
labels that are stored in P may be plagued by artificial ones created by Byzantine agents. In all the other
steps, the searchers never recompute a new imperfect map, but always use the one computed in the first
step, along with some possible updates on the lists of labels. How and when these updates are applied is
explained below: they are obviously related to “bad behaviors” coming from Byzantine agents.

8

For the convenience of the explanation, let us first consider an ideal situation in which there is a unique
follower among the good agents. If there is no Byzantine agent, during the first step, by moving to the node
that hosts the unique follower, all searchers meet in the same node: using their maps, they are all able to
determine a path to this follower. Thus, if the number of good agents is at least x, there is necessarily a
round in which x agents meet in the same node. However, when Byzantine agents come into the picture,
the problem becomes a tricky one, as these malicious agents can also pretend to have the status of followers
(with the same label or not). Hence, all the searchers may not necessarily choose to move towards the same
follower, which may prevent in fine the meeting of x agents. To deal with this issue and limit the confusion
caused by Byzantine agents, in each step every good searcher A proceeds as follows. Let ℓ be the smallest
label in sequence P (corresponding to the imperfect map of A) and let i be the first object of P in which ℓ
appears. Agent A moves to the node u of the graph corresponding to the i-th object of P in order to meet
again the follower with label ℓ and waits some prescribed amount of rounds with it at node u. If A does
not see a follower with label ℓ when reaching u, or at some point during its waiting period at u it does not
see anymore any follower with label ℓ, then agent A updates its imperfect map by removing ℓ from the
list of the i-th object. Then, in all cases, the agent will end up starting the following step (if any) with its
possibly updated map. The total number S of steps has been carefully chosen so that it is larger than the
total number of map updates that can be made by all good agents in the network. Hence, we can ensure the
existence of a step in which there is no map update: in such a step we will be able to prove that the number
of different locations that are reached by searchers is at most f + 1. Thus, if the number of good agents is
at least (x − 1)(f + 1) + 1, using arguments relying on the pigeonhole principle, we will prove the meeting
of x agents. Keep in mind that all the above explanations are made under the assumption there is a single
good follower in the team. When there are more than one good follower, things get more complicated. For
instance, observe in this case that even though the number of good agents is at least (x − 1)(f + 1) + 1,
our approach, without additional precautions, may fail to make at least x agents meet on the same node
as the number of good searchers may not be enough to ensure the meeting. Indeed, for a given number
of agents, the more followers, the less searchers to distribute. However, through extra technical actions
requiring sometimes some followers to end up behaving as a searcher, we will be able to overcome this
issue and still ensure the meeting of x agents provided the cardinality of the set of good agents is at least
(x − 1)(f + 1) + 1.
3.1.2

Detailed description

To describe subroutine GROUP, we use a function called IM that takes as input two integers n and q ∈ {0, 1},
and returns an ordered sequence P of lists of labels: P =< L1 , . . . , LXn >. The returned sequence P is
called an imperfect map. When a given agent A performs IM (q, n), it actually executes EXPLO(n) with
some additional actions. At each step of EXPLO(n), depending on the value of q, A checks the presence
of a given agent or a group of agents to compute P . During the first step, the agent is at the node from
which it starts IM (q, n). Let us consider the j th step of EXPLO(n) (j ∈ {1, . . . , Xn }) and let u be the
node on which A is at this step. If q = 0, Lj is a list of pairwise distinct labels such that ℓB ∈ Lj iff there
is on u an agent B with label ℓB being or pretending to be a follower. If q = 1, Lj is a list of pairwise
distinct labels such that ℓB ∈ Lj iff there is on u an agent B with label ℓB being or pretending to be a
follower in state Wait-for-attendees. State Wait-for-attendees is defined in the description
of the algorithm. When ℓB is added to a list of P by A, we say that A records B. At the end of EXPLO(n),

9

the agent traverses all the edges traversed in EXPLO(n) in the reverse order, and then it exits IM (q, n).
To facilitate the presentation of the formal description of procedure GROUP, we also need the following two
definitions.
Definition 3.1 (Useful map) An imperfect map P is said to be useful iff P contains a non-empty list.
Definition 3.2 (Index of a map) Let P =< L1 , . . . , LXn > be a useful map. Let S be the set of every label
that appears in at least one list of P . Let j be the smallest integer such that Lj contains the smallest label
of S: j is the index of P .
Now, we are ready to give the formal description of the subroutine. Subroutine GROUP(T , n, bin) comprises
two phases: Process and Build-up. Let us consider a given agent A executing GROUP(T , n, bin) from an
initial node v. When bin = 0, the agent is said to be a follower. Otherwise, it is said to be a searcher. The
description is in the form of several states along with rules to transit among them. At the beginning of each
state, the agent is in its initial node v.
• Phase Process. Agent A proceeds in steps 1, 2, . . . , S where S = n2 .T .Xn + 1. Assume without
loss of generality that A is at step s ∈ {1, . . . , S}. Unless stated explicitly, all the transitions between
states which are presented below are performed within the same step. In all what follows H =
(n + 1)[T + 4Xn + (Xn .n)(T n + n)(2Xn + T )] + 3. We describe A’s behavior depending on the
value of bin.
– bin = 0 (A is a follower). In this case, A can be in one of the following states: Invite,
Wait-for-attendees, Search-for-a-group and Follow-up. At the beginning of
each step s, agent A is in state Invite. The actions to be performed in each state are presented
in what follows.
State Invite. Agent A waits 2T + 3Xn rounds. At the end of this waiting time, if A is on the
same node as at least one searcher, A transits to state Wait-for-attendees. Otherwise, it
transits to state Search-for-a-group.
State Wait-for-attendees. Agent A waits 2T + Xn + H rounds. If at each round of this
waiting period, there is at least one searcher at node v, then at the end of the waiting period agent
A transits to state Follow-up. Otherwise, as soon as there is a round of the waiting period
when there is no searcher at node v, agent A transits to state Search-for-a-group (hence
the waiting period may be prematurely stopped).
State Search-for-a-group. Let k be the number of rounds spent by agent A in
state Wait-for-attendees of step s.
Note that k = 0 if A transited directly to state Search-for-a-group from state Invite
in step s. Let w be a counter, the initial value of which is 0. The way this counter is incremented
and decremented is explained below.
10

While agent A does not reach round t + 2T + Xn + H − k where t is the round when it entered
this state in step s, it proceeds as follows (thus, what follows is then interrupted when reaching
round t + 2T + Xn + H − k). Agent A first waits T rounds and then executes IM (1, n). Once
this is done, the agent has a map P . Each time P is useful (refer to Definition 3.1) and w = 0,
the agent performs the first i − 1 edge traversals of EXPLO(n) from its initial node v where i is
the index of P : just before each edge traversal, counter w is incremented by one. Let us refer to
the node reached at the end of these i − 1 edge traversals by u. As long as there is a follower B
in state Wait-for-attendees on u such that ℓB is the smallest label in the i-th list Li of P ,
A remains idle. By contrast, if there is no such follower on u in some round, agent A updates P
by removing from Li its smallest element and then goes back to its initial node v by performing
the (i − 1) edge traversals executed above in the reverse order: just before each edge traversal
of this backtrack, counter w is decremented by one.
As soon as agent reaches round t + 2T + Xn + H − k, the agents proceeds as follows: if
w = 0, it transits to state Follow-up. Otherwise, if w > 0, A goes back to its initial node v
by traversing in the reverse order the sequence of w edges e1 , e2 , . . . , ek corresponding to the w
first edge traversals of EXPLO(n) from node v: once this is done, it transits to state Follow-up.
State Follow-up. Let x be the number of rounds elapsed from the beginning of the current
step. Agent A waits 5T + 5Xn + H − x rounds. At the end of the waiting time, if s < S,
A transits to state Invite of step s + 1. Otherwise, A transits to state Restart of phase
Build-up.
– bin = 1 (A is a searcher). Agent A can be in one of the following states:
Search-for-an-invitation, Accept-an-invitation and Follow-up.
At the beginning of each step s, agent A is in state Search-for-an-invitation. We
present in what follows the set of actions to be performed for each state.
State Search-for-an-invitation. Agent A first waits T rounds. Next, if s = 1 (first
step of phase Process), A executes IM (0, n) and then transits to state Accept-an-invitation.
The output of the execution of IM (0, n) is stored in variable Z. This variable may be updated
in the current step as well as the following ones: each time we will mention this variable, we
will implicitly consider its up-to-date value. If s > 1, A waits 2Xn rounds and then transits to
state Accept-an-invitation.
State Accept-an-invitation. In the case where Z is not a useful map, A transits to
state Follow-up. Otherwise, let j and ℓ be the index of Z and the smallest label in the j-th
list of Z respectively. Agent A performs the first j − 1 edge traversals of EXPLO(n). Let t be
the round when agent A finishes these first j − 1 edge traversals, and let u be the node reached
by A in round t. As soon as there is a round in {t + 1, t + 2, . . . , t + 2T + Xn + H} for which
there is no follower B at node u such that label ℓB = ℓ, agent A updates P by removing ℓ from
Lj and goes back to its initial node v by performing the (j − 1) edge traversals executed above
in the reverse order. Once this backtrack is done, agent A transits to state Follow-up.
11

If agent A is still in state Accept-an-invitation in round t + 2T + Xn + H, it goes back
to its initial node v by performing the (j − 1) edge traversals executed above in the reverse order, and then it transits to state Follow-up (note that in this latter case, Z remains unchanged).
State Follow-up. Let x be the number of rounds elapsed from the beginning of the current
step. Agent A waits 5T + 5Xn + H − x rounds. At the end of the waiting time, if s < S,
then A transits to state Search-for-an-invitation of step s + 1. Otherwise, it transits
to state Restart of phase Build-up.
• Phase Build-up. Agent A can only be in state Restart.
//At the beginning of this phase, the agent is at the node from which it started procedure GROUP i.e.,
node v
State Restart. Let r be the round in which A initiated GROUP and let r + i be the round in phase
Process in which A is on a node containing the largest number of agents (including A itself) that are
not in state Restart. If there are several such rounds, it chooses the one with the largest value i.
Denote by r ′ the round in which the agent enters this state. From round r ′ to r ′ +i−1, agent A replays
exactly the same waiting periods and edges traversals from round r to r + i − 1. More precisely, for
each integer y in {0, 1, . . . , i − 1}, if agent A remains idle (resp. leaves the current node via a port o)
from round r + y to round r + y + 1, then agent A remains idle (resp. leaves the current node via port
o) from round r ′ + y to r ′ + y + 1. In round r ′ + i, the agent stops the execution of GROUP.
3.1.3

Correctness and complexity analysis

Let E and ∆ be respectively the set of all good agents in the network and the first round in which an
agent of E starts executing GROUP(T , n, bin). Let x be an integer that is at least f + 2. To conduct
the proof of correctness as well as the complexity analysis, we assume in the rest of this subsection that
|E| ≥ (x − 1)(f + 1) + 1, every agent of E starts executing GROUP(T , n, bin) at round ∆ + T − 1 at the
latest, and at least one agent of A starts executing the procedure with bin = 0 (resp. bin = 1).
We start with the following lemma about the duration of each step and the duration of phase Process. Recall
that S and H are polynomials in n and T given in the detailed description of procedure GROUP.
Lemma 3.1 Let A be an agent of E. We have the following two properties.
1. Each step of phase Process executed by A lasts exactly 5T + 5Xn + H rounds.
2. The execution of phase Process by agent A lasts exactly S · (5T + 5Xn + H) rounds.
Proof. According to the algorithm, S corresponds to the number of steps in phase Process. So, if the first
property holds, the second one also holds. Hence, to prove the lemma, it is enough to prove that the first
property is true: this will be the purpose of the rest of this proof.
Let s be a step of phase Process executed by agent A. Let us first prove that A transits to state Follow-up
of step s after having spent at most 4T + 5Xn + H rounds in this step. Depending on the value of bin, A
can be either a searcher or a follower. We consider the two cases.
12

• A is a follower. The state of A in the first round of every step s of phase Process during the execution of GROUP is Invite. Agent A spends 2T + 3Xn rounds in state Invite before transiting
to either state Wait-for-attendees or state Search-for-a-group depending on whether
there is a searcher on the same node as A at the end of this waiting time. Agent A remains in either
state Wait-for-attendees or Search-for-a-group at most 2T + 2Xn + H rounds before
transiting to state Follow-up. Hence, agent A spends at most 4T + 5Xn + H in step s before
transiting to state Follow-up.
• A is a searcher. The state of A in the first round of GROUP is Search-for-an-invitation.
First, agent A waits T rounds. Next, if s = 1, A executes IM (0, n) that lasts 2Xn rounds before transiting to state Accept-an-invitation. Otherwise s > 1 and A waits 2Xn rounds before transiting to state Accept-an-invitation. That is, in both cases, A spends T + 2Xn in total before
transiting to state Accept-an-invitation. Once A transits to state Accept-an-invitation,
if Z, the output of IM (0, n) performed while in state Search-for-an-invitation in the first
step of phase Process, is not a useful map, A transits to state Follow-up and the lemma holds. If
by contrast, Z is useful then A performs the first (j − 1) edge traversals of EXPLO(n) where j is the
index of Z. Agent A waits at most 2T + Xn + H rounds (with a follower) and then performs less than
Xn edge traversals to retrieve its initial position before transiting to state Follow-up. So, agent A
spends at most 3T + 5Xn + H in step s before transiting to state Follow-up.
Hence, whether A is a follower or not, it spends at most x ≤ 4T + 5Xn + H rounds in step s before
transiting to state Follow-up of step s. However, according to state Follow-up, the agent waits exactly
5T + 5Xn + H − x rounds before leaving step s. Hence, the lemma holds.

From the previous lemma, we get the following corollary and remark.
Corollary 3.1 Let A and B be any two good agents of E such that tA − tB ≥ 0, where tA (resp. tB ) is
the round when A (resp. B) starts executing GROUP. For every step s of phase Process, agent A finishes
executing s, exactly tA − tB rounds after B finishes executing it.
In the following, by initial node we mean the node from which the agent starts executing procedure GROUP.
Note that the statement of Lemma 3.2 calls for the notion of “recording” that is introduced in the description
of function IM .
Lemma 3.2 Let A be a good searcher of E. For every follower B in E, agent A records B during its
execution of IM (0, n) when B is on its initial node.
Proof. According to the algorithm, agent A executes IM (0, n) while in state Search-for-an-invitation
of step 1. More precisely, when starting step 1, agent A first waits T rounds and then executes IM (0, n)
that lasts 2Xn rounds. On the other hand, agent B waits 2T + 3Xn rounds in its initial node at the beginning
of step 1. Hence, in view of the initial delay T , the lemma follows.

13

To continue, we need to introduce the definition of target node. A node u is said to be a target node of a good
searcher A in a step s > 1, if u is the node that is reached after performing the first (j − 1) edge traversals
of EXPLO(n) from the initial node of A and j is the index of the imperfect map of A at the beginning of its
execution of step s.
Lemma 3.3 Let A be a searcher of set E starting a step s with a useful map P , the index of which is j. Let
ℓ be the smallest label in the j-th list of P . If the target node of A in step s is the initial node of a good
follower B such that ℓB = ℓ, then A does not update P in any step s′ ≥ s.
Proof. We prove by induction on i ≥ 0 that A does not update P in step s + i. First consider, the initial step
in which i = 0. Assume by contradiction that the target node of A in step s is the initial node u of a good
follower B such that ℓB = ℓ, but A updates P in step s. According to procedure GROUP, agent A reaches
node u while in state Accept-an-invitation. Then, agent A updates P in step s only if agent A does
not meet agent B when reaching target node u or A notices the absence of B on u within 2T +Xn +H rounds
after its meeting with B. However, when agent B starts step s, it first waits 2T + 3Xn in state Invite.
Hence in view of Corollary 3.1 and the definition of T , agent A meets B when reaching target node u while
B is in state Invite: indeed agent A spends T + 2Xn rounds in state Search-for-an-invitation
and at most Xn rounds in state Accept-an-invitation before reaching its target node u at some
round t. Moreover, since agent A and B are good, according to states Wait-for-attendees and
Accept-an-invitation agent A remains with B at node u at least 2T + Xn + H rounds after round
t. As a result, agent A does not update P in step s, which is a contradiction and proves the first step of the
induction. Now consider there exits a positive integer i′ such that the property holds for all i ≤ i′ . If the
last step of procedure GROUP is step s + i′ , the lemma directly follows. Otherwise, note that agent A begins
step s + i′ + 1 with the exact same map as in step s + i′ . Hence using the same arguments as in step s + i′ ,
agent A does not update P in step s + i′ + 1. This closes the induction and proves the lemma.

Note that in view of Lemmas 3.2 and 3.3, we know that the imperfect map of every searcher of E remains
always useful. In other terms, each of them always have a target node in every step of procedure GROUP.
This is stated in the following proposition.
Proposition 3.1 The map of every searcher of E is always useful.
In order to prove the main result of this section, i.e., Theorem 3.1, we need the next three lemmas.
Lemma 3.4 If f < n, then there exists an integer s in {1, · · · , S} such that no searcher in set E updates its
imperfect map P during its execution of step s.
Proof. Assume for the sake of a contradiction that for each s in {1, · · · , S} there is at least one searcher of E
that updates the output of its imperfect map P during its execution of step s. According to procedure GROUP,
every searcher A in E executes IM (0, n) to compute P . When A performs IM (0, n), A records all the
followers it meets during the execution of EXPLO(n) in IM (0, n). In particular, for each visited node A
14

can record at most f Byzantine agents. This leads to at most f “wrong” labels in each list of P . Since
f < n, in view of Lemma 3.3, each searcher of E performs at most n.Xn updates of P . Note that, two
distinct searchers of E which start executing procedure GROUP from the same node and at the same round
act exactly in the same manner: in particular, they traverse the same edges synchronously, compute the same
imperfect map and make the same updates at the same time. Hence, taking into account the maximum delay
T , we know that the number of rounds in which we have a searcher of E making an update of its imperfect
map is upper bounded by U = T n2 Xn . However, according to the algorithm S = U + 1. Hence, we get a
contradiction, which proves the lemma.

In view of Lemma 3.4, we can define smin as being the first step for which there is no updates made by a
searcher of E.
Lemma 3.5 If f < n, then there exist a round α and a node v such that x agents meet on node v at round
α, and a searcher of E is in state Accept-an-invitation at round α.
Proof. In order to prove the lemma, we first proceed by proving a series of 4 claims. We start by introducing
some notations that will facilitate the conduct of this proof.
Let Q be the set of nodes verifying the following condition: a node u is in Q if u is a target node of a
searcher of E in step smin . In view of Proposition 3.1, Q =
6 ∅. Let FQ be the set of followers of E being on a
node of Q at the beginning of their execution of step smin . Let ρ be the last round in which a follower of E is
in state Invite before entering either state Search-for-a-group or state Wait-for-attendees
(at round ρ + 1) during its execution of step smin .
Claim 1 At round ρ, every searcher A of E is on its target node. Moreover, A remains on its target node for
at least H rounds after round ρ.
Proof of Claim 1 According to procedure GROUP and the maximal delay T , at round ρ every searcher
has spent in step smin at least T + 3Xn rounds and at most 3T + 3Xn rounds. Moreover, in view of the
definition of step smin and Proposition 3.1, we know that every searcher remains in its target node at least
2T + Xn + H rounds while in state Accept-an-invitation of step smin . However, before entering
state Accept-an-invitation of step smin , each searcher spends at least T + 2Xn rounds and at most
T + 3Xn in step smin . Hence the claim follows.
Claim 2 Let B be a follower of FQ . Agent B remains idle in state Wait-for-attendees on its initial
node from round ρ + 1 to round ρ + H.
Proof of Claim 2 Let u be the initial node of B and ρ′ the last round in which it is in state Invite of step
smin . Since u is a target node of a searcher A of E, agent A reaches u after having spent at least T + 2Xn
rounds and at most T +3Xn rounds in step smin . Since B waits 2T +3Xn in state Invite at the beginning
of step smin , in view of the maximum delay between any pair of agents of E, A reaches node u while B is
still in state Invite. Moreover, by definition of step smin , A remains on u during 2T + Xn + H rounds (in
state Accept-an-invitation). Hence according to procedure GROUP, at round ρ′ agent B has shared
its initial node with agent A for at most 2T + Xn rounds and it enters state Wait-for-attendees at

15

round ρ′ + 1. So, after ρ′ , agent A stays idle with B for at least H rounds. This means in particular that B
is in state Wait-for-attendees from round ρ′ + 1 to ρ′ + H.
Let dif f = ρ−ρ′ . Note that 0 ≤ dif f ≤ T . According to the description of state Wait-for-attendees,
from round ρ′ + H to ρ′ + H + dif f , agent B leaves state Wait-for-attendees only if A leaves u at
some round in {ρ′ + H, . . . , ρ′ + H + dif f }. However, this is impossible according to Claim 1 and the fact
that ρ′ ∈ {ρ − T + 1; ρ − T + 2, . . . , ρ}: indeed ρ′ + H > ρ + 1 and ρ′ + H + dif f = ρ + H. Hence
agent B remains in Wait-for-attendees from round ρ′ + 1 to round ρ′ + H + dif f , which proves the
claim.
Claim 3 Among the nodes of Q, at least |Q| − 1 of them host a Byzantine agent in every round from round
ρ + 1 to round ρ + H.
Proof of Claim 3 Let I be the time interval between round ρ + 1 and round ρ + H. We show that during I,
at least |Q| − 1 nodes of Q host a Byzantine agent. Let B be the first follower of E that starts the execution
of GROUP: if there are several agents satisfying the condition, we choose the one with the smallest label. Let
us denote by ∆B the round in which B starts the execution of GROUP. From Claim 1, during time interval I,
every searcher is on its target node. That is, there are |Q| distinct target nodes for the searchers of E. Hence,
from procedure GROUP and Lemmas 3.2 and 3.3, it follows that on each node of Q there is at least one agent
B ′ being (or pretending to be) a follower such that its label is at most ℓB . According to the definition of B,
and in particular its unicity, we know that at least |Q| − 1 target nodes host a Byzantine agent from round
ρ + 1 to ρ + H. Hence the claim holds.
Let X = T + 4Xn + (nXn )(T n + n)(2Xn + T ). Note that H = (n + 1)X +3. We show the following
claim.
Claim 4 Let ρ + 1 ≤ ν ≤ ρ + H − X be a round, if any, such that no good follower of E enters
state Search-for-a-group from round ν to round ν + X − 1. At least x agents meet at some round in
{ν + 1, . . . , ν + X }.
Proof of Claim 4
Let FQ′ be the set of followers of E that do not belong to FQ and do not enter state Search-for-a-group
of step smin by round v − 1. Let FQ′′ be the set of followers of E that do not belong to FQ and enter
state Search-for-a-group of step smin by round v − 1. Let Q′ be the set of initial nodes of agents in
FQ′ . Note that every good follower belongs to FQ ∪ FQ′ ∪ FQ′′ .
Let B be a follower of FQ′′ . We first show that the map of B, when it is computed, is always useful in step
smin till round ρ + H included. Note that in view of Claim 1, it is enough to prove that agent B starts and
finishes the execution of IM (1, n) in {ρ + 1, . . . , ρ + H}. In view of the definition of ρ and Corollary 3.1,
we know that B enters state Search-for-a-group at some round in {ρ − T + 1, . . . , ν − 1}. Moreover,
when a follower enters this state, it first waits T before executing IM (1, n) that lasts 2Xn rounds. Hence
B starts and finishes IM (1, n) in {ρ + 1, . . . , ν + T + 2Xn }. However, ν + T + 2Xn ≤ ρ + H, which
proves that the map of B, when it is computed, remains always useful in {ρ + 1, . . . , ρ + H}.
As mentioned above, at round ν +T +2Xn , every follower of FQ′′ has completed its execution of IM (1, n).
Observe that when a good follower B transits to state Search-for-a-group from

16

state Wait-for-attendees on a node u at some given round w between round ρ+1 and round ρ+H, every good follower on u also transits to state Search-for-a-group from state Wait-for-attendees
at round w: moreover, these good followers behave in a same synchronous manner i.e., they execute the same
actions in each round between w to round ρ + H. That is, the total number of distinct maps of the agents of
FQ′′ at round ν + T + 2Xn is at most (T .n + n): there are at most T n distinct maps of the good followers
that transit to state Search-for-a-group from eitherstate Invite or state Wait-for-attendees
before round ρ + 1 and at most n additional distinct maps of the good followers that transit from
state Wait-for-attendees to state Search-for-a-group after round ρ.
Next, assume that there exists a round α′ such that ν + T + 2Xn ≤ α′ ≤ ν + X − 2Xn and no good
follower of FQ′′ updates its imperfect map from round α′ to round α′ + 2Xn . We show that in this case,
x agents meet on the same node at some round in {α′ , . . . , α′ + 2Xn }. Let B, P and j be respectively a
follower of FQ′′ , the imperfect map of B and its index from round α′ to round α′ + 2Xn . The target node of
B is the node that is reached after performing the first (j − 1) edge traversals of EXPLO(n) from the initial
node of B. Agent B updates its imperfect map P only if on its target node, there is no follower B ′ such that
ℓB ′ is the smallest label in Lj of P . Since there are no updates from round α′ to round α′ + 2Xn , at round
α′ + 2Xn , every follower B of FQ′′ is on its target node u.
Let us consider the case where u is neither in Q nor Q′ , we show that u hosts at least one Byzantine agent.
From procedure GROUP, we know that at round α′ + 2Xn , node u hosts a follower B ′ such that ℓB ′ is the
smallest label in Lj of P . If B ′ is a good follower, B ′ is in state Wait-for-attendees with a searcher
A (recall that no good follower transits to state Search-for-a-group from round ν to round ν +X −1).
However, A cannot be a good searcher of E since u is not in Q. Hence, u hosts indeed a Byzantine agent
at round α′ + 2Xn . Note that in view of the definition of ν and the algorithm, each agent of FQ′ is on its
initial node with a Byzantine agent pretending to be a searcher from round ρ + 1 to ν + X − 1 (as all the
good searchers are in nodes ∈
/ Q′ according to Claim 1). Let Q′′ be the target nodes which do not belong to
′
Q∪Q , of the good followers of FQ′′ at round α′ +2Xn . By Claim 3, we then have |Q|+|Q′ |+|Q′′ | ≤ f +1.
Moreover, at round α′ + 2Xn , every good agent is in a node of Q ∪ Q′ ∪ Q′′ . Hence by the Pigeonhole
principle, it follows that x agents share the same node at round α′ + 2Xn . If round α′ exists, then the claim
holds. So to conclude the proof of this claim, it remains to show the existence of round α′ . Recall that
each follower of FQ′′ performs at most Xn .n updates of its imperfect map P (since it can record at most f
Byzantine agents that pretend to be followers in state Wait-for-attendees on each node during the
execution of IM (1, n)). Besides, as argued earlier, the total number of distinct maps of the agents of FQ′′
at round ν + T + 2Xn is at most (T .n + n). So, after at most (T .n + n).(Xn .n)(T + 2Xn = X − T − 4Xn
rounds from ν + T + 2Xn , no good follower of FQ′′ updates its imperfect map. Moreover, every good
follower of FQ′′ spends at most 2Xn rounds before reaching its target node. This proves the existence of
round α′ and by extension the claim.
We are now able to prove our lemma. Assume by contradiction that the lemma does not hold. This means
either there is no round when x agents meet, or in every round z when x agent meet, no searcher of E
is in state Accept-an-invitation at round z. Let us first consider the former case. Let F ′ be the
set of good followers that enter state Search-for-a-group from state Wait-for-attendees at
some round in {ρ + 1, . . . , ρ + H}. From Claim 4, we can deduce that there is no consecutive X rounds
in {ρ + 1, . . . , ρ + H − X } in which no good follower of E transits to state Search-for-a-group

17

(otherwise, round α, which is defined in the statement of this lemma, exits). From round ρ + 2 to ρ + H,
only the followers of F ′ may enter state Search-for-a-group. From round ρ + 2 all the agents
of F ′ have already entered state Wait-for-attendees in view of the definition of ρ. Note that
|QF ′ | ≤ n where |QF ′ | is the set of initial nodes of at least one follower of F ′ . Moreover, let C be an
agent of F ′ that enters state Search-for-a-group from state Wait-for-attendees at a round
t ∈ {ρ + 2, . . . , ρ + H}: before round t, agent C does not move in step smin , and all the agents of
F ′ that are in state Wait-for-attendees and share the same node as C in round t − 1 also enter
state Search-for-a-group at round t. Hence, after at most nX rounds from round ρ + 2, there
is no agent that can enter state Search-for-a-group till round ρ + H included. However round
ρ + 3 + nX ≤ ρ + H − X . Hence there exists a round v satisfying the statement of Claim 4 and there is a
meeting of at least x agents at some round in {ν + 1, . . . , ν + X }: we get a contradiction with the fact that α
does not exist. Concerning the latter case, note that there is a round α in {ν +1, . . . , ν +X } in which x agents
meet. In view of Claim 1 and procedure GROUP, every searcher of E is in state Accept-an-invitation
in every round belonging to {ν + 1, . . . , ν + X } : we get a contradiction with the fact that no searcher of E
is in state Accept-an-invitation at round α.


Lemma 3.6 If there exists a round r at which at least x ≥ f + 2 agents meet on the same node and among
them all the good ones are executing phase Process at round r, then at least (x − f ) good agents exit their
execution of GROUP at the same round and on the same node.
Proof. Assume there exists such a round. Let us show that (x − f ) good agents exit their execution of
GROUP at the same round and on the same node. Let x′ be the largest number of agents executing GROUP
but not in state Restart which met in the same node u in some round ∆ + w. If there are several such
rounds, we consider the one with the largest value of w. The good agents executing GROUP but in another
state than Restart are precisely those executing phase Process, which implies that x′ ≥ x. Let Y be the
set of good agents executing phase Process on u at round ∆ + w. Remark that at round ∆ + w on u there
are at most f Byzantine agents. Hence, |Y| ≥ x′ − f .
When in state Restart, every agent A of Y repeats exactly the same waiting periods and edge traversals
as in its execution phase Process in order to reconstruct the group of agents that was at node u in round
∆ + w. More precisely, let r and r ′ be the round when A initiated GROUP and the round when A enters
state Restart respectively. Let i be an integer such that r + i = ∆ + w. From round r ′ to r ′ + i − 1, agent
A replays exactly the same waiting periods and edges traversals from round r to r + i − 1: for each integer
y in {0, 1, . . . , i − 1}, if agent A remains idle (resp. leaves the current node via a port o) from round r + y
to round r + y + 1, then agent A remains idle (resp. leaves the current node via port o) from round r ′ + y
to r ′ + y + 1. In round r ′ + i, agent A is in node u and stops the execution of GROUP. Besides, in view of
Lemma 3.1, every good agent spends the same number of rounds executing phase Process: let us denote this
number by W. So, r ′ + i = r + W + i = ∆ + w + W. Hence, every agent of Y is in node u and stops the
execution of GROUP at round ∆ + w + W.

Now we are ready to end this subsection by giving the main theorem related to procedure GROUP. In order
18

to use the theorem outside of this subsection, we recall in the statement the assumptions that were made in
the beginning of this subsection.
Theorem 3.1 Consider a team made of at least (x − 1)(f + 1) + 1 good agents in a graph of size at most
n, where x ≥ f + 2. Let ∆ be the first round when a good agent starts executing GROUP(T , n, bin). If all
good agents start executing GROUP(T , n, bin) by round ∆ + T − 1, and parameter bin is 0 (resp. 1) for at
least one good agent, then we have the following property. After at most a time polynomial in n and T from
∆, at least (x − f ) good agents finish the execution of GROUP at the same round and in the same node.
Proof. When in state Restart, an agent only replays all or part of the waiting periods and edge traversals
made in phase Process. Hence, according to Lemma 3.1 and the initial delay that is at most T , we know that
every good agent finishes the execution of GROUP after at most a time polynomial in n and T from ∆.
So to prove the theorem it remains just to show that there is a group of at least (x − f ) good agents that exit
GROUP on the same node and at the same time. This follows directly from Lemma 3.6 and the claim that is
proven below.
Claim 1 At least x agents meet on the same node at some round t, and among them all the good ones are
executing phase Process of procedure GROUP at round t.
Proof of Claim 1
If f ≥ n, there are always x agents sharing the same node as the number of good agent is at least (f + 1)x.
Moreover, at round ∆ + T every good agent is executing phase process of procedure GROUP. Hence, the
claim holds if f ≥ n.
So let us focus on the case where f < n. From Lemma 3.5, there is a round α when x agents meet in some
node v and there is a good searcher A in state Accept-an-invitation of some step s in round α. At
round α, it remains for agent A at least T rounds to spend in step s. Indeed, in state Follow-up of step s,
an agent has to wait 5T + 5Xn + H − x rounds and x is upperbounded by 4T + 5Xn + H (this is shown
in the proof of Lemma 3.1). Hence, in view of Corollary 3.1, no good agent has finished step s of phase
Process at round α. Moreover, agent A has necessarily spent more than T rounds in step s when in round α.
So, every good agent is executing phase Process of procedure GROUP at round α, which proves the claim.

3.2

Procedure MERGE

The second building block called MERGE takes as input two integers n and T . Subroutine MERGE(T , n)
allows all the good agents to finish their executions of the subroutine in the same node and at the same
round, provided the following two conditions are satisfied. The first condition is that all good agents are
in a graph of size at most n and start executing MERGE(T , n) in an interval lasting at most T rounds. The
second condition is that at least 4f + 2 good agents start executing MERGE(T , n) at the same round and in
the same node. The time complexity of the procedure is polynomial in T and n.

19

3.2.1

High level idea

For the sake of convenience, we will consider in this subsubsection that a group of agents is a set of all
agents, at least one of which is good, that start executing procedure MERGE in the same node and at the
same round. In the sequel, we assume there is a group of at least 4f + 2 good agents. The reasons why we
need such an assumption will appear at the end of the explanations. Let Gmax and vmax be respectively the
group with the largest initial number of agents and its starting node. In case there are several possible groups
Gmax , we choose among them the one having the largest lexicographically ordered list of pairwise distinct
labels denoted by Lmax : this guarantees the unicity of Gmax as it contains at least 4f + 2 good agents. The
cardinality of a list L will be denoted by |L|.
The idea underlying procedure MERGE is to make all good agents elect the same node, and then gather in it
(if we ensure this, then we can ensure that all good agents finish the execution of MERGE at a same round
using some technicalities). Each node is a candidate, and each good agent supports the node in which it
started executing the procedure. Besides supporting its candidate, each good agent is also a voter. When
acting as a supporter, a good agent stays idle to promote its candidate and when acting as a voter, it makes
a traversal of the graph in order to visit all nodes of the graph (using procedure EXPLO(n)), and then elects
one of the nodes using the information provided by the supporters. In order to establish such a strategy, note
that all good agents must not act as voters at the same time. Otherwise, there would be no supporter left in
its candidate node to promote it. Hence, the election process is divided into two parts, and each group is
divided into two subgroups of nearly equal size using the labels of the agents. During the first (resp. second)
part of the election, the first (resp. second) subgroup of each group acts as voters while the second (resp.
first) subgroup of each group acts as supporters.
When visiting a node during its traversal of the graph, a voter gets from each supporter of this node a
promotional information: for a good supporter, it is simply the lexicographically ordered list of all pairwise
distinct labels of the agents that were initially in its group. Once its traversal is done, the voter considers
each node v satisfying the property that at least ⌈ |L|
4 ⌉ distinct agents in v have transmitted a lexicographically
ordered list L. Among these nodes, the voter elects the one for which the property is true with the list L
having the largest cardinality: in case of a tie, the lexicographical order on the labels is used as done to
ensure the unicity of Gmax . By doing so, all good agents elect node vmax and then gather in it: the purpose
of the last paragraph is to explain why we have the guarantee that vmax is unanimously elected.
By definition, the number of good agents that is initially in Gmax , and thus |Lmax | is at least 4f + 2.
Moreover, the number of Byzantine agents is initially at most f in Gmax . Hence, we can show that our
|
strategy permits to always have at least ⌈ |Lmax
⌉ distinct agents in vmax that transmit list Lmax to all voters.
4
Note that each good supporter transmits a list L such that |L| < |Lmax |, or |L| = |Lmax | and L is not
lexicographically larger than Lmax . So, the only way the Byzantine agents could prevent the good agents
′
to elect vmax would be that at least ⌈ |L4 | ⌉ Byzantine agents transmit a list L′ such that |L′ | > |Lmax |, or
|L′ | = |Lmax | and L′ is lexicographically larger than Lmax . However this situation is impossible because
′
the Byzantine agents are not numerous enough: indeed ⌈ |L4 | ⌉ ≥ f + 1.

20

3.2.2

Formal description of the algorithm

When an agent A executes MERGE(T , n), it can transit to different states that are Census, Election
and Synchronisation. When agent A starts the execution of MERGE, it is in state Census. In the
algorithm, the cardinality of a list L will be denoted by |L|.
State Census. Agent A spends a single round in this state. Besides its state, it transmits its label to
the agents sharing the same node. Agent A assigns to variable H, the lexicographically ordered list of all
pairwise distinct labels of agents that are currently in its node and in state Census. Then A transits to
state Election.
State Election. When it enters this state, agent A initializes two variables: it assigns an empty list to
variable I, and 0 to variable π. This state is made of five different periods: the first, third and fifth (resp. the
second and fourth) ones are waiting periods (resp. moving periods). In each round of the two first waiting
periods, agent A transmits the list H built when in state Census. If ℓA belongs to the first ⌊ |H|
2 ⌋ labels of
H, then the durations of the two first waiting periods are respectively T − 1 and T + 2Xn − 1. Otherwise,
they respectively last T + 2Xn − 1 and T − 1 rounds. The duration of the third waiting period is given after
describing the second moving period.
During the first moving period, agent A executes EXPLO(n) followed by a backtrack in which the agent
traverses all edges traversed in EXPLO(n) in the reverse order. Once this backtrack is done, the agent
assigns to variable I the largest list I1 , if any, having the following property: there is a round during the
execution of EXPLO(n) at which agent A is in a node where at least ⌈ |I41 | ⌉ distinct agents in state Election
transmit I1 . (We consider that a list I2 is larger than another list I3 if and only if I2 contains more elements,
or I2 and I3 contain the same number of elements and I2 is lexicographically larger than I3 ). If such a list
I1 exists, the agent also assigns to variable π, the smallest number of edge traversals made by A during the
execution of EXPLO(n) to reach a node satisfying the above property with I1 . Otherwise, the agent leaves
variables I and π unchanged.
During the second moving period, agent A performs the first π edge traversals of EXPLO(n). Once this is
done, agent A checks whether H = I or not. If H = I, then the third waiting period lasts T + Xn − 1
rounds, and at its expiration, A transits to state Synchronisation. Otherwise, the third waiting period
lasts 2T + Xn − 1 but can be interrupted when agent A notices at least ⌈ 3|I|
4 ⌉ agents in state Synchronisation in its node: as soon as such an event occurs, agent A exits the execution of MERGE(T , n). In
case such an interruption does not occur, the agent exits the execution of MERGE(T , n) at the end of the
waiting period.
State Synchronisation. Agent A spends one round in this state and then exits the execution of
MERGE(T , n).
3.2.3

Correctness and complexity analysis

Concerning procedure MERGE, we only have the following theorem.
Theorem 3.2 Consider a team of agents in a graph of size at most n. Let r0 be the first round when a
good agent starts executing MERGE(T , n). If every good agent starts executing MERGE(T , n) by round
21

r0 + T − 1 and among them at least 4f + 2 start the execution in the same node and at the same round,
then all good agents finish their executions of procedure MERGE in the same node and at the same round
r < r0 + 4T + 6Xn − 1.
Proof. Note that according to procedure MERGE, every good agent spends at most 4T + 6Xn − 1 rounds in
any execution of procedure MERGE(T , n). Hence, to prove the theorem we just have to prove that all good
agents finish their executions of procedure MERGE in the same node and at the same round.
Let us denote by H1 the largest list H built by any good agent in state Census, and by A one of the good
agents that builds it. By assumption, they are at least 4f + 2 good agents that start the execution in the
same node and at the same round. As a result, in view of the description of state Census, H1 contains at
least 4f + 2 elements, and agent A belongs to the group of at least 3f + 2 good agents in state Census
that compute the same list H1 at a round r1 in a node v1 . Let us call T1 the group of all the good agents in
state Census in node v1 at round r1 . We prove the following two claims.
Claim 1 The agents of T1 are the only good agents that build list H1 while in state Census.
Proof of Claim 1 Let us assume by contradiction that the claim is false. Hence, there is a good agent B in
state Census which also builds H1 in a node v2 at a round r2 such that v2 6= v1 or r2 6= r1 . In view of the
description of state Census, there are all the labels of the agents of T1 in H1 . Thus, for each good agent of
T1 , there is an agent in state Census with the same label in node v2 at round r2 . However, there are at least
3f + 2 agents in T1 , and since they only spend round r1 in state Census in node v1 , none of them is in this
state in node v2 at round r2 . Besides, all the good agents have different labels and the Byzantine agents are
not numerous enough to be these 3f + 2 agents in state Census in node v2 at round r2 . This contradicts
the existence of these 3f + 2 agents and the assumption that B builds H1 in node v2 at round r2 . Hence, the
claim is proven.
Claim 2 Each good agent starts its third waiting period in node v1
Proof of Claim 2
To prove the claim, we first need to prove the following two facts. The first fact is that in each of the rounds
belonging to {r1 + 1, . . . , r1 + 2T + 4Xn − 2}, there are at least ⌈ |H41 | ⌉ good agents in state Election that
transmit the list H1 in node v1 . The second fact is that each good agent performs entirely its first moving
period between round r1 + 1 and round r1 + 2T + 4Xn − 2.
Let us focus on the first fact. In view of the description of state Census, the list H1 contains at least 3f + 2
elements corresponding to the labels of the agents of T1 , all of which are good, and at most |T1 |+f elements,
|H1 |
|H1 |
1|
with |T1 | the number of agents in T1 . This means that f < ⌈ |H41 | ⌉, |T1 | > ⌈ 3|H
4 ⌉, ⌊ 2 ⌋ − f ≥ ⌈ 4 ⌉
and ⌈ |H21 | ⌉ − f ≥ ⌈ |H41 | ⌉ i.e., in each half of H1 there are at least ⌈ |H41 | ⌉ labels of agents of T1 . This implies
that in each of the rounds belonging to {r1 + T , . . . , r1 + T + 4Xn − 1}, there are at least ⌈ |H41 | ⌉ good
agents in state Election transmitting the list H1 in node v1 . Moreover, in view of the description of
state Election, all the agents of T1 wait in v1 and transmit H1 in each round from round r1 + 1 to round
r1 + T − 1, and from round r1 + T + 4Xn to round r1 + 2T + 4Xn − 2. Hence, the first fact is true.
Let us go further by considering the second fact. Each good agent starts the execution of procedure MERGE
between rounds r0 and r0 +T −1. Then, it spends a single round in state Census, and enters state Election
22

between round r0 + 1 and round r0 + T . Actually, the good agents of T1 are in state Census at round r1 .
This means that r1 belongs to {r0 ; . . . ; r0 + T − 1}. Since every good agent spends at least T − 1 rounds
and at most T + 2Xn − 1 rounds in the first waiting period, every good agent starts its first moving period
between round r0 +T and round r0 +2T +2Xn −1 i.e., between round r1 +1 and round r1 +2T +2Xn −1.
Since the first moving period lasts 2Xn rounds, the second fact is true.
Hence, from the two facts, we know that during its first moving period each good agent visits v1 and notices
at least ⌈ |H41 | ⌉ agents in state Election transmitting the same list H1 . As a result, in view of the description
of state Election each good agent finishes the second moving period at round v1 except if the following
event occurs: there is a list H2 strictly larger than or identical to H1 such that at a round r3 , in a node
v3 6= v1 , at least ⌈ |H42 | ⌉ agents in state Election transmit H2 to a good agent while it is performing the
EXPLO(n) of its first moving period. However, such an event cannot occur. Let us assume by contradiction
it can. Since |H2 | ≥ |H1 | ≥ 4f + 2, among ⌈ |H42 | ⌉ > f agents in state Election transmitting H2 , there
must be at least one good agent which builds H2 in state Census. Note that either H2 is identical to H1 or
it is larger than H1 . If H2 is identical to H1 we get a contradiction with Claim 1. If H2 is larger than H1 ,
we get a contradiction with the maximality of H1 , which concludes the proof of the claim.
In view of Claim 2 and the description of states Census and Election, we know that every good agent
finishes its execution in the same node. Hence, to conclude the proof of the theorem, we just have to
prove now that all good agents finish the execution at the same time. To do this, in view of the fact that
1|
|T1 | ≥ ⌈ 3|H
4 ⌉ and the fact that each good agent assigns to variable I the same list H1 at the end of
its first moving period, it is enough to show that there is a round in which the good agents of T1 are in
state Synchronisation and all the others good agents are performing their third waiting period. It is
the purpose of the following lines.
First assume that no good agent prematurely interrupts its third waiting period before round r1 +3T +5Xn −
2. Since each good agent assigns to variable I the same list H1 , each agent of T1 performs no edge traversal
in the second moving period and enters state Synchronisation at round r1 + 3T + 5Xn − 2. Each good
agent starts its first waiting period between round r1 − T + 2 and round r1 + T . Moreover, it can spend
from 0 to Xn rounds in its second moving period. This implies that each good agent completes it between
round r1 + T + 4Xn − 1 and round r1 + 3T + 5Xn − 3 and starts the third waiting period between round
r1 +T +4Xn and round r1 +3T +5Xn −2. Furthermore, each good agent that does not belong to T1 assigns
to variable I a list that is different from the list it has built when in state Census, and thus its third waiting
period lasts 2T + Xn − 1 rounds. This means that each good agent which does not belong to T1 completes
its third waiting period between round r1 + 3T + 5Xn − 2 and round r1 + 5T + 6Xn − 4. Hence, each good
agent that does not belong to T1 is performing its third waiting period at round r1 + 3T + 5Xn − 2 when the
agents of T1 enter state Synchronisation. As a result, the theorem is true if no good agent prematurely
interrupts its third waiting period before round r1 + 3T + 5Xn − 2. However, no good agent can interrupt its
third waiting period at a round r < r1 + 3T + 5Xn − 2. Indeed, if it was the case, that would imply that there
1|
are at least ⌈ 3|H
4 ⌉ agents in state Synchronisation at round r and among them there is necessarily one
good agent of T1 : this contradicts the fact that the agents of T1 enter state Synchronisation at round
r1 + 3T + 5Xn − 2. This ends the proof of the theorem.


23

4 The positive result
In this section we show an algorithm, called GATHER, that solves f -Byzantine gathering with strong teams
in all graphs of size at most n, assuming that GK = ⌈log log n⌉: note that such a global knowledge can be
coded using O(log log log n) bits. The algorithm works in a time polynomial in n and |lmin |, and it makes
use of the building blocks introduced in the previous section.
In the sequel, we denote by Gn the maximal time complexity of procedure GROUP(Xn, n, ρ) with ρ ∈
{0; 1} in all graphs of size at most n. We also denote by Mn the maximal time complexity of procedure MERGE(Xn + Gn , n) in all graphs of size at most n. Note that according to Theorems 3.1 and 3.2, Gn
and Mn exist and are polynomials in n.
4.1

Intuition

In order to better describe the high level idea of our solution, let us first consider a situation that would be
ideal to solve Byzantine gathering with a strong team and that would be as follows. Instead of assigning
distinct labels to all agents, the adversary assigns to each of them just one bit ρ ∈ {0; 1}, so that there are
at least one good agent for which ρ = 0 and at least one good agent for which ρ = 1. Such a situation
would clearly constitute an infringement of our model, but would allow the simple protocol described in
Algorithm 1 to solve the problem in a time that is polynomial in n when GK = ⌈log log n⌉. Let us briefly
explain why.
Algorithm 1 Algorithm executed by every good agent in the ideal situation.
1: Let ρ be the bit assigned to me by the adversary
2: Execute A(ρ)
3: Declare that gathering is achieved

Algorithm 2 A(ρ) executed by a good agent.
1:
2:
3:
4:

GK

N ← 2(2 )
Execute EXPLO(N )
Execute GROUP(XN , N, ρ)
Execute MERGE(XN + GN , N )

Algorithm 1 consists mainly of a call to A(ρ) that is given by Algorithm 2. Since GK = ⌈log log n⌉, we
know that at line 1 of Algorithm 2, N is a polynomial upperbound on n, and the execution of EXPLO(N )
in a call to A(ρ) by the first woken-up good agent permits to visit every node of the graph and to wake up
all dormant agents. As a result, the delay between the starting times of GROUP(XN , N, ρ) by any two good
agents of the strong team is at most XN . According to the properties of procedure GROUP (cf. Theorem 3.1),
this guarantees in turn that the delay between the starting times of MERGE(XN + GN , N ) by any two good
agents is at most XN + GN , and at least 4f + 2 good agents start this procedure at the same time in the
same node. Hence, in view of the properties of procedure MERGE (cf. Theorem 3.2), all good agents declare
gathering is achieved at the same time in the same node after a polynomial number of rounds (w.r.t n) since
the wake-up time of the earliest good agent.
Unfortunately, we are not in such an ideal situation. At first glance, one might argue that it is not really a
problem because all agents are assigned distinct labels that are, after all, distinct binary strings. Thus, by
24

ensuring that each good agent applies on its label the transformation given in Section 2, and then processes
one by one each bit bi of its transformed label by executing A(bi ), we can guarantee (with some minor
technical adjustments) that the gathering of all good agents is done in time polynomial in n and |lmin |.
Indeed, in view of Proposition 2.1 the conditions of the ideal situation are recreated when the agents process
their j-th bits for some j ≤ 2|lmin | + 4. Unfortunately it is not enough for our purpose. In fact, in the
ideal situation, there is just one bit to process: thus, de facto every good agent knows that every good agent
knows that gathering will be done at the end of this single process. However, it is no longer the case when
the agents have to deal with sequences of bit processes: the good agents have a priori no mean to detect
collectively and simultaneously when they are gathered. It should be noted that if the agents knew f , we
could use an existing algorithmic component (cf. [17]) allowing to solve f -Byzantine gathering if at some
point some good agents detect the presence of a group of at least 2f + 1 agents in the network. Such a group
is necessarily constructed during the sequence of bit processes given above, but again, it cannot be a priori
detected as the agents do not know f or an upperbound on it. Hence, in our goal to optimize the amount
of global knowledge, we need to implement a new strategy to allow the good agents to declare gathering
achieved jointly and simultaneously. It is the purpose of the rest of this subsection.
To get all good agents declare simultaneously the gathering achieved, we want to reach a round in which
every good agent knows that every good agent knows that gathering is done. So, let us return to our sequence
of bit processes. As mentioned above, when a good agent has finished to read the first half of its transformed
label – call such an agent experienced – it has the guarantee that the gathering of all good agents has been
done at least once. Hence, when an experienced agent starts to process the second half of its transformed
label, it actually knows an approximation of the number of good agents with a margin of error of f at the
most. For the sake of convenience, let us consider that an experienced agent knows the exact number µ of
good agents: the general case adds a slight level of complexity that is unnecessary to understand the intuition.
So, each time an experienced agent completes the process of a bit in the second half of its transformed label,
it is in a node containing less than µ agents or at least µ agents. In the first case, the experienced agent is
sure that the gathering is not achieved. In the second case, the experienced agent is in doubt. In our solution,
we build on this doubt. How do we do that? So far, each bit process was just made of one call to procedure
A: now at the end of each bit process, we add a waiting period of some prescribed length, followed by
an extra step that consists in applying A again, but this time according to the following rule. If during the
waiting period it has just done, an agent X was in a node containing, for a sufficiently long period, an agent
pretending to be experienced and in doubt (this agent may be X itself), then agent X is said to be optimistic
and the second step corresponds to the execution of A(0). Otherwise, agent X is said to be pessimistic and
the second step corresponds to the execution of A(1).
If at least one good agent is optimistic within a given second step, then the gathering of all good agents
is done at the end of this step. Indeed, through similar arguments of partition to those used for the ideal
situation, we can show it is the case when at least another agent is pessimistic. However, it is also, more
curiously, the case when there is no pessimistic agents at all. This is due in part to the fact that two good
experienced agents cannot have been in doubt in two distinct nodes during the previous waiting period
(otherwise, we would get a contradiction with the definition of µ). Thus, all good agents start A(0) from at
most f + 1 distinct nodes (as the Byzantine agents can mislead the good agents in at most f distinct nodes
during the waiting period), which implies by the pigeonhole principle that at least 4f + 2 good agents start
it from the same node. Combined with some other technical arguments, we can show that the conditions of
25

Theorem 3.2 are fulfilled when the agents execute MERGE at the end of A(0), thereby guaranteeing again
gathering of all good agents.
As a result, the addition of an extra step to each bit process gives us the following interesting property:
when a good agent is optimistic at the beginning of a second step, at its end the gathering is done and,
more importantly, the optimistic agent knows it because its existence ensures it. Note that, it is a great
progress, but unfortunately it is not yet sufficient, particularly because the pessimistic agents do not have
the same kind of guarantee. The way of remedying this is to repeat once more the same kind of algorithmic
ingredient as above. More precisely, at the end of each second step, we add again a waiting period of some
prescribed length, followed by a third step that consists in applying A in the following manner. If during
the waiting period it has just done, an agent X was in a node containing, for a sufficiently long period, an
agent pretending to be optimistic, then the third step of agent X corresponds to the execution of A(0) and it
becomes optimistic if it was not. Otherwise, the third step of agent X corresponds to the execution of A(1)
and the agent stays pessimistic.
By doing so, we made a significant move forward. To understand why, we want to invite the reader to
reconsider the case when there is at least one good agent that is optimistic at the beginning of a second
step. As we have seen earlier, at the end of this second step, all good agents are necessarily gathered and
every optimistic agent knows it. In view of the last changes made to our solution, when starting the third
step, every good agent is then optimistic. As explained above the absence of pessimistic good agent is very
helpful, and using here the same arguments, we are sure that when finishing the third step, all good agents are
gathered and every good agent knows it because all of them are optimistic. Actually, it is even a little more
subtle: the optimistic agents of the first generation (i.e., those that were already optimistic when starting
the second step) know that the gathering is done and know that every good agent knows it. Concerning the
optimistic agents of the second generation (i.e., those that became optimistic only when starting the third
step), they just know that the gathering is done, but do not know whether the other agents know it or not.
Recall that to get all good agents declare simultaneously the gathering achieved, we want to reach a round
in which every good agent knows that every good agent knows that gathering is done. We are very close to
such a consensus. To reach it, at the end of a third step, the optimistic agents of the first generation make
themselves known to all agents. Note that if there were at least f + 1 agents declaring to be optimistic agents
of the first generation and if f was part of GK, the consensus would be reached. Indeed, among the agents
declaring to be optimistic of the first generation, at least one is necessarily good and every agent can notice
it: at this point we can show that every good agent knows that every good agent knows that gathering is
done.
However, the agents do not know f . That being said, at the end of a third step, note that an optimistic
agent knowing that the gathering is done can compute an approximation f˜ of the number of Byzantine
agents. More precisely, if the number of agents gathered in its node is p, the optimistic agent knows than the
number of Byzantine agents cannot exceed f˜ = max{y|(5y +1)(y +1)+1 ≤ p} according to the definition
of a strong team. Based on this fact, we are saved. Indeed, our algorithm is designed in such a way that all
good agents correctly declare the gathering is achieved in the same round after having computed the same
approximation f˜ and noticed at least f˜ + 1 agents that claim being optimistic of the first generation during
a third step. We show that such an event necessarily occurs before any agent finishes the (4|lmin | + 8)-th
bit process of its transformed label, which permits to obtain the promised polynomial complexity. This is

26

where our feat of strength is: obtaining such a complexity with a small amount of global knowledge, while
ensuring that the Byzantine agents cannot confuse the good agents in any way. Actually, our algorithm
is judiciously orchestrated so that the only thing Byzantine agents can really do is just to accelerate the
resolution of the problem.
4.2

Formal description

Algorithm 3 gives the formal description of procedure GATHER. As mentioned at the beginning of this
section, we assume that GK = ⌈log log n⌉. Procedure GATHER uses the two building blocks GROUP and
MERGE described in the previous section. It also uses two small subroutines, LEARN and CHECK-GATHERING,
which are described after Algorithm 3. Both these subroutines do not have any input parameters, but when
executing them, the agent can access to the current value of every variable defined in Algorithm 3. Hence
the variables defined in Algorithm 3 can be viewed as variables of global scope.
Algorithm 3 Procedure GATHER executed by an agent A with label ℓA .
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:

GK

N ← 2(2 )
Let ℓ∗A = b∗1 . . . b∗|ℓ∗ |
A
// Recall that ℓ∗A is the transformed label of agent A (refer to Section 2)
γ←1
i←1
Execute EXPLO(N )
while i ≤ 3|ℓ∗A | do
if i mod 3 = 1 then
ω←0
ρ ← b∗(i div 3)+1
end if
Execute GROUP(XN , N, ρ)
Execute MERGE(XN + GN , N )
Execute LEARN()
Let (ρ, γ) be the value returned by LEARN()
if ρ = 0 then
ω =ω+1
end if
if i mod 3 = 0 then
Execute CHECK-GATHERING()
Let flag be the boolean value returned by CHECK-GATHERING()
if flag=TRUE then
Declare that gathering is achieved
end if
end if
Let r be the time elapsed since the beginning of the execution of this procedure
Wait XN + i(3XN + 4(GN + MN ) + 2) − r rounds
i←i+1
end while

When presenting the high level idea of our solution in the previous subsection, we used some qualifiers like
“experienced and in doubt”, “optimistic of the second generation” or “optimistic of the first generation”.
These qualifiers were only used to help the reader understand the essence of our solution and they do not
appear explicitely in the formal description. To ease the transition from the high level idea, just note that
these qualifiers are reflected in the values 1, 2 or 3 of variable ω. For example, an optimistic agent of the
27

first generation corresponds to an agent for which ω = 3.
Now we give the formal descriptions of the subroutines LEARN and CHECK-GATHERING. Let us begin by
subroutine LEARN.
Subroutine LEARN()
When executing this subroutine, an agent A can transit to different states that are Learning, Optimist
and Pessimist. The initial state is Learning. During an execution of this procedure, A never moves.
Let us denote by v the node occupied by the agent while executing this subroutine and by TN the value
XN + GN + MN .
State Learning. Agent A spends one round in this state. Let x be the maximum number of agents in
state Learning (including itself) that A notices at this round in node v. Let z be max(γ, x). The agent
A transits either to state Optimist or to state Pessimist. It transits to state Optimist if ω 6= 0, or
2i > 3|ℓ∗A | and x ≥ z − max{y|(5y + 1)(y + 1) + 1 ≤ z}. Otherwise, it transits to state Pessimist.
State Optimist. Agent A waits 3TN rounds in this state. At the end of this waiting period, the agent exits
the execution of LEARN(): the returned value of the subroutine is then the couple (0, z).
State Pessimist. Agent A waits 3TN rounds in this state. At the end of the waiting period, the agent
exits the execution of LEARN() and returns a couple, the value of which is as follows. If during the waiting
period, agent A notices 2TN consecutive rounds such that in each of them there is at least one agent in
state Optimist in node v, then the returned value is (0, z). Otherwise the returned value is (1, z).
Now, let us describe the second subroutine CHECK-GATHERING().
Subroutine CHECK-GATHERING()
Agent A waits a single round and then exists the execution of CHECK-GATHERING(). During this round,
agent A transmits the value of its variable ω, and the word “Check-gathering” in order to indicate that it is
executing the same named subroutine. Let us denote by p the number of agents in its current node during
the single round of the execution. If the value of the variable ω of A belongs to {2; 3}, and there are more
than max{y|(5y + 1)(y + 1) + 1 ≤ p} distinct agents transmitting 3 and “Check-gathering”, the subroutine
returns TRUE. Otherwise, the subroutine returns FALSE.
4.3

Proof and analysis

In this subsection, we prove the correctness and the polynomiality of Algorithm GATHER to solve f Byzantine gathering with strong teams in all graphs of size at most n, assuming that GK = ⌈log log n⌉.
We start with the following proposition.
Proposition 4.1 Let p be a positive integer. If within a team of p agents, there are g ≥ (5f + 1)(f + 1) + 1
good agents and at most f Byzantine agents, then we have f ≤ max{y|(5y + 1)(y + 1) + 1 ≤ p} < g.
Proof. First of all, f ≤ max{y|(5y + 1)(y + 1) + 1 ≤ p} follows from the fact that p ≥ (5f + 1)(f + 1) + 1.
Then, let us assume by contradiction that max{y|(5y + 1)(y + 1) + 1 ≤ p} ≥ g. This implies that
(5g + 1)(g + 1) + 1 ≤ p. However, 2g < (5g + 1)(g + 1) + 1 and p ≤ g + f < 2g. By transitivity, we get
2g < 2g. This is a contradiction, which completes the proof.

28

The executions of all the subroutines and building blocks that are mentioned in the following statements and
their proofs always occur during an execution of procedure GATHER(⌈log log n⌉) by an agent in a graph
of size at most n. Hence, for ease of reading, we omit to mention it. Before going further, we give some
notations that are used in the statement of the next lemma and its proof. For any good agent A, we denote
by rA,i the round (if any) at which A starts its i-th execution of procedure GROUP. We also denote by ti the
first round (if any) at which there is at least one good agent that starts its i-th execution of procedure GROUP.
GK
Finally, according to line 1 of Algorithm 3, N is the value 2(2 ) .
Lemma 4.1 Let A be a good agent. For any positive integer i, rA,i+1 = rA,i + 3XN + 4GN + 4MN + 2,
and every good agent that starts its i-th execution of GROUP does it at round ti + XN − 1 at the latest.
Proof. Since EXPLO(N ) allows to visit every node of the graph, once the first awoken good agent has
completed its first execution of EXPLO(N ) at the beginning of Algorithm GATHER, each good agent is
awoken and has at least started its first execution of EXPLO(N ). Every good agent spends exactly XN
rounds executing it, and then starts its first execution of procedure GROUP. Hence, every good agent starts
its first execution of procedure GROUP in some interval of XN rounds, between rounds t1 and t1 + XN − 1.
We now consider the routines a good agent executes between the beginnings of any two consecutive executions of GROUP. Let us show that their execution lasts at most 3XN + 4GN + 4MN + 2 rounds. Any
good agent spends at most GN rounds executing GROUP(XN , N, bin) for any bin ∈ {0; 1}, at most MN
rounds executing MERGE(XN + GN , N ), exactly 3TN + 1 rounds executing LEARN(), and exactly 1 round
executing CHECK-GATHERING(). The sum of these amounts of rounds is 2 + 3TN + MN + GN .
In view of line 27 of Algorithm 3 and since each agent spends exactly XN rounds executing the initial
EXPLO(N ), for any positive integer i and any good agent A, the above sum is exactly the amount of rounds
between rA,i and rA,i+1 . Hence, any good agent spends exactly 4MN + 4GN + 3XN + 2 rounds between
the beginnings of any two consecutive executions of procedure GROUP, which completes the proof.


Proposition 4.2 Consider a round r at which two good agents A and B execute the same routine R from
the set {GROUP; LEARN; MERGE; CHECK-GATHERING}. If A is executing its i-th execution of R at round
r, then B is also executing its i-th execution of R at round r.
Proof. Let us assume by contradiction that there exists some round r1 at which two good agents A and B
are respectively executing their i-th and j-th execution of a same routine R from the set {GROUP; LEARN;
MERGE; CHECK-GATHERING} with i < j. In view of Lemma 4.1, we know that (rB,j − rB,i ) ≥ 3XN +
4GN + 4MN + 2. Thus (r1 − rB,i ) ≥ 3XN + 4GN + 4MN + 2. However, if R is GROUP or MERGE, we
know that (r1 − rA,i ) ≤ GN + MN . Hence, (rA,i − rB,i ) > XN , which contradicts Lemma 4.1.
Hence, R must be LEARN or CHECK-GATHERING. In either case, in view of Algorithm 3, between rB,j
and r1 , B must have executed GROUP and MERGE. Executing these routines requires a minimal number a
rounds which is strictly larger than XN . This means that, (r1 − rB,i ) ≥ 4XN + 4GN + 4MN + 3. On the
other hand, (r1 − rA,i ) ≤ 3XN + 4GN + 4MN + 2 rounds. Hence, (rA,i − rB,i ) > XN , which contradicts
again Lemma 4.1.

29

By Lemma 4.1 and lines 12-13 of Algorithm 3, we know that all good agents that start their i-th execution
of MERGE(XN + GN , N ) for a given positive integer i, do it in an interval lasting at most the number of
rounds given as first parameter of MERGE. Hence, in view of Theorem 3.1, Theorem 3.2, and Lemma 4.1,
we have the following corollary.
Corollary 4.1 Assume that for a given positive integer i, there is a group of at least (5f + 1)(f + 1) + 1
good agents that start (at possibly different nodes or rounds) their i-th executions of GROUP(XN , N, ρ) with
ρ = 0 for at least one good agent and ρ = 1 for at least one other good agent. There exist a node v1 and a
round r1 such that each good agent in the graph that completes its i-th execution of MERGE does it at round
r1 in node v1 .
Before proving Theorem 4.1 that is the main result of this section, we still need to prove the following series
of four lemmas.
Lemma 4.2 Assume that for a given positive integer i, there are at least 5f + 2 good agents that start (at
possibly different rounds) their i-th executions of GROUP(XN , N, ρ) in the same node v1 with ρ = 0. There
exist a round r2 and a node v2 such that each good agent in the graph that completes its i-th execution of
procedure MERGE does it at round r2 in node v2 .
Proof. Assume that there exist an integer i and a node v1 such that a group T1 of at least 5f + 2 good agents
all start their i-th executions of GROUP(XN , N, ρ) in the same node v1 with ρ = 0. In view of Lemma 4.1,
every good agent that starts its i-th execution of GROUP, does it between rounds ti and ti + XN − 1. In
view of the description of GROUP, at the beginning of its execution of GROUP(XN , N, 0), every good agent,
which is called a follower, first enters state Invite and spends strictly more than XN rounds waiting in this
state. Hence, there is at least one round at which each good agent of T1 is waiting in state Invite in node
v1 during the first phase of its i-th execution of GROUP. Thus, by Lemma 3.6, at least 4f +2 good agents exit
their i-th execution of GROUP at the same round and in the same node. This means that at least 4f + 2 good
agents start their i-th execution of MERGE(XN + GN , N ) at the same round and in the same node. Besides,
each good agent spends at most GN rounds in any execution of GROUP which means that each good agent
that completes its i-th execution of GROUP does it between round ti and round ti + GN + XN − 1. Hence,
in view of Theorem 3.2, there exist a round r2 and a node v2 such that each good agent that completes its
i-th execution of MERGE(XN + GN , N ) does it at r2 in v2 .


Lemma 4.3 Assume that g ≥ (5f + 1)(f + 1) + 1 good agents start (at possibly different nodes or rounds)
their (3j + 1)-th execution of subroutine GROUP, for a given integer j. Let k ≤ 3 be the smallest positive integer, if any, such that the (3j + k)-th execution of procedure LEARN by at least one good agent
returns a couple whose the first element is 0. There exists a node v1 such that each good agent that enters
state Optimist during its (3j + k)-th execution of LEARN, does it in v1 .
Proof. Let us assume by contradiction that two good agents A and B both enter state Optimist during
their (3j + k)-th executions of LEARN but from different nodes, respectively vA and vB . To conduct this
30

proof, we need to explain what the entrance of these good agents in state Optimist implies. Note that
during their (3j + k)-th executions of LEARN, both agents have the same value for variable i i.e., (3j + k).
In view of lines 8-9 of Algorithm 3, when a good agent starts its (3j + 1)-th execution of GROUP, the
value of its variable ω is 0. Since ω is only incremented on line 17, when the first element of the pair
returned by LEARN is 0, we know by definition of k that at the beginning of their (3j + k)-th executions of
LEARN, the value of ω for both A and B is still 0. Thus, in view of the description of procedure LEARN,
2(3j + k) > 3|ℓ∗A | (resp. 2(3j + k) > 3|ℓ∗B |) and while in state Learning, A (resp. B) notices at least
zA − max{yA |(5yA + 1)(yA + 1) + 1 ≤ zA } (resp. zB − max{yB |(5yB + 1)(yB + 1) + 1 ≤ zB }) agents in
state Learning in its node, where |ℓ∗A | (resp. |ℓ∗B |) denotes the length of the transformed label of A (resp.
B) as defined in Algorithm 3 and zA (resp. zB ) denotes the value of z that is used in state Learning by
agent A (resp. B).
We now explain what 2(3j + k) > 3|ℓ∗A | and 2(3j + k) > 3|ℓ∗B | imply. By Proposition 2.1, it means that
there exists a positive integer s ≤ j such that the s-th bits in the transformed labels of A and B are different.
In view of Algorithm 3, this means that for their (3s − 2)-th executions of GROUP, one of them executes
GROUP(XN , N, 0) while the other one executes GROUP(XN , N, 1). Hence, in view of Corollary 4.1, there
exist a node v3 and a round r3 such that each good agent that completes its (3s − 2)-th execution of MERGE,
does it in v3 at round r3 . This means that each good agent that starts its (3s − 2)-th execution of LEARN,
and thus enters state Learning, does it in v3 at round r3 + 1. By assumption, these good agents are at
least g ≥ (5f + 1)(f + 1) + 1 and among them, there are A and B. This means that the number of agents
in state Learning that A (resp. B) notices during its (3s − 2)-th execution of LEARN, and thus zA (resp.
zB ) is at least g.
Let us now give the consequences of the fact that A (resp. B) notices at least zA − max{yA |(5yA + 1)(yA +
1) + 1 ≤ zA } (resp. zB − max{yB |(5yB + 1)(yB + 1) + 1 ≤ zB }) agents in state Learning while in
the same state during its (3j + k)-th execution of LEARN. In view of Proposition 4.1, both max{yA |(5yA +
1)(yA +1)+1 ≤ zA } and max{yB |(5yB +1)(yB +1)+1 ≤ zB } are at least f . Let us assume without loss of
generality that zB −max{yB |(5yB +1)(yB +1)+1 ≤ zB } is at least zA −max{yA |(5yA +1)(yA +1)+1 ≤
zA }. Hence, the sum of the numbers of agents in state Learning noticed by A or B while in the same state
during their (3j +k)-th execution of LEARN is at least 2(zA −max{yA |(5yA +1)(yA +1)+1 ≤ zA }) i.e., at
least g+zA −2max{yA |(5yA +1)(yA +1)+1 ≤ zA }. Besides, zA −2max{yA |(5yA +1)(yA +1)+1 ≤ zA }
is greater than 2max{yA |(5yA + 1)(yA + 1) + 1 ≤ zA } ≥ 2f . This means that the total number q of agents
in state Learning noticed by A or B while in the same state during their (3j + k)-th executions of LEARN
is greater than g + 2f . However, this is impossible as explained in the next paragraph.
In view of Proposition 4.2, when A or B starts its (3j + k)-th execution of LEARN, each good agent in
state Learning is also starting its (3j+k)-th execution of LEARN. No good agent can be in state Learning
during its (3j + k)-th execution of LEARN both in vA and in vB , which means that among the q > g + 2f
agents noticed by A or B, at most g are good. However, in every round, there are at most f Byzantine agents
in vA or vB . Hence, q cannot be greater than g + 2f : this leads to a contradiction that proves the theorem.

Lemma 4.4 Let i and j two integers such that j ∈ {1; 2}. Assume that at least (5f + 1)(f + 1) + 1 good
agents start (at possibly different nodes or rounds) their (3i + 1)-th executions of subroutine GROUP. If
31

the (3i + j)-th execution of subroutine LEARN by at least one good agent returns a couple whose the first
element is 0, then for every integer j < k ≤ 3, there exist a round r and a node v such that every (3i + k)-th
execution of LEARN by any good agent finishes at round r in node v and returns a pair whose first element
is 0.
Proof. To prove this lemma, it is enough to show that for all integers i and j such that j ∈ {1; 2}, if at least
(5f + 1)(f + 1) + 1 good agents start (at possibly different nodes or rounds) their (3i + 1)-th executions of
GROUP, and the (3i + j)-th execution of subroutine LEARN by at least one good agent A returns a couple
whose the first element is 0, then we have the following property: there exist a round r and a node v such
every (3i + j + 1)-th execution of LEARN by any good agent finishes in node v at round r, and returns a
couple whose the first element is 0.
We consider three cases. In the first case, j = 1. In the second case, j = 2 and there is no good agent whose
(3i + 1)-th execution of LEARN returns a couple in which the first element is 0. In the third case, j = 2 and
there is at least one good agent B (not necessarily different from A) whose (3i + 1)-th execution of LEARN
returns a couple in which the first element is 0.
Let us consider the first case. We first prove that all the good agents which complete their (3i + 2)-th
execution of MERGE do it at the same round, and in the same node. In view Algorithm 3, during the (3i+ 2)th execution of GROUP(XN , N, ρ) by agent A we have ρ = 0. So, if there exists a good agent that uses 1
for parameter ρ during its (3i + 2)-th execution of GROUP(XN , N, ρ), then in view of Corollary 4.1, all the
good agents that complete their (3i + 2)-th executions of MERGE do it at the same round and in the same
node. The situation, in which each good agent that starts its (3i + 2)-th execution of GROUP(XN , N, ρ)
uses ρ = 0, is a little trikier to analyse. In this situation, in view of Algorithm 3, this means that every
(3i + 1)-th execution of LEARN by any good agent C returns a couple whose first element is 0. Thus,
during this execution agent C either enters state Optimist, or while in state Pessimist it notices at
least one agent in state Optimist for at least 2TN consecutive rounds. Moreover, in view of Lemma 4.1
and the definitions of values GN and MN , every good agent that starts its (3i + 1)-th execution of LEARN,
does it between rounds t3i+j and t3i+j + GN + MN + XN − 1 = t3i+j + TN − 1 (TN is defined in the
description of LEARN). According to the description of state Learning (resp. state Pessimist), every
good agent that enters (resp. exits) state Pessimist, does it between rounds t3i+j + 1 and t3i+j + TN
(resp. t3i+j + 3TN and t3i+j + 4TN − 1). Hence, there are at most 4TN − 1 rounds at which at least one
good agent is in state Pessimist during its (3i + 1)-th execution of LEARN. This implies there is at least
one round r1 that overlaps all the intervals of 2TN rounds noticed by the good agents in state Pessimist,
and such that in round r1 each good agent in state Pessimist is in the same node as at least one agent in
state Optimist. By Lemma 4.3, there is at most one node where good agents can enter state Optimist
during their (3i + 1)-th executions of LEARN. This implies that there are at most f + 1 nodes in the graph
from which any good agent can exit state Learning during its (3i + 1)-th execution of LEARN. Since
by assumption at least (5f + 1)(f + 1) + 1 good agents execute their (3i + 1)-th executions of LEARN,
we have the following: there exists at least one node v1 such that at least 5f + 2 good agents are in v1
during their (3i + 1)-th executions of LEARN as well as at the beginning of their (3i + 2)-th executions of
GROUP(XN , N, ρ). Recall that these good agents all use 0 as value for parameter ρ during their (3i + 2)-th
executions of GROUP(XN , N, ρ). Hence, by Lemma 4.2 it follows that all the good agents that complete
their (3i + 2)-th executions of MERGE do it at the same round and in the same node.
32

So, in the first case, we know that all the good agents that complete their (3i + 2)-th executions of MERGE
do it at the same round and in the same node. Now, we show that these agents all complete at the same round
and in the same node their (3i + 2)-th executions of LEARN that returns a couple whose the first element is
0. In view of the description of LEARN, these good agents do not move and spend exactly 3TN + 1 rounds
during their (3i+2)-th executions of LEARN. Hence, they enter and exit state Learning at the same round,
and complete their (3i + 2)-th executions of LEARN at the same round and in the same node. Moreover,
since the (3i + 1)-th execution of subroutine LEARN by agent A returns a couple whose the first element is
0, we know that during its (3i + 2)-th of subroutine LEARN, the value of its variable ω is different from 0
and it enters state Optimist. Hence, each good agent that enters state Pessimist during its (3i + 2)-th
execution of LEARN notices agent A in state Optimist during 3TN ≥ 2TN consecutive rounds. As a
result, there exist a round r and a node v such that every (3i + 2)-th execution of LEARN by any good agent
finishes in node v at round r, and returns a couple whose the first element is 0.
Using similar arguments to those used in the first case, we can show in the second case that there exist a
round and a node in which every (3i + 3)-th execution of LEARN by any good agent finishes and returns a
couple whose the first element is 0.
Let us now consider the third case i.e., j = 2 and there is at least one good agent B whose (3i + 1)-th
execution of LEARN returns a couple in which the first element is 0. Using similar arguments to those used
in the first case, we can show that, there exist a round and a node in which every (3i + 2)-th execution of
LEARN by any good agent finishes and returns a couple whose first element is 0. All these good agents start
their (3i + 3)-th executions of GROUP(XN , N, ρ) from the same node with ρ = 0. In view of Lemma 4.2,
this implies that there exist a round r2 and a node v2 such that every (3i + 3)-th executions of MERGE by
any good agent finishes in node v2 at round r2 . Moreover, since every (3i + 2)-th execution of LEARN of
any good agent C returns a couple whose the first element is 0, during its (3i + 3)-th execution of LEARN,
agent C enters state Optimist: this execution of LEARN by agent C lasts exactly 3TN + 1 rounds during
which it does not move from v2 . Hence, the (3i + 3)-th execution of LEARN of agent C returns a couple
whose the first element is 0 at round r2 + 3TN + 1, which completes the proof.

Lemma 4.5 Assume there is a group G of at least (5f + 1)(f + 1) + 1 good agents executing Algorithm GATHER at a round r1 . If at least one agent of G declares that gathering is achieved at round r1 in a
node v1 , then all agents of G declare that gathering is achieved at r1 in v1 .
Proof. By assumption, there is at least one good agent A that declares that gathering is achieved at r1 .
Let i1 be the value of the variable i of agent A at round r1 . In view of Algorithm 3, it declares that
gathering is achieved after executing subroutine CHECK-GATHERING, and there exists an integer i2 such
that i1 = (3i2 + 3).
In view of subroutine CHECK-GATHERING, since A declares gathering achieved at round r1 , the value of
its variable ω is either 2 or 3. In view of Algorithm 3, this means that there are either two or three executions
of LEARN, out of the three since the beginning of the (3i2 + 1)-th execution of GROUP by agent A, which
have returned a couple whose the first element is 0. In view of Lemma 4.4, this means that there exist a
round r2 and a node v1 such that each agent of G completes at r2 in v1 its (3i2 + 3)-th execution of LEARN,
the returned value of which is a couple whose the first element is 0.
33

Consider the set of the values of variable ω of every good agent of G at the end of its (3i2 + 3)-th execution
of LEARN, and denote by ω1 the maximum one. Since at the end of the (3i2 + 3)-th execution of LEARN by
agent A, the variable ω of A is either 2 or 3, we know that ω1 ∈ {2; 3}. Lemma 4.4 implies that at the end
of the (3i2 + 3)-th execution of LEARN by every good agent B of G (including A), the variable ω of B is
either ω1 or ω1 − 1.
Each agent of G starts its (i2 + 1)-th execution of subroutine CHECK-GATHERING at r2 + 1 in v1 . According to the description of this subroutine and Algorithm 3, agent A declares that gathering is achieved
at round r1 because at the previous round, while executing CHECK-GATHERING, it notices strictly more
than max{y|(5y + 1)(y + 1) + 1 ≤ p} distinct agents executing the same procedure and transmitting 3.
Thus, the round at which all the agents of G execute CHECK-GATHERING() in v1 is r1 − 1. Since at least
(5f + 1)(f + 1) + 1 good agents are in the same node, by Proposition 4.1, we know that at least one good
agent transmits 3 at round r1 − 1. In view of the fact that the integer transmitted by any good agent executing
CHECK-GATHERING() is the value of its variable ω, we know that ω1 is 3 and the value of variable ω of
each agent of G is either 2 or 3. This means the execution of CHECK-GATHERING() of every good agent
of G returns TRUE at round r1 − 1 in v1 , and every good agent of G declares that gathering is achieved at
round r1 with agent A, which completes this proof.

We are now ready to prove the final result of this section. Recall that a strong team is a team in which the
number of good agents is at least 5f 2 + 6f + 2. As the reader would have noticed, a good agent can execute
several iterations of the while loop of Algorithm 3 (cf. lines 7 to 29): given a good agent A, we will say that
the i-th iteration of this while loop by agent A is of order i.
Theorem 4.1 Assuming that GK = ⌈log log n⌉, Algorithm GATHER solves f -Byzantine gathering with
every strong team in all graph of size at most n, and has a time complexity that is polynomial in n and
|lmin |.
Proof. Let r be the first round in which a good agent finishes the execution of Algorithm GATHER. Since,
the adversary wakes up at least one good agent, we know that round r exists. Since GK = ⌈log log n⌉, we
GK
know that N = 2(2 ) is at least n, and thus according to line 6 of Algorithm 3, all the good agents are
executing Algorithm GATHER at round r. As a result, in view of Lemma 4.5, we just have to prove the
following two properties to state that the theorem holds. The first property is that there exists at least one
good agent that declares gathering is achieved at round r (note that although we will show in the sequel
that it is impossible, we cannot rule out for now the possibility that an agent might finish the execution of
Algorithm GATHER without declaring gathering is achieved). The second property is that at round r, the
first woken-up agent (or one of the first, if there are several such agents) has spent a time that is at most
polynomial in n and |lmin | to execute Algorithm GATHER.
Let us first focus on the first property and consider the good agent A with the smallest label lmin . Let
∗ |. In view of Algorithm 3, each good agent executes at least α iterations of the while loop of
α = 3|lmin
Algorithm 3, unless it declares that gathering is achieved before. We consider two cases: either there is at
least one good agent B that never starts executing its α-th iteration of the while loop, or every good agent
start executing at some point its α-th iteration of the while loop.
34

Concerning the first case, assume without loss of generality that B is the first agent that stops executing
Algorithm GATHER before starting its α-th iteration of the while loop. According to Lemma 4.1, the time
spent executing an iteration is the same regardless of the executing good agent and the order of the iteration,
and this time is greater than the difference between the rounds at which any two good agents start iterations
of the same order. Hence, when agent B stops executing Algorithm GATHER, no good agent has completed
its α-th iteration of the while loop. This implies that agent B finishes its execution of Algorithm GATHER at
round r. Moreover, the fact that B stops executing Algorithm GATHER before starting its α-th iteration of
the while loop, implies that B declares the gathering is achieved at round r: this proves that the first property
holds in the first case.
Let us move on to the second case. In view of Proposition 2.1, for any given good agent C different from
∗ |, |l∗ | < 2j ≤ 2|l∗ | and the i-th (resp.
A, there exist two positive integers i and j such that 2i ≤ |lmin
min
min
j-th) bits in the transformed labels of A and C are different. Hence, at round r, each good agent has at least
started executing its α-th iteration of the while loop, and thus has completed its (3i − 2)-th iteration and at
least started its (3j − 2)-th iteration.
Moreover, in view of Algorithm 3, for its (3i − 2)-th (resp. (3j − 2)-th) execution of GROUP(XN , N, ρ),
agent A uses for parameter ρ a value belonging to {0; 1} that is different of that used by agent C (which
also belongs to {0; 1}) during its (3i − 2)-th (resp. (3j − 2)-th) execution of GROUP(XN , N, ρ). By
Corollary 4.1, there exist a round ri and a node vi (resp. rj and vj ) such that each good agent completes
its (3i − 2)-th (resp. (3j − 2)-th) execution of MERGE at ri in vi (resp. at rj in vj ). At round ri + 1, each
good agent enters state Learning in node vi . Thus, at this point the value of variable γ of each good
agent is at least the number of good agents and at most the total number of agents. Since there are at least
(5f + 1)(f + 1) + 1 good agents, in view of Proposition 4.1, max{y|(5y + 1)(y + 1) + 1 ≤ γ} is at least
f , and γ − max{y|(5y + 1)(y + 1) + 1 ≤ γ} is at most the number of good agents.
∗ |. This means that during its (3j − 2)-th
Furthermore, the length of the transformed label of A is |lmin
execution of LEARN, at round rj + 2, while all good agents are in vj , agent A enters state Optimist. At
the same round, every other good agent is also in vj entering either state Optimist or state Pessimist.
Whichever the state, they spend 3TN rounds in it so that all the good agents in state Pessimist notice
agent A in state Optimist during at least 2TN rounds. As a result, every good agent finishes its (3j −2)-th
execution of LEARN that returns a pair whose first element is 0. From Lemma 4.4, it follows that there exist
a round r1 and a node v1 such that each good agent completes its 3j-th execution of subroutine LEARN at r1
in v1 , and the value of variable ω of each good agent at round r1 is 3. From round r1 + 1 on, each good agent
starts its j-th execution of CHECK-GATHERING. When executing this procedure, each of them transmits
the word “Check-gathering” and the value 3 of its variable ω. In view of Proposition 4.1, there are strictly
more than max{y|(5y + 1)(y + 1) + 1 ≤ p} good agents. Hence, agent A as well as all good agents return
TRUE, and thus declare that gathering is achieved at round r = r1 + 2 in node v1 which proves that the first
property holds in the second case as well.

We now show the second property. According to the two cases analyzed above, the good agents declare that
the gathering is achieved at round r before any of them starts its iteration of the while loop of order α + 1:
∗ | and |l∗ | = 4|l
the value α is polynomial in |lmin | since α = 3|lmin
min | + 8. Besides, the number of
min
rounds required to execute any iteration of the while loop is bounded by 4(XN + GN + MN + 1) in view of
Lemma 4.1. Note that in view of the definitions of XN , GN and MN , 4(XN + GN + MN + 1) is polynomial
35

⌈log log n⌉

) (cf. line 1 of Algorithm 3). Hence, the total number of rounds spent
in N , and thus in n as N = 2(2
by any good agent before round r is bounded by 12(4|lmin |+ 8)(XN + GN + MN + 1), which is polynomial
in n and |lmin |. This concludes the proof of the second property, and by extension, of the theorem.



5 The negative result
Algorithm GATHER introduced in the previous section uses the value ⌈log log n⌉ as global knowledge, which
can be coded with a binary string of size O(log log log n). In this section, we show that, to solve Byzantine
gathering with strong teams, in all graph of size at most n, in a time polynomial in n and |lmin |, the order
of magnitude of the size of knowledge used by our algorithm GATHER is optimal. More precisely, we have
the following theorem.
Theorem 5.1 There is no algorithm solving f -Byzantine gathering with strong teams for all f and in all
graphs of size at most n, which is polynomial in n and |lmin | and which uses a global knowledge of size
o(log log log n).
Proof. Suppose by contradiction that the theorem is false. Hence, there exists an algorithm Alg that solves
f -Byzantine gathering with strong teams for all f in all graphs of size at most n, which is polynomial in n
and |lmin | and which uses a global knowledge of size o(log log log n). The proof relies on the construction
of a family Fn (for any n ≥ 4) of initial instances with strong teams such that for each of them the graph size
is at most n. Our goal is to prove that there is an instance from Fn for which algorithm Alg needs a global
knowledge whose size does not belong to o(log log log n), which would be a contradiction with the definition
of Alg. Let us first present the construction of an infinite sequence of instances I = I0 , I1 , I2 , . . . , Ii , . . .
by induction on i. Instance I0 consists of an oriented ring of 4 nodes (i.e., a ring in which at each node the
edge going clockwise has port number 0 and the edge going anti-clockwise has port 1). In this ring, there is
no Byzantine agent but there are two good agents labeled 0 and 1 that are placed in diametrically opposed
nodes. All the agents in I0 wake up at the same time.
Now let us describe the construction of instance Ii with i ≥ 1 using some features of instance Ii−1 . Let c
be the smallest constant integer such that the time complexity of algorithm Alg is at most nc from every
instance made of a graph of size at most n with a strong team in which |lmin | = 1. Let µi−1 and ni−1 be
respectively the total number of agents in Ii−1 and the number of nodes in the graph of Ii−1 . Instance Ii
consists of an oriented ring of (ni−1 )4c nodes. In this ring an agent labeled 0 is placed on a node denoted by
v0 . In each of both nodes that are adjacent to v0 , (ni−1 )c ∗ µi−1 Byzantine agents are placed (which gives a
total of 2 ∗ (ni−1 )c ∗ µi−1 Byzantine agents). On the node that is diametrically opposed to v0 , enough good
agents are placed in order to have a strong team. The way of assigning labels to all agents that are not at v0
is arbitrary but respects the condition that initially no two agents share the same label. Finally, all the agents
in Ii wake up at the same time. This closes the description of the construction of I, for which we have the
following claim.
Claim 1 For any two instances Ij and Ij ′ of I, algorithm Alg requires a distinct global knowledge.
36

Proof of Claim 1
Assume by contradiction that the claim does not hold for two instances Ij and Ij ′ such that j < j ′ . Consider
any execution EXj of algorithm Alg from Ij . According to the construction of I, we know that every
agent is woken up at the first round of EXj . We denote by r1 , r2 , . . . , rk the sequence of consecutive
rounds from the first round of EXj to the round when all good agents declare that gathering is done. We
also denote by Gi the group of agents (possibly empty) that are with the good agent labeled 0 at round ri
of EXj . Now, using execution EXj , let us describe a possible execution EXj ′ of algorithm Alg from Ij ′ :
this execution is designed in such a way that it will fool the good agent labeled 0 and will induce it into
premature termination. According to the construction of I, all the agents of Ij ′ are woken up in the first
round of Ij ′ and all the good ones are executing algorithm Alg. In the first round of EXj ′ the agent labeled
0 is alone (as in the first round of EXj ). Then, for each i ∈ 2, . . . , k, the good agent labeled 0 in EXj ′
meets a group of |Gi | Byzantine agents whose the multiset of labels is exactly the same as the multiset of
labels belonging to the agents of Gi in the ith round of EXj . This is always possible in view of the fact that
for each i ∈ 1, . . . , k, |Gi | ≤ µj and the Byzantine agents of Ij ′ can choose to move by ensuring that in the
ith round of EXj ′ it remains at least (k − i) ∗ µj Byzantine agents in the node adjacent to the one occupied
by the agent labeled 0 in the clockwise direction (resp. anti-clockwise direction): indeed according to the
construction of Ij ′ , in each of both nodes adjacent to the starting node of the good agent labeled 0, there
are initially (nj ′ −1 )c ∗ µj ′ −1 ≥ k ∗ µj ′ −1 Byzantine agents, as k ≤ (nj )c ≤ (nj ′ −1 )c . Finally, if algorithm
Alg prescribes some message exchange between agents during their meetings, then the Byzantine agents
in execution EXj ′ give exactly the same information to 0, as the agents with respective labels in execution
EXj . Hence, from the point of view of agent 0, the first k rounds of EXj look exactly identical to the first
k rounds of EXj ′ . This is due to the actions of Byzantine agents, the fact that all nodes in Ij and Ij ′ look
identical, and also because k ≤ (nj )c which implies that, regardless of the algorithm Alg, the agent labeled
0 cannot meet any good agent in the first k rounds of EXj ′ as the distance between agent 0 and any other
(n

′

)4c

(n )4c

good agent is initially at least j −1
≥ j2 . Therefore, in the kth round of execution EXj ′ , the good
2
agent labeled 0 declares having met all good agents and stops, which is incorrect, since it has not met any
good agent. This contradicts the definition of algorithm Alg and closes the proof of this claim.
Now, consider the largest x such that in each of the x + 1 first instances I0 , I1 , . . . , Ix of I, the graph size
is at most n: these x + 1 instances constitute family Fn . In view of the construction of sequence I and the
x
x+1
definition of x, we have 4((4c) ) ≤ n < 4((4c) ) . Hence, x belongs to Ω(log log n). However, according
to Claim 1, the global knowledge given to distinct instances in this family must be different. Hence, there
is at least one instance of Fn for which algorithm Alg uses a global knowledge of size Ω(log x): since
x ∈ Ω(log log n), we have Ω(log x) ∈ Ω(log log log n). This contradicts the fact that Alg uses a global
knowledge of size o(log log log n) and proves the theorem.


6 Conclusion
In this paper, we designed the first polynomial algorithm w.r.t n and |lmin | allowing to gather all good agents
in presence of Byzantine ones that can act in an unpredictable way and lie about their labels. Our algorithm
works under the assumption that the team evolving in the network is strong i.e., the number of good agents
is roughly at least quadratic in the number f of Byzantine agents. The required global knowledge GK is of
37

size O(log log log n), which is of optimal order of magnitude to get a time complexity that is polynomial in
n and |lmin | even with strong teams.
A natural open question that immediately comes to mind is to ask if we can do the same by reducing the
ratio between the good agents and the Byzantine agents. For example, could it be still possible to solve the
problem in polynomial time with a global knowledge of size O(log log log n) if the number of good agents
is at most o(f 2 )? Note that the answer to this question may be negative but then may become positive with a
little bit more global knowledge. Actually, we can even easily show that the answer is true if the agents are
initially given a complete map of the graph with all port numbers, and in which each node v is associated to
the list of all labels of the good agents initially occupying node v. However, the size of GK is then huge as
it belongs to Ω(n2 ). In fact, in this case what is really interesting is to find the optimal size for GK. This
observation allows us to conclude with the following open problem that is more general and appealing.
What are the trade-offs among the ratio good/Byzantine agents, the time complexity and the amount of
global knowledge to solve f -Byzantine gathering?
Bringing an exhaustive and complete answer to this question appears to be really challenging but would turn
out to be a major step in our understanding of the problem.

References
[1] Serge Abiteboul, Haim Kaplan, and Tova Milo. Compact labeling schemes for ancestor queries. In
Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, January 7-9, 2001, Washington,
DC, USA., pages 547–556, 2001.
[2] Noa Agmon and David Peleg. Fault-tolerant gathering algorithms for autonomous mobile robots.
SIAM J. Comput., 36(1):56–82, 2006.
[3] Steve Alpern. Rendezvous search: A personal perspective. Operations Research, 50(5):772–795,
2002.
[4] Steve Alpern. The theory of search games and rendezvous. International Series in Operations Research
and Management Science, Kluwer Academic Publishers, 2003.
[5] Evangelos Bampas, Jurek Czyzowicz, Leszek Gasieniec, David Ilcinkas, and Arnaud Labourel. Almost optimal asynchronous rendezvous in infinite multidimensional grids. In Distributed Computing,
24th International Symposium, DISC 2010, Cambridge, MA, USA, September 13-15, 2010. Proceedings, pages 297–311, 2010.
[6] Michael Barborak and Miroslaw Malek. The consensus problem in fault-tolerant computing. ACM
Comput. Surv., 25(2):171–220, 1993.
[7] Sébastien Bouchard, Yoann Dieudonné, and Bertrand Ducourthial. Byzantine gathering in networks.
Distributed Computing, 29(6):435–457, 2016.
[8] Mark Cieliebak, Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro. Distributed computing by
mobile robots: Gathering. SIAM J. Comput., 41(4):829–879, 2012.

38

[9] Reuven Cohen, Pierre Fraigniaud, David Ilcinkas, Amos Korman, and David Peleg. Label-guided
graph exploration by a finite automaton. ACM Trans. Algorithms, 4(4):42:1–42:18, 2008.
[10] Andrew Collins, Jurek Czyzowicz, Leszek Gasieniec, and Arnaud Labourel. Tell me where I am so
I can meet you sooner. In Automata, Languages and Programming, 37th International Colloquium,
ICALP 2010, Bordeaux, France, July 6-10, 2010, Proceedings, Part II, pages 502–514, 2010.
[11] Jurek Czyzowicz, Konstantinos Georgiou, Evangelos Kranakis, Danny Krizanc, Lata Narayanan,
Jaroslav Opatrny, and Sunil M. Shende. Search on a line by byzantine robots. In 27th International
Symposium on Algorithms and Computation, ISAAC 2016, December 12-14, 2016, Sydney, Australia,
pages 27:1–27:12, 2016.
[12] Jurek Czyzowicz, Adrian Kosowski, and Andrzej Pelc. How to meet when you forget: log-space
rendezvous in arbitrary graphs. Distributed Computing, 25(2):165–178, 2012.
[13] Jurek Czyzowicz, Andrzej Pelc, and Arnaud Labourel. How to meet asynchronously (almost) everywhere. ACM Transactions on Algorithms, 8(4):37, 2012.
[14] Shantanu Das, Dariusz Dereniowski, Adrian Kosowski, and Przemyslaw Uznanski. Rendezvous of
distance-aware mobile agents in unknown graphs. In Structural Information and Communication
Complexity - 21st International Colloquium, SIROCCO 2014, Takayama, Japan, July 23-25, 2014.
Proceedings, pages 295–310, 2014.
[15] Xavier Défago, Maria Gradinariu, Stéphane Messika, and Philippe Raipin Parvédy. Fault-tolerant and
self-stabilizing mobile robots gathering. In Distributed Computing, 20th International Symposium,
DISC 2006, Stockholm, Sweden, September 18-20, 2006, Proceedings, pages 46–60, 2006.
[16] Anders Dessmark, Pierre Fraigniaud, Dariusz R. Kowalski, and Andrzej Pelc. Deterministic rendezvous in graphs. Algorithmica, 46(1):69–96, 2006.
[17] Yoann Dieudonné, Andrzej Pelc, and David Peleg. Gathering despite mischief. ACM Transactions on
Algorithms, 11(1):1, 2014.
[18] Yoann Dieudonné, Andrzej Pelc, and Vincent Villain. How to meet asynchronously at polynomial
cost. SIAM J. Comput., 44(3):844–867, 2015.
[19] Pierre Fraigniaud, Cyril Gavoille, David Ilcinkas, and Andrzej Pelc. Distributed computing with advice: information sensitivity of graph coloring. Distributed Computing, 21(6):395–403, 2009.
[20] Pierre Fraigniaud, David Ilcinkas, and Andrzej Pelc. Tree exploration with advice. Inf. Comput.,
206(11):1276–1287, 2008.
[21] Pierre Fraigniaud and Andrzej Pelc. Deterministic rendezvous in trees with little memory. In Distributed Computing, 22nd International Symposium, DISC 2008, Arcachon, France, September 22-24,
2008. Proceedings, pages 242–256, 2008.
[22] Pierre Fraigniaud and Andrzej Pelc. Delays induce an exponential memory gap for rendezvous in trees.
ACM Transactions on Algorithms, 9(2):17, 2013.
39

[23] Samuel Guilbault and Andrzej Pelc. Gathering asynchronous oblivious agents with local vision in
regular bipartite graphs. Theor. Comput. Sci., 509:86–96, 2013.
[24] Taisuke Izumi, Samia Souissi, Yoshiaki Katayama, Nobuhiro Inuzuka, Xavier Défago, Koichi Wada,
and Masafumi Yamashita. The gathering problem for two oblivious robots with unreliable compasses.
SIAM J. Comput., 41(1):26–46, 2012.
[25] Michal Katz, Nir A. Katz, Amos Korman, and David Peleg. Labeling schemes for flow and connectivity. SIAM J. Comput., 34(1):23–40, 2004.
[26] Dariusz R. Kowalski and Adam Malinowski. How to meet in anonymous network. Theor. Comput.
Sci., 399(1-2):141–156, 2008.
[27] Evangelos Kranakis, Danny Krizanc, Euripides Markou, Aris Pagourtzis, and Felipe Ramı́rez. Different speeds suffice for rendezvous of two agents on arbitrary graphs. In SOFSEM 2017: Theory
and Practice of Computer Science - 43rd International Conference on Current Trends in Theory and
Practice of Computer Science, Limerick, Ireland, January 16-20, 2017, Proceedings, pages 79–90,
2017.
[28] Evangelos Kranakis, Danny Krizanc, and Sergio Rajsbaum. Mobile agent rendezvous: A survey. In
Structural Information and Communication Complexity, 13th International Colloquium, SIROCCO
2006, Chester, UK, July 2-5, 2006, Proceedings, pages 1–9, 2006.
[29] Nancy A. Lynch. Distributed Algorithms. Morgan Kaufmann, 1996.
[30] Gianluca De Marco, Luisa Gargano, Evangelos Kranakis, Danny Krizanc, Andrzej Pelc, and Ugo
Vaccaro. Asynchronous deterministic rendezvous in graphs. Theor. Comput. Sci., 355(3):315–326,
2006.
[31] Avery Miller and Andrzej Pelc. Fast rendezvous with advice. Theor. Comput. Sci., 608:190–198, 2015.
[32] Avery Miller and Andrzej Pelc. Time versus cost tradeoffs for deterministic rendezvous in networks.
Distributed Computing, 29(1):51–64, 2016.
[33] Nicolas Nisse and David Soguet. Graph searching with advice. Theor. Comput. Sci., 410(14):1307–
1318, 2009.
[34] Marshall C. Pease, Robert E. Shostak, and Leslie Lamport. Reaching agreement in the presence of
faults. J. ACM, 27(2):228–234, 1980.
[35] Omer Reingold. Undirected connectivity in log-space. J. ACM, 55(4), 2008.
[36] Thomas Schelling. The Strategy of Conflict. Oxford University Press, Oxford, 1960.
[37] Amnon Ta-Shma and Uri Zwick. Deterministic rendezvous, treasure hunts, and strongly universal
exploration sequences. ACM Transactions on Algorithms, 10(3):12, 2014.
[38] Mikkel Thorup and Uri Zwick. Approximate distance oracles. J. ACM, 52(1):1–24, 2005.

40

