Project Topics
Get Complete Project Material File(s) Now! »
State of the Art for Deterministic Rendezvous in Networks Modeled as Finite Graphs
For deterministic rendezvous in networks modeled as graphs [94], attention concentrates on the study of the feasibility of rendezvous, and on the time required to achieve this task, when feasible. This task has been considered in the literature under two alternative scenarios: weak and strong. Under the weak scenario [43, 52, 86], agents may meet either at a node or inside an edge. Under the strong scenario [48, 77, 98], they have to meet at a node, and they do not even notice meetings inside an edge. Each of these scenarios is appropriate in different applications. The weak scenario is suitable for physical robots in a network of corridors, while the strong scenario is needed for software agents in computer networks.
Rendezvous algorithms under the strong scenario are known for synchronous agents, where time is slotted in rounds, and in each round each agent can either wait at a node or move to an adjacent node. Thus, in synchronous settings, the strong scenario is implicitly considered. One of earliest algorithms for rendezvous in synchronous settings [48] guarantees a meeting of the two involved agents after a number of rounds that is polynomial in the size n of the graph, the length |`min| of the shortest of the two labels and the time interval θ between their wake-up times. As an open problem, the authors asked whether it was possible to obtain a polynomial algorithm to this task which would be independent of θ. A positive answer to this question was given independently in two articles [77, 98]. To do so, one of them [98] explicitly builds upon a treasure hunt algorithm.
While these algorithms ensure rendezvous in polynomial duration (i.e., a polynomial number of rounds), they also ensure it at polynomial cost because the cost of a rendezvous protocol in a graph is the number of edges traversed by the agents until they meet and each agent can make at most one edge traversal per round. Note that despite the fact a polynomial duration implies a polynomial cost in this context, the reciprocal is not always true as the agents can have very long waiting periods, sometimes interrupted by a movement. Thus these parameters of cost and time are not always linked to each other. This was highlighted in [89] where the authors studied the trade-offs between cost and time for the deterministic rendezvous task.
More recently, some efforts have been dedicated to analyze the impact on time complexity of rendezvous when in every round the agents are provided some pieces of information by making a query to some device or some oracle [45, 88]. Along with the work aiming at optimizing the parameters of duration and/or cost of rendezvous, some other work have examined the amount of memory required to achieve the task in trees [63, 64] and arbitrary finite graphs [42]. The task has been approached in a fault-prone framework [33], in which the adversary can delay an agent for a finite number of rounds, each time it wants to traverse an edge of the network. Furthermore, some articles assume that the agents are equipped with tokens used to mark nodes [16, 79].
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 asynchronous settings, each agent decides to which neighbor it wants to move but the adversary totally controls the walk of each agent and can arbitrarily vary its speed.
The scenario of possibly different fixed speeds of the agents is considered in several articles [78] and in this scenario, only weak rendezvous is ensured. However, it is not known whether strong rendezvous is possible in these settings.
Several authors investigated asynchronous rendezvous in network environments [43, 52, 86]. Under this assumption, rendezvous under the strong scenario cannot be guaranteed even in very simple graphs, and hence the rendezvous requirement is weakened by considering the scenario called weak in the present thesis. In the earliest study of this task [86], the authors investigated the cost of rendezvous for both infinite and finite graphs. In the former case, the graph is reduced to the (infinite) line and bounds are given depending on whether the agents know the initial distance between them or not. In the latter case (finite graphs), similar bounds are given for ring shaped networks. They also proposed a rendezvous algorithm for arbitrary graphs provided the agents initially know an upper bound on the size of the graph. This assumption was subsequently removed [43]. However, in these studies, the cost of rendezvous was exponential in the size of the graph. A third article [52] presented the first rendezvous algorithm working for arbitrary finite connected graphs at cost polynomial in the size of the graph and in the length of the shortest label.
State of the Art for Gathering in Networks Modeled as Graphs
Rendezvous is much more studied than gathering. This is partly due to the fact that gathering can be obtained thanks to a rendezvous algorithm by applying the “stick together” strategy as described in Section 1.1.3.3. However, the task of gathering has been studied when sticking together is not that easy.
This is the case when the agents are anonymous [50]. However, in this case, as explained in Section 1.1.3.2, there are initial positions of the agents which are not gatherable i.e., from which no deterministic algorithm can achieve gathering due to symmetry. The authors characterize the gatherable positions and provided two gathering algorithms for every gatherable position.
More precisely, the characterization of gatherable positions relies on the notion of view of a node v in the graph G. Intuitively, this is the view that an agent at v would have if it looked at the whole graph from v . More formally, it is a infinite tree rooted at v and such that the children of any node u in the tree are all its neighbors in G but its father in the tree. This notion well captures symmetry in graphs since two nodes having different views can be thought as not symmetrical.
Apart from this interesting characterization, the two algorithms show an interesting trade-off. The first algorithm relies on the knowledge by every agent of a polynomial upper bound on the number of nodes in the graph and ensures detection of termination. On the contrary, the authors show that no algorithm can ensure gathering with detection of termination without this information and their second algorithm does not require any additional information but does not detect termination. The agents eventually stop but do not know whether there are other agents.
Another case in which the “stick together” strategy cannot be easily applied occurs when some of the agents are Byzantine i.e., prone to Byzantine faults. First introduced at the beginning of the 80s [93], 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 agents are fixed nodes of the graph [14, 85].
When some agents are Byzantine, gathering all agents, including the Byzantine ones, can not be ensured because the Byzantine agents may never be with the other agents, called good, or may declare that the gathering is achieved at any time. Thus, the task known as Byzantine gathering is considered instead. It consists in gathering all good agents, and having them all declare that the gathering is achieved, in the presence of f Byzantine agents.
The latter task is introduced [51] via the following question: what is the minimum number M of good agents that guarantees Byzantine gathering in all graphs of size n? 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 in which Byzantine agents can lie about their identities. For the relaxed variant, it is proved that the minimum number M of good agents that guarantees Byzantine gathering is precisely 1 when the each agent knows both n and f and f + 2 when each agent knows 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. The authors also give, for the harsher form of 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 each agent knows both n and f (resp. when it knows f only). Both these algorithms have a huge complexity as they are exponential in n and `max, where `max is the largest label of a good agent evolving in the graph.
Some advances are subsequently made [23], via the design of two algorithms, one for each case, that work with a number of good agents that perfectly matches the lower bounds of f + 1 and f + 2 shown in the first article. However, these algorithms also suffer from a complexity that is exponential in n and `max.
State of the Art for Rendezvous and Gathering in the Plane
A good starting point for presenting the state of art of rendezvous and gathering in the plane is paradoxically the article [43] which shows that asynchronous rendezvous (bringing two asynchronous agents at the exact same point) in the plane is impossible. This leads the authors to introducing the task of approximate rendezvous (also known as approach), which considers two agents with some constant range of vision and consists in bringing them not to the same position but within each other’s range. This article also provides the first algorithm ensuring asynchronous approach of two agents in the plane. To provide the latter, the authors discretize the plane into an infinite graph: the task of approach is reduced to that of rendezvous in an infinite graph. Unfortunately, the cost of their algorithm is super-exponential.
The rest of the state of art in the plane can be viewed as successive attempts to improve on this result. The same reduction to asynchronous rendezvous in infinite graphs such as the infinite grid i.e., the infinite graph in which each node has degree 4, is used. However, no algorithm achieving approach, with a cost polynomial in the initial distance Δ between the agents and the length of the smallest label, in asynchronous settings, without providing additional information to the agents, has been proposed yet.
A first article restricts asynchrony to a model in which each agent is given a constant speed at which it travels during the whole execution [49]. It is also worth mentioning an algorithm whose cost is polynomial in Δ but which relies on the assumption that the agents are location aware [13, 40]: each agent knows the coordinates of its initial position in some common coordinate system. This hypothesis enables the authors not only to reach polynomiality but also a fine-grained complexity since their cost belongs to O(Δ2 log(Δ)).
Another Model: Look-Compute-Move Robots
The previous section focuses on the literature which, because it addresses the gathering task in a similar model, is the closest to this thesis. However, mobile distributed systems have been considered in other models and other tasks have been studied. A comprehensive book about mobile distributed systems, the various model variants in which they are considered, the results in gathering and several other tasks appeared shortly before the writing of this thesis [59]. The authors are among the leading figures of this area of research. The model which is the most investigated both in the latter book, and in literature is called Look-Compute-Move robots [58, 100].
In this model, the execution of its algorithm by each robot can be viewed as a cycle of three phases namely Look, Compute and Move. During the first one, the robot observes its environment, taking a snapshot. Then, it executes its algorithm to compute its next position. Lastly, it moves to the chosen location. Even though this three phases cycle does not really differ from the model described in this thesis and can be viewed as a low level description of the execution of their algorithm by the mobile agents assumed in this thesis, it is often associated with a set of abilities different from the one considered in this thesis. More precisely, these Look-Compute-Move robots are often assumed to be anonymous i.e., have no kind of identifier and oblivious i.e., forget previous observations and computations, but to take snapshots of the whole environment, including the positions of the others. In such a context locality refers to the possibly different coordinate systems the robots have. Some agreement is often reached thanks to geometric properties of the set of positions, independent from the local coordinate systems such as the smallest enclosing circle [31].
Since the introduction of this model [100], pattern formation in the plane has been the most studied task in these settings [36, 58, 103]. The input for this task is common to all robots: the pattern to draw. The task is considered completed whenever the robots have reached positions whose relative positions are the same as those of the points in the input pattern, regardless of enlargements, rotations. . .
Failing to give as much insight about the literature on Look-Compute-Move robots as the recent book [59], this section aims at giving pointers to some of the reasearch directions of the state of the art related to the gathering of Look-Compute-Move robots. The synchronous gathering of robots has been addressed assuming the occurrence of several kinds of faults (crash, Byzantine faults, and self-stabilization) [2, 46, 53]. Asynchronous rendezvous and gathering of robots have been considered both in graphs [44, 67] and in the plane [37]. Another article [69] studies the impact of the differences between the coordinate systems of the robots (somehow the impact of locality) on the feasibility of gathering in synchronous and asynchronous settings. Several other studies of the latter case investigate different sets of assumptions including inaccuracy in perception and movement [39], restricted visibility [60], occurrence of faults [2, 41, 46], or pay attention to avoiding collisions [91]. In the Look-Compute-Move model, since robots take snapshots of the whole system, the set of positions of the agents can be viewed as a memory in which they write by moving and read with these snapshots. This in particular permits to establish an equivalence between gathering in a variant of the Look-Compute-Move model, and consensus between processes sharing memory [4]. The latter task is the most studied in distributed systems. Each process is given a binary input and they have to agree in finite time on one of the inputs.
The Environment of the Mobile Agents
This section is dedicated to defining the elements which compose any environment in which the mobile agents move and interact, and stating some of the environments considered in this thesis. The main definitions of this section are those of environment and model variant, in Section 2.1.3. They rely on the definitions of timeline and space defined in Sections 2.1.1 and 2.1.2, respectively.
Execution of an Algorithm by a Distributed System of Mobile Agents
Two kinds of elements are needed to define the execution of an algorithm by mobile agents. On one hand, there are the theatre stage, the actors, and the play i.e., the environment, the mobile agents, and the algorithm they execute. On the other hand, there are the deterministic rules governing the effects of the instructions of the algorithm on the environment and the mobile agents. Given the environment, the algorithm, and these rules, it is possible to determine the state of the system at any time.
This section starts with the formal definition of the execution of an algorithm by mobile agents. However, this definition only includes the elements of the first kinds.
The set of rules depends in particular on the environment considered. Sections 2.2.1 and 2.2.2 describe the rules which apply in the environment described by Definition 2.11. Even though other chapters derive the present model, and change some of these rules, the environments considered are always based on those of Definition 2.11, and most of the rules keep applying in the other chapters. The nature of the changes is specified in the corresponding chapters.
Precisely, Section 2.2.1 focuses on the rules determining the initial state of the mobile agents. Section 2.2.2 lists the abilities of the mobile agents and states the rules which apply whenever an agent is instructed to use them (e.g., input and effects). Definition 2.13 (Execution of an algorithm by mobile agents). An execution is a couple (e, A) such that:
• e is an environment.
• A is a mobile agent algorithm.
Remark that “execution” is thus used to designate both the local execution by one mobile agent of the sequence of instructions which compose the algorithm, and a more global view of the system composed of mobile agents all locally executing the algorithm). When using this word, it is made clear from the context which meaning it is given.
Table of contents :
1 Introduction
1.1 Context and State of the Art
1.1.1 Distributed Systems
1.1.2 Related Research Fields
1.1.3 The Tasks and Model Considered throughout this Thesis
1.1.4 Another Model: Look-Compute-Move Robots
1.2 Contributions
2 Model
2.1 The Environment of the Mobile Agents
2.1.1 Modeling Time
2.1.2 Modeling Space
2.1.3 Defining the Whole Environment
2.2 Execution of an Algorithm by a Distributed System of Mobile Agents
2.2.1 Initialization
2.2.2 Progress of the Execution: Abilities of the Mobile Agents
2.3 Tasks Specifications and Efficiency of an Algorithm
2.4 Notations
3 Strong Rendezvous in Finite Graphs
3.1 Introduction
3.1.1 Related Work
3.1.2 Contribution
3.1.3 Roadmap
3.2 Preliminaries
3.3 The Algorithm and its Analysis
3.4 Discussion of Alternative Scenarios
3.5 Conclusion
4 Asynchronous Approach in the Plane
4.1 Introduction
4.1.1 Related Work
4.1.2 Model and Reduction from Asynchronous Approach in the Plane to Weak Rendezvous in the Infinite Grid
4.1.3 Contribution
4.1.4 Roadmap
4.2 Preliminaries
4.3 Idea of the Algorithm
4.3.1 Informal Description in a Nutshell
4.3.2 Under the Hood
4.4 Basic Patterns
4.4.1 Pattern Seed
4.4.2 Pattern RepeatSeed
4.4.3 Pattern Berry
4.4.4 Pattern CloudBerry
4.5 Main Algorithm
4.6 Proof of Correctness and Cost Analysis
4.6.1 Properties of the Basic Patterns
4.6.2 Agents Synchronizations
4.6.3 Correctness of Procedure AsyncGridRV
4.6.4 Cost Analysis
4.7 Conclusion
5 Byzantine Gathering in Finite Graphs
5.1 Introduction
5.1.1 Introduction and Related Work
5.1.2 Model
5.1.3 Contribution
5.1.4 Roadmap
5.2 Preliminaries
5.3 Building Blocks
5.3.1 Procedure Group
5.3.2 Procedure Merge
5.4 The Positive Result
5.4.1 Intuition
5.4.2 Formal Description
5.4.3 Proof and Analysis
5.5 The Negative Result
5.6 Conclusion
6 Treasure Hunt in the Plane with Angular Hints
6.1 Introduction
6.1.1 Model and Task Formulation
6.1.2 Contribution
6.2 Preliminaries
6.3 Angles at most
6.3.1 High Level Idea of the Algorithm
6.3.2 Algorithm and Analysis
6.4 Angles Bounded by < 2
6.4.1 High Level Idea
6.4.2 Algorithm and Analysis
6.5 Arbitrary Angles
6.6 Conclusion
7 Conclusion of the Thesis
7.1 Sum up of the Main Parts
7.2 Perspectives of the Thesis
Bibliography
