A team of mobile agents, starting from distinct nodes of a network modeled as an undirected graph, have to meet at the same node and simultaneously declare that they all met. Agents execute the same algorithm, which they start when activated by an adversary or when an agent enter their initial node. While executing their algorithm, agents move from node to node by traversing edges of the network in synchronous rounds. Their perceptions and interactions are always strictly local: they have no visibility beyond their current node and can communicate only with agents occupying the same node. This task, known as gathering, is one of the most fundamental problems in distributed mobile systems. Over the past decades, numerous gathering algorithms have been designed, with a particular focus on minimizing their time complexity, i.e., the worst-case number of rounds between the start of the earliest agent and the completion of the task. To solve gathering deterministically, a common widespread assumption is that each agent initially has an integer ID, called label, only known to itself and that is distinct from those of all other agents. Labels play a crucial role in breaking possible symmetries, which, when left unresolved, may make gathering impossible. But must all labels be pairwise distinct to guarantee deterministic gathering?

A mobile agent, starting from a node $s$ of a simple undirected connected graph $G=(V,E)$, has to explore all nodes and edges of $G$ using the minimum number of edge traversals. To do so, the agent uses a deterministic algorithm that allows it to gain information on $G$ as it traverses its edges. During its exploration, the agent must always respect the constraint of knowing a path of length at most $D$ to go back to node $s$. The upper bound $D$ is fixed as being equal to $(1+α)r$, where $r$ is the eccentricity of node $s$ (i.e., the maximum distance from $s$ to any other node) and $α$ is any positive real constant. This task has been introduced by Duncan et al. [ACM Trans. Algorithms 2006] and is known as \emph{distance-constrained exploration}. The \emph{penalty} of an exploration algorithm running in $G$ is the number of edge traversals made by the agent in excess of $|E|$. Panaite and Pelc [J. Algorithms 1999] gave an algorithm for solving exploration without any constraint on the moves that is guaranteed to work in every graph $G$ with a (small) penalty in $\mathcal{O}(|V|)$. Hence, a natural question is whether we could obtain a distance-constrained exploration algorithm with the same guarantee as well. In this paper, we provide a negative answer to this question. We also observe that an algorithm working in every graph $G$ with a linear penalty in $|V|$ cannot be obtained for the task of \emph{fuel-constrained exploration}, another variant studied in the literature. This solves an open problem posed by Duncan et al. [ACM Trans. Algorithms 2006] and shows a fundamental separation with the task of exploration without constraint on the moves.

A team of mobile agents, starting from different nodes of an unknown network, possibly at different times, have to meet at the same node and declare that they have all met. Agents have different labels which are positive integers, and move in synchronous rounds along links of the network. The above task is known as gathering and was traditionally considered under the assumption that when some agents are at the same node then they can talk, i.e., exchange currently available information. In this paper we ask the question of whether this ability of talking is needed for gathering. The answer turns out to be no.

A mobile agent navigating along edges of a simple connected unweighted graph, either finite or countably infinite, has to find an inert target (treasure) hidden in one of the nodes. This task is known as treasure hunt. The agent has no a priori knowledge of the graph, of the location of the treasure, or of the initial distance to it. The cost of a treasure hunt algorithm is the worst-case number of edge traversals performed by the agent until finding the treasure. Awerbuch et al. [ 3 ] considered graph exploration and treasure hunt for finite graphs in a restricted model where the agent has a fuel tank that can be replenished only at the starting node s . The size of the tank is B = 2 (1+α) r , for some positive real constant α, where r , called the radius of the graph, is the maximum distance from s to any other node. The tank of size B allows the agent to make at most ⌊ B ⌋ edge traversals between two consecutive visits at node s . Let e(d) be the number of edges whose at least one endpoint is at distance less than d from s . Awerbuch et al. [ 3 ] conjectured that it is impossible to find a treasure hidden in a node at distance at most d at cost nearly linear in e(d) . We first design a deterministic treasure hunt algorithm working in the model without any restrictions on the moves of the agent at cost 𝒪(e(d) log d ) and then show how to modify this algorithm to work in the model from Awerbuch et al. [ 3 ] with the same complexity. Thus, we refute the preceding 20-year-old conjecture. We observe that no treasure hunt algorithm can beat cost Θ ( e(d) ) for all graphs, and thus our algorithms are also almost optimal.

