Search

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 + a)r, for some positive real constant a, 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 O(e (d) logd) 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 T(e (d)) for all graphs, and thus our algorithms are also almost optimal. [ABSTRACT FROM AUTHOR]

Leader election is a fundamental task in distributed computing. It is a symmetry breaking problem, calling for one node of the network to become the leader, and for all other nodes to become non-leaders. We consider leader election in anonymous radio networks modeled as simple undirected connected graphs. Nodes communicate in synchronous rounds. In each round, a node can either transmit a message to all its neighbours, or stay silent and listen. A node v hears a message from a neighbour w in a given round if v listens in this round and if w is its only neighbour transmitting in this round. If v listens in a round in which more than one neighbour transmits, then v hears noise that is different from any message and different from silence. We assume that nodes are identical (anonymous) and execute the same deterministic algorithm. Under this scenario, symmetry can be broken only in one way: by different wake-up times of the nodes. In which situations is it possible to break symmetry and elect a leader using time as symmetry breaker? In order to answer this question, we consider configurations. A configuration is the underlying graph with nodes tagged by non-negative integers with the following meaning. A node can either wake up spontaneously in the round shown on its tag, according to some global clock, or can be woken up hearing a message sent by one of its already awoken neighbours. The local clock of a node starts at its wakeup and nodes do not have access to the global clock determining their tags. A configuration is feasible if there exists a distributed algorithm that elects a leader for this configuration. Our main result is a complete algorithmic characterization of feasible configurations. More precisely, we design a centralized decision algorithm, working in polynomial time, whose input is a configuration and which decides if the configuration is feasible. Using this algorithm we also provide a dedicated deterministic distributed leader election algorithm for each feasible configuration that elects a leader for this configuration in time O(n²σ), where n is the number of nodes and σ is the difference between the largest and smallest tag of the configuration. We then ask the question whether there exists a universal deterministic distributed algorithm electing a leader for all feasible configurations. The answer turns out to be no, and we show that such a universal algorithm cannot exist even for the class of 4-node feasible configurations. We also prove that a distributed version of our decision algorithm cannot exist. [ABSTRACT FROM AUTHOR]

We consider the fundamental task of graph exploration. An n-node graph has unlabeled nodes, and all ports at any node of degree d are arbitrarily numbered 0,..., d−1. A mobile agent, initially situated at some starting node v, has to visit all nodes and stop. The time of the exploration is the number of edge traversals. We consider the problem of how much knowledge the agent has to have a priori, to explore the graph in a given time, using a deterministic algorithm. Following the paradigm of algorithms with advice, this a priori information (advice) is provided to the agent by an oracle, in the form of a binary string, whose length is called the size of advice. We consider two types of oracles. The instance oracle knows the entire instance of the exploration problem, i.e., the port-numbered map of the graph and the starting node of the agent in this map. The map oracle knows the port-numbered map of the graph but does not know the starting node of the agent. What is the minimum size of advice that must be given to the agent by each of these oracles, so that the agent explores the graph in a given time? We first determine the minimum size of advice to achieve exploration in polynomial time. We prove that some advice of size log log log n − c, for any constant c, is sufficient for polynomial exploration, and that no advice of size log log log n −φ (n), where φ is any function diverging to infinity, can help to do this. These results hold both for the instance and for the map oracles. On the other side of the spectrum, when advice is large, there are two natural time thresholds: Θ (n2) for a map oracle, and Θ (n) for an instance oracle. This is because, in both cases, these time benchmarks can be achieved with sufficiently large advice (advice of size O(nlog n) suffices). We show that, with a map oracle, time Θ (n2) cannot be improved in general, regardless of the size of advice. What is then the smallest advice to achieve time Θ (n2) with a map oracle? We show that this smallest size of advice is larger than nΔ, for any Δ < 1/3. For large advice, the situation changes significantly when we allow an instance oracle instead of a map oracle. In this case, advice of size O(nlog n) is enough to achieve time O(n). Is such a large advice needed to achieve linear time? We answer this question affirmatively. Indeed, we show more: with any advice of size o(nlog n), the time of exploration must be at least n∊, for any ∊ < 2, and with any advice of size O(n), the time must be Ω(n2). We finally look at Hamiltonian graphs, as for them it is possible to achieve the absolutely optimal exploration time n−1, when sufficiently large advice (of size o(nlog n)) is given by an instance oracle. We show that a map oracle cannot achieve this: regardless of the size of advice, the time of exploration must be Ω(n2), for some Hamiltonian graphs. However, even for the instance oracle, with advice of size o(nlog n), optimal time n−1 cannot be achieved: Indeed, we show that the time of exploration with such advice must sometimes exceed the optimal time n−1 by a summand n∊, for any ∊ < 1. [ABSTRACT FROM AUTHOR]

