We consider the problem of finding a treasure at an unknown point of an n-dimensional infinite grid, n >= 3, by initially collocated finite automaton agents (scouts/robots). Recently, the problem has been well characterized for 2 dimensions for deterministic as well as randomized agents, both in synchronous and semi-synchronous models [S. Brandt et al., 2018; Y. Emek et al., 2015]. It has been conjectured that n+1 randomized agents are necessary to solve this problem in the n-dimensional grid [L. Cohen et al., 2017]. In this paper we disprove the conjecture in a strong sense: we show that three randomized synchronous agents suffice to explore an n-dimensional grid for any n. Our algorithm is optimal in terms of the number of the agents. Our key insight is that a constant number of finite automaton agents can, by their positions and movements, implement a stack, which can store the path being explored. We also show how to implement our algorithm using: four randomized semi-synchronous agents; four deterministic synchronous agents; or five deterministic semi-synchronous agents. We give a different algorithm that uses 4 deterministic semi-synchronous agents for the 3-dimensional grid. This is provably optimal, and surprisingly, matches the result for 2 dimensions. For n >= 4, the time complexity of the solutions mentioned above is exponential in distance D of the treasure from the starting point of the agents. We show that in the deterministic case, one additional agent brings the time down to a polynomial. Finally, we focus on algorithms that never venture much beyond the distance D. We describe an algorithm that uses O(sqrt{n}) semi-synchronous deterministic agents that never go beyond 2D, as well as show that any algorithm using 3 synchronous deterministic agents in 3 dimensions, if it exists, must travel beyond Omega(D^{3/2}) from the origin.

In STOC'16, Fraigniaud et al. consider the problem of finding a treasure hidden in one of many boxes that are ordered by importance. That is, if a treasure is in a more important box, then one would like to find it faster. Assuming there are many searchers, the authors suggest that using an algorithm that requires no coordination between searchers can be highly beneficial. Indeed, besides saving the need for a communication and coordination mechanism, such algorithms enjoy inherent robustness. The authors proceed to solve this linear search problem in the case of countably many boxes and an adversary placed treasure, and prove that the best speed-up possible by $k$ non-coordinating searchers is precisely $\frac{k}{4}(1+1/k)^2$. In particular, this means that asymptotically, the speed-up is four times worse compared to the case of full coordination. We suggest an important variant of the problem, where the treasure is placed uniformly at random in one of a finite, large, number of boxes. We devise non-coordinating algorithms that achieve a speed-up of $6/5$ for two searchers, a speed-up of $3/2$ for three searchers, and in general, a speed-up of $k(k+1)/(3k-1)$ for any $k \geq 1$ searchers. Thus, as $k$ grows to infinity, the speed-up approaches three times worse compared to the case of full coordination. Moreover, these bounds are tight in a strong sense as no non-coordinating search algorithm for $k$ searchers can achieve better speed-ups. We also devise non-coordinating algorithms that use only logarithmic memory in the size of the search domain, and yet, asymptotically, achieve the optimal speed-up. Finally, we note that all our algorithms are extremely simple and hence applicable.

We consider a problem of routing on directed paths and trees to a single destination, with rate-limited, adversarial traffic. In particular, we focus on local buffer management algorithms that ensure no packet loss, while minimizing the size of the required buffers. While a centralized algorithm for the problem that uses constant-sized buffers has been recently shown [21], there is no known local algorithm that achieves a sub-linear buffer size. In this paper we show tight bounds for the maximum buffer size needed by l-local algorithms for information gathering on directed paths and trees, where an algorithm is called l-local if the decision made by each node v depends only on the sizes of the buffers at most l hops away from v.

Almost all the vast literature on graph exploration assumes that the graph is static: its topology does not change during the exploration, except for occasional faults. To date, very little is known on exploration of dynamic graphs, where the topology is continously changing. The few studies have been limited to the centralized (or post-mortem) case, assuming complete a priori knowledge of the changes and the times of their occurrence, and have only considered fully synchronous systems. In this paper, we start the study of the decentralized (or live) exploration of dynamic graphs, i.e. when the agents operate in the graph unaware of the location and timing of the changes. We consider dynamic rings under the standard 1-interval-connected restriction, and investigate the feasibility of their exploration, in both the fully synchronous and semi-synchronous cases. When exploration is possible we examine at what cost, focusing on the minimum number of agents capable of exploring the ring. We establish several results highlighting the impact that anonymity and structural knowledge have on the feasibility and complexity of the problem.

A black hole is a highly harmful host that disposes of visiting agents upon their arrival without any observable trace of the destruction. The problem of locating the black hole in asynchronous ring network is known to be solvable by a team of mobile agents if each node is equipped with a whiteboard. A simpler and less expensive inter-communication and synchronization mechanism is provided by tokens: each agent has available a bounded number of tokens that can be carried, placed in a node or/and on a port of the node, or removed. All tokens are identical and no other form of communication or coordination is available to the agents. It is known that locating the black hole in an anonymous ring network using tokens is feasible when the team of agents is initially collocated (i.e. they all start from the same host). Recently, the more difficult case when the agents are scattered (i.e., when the agents do not start from the same host) has also been examined and solutions requiring only O(1) tokens per agent but using a total of O(n2) moves have been presented. The number of moves can be reduced to O(kn + n log n) if the number k of agents is known. In this paper, we study the impact of orientation and knowledge of team size on the cost of black hole location by scattered agents with tokens. We prove that, in oriented rings, the number of moves can be reduced from O(n2) to the optimal Theta(nlogn) using only O(1) tokens per agent, without any knowledge of the team size. This result holds even if both agents and nodes are anonymous. Interestingly, the proposed algorithm solves, with the same cost, also the leader election problem and the rendezvous problem for the scattered agents despite the presence of a BH.