Gathering is a key task in distributed and mobile systems, which becomes significantly harder if some agents are subject to Byzantine faults, known as being the worst ones. We propose here to study the task of Byzantine gathering in an arbitrary graph: despite the presence of Byzantine agents, the goal is to ensure that all the other (good) agents, executing the same algorithm, eventually meet at the same node and stop. Initially, each agent gets as input a different label and some global knowledge that is common to all agents. The agents move in synchronous rounds and communicate with each other only when located at the same node. There are f Byzantine agents. These agents act in an unpredictable way, e.g., they may convey arbitrary informations or forge any label. In the literature, the gathering algorithms working in such a context all have an exponential time complexity in the number n of nodes and the labels of the good agents. In this paper, we design a deterministic algorithm to solve Byzantine gathering in time polynomial in n and the logarithm $$\ell $$ of the smallest label of a good agent, provided the agents are a strong team i.e., a team where the number of good agents is at least some quadratic polynomial in f. Our algorithm requires global knowledge that can be coded in $$O(\log \log \log n)$$ bits: we prove this size is of optimal order of magnitude to obtain a polynomial time complexity in n and $$\ell $$ with strong teams.

A mobile agent navigating along edges of a simple connected graph, either finite or countably infinite, has to find an inert target (treasure) hidden in one of the nodes. This task is known as treasure hunt. The agent has no a priori knowledge of the graph, of the location of the treasure or of the initial distance to it. The cost of a treasure hunt algorithm is the worst-case number of edge traversals performed by the agent until finding the treasure. Awerbuch, Betke, Rivest and Singh [3] considered graph exploration and treasure hunt for finite graphs in a restricted model where the agent has a fuel tank that can be replenished only at the starting node $s$. The size of the tank is $B=2(1+α)r$, for some positive real constant $α$, where $r$, called the radius of the graph, is the maximum distance from $s$ to any other node. The tank of size $B$ allows the agent to make at most $\lfloor B\rfloor$ edge traversals between two consecutive visits at node $s$. Let $e(d)$ be the number of edges whose at least one extremity is at distance less than $d$ from $s$. Awerbuch, Betke, Rivest and Singh [3] conjectured that it is impossible to find a treasure hidden in a node at distance at most $d$ at cost nearly linear in $e(d)$. We first design a deterministic treasure hunt algorithm working in the model without any restrictions on the moves of the agent at cost $\mathcal{O}(e(d) \log d)$, and then show how to modify this algorithm to work in the model from [3] with the same complexity. Thus we refute the above twenty-year-old conjecture. We observe that no treasure hunt algorithm can beat cost $Θ(e(d))$ for all graphs and thus our algorithms are also almost optimal.

Two mobile agents represented by points freely moving in the plane and starting at two different positions, have to meet. The meeting, called rendezvous, occurs when agents are at distance at most r of each other and never move after this time, where r is a positive real unknown to them, called the visibility radius. Agents are anonymous and execute the same deterministic algorithm. Each agent has a set of private attributes, some or all of which can differ between agents. These attributes are: the initial position of the agent, its system of coordinates (orientation and chirality), the rate of its clock, its speed when it moves, and the time of its wake-up. If all attributes (except the initial positions) are identical and agents start at distance larger than r then they can never meet, as the distance between them can never change. However, differences between attributes make it sometimes possible to break the symmetry and accomplish rendezvous. Such instances of the rendezvous problem (formalized as lists of attributes), are called feasible.

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

