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.

Abstract Treasure hunt is finding a hidden inert target by a mobile agent. We consider deterministic algorithms for treasure hunt in trees. Our goal is to establish the impact of different kinds of initial knowledge given to the agent on the cost of treasure hunt, defined as the total number of edge traversals until the agent reaches the treasure. The agent can be initially given either a complete map of the tree rooted at its starting node, with all port numbers marked, or a blind map of the tree rooted at its starting node but without port numbers. It may also be given, or not, the distance from the root to the treasure. This yields four different knowledge types that are partially ordered by their precision. The penalty of a less precise knowledge type over a more precise knowledge type measures intuitively the worst‐case ratio of the cost of an algorithm supplied with knowledge of type over the cost of an algorithm supplied with knowledge of type . Our main results establish penalties for comparable knowledge types in this partial order. For knowledge types with known distance, the penalty for having a blind map over a complete map turns out to be very large. By contrast, for unknown distance, the penalty of having a blind map over having a complete map is small. When a map is provided (either complete or blind), the penalty of not knowing the distance over knowing it is medium.

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.