In this paper we consider a dangerous process located at a node of a network (called Black Hole ) and a team of mobile agents deployed to locate that node. The nature of the danger is such that when an agent enters the dangerous node, it is trapped there leaving no trace of its destruction. The goal is to deploy as few agents as possible and to locate the black hole in as few moves as possible. We present a simple algorithm that works on any topology (a-priori known by the agents). Our algorithm, based on the pre-computation of an open vertex cover by cycles of the network, uses the optimal number of agents (two); its cost (number of moves) depends on the choice of the cover and it is optimal for several classes of networks.

Abstract We address the problem of discovering routes in strongly connected planar geometric networks with directed links. Motivated by the necessity for establishing communication in wireless ad hoc networks in which the only information available to a vertex is its immediate neighborhood, we are considering routing algorithms that use the neighborhood information of a vertex for routing with constant memory only. We solve the problem for three types of directed planar geometric networks: Eulerian (in which every vertex has the same number of incoming and outgoing edges), Outerplanar in which a single face contains all vertices of the network, and Strongly Face Connected, a new class of geometric networks that we define in the article, consisting of several faces, each face being a strongly connected outerplanar graph. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 48(1), 7–15 2006

Abstract Mobile agents operating in networked environments face threats from other agents as well as from the hosts (i.e., network sites) they visit. A black hole is a harmful host that destroys incoming agents without leaving any trace. To determine the location of such a harmful host is a dangerous but crucial task, called black hole search. The most important parameter for a solution strategy is the number of agents it requires (the size); the other parameter of interest is the total number of moves performed by the agents (the cost). It is known that at least two agents are needed; furthermore, with full topological knowledge, Ω(n log n) moves are required in arbitrary networks. The natural question is whether, in specific networks, it is possible to obtain (topology‐dependent but) more cost efficient solutions. It is known that this is not the case for rings. In this article, we show that this negative result does not generalizes. In fact, we present a general strategy that allows two agents to locate the black hole with O(n) moves in common interconnection networks: hypercubes, cube‐connected cycles, star graphs, wrapped butterflies, chordal rings, as well as in multidimensional meshes and tori of restricted diameter. These results hold even if the networks are anonymous. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 47(2), 61–71 2006

Summary form only given. The problem of traversal of planar subdivisions or other graph-like structures without using mark bits is central to many real-world applications. The first such algorithms were able to traverse triangulated subdivisions. Later these algorithms were extended to traverse vertices of an arrangement or a convex polytope. The research progress culminated in an algorithm that can traverse any planar subdivision. We extend the notion of planar subdivision to quasiplanar subdivision in which we allow many edges to cross each other. We describe an algorithm to traverse any quasiplanar subdivision that satisfies a simple requirement. The worst case running time of our algorithm is O(|E| log |E|), which matches the running time of the traversal algorithm for planar subdivisions.

Protecting agents from host attacks is a pressing security concern in networked environments supporting mobile agents. In this paper, we consider a black hole: a highly harmful host that disposes of visiting agents upon their arrival, leaving no observable trace of such a destruction. The task to identify the location of the harmful host is clearly dangerous for the searching agents. We study under what conditions and at what cost a team of autonomous asynchronous mobile agents can successfully accomplish this task; we are concerned with solutions that are generic (i.e., topology-independent). We study the size of the optimal solution (i.e., the minimum number of agents needed to locate the black hole), and the cost of the minimal solution (i.e., the number of moves performed by the agents executing a size-optimal solution protocol). We establish tight bounds on size and cost depending on the a priori knowledge the agents have about the network, and on the consistency of the local labellings. In particular, we prove that: with topological ignorance Δ + 1 agents are needed and suffice, and the cost is Θ(n2), where Δ is the maximal degree of a node and n is the number of the nodes in the network; with topological ignorance but in presence of sense of direction only two agents suffice and the cost is Θ(n2); and with complete topological knowledge only two agents suffice and the cost is Θ(n log n). All the upper-bound proofs are constructive.

The problem of performing t tasks on n asynchronous or undependable processors is a basic problem in parallel and distributed computing. We consider an abstraction of this problem called the Write-All problem— using n processors write 1's into all locations of an array of size t. The most efficient known deterministic asynchronous algorithms for this problem are due to Anderson and Woll. The first class of algorithms has work complexity of Ο(t . n ε), for n ≰ ty and any ε > 0, and they are the best known for the full range of processors (n = t). To schedule the work of the processors, the algorithms use sets of q permutations on [q] (q ≰ n) that have certain combinatorial properties. Instantiating such an algorithm for a specific ε either requires substantial pre-processing (exponential in 1/ε2) to find the requisite permutations, or imposes a prohibitive constant (exponential in 1/ε3) hidden by the asymptotic analysis. The second class deals with the specific case of t = nu, u ≰ 2, and these algorithms have work complexity of Ο(t log t). They also use sets of permutations with the same combinatorial properties. However instantiating these algorithms requires exponential in n preprocessing to find the permutations. To alleviate this costly instantiation Kanellakis and Shvartsman proposed a simple way of computing the permutation schedules. They conjectured that their construction has the desired properties but they provided no analysis.