A mobile agent equipped with a compass and a measure of length has to find an inert treasure in the Euclidean plane. Both the agent and the treasure are modeled as points. In the beginning, the agent is at a distance at most D>0 from the treasure, but knows neither the distance nor any bound on it. Finding the treasure means getting at distance at most 1 from it. The agent makes a series of moves. Each of them consists in moving straight in a chosen direction at a chosen distance. In the beginning and after each move the agent gets a hint consisting of a positive angle smaller than 2 pi whose vertex is at the current position of the agent and within which the treasure is contained. We investigate the problem of how these hints permit the agent to lower the cost of finding the treasure, using a deterministic algorithm, where the cost is the worst-case total length of the agent's trajectory. It is well known that without any hint the optimal (worst case) cost is Theta(D^2). We show that if all angles given as hints are at most pi, then the cost can be lowered to O(D), which is optimal. If all angles are at most beta, where beta<2 pi is a constant unknown to the agent, then the cost is at most O(D^{2-epsilon}), for some epsilon>0. For both these positive results we present deterministic algorithms achieving the above costs. Finally, if angles given as hints can be arbitrary, smaller than 2 pi, then we show that cost Theta(D^2) cannot be beaten.

Leader election is one of the basic problems in distributed computing. This is a symmetry breaking problem: all nodes of a network must agree on a single node, called the leader. If the nodes of the network have distinct labels, then such an agreement means that all nodes have to output the label of the elected leader. For anonymous networks, the task of leader election is formulated as follows: every node v of the network must output a simple path, which is coded as a sequence of port numbers, such that all these paths end at a common node, the leader. In this paper, we study deterministic leader election in arbitrary anonymous networks.

Two mobile agents starting at different nodes of an unknown network have to meet. This task is known in the literature as rendezvous. Each agent has a different label which is a positive integer known to it but unknown to the other agent. Agents move in an asynchronous way: the speed of agents may vary and is controlled by an adversary. The cost of a rendezvous algorithm is the total number of edge traversals by both agents until their meeting. The only previous deterministic algorithm solving this problem has cost exponential in the size of the graph and in the larger label. In this paper we present a deterministic rendezvous algorithm with cost polynomial in the size of the graph and in the length of the smaller label. Hence, we decrease the cost exponentially in the size of the graph and doubly exponentially in the labels of agents. As an application of our rendezvous algorithm we solve several fundamental problems involving teams of unknown size larger than 1 of labeled agents moving asynchronously in unknown networks. Among them are the following problems: \tt team size, in which every agent has to find the total number of agents; \tt leader election, in which all agents have to output the label of a single agent; \tt perfect renaming, in which all agents have to adopt new and different labels from the set $\{1,\dots,k\}$, where $k$ is the number of agents; and \tt gossiping, in which each agent has initially a piece of information (value) and all agents have to output all the values. Using our rendezvous algorithm, we solve all of these problems at cost polynomial in the size of the graph and in the smallest length of all labels of participating agents.

A team consisting of an unknown number of mobile agents starting from different nodes of an unknown network, possibly at different times, have to explore the network: Every node must be visited by at least one agent, and all agents must eventually stop. Agents are anonymous (identical), execute the same deterministic algorithm, and move in synchronous rounds along links of the network. They are silent: They cannot send any messages to other agents or mark visited nodes in any way. In the absence of any additional information, exploration with termination of an arbitrary network in this model, devoid of any means of communication between agents, is impossible. Our aim is to solve the exploration problem by giving to agents very restricted local traffic reports . Specifically, an agent that is at a node v in a given round is provided with three bits of information answering the following questions: Am I alone at v ? Did any agent enter v in this round? Did any agent exit v in this round? We show that this small amount of information permits us to solve the exploration problem in arbitrary networks. More precisely, we give a deterministic terminating exploration algorithm working in arbitrary networks for all initial configurations that are not perfectly symmetric ; that is, in which there are agents with different views of the network. The algorithm works in polynomial time in the (unknown) size of the network. A deterministic terminating exploration algorithm working for all initial configurations in arbitrary networks does not exist.

