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]

Abstract: Asynchrony is one of the main challenges in distributed computing. Some tasks, such as distributed Byzantine consensus, are impossible in the asynchronous setting, while they can be carried out synchronously. For other tasks, such as rendezvous in arbitrary graphs, the best known synchronous algorithm has cost much lower than the best asynchronous one. Various degrees of asynchrony and synchrony and comparisons between them in terms of feasibility of distributed tasks have been particularly intensely studied in the context of mobile agents computing. However, somewhat surprisingly, there are no results showing a provable difference of cost between the synchronous and asynchronous versions of a task executed by mobile agents. The aim of this paper is to fill up this gap. We show for the first time that for some natural task executed by mobile agents in a network, the optimal cost of its deterministic solution in the asynchronous setting has higher order of magnitude than that in the synchronous scenario. The task for which we show this difference is well-studied: that of rendezvous of two agents in an infinite oriented grid. More precisely, we consider two agents with distinct integer labels starting at a distance D in the infinite oriented grid. Each agent knows D and its own label but not the label of the other agent and it does not know the position of the other agent relative to its own. Agents do not have any global system of coordinates. They have to meet in a node or inside an edge of the grid, and the cost of a rendezvous algorithm is the number of edge traversals by both agents until the meeting. We show that in the synchronous scenario rendezvous can be performed at cost , where ℓ is the length of the (binary representation of the) smaller label, while cost is needed for asynchronous completion of rendezvous. Hence, for instances with , the optimal cost of asynchronous rendezvous is asymptotically larger than that of synchronous rendezvous. [Copyright &y& Elsevier]