The leader election task calls for all nodes of a network to agree on a single node. If the nodes of the network are anonymous, the task of leader election is formulated as follows: every node v of the network must output a simple path, 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 anonymous trees. Our aim is to establish tradeoffs between the allocated time τ and the amount of information that has to be given a priori to the nodes to enable leader election in time τ in all trees for which leader election in this time is at all possible. Following the framework of algorithms with advice, this information (a single binary string) is provided to all nodes at the start by an oracle knowing the entire tree. The length of this string is called the size of advice. For an allocated time τ, we give upper and lower bounds on the minimum size of advice sufficient to perform leader election in time τ. We consider n-node trees of diameter diam≤D. While leader election in time diam can be performed without any advice, for time diam−1 we give tight upper and lower bounds of Θ(logD). For time diam−2 we give tight upper and lower bounds of Θ(logD) for even values of diam, and tight upper and lower bounds of Θ(logn) for odd values of diam. For the time interval [β⋅diam,diam−3] for constant β>1/2, we prove an upper bound of O(nlognD) and a lower bound of Ω(nD), the latter being valid whenever diam is odd or when the time is at most diam−4. Finally, for time α⋅diam for any constant α<1/2 (except for the case of very small diameters), we give tight upper and lower bounds of Θ(n). [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

The aim of rendezvous in a graph is meeting of two mobile agents at some node of an unknown anonymous connected graph. In this article, we focus on rendezvous in trees, and, analogously to the efforts that have been made for solving the exploration problem with compact automata, we study the size of memory of mobile agents that permits to solve the rendezvous problem deterministically. We assume that the agents are identical, and move in synchronous rounds. We first show that if the delay between the starting times of the agents is arbitrary, then the lower bound on memory required for rendezvous is Ω(log n) bits, even for the line of length n. This lower bound meets a previously known upper bound of O(log n) bits for rendezvous in arbitrary graphs of size at most n. Ourmain result is a proof that the amount of memory needed for rendezvous with simultaneous start depends essentially on the number ... of leaves of the tree, and is exponentially less impacted by the number n of nodes. Indeed, we present two identical agents with O(log ... + log log n) bits of memory that solve the rendezvous problem in all trees with at most n nodes and at most leaves. Hence, for the class of trees with polylogarithmically many leaves, there is an exponential gap in minimum memory size needed for rendezvous between the scenario with arbitrary delay and the scenario with delay zero. Moreover, we show that our upper bound is optimal by proving that Ω(log ... + log log n) bits of memory are required for rendezvous, even in the class of trees with degrees bounded by 3. [ABSTRACT FROM AUTHOR]

Two mobile agents (robots) with distinct labels have to meet in an arbitrary, possibly infinite, unknown connected graph or in an unknown connected terrain in the plane. Agents are modeled as points, and the route of each of them only depends on its label and on the unknown environment. The actual walk of each agent also depends on an asynchronous adversary that may arbitrarily vary the speed of the agent, stop it, or even move it back and forth, as long as the walk of the agent is continuous, does not leave its route and covers all of it. Meeting in a graph means that both agents must be at the same time in some node or in some point inside an edge of the graph, while meeting in a terrain means that both agents must be at the same time in some point of the terrain. Does there exist a deterministic algorithm that allows any two agents to meet in any unknown environment in spite of this very powerful adversary? We give deterministic rendezvous algorithms for agents starting at arbitrary nodes of any anonymous connected graph (finite or infinite) and for agents starting at any interior points with rational coordinates in any closed region of the plane with path-connected interior. In the geometric scenario agents may have different compasses and different units of length. While our algorithms work in a very general setting - agents can, indeed, meet almost everywhere - we show that none of these few limitations imposed on the environment can be removed. On the other hand, our algorithm also guarantees the following approximate rendezvous for agents starting at arbitrary interior points of a terrain as previously stated agents will eventually get to within an arbitrarily small positive distance from each other. [ABSTRACT FROM AUTHOR]