A team consisting of an unknown number of mobile agents, starting from different nodes of an unknown network, have to meet at the same node. Agents move in synchronous rounds. Each agent has a different label. Up to f of the agents are Byzantine. We consider two levels of Byzantine behavior. A strongly Byzantine agent can choose an arbitrary port when it moves and it can convey arbitrary information to other agents, while a weakly Byzantine agent can do the same, except changing its label. What is the minimum number of good agents that guarantees deterministic gathering of all of them, with termination? We solve exactly this Byzantine gathering problem in arbitrary networks for weakly Byzantine agents and give approximate solutions for strongly Byzantine agents, both when the size of the network is known and when it is unknown. It turns out that both the strength versus the weakness of Byzantine behavior and the knowledge of network size significantly impact the results. For weakly Byzantine agents, we show that any number of good agents permits solving the problem for networks of known size. If the size is unknown, then this minimum number is f +2. More precisely, we show a deterministic polynomial algorithm that gathers all good agents in an arbitrary network, provided that there are at least f +2 of them. We also provide a matching lower bound: we prove that if the number of good agents is at most f +1, then they are not able to gather deterministically with termination in some networks. For strongly Byzantine agents, we give a lower bound of f +1, even when the graph is known: we show that f good agents cannot gather deterministically in the presence of f Byzantine agents even in a ring of known size. On the positive side, we give deterministic gathering algorithms for at least 2 f +1 good agents when the size of the network is known and for at least 4 f +2 good agents when it is unknown.

Two mobile agents starting at different nodes of an unknown network have to meet. This task is known in the literature as rendezvous. Each agent has a different label which is a positive integer known to it, but unknown to the other agent. Agents move in an asynchronous way: the speed of agents may vary and is controlled by an adversary. The cost of a rendezvous algorithm is the total number of edge traversals by both agents until their meeting. The only previous deterministic algorithm solving this problem has cost exponential in the size of the graph and in the larger label. In this paper we present a deterministic rendezvous algorithm with cost polynomial in the size of the graph and in the length of the smaller label. Hence we decrease the cost exponentially in the size of the graph and doubly exponentially in the labels of agents.

A team consisting of an unknown number of mobile agents, starting from different nodes of an unknown network, possibly at different times, have to meet at the same node. Agents are anonymous (identical), execute the same deterministic algorithm and move in synchronous rounds along links of the network. An initial configuration of agents is called gatherable if there exists a deterministic algorithm (even dedicated to this particular configuration) that achieves meeting of all agents in one node. Which configurations are gatherable and how to gather all of them deterministically by the same algorithm? We give a complete solution of this gathering problem in arbitrary networks. We characterize all gatherable configurations and give two universal deterministic gathering algorithms, i.e., algorithms that gather all gatherable configurations. The first algorithm works under the assumption that an upper bound n on the size of the network is known. In this case our algorithm guarantees gathering with detection, i.e., the existence of a round for any gatherable configuration, such that all agents are at the same node and all declare that gathering is accomplished. If no upper bound on the size of the network is known, we show that a universal algorithm for gathering with detection does not exist. Hence, for this harder scenario, we construct a second universal gathering algorithm, which guarantees that, for any gatherable configuration, all agents eventually get to one node and stop, although they cannot tell if gathering is over. The time of the first algorithm is polynomial in the upper bound n on the size of the network, and the time of the second algorithm is polynomial in the (unknown) size itself. Our results have an important consequence for the leader election problem for anonymous agents in arbitrary graphs. Leader election is a fundamental symmetry breaking problem in distributed computing. Its goal is to assign, in some common round, value 1 (leader) to one of the entities and value 0 (non-leader) to all others. For anonymous agents in graphs, leader election turns out to be equivalent to gathering with detection. Hence, as a by-product, we obtain a complete solution of the leader election problem for anonymous agents in arbitrary graphs.

In this paper, we present a protocol to collect data within a vehicular ad hoc network (VANET). In spite of the intrinsic dynamic of such network, our protocol simultaneously offers three relevant properties: (1) It allows any vehicle to collect data beyond its direct neighborhood (i.e., vehicles within direct communication range) using vehicle-to-vehicle communications only (i.e., the infrastructure is not required); (2) It tolerates possible network partitions; (3) It works on demand and stops when the data collection is achieved. To the best of our knowledge, this is the first collect protocol having these three characteristics. All that is chiefly obtained thanks to a specific tool, namely Operator ant, borrowed from the self-stabilization area which confers to our algorithm the nice property to recover by itself from topology changes. In addition to a theoretical proof of correctness, our protocol has been implemented and tested through the Airplug Software Distribution: Road and lab experiments are presented and discussed.

A team consisting of an unknown number of mobile agents, starting from different nodes of an unknown network, have to meet at the same node. Agents move in synchronous rounds. Each agent has a different label. Up to f of the agents are Byzantine. We consider two levels of Byzantine behavior. A strongly Byzantine agent can choose an arbitrary port when it moves and it can convey arbitrary information to other agents, while a weakly Byzantine agent can do the same, except changing its label. What is the minimum number of good agents that guarantees deterministic gathering of all of them, with termination? We solve exactly this Byzantine gathering problem in arbitrary networks for weakly Byzantine agents, and give approximate solutions for strongly Byzantine agents, both when the size of the network is known and when it is unknown. It turns out that both the strength versus weakness of Byzantine behavior and the knowledge of network size significantly impact the results. For weakly Byzantine agents we show that any number of good agents permit to solve the problem for networks of known size. If the size is unknown, then this minimum number is f + 2. More precisely, we show a deterministic polynomial algorithm that gathers all good agents in an arbitrary network, provided that there are at least f + 2 of them. We also provide a matching lower bound: we prove that if the number of good agents is at most f + 1, then they are not able to gather deterministically with termination in some networks. For strongly Byzantine agents we give a lower bound of f + 1, even when the graph is known: we show that f good agents cannot gather deterministically in the presence of f Byzantine agents even in a ring of known size. On the positive side we give deterministic gathering algorithms for at least 2f + 1 good agents when the size of the network is known, and for at least 4f + 2 good agents when it is unknown.

In this paper, we study the relationship between two fundammental problem in Robotics namely, leader election problem and pattern formation problem. In particular, we prove that both problems are equivalent for n≥4 in a fully asynchronous model, called CORDA, provided the robots share the same chirality.

This paper provides a complexity study of the deterministic localization problem in robot networks using local and relative observations only. This is an important issue in collective and cooperative robotics where global positioning systems (GPS) are not available, and the basic premise is the localization ability of the group. We prove that given a set of relative observations made by the robots, the unique unambiguous pose estimation of the robot network in a deterministic way is an$N\!P$-hard problem. This means that no polynomial-time algorithm can deterministically solve the unique pose estimation problem based on relative observations unless$P=N\!P$. The consequence is that no guarantee can be provided, in a polynomial time, that the possibly estimated poses of the robots will correspond to the effective (actual) ones. The proof is based on complexity theory where we build appropriate polynomial-time reductions interrelating the multirobot localization problem to a well-known$N\!P$-complete problem (the partition problem). This$N\!P$-hardness result opens questions and perspectives for research into approximations to overcome its intractability.

We introduce the use of movement-signals (analogously to flight signals and bees waggle) as a mean to transfer messages, enabling the use of distributed algorithms among the robots. We propose one-to-one deterministic movement protocols that implement explicit communication.

This paper contributes to the problem of deterministic localization of robot networks using local and relative observations only. This is an important issue in collective and cooperative robotics where global positioning systems are not available, and the basic premise is the localization ability of the group. We prove that, giving a set of relative observations made by the robots, the unique non ambiguous pose estimation of the robot network in a deterministic way, is a NP-hard problem. This means that no polynomial-time algorithm can deterministically solve the unique pose estimation problem based on relative observations. The consequence is that no guaranty can be provided, in a polynomial time, that the possibly estimated poses of the robots, will correspond to the effective (actual) ones. The proof is based on complexity theory. We build appropriate polynomial-time reductions acting on the localization problem and leading to well known NP-hard problems. The paper gives some tracks to overcome this issue.

We consider distributed systems made of weak mobile robots, that is, mobile devices, equipped with sensors, that are anonymous , autonomous , disoriented , and oblivious . The Circle Formation Problem (CFP) consists of the design of a protocol insuring that, starting from an initial arbitrary configuration where no two robots are at the same position, all the robots eventually form a regular n-gon —the robots take place on the circumference of a circle C with equal spacing between any two adjacent robots on C . CFP is known to be unsolvable by arranging the robots evenly along the circumference of a circle C without leaving C —that is, starting from a configuration where the robots are on the boundary of C . We circumvent this impossibility result by designing a scheme based on concentric circles . This is the first scheme that deterministically solves CFP. We present our method with two different implementations working in the semi-synchronous system (SSM) for any number n ≥ 5 of robots.