In this paper, we investigate the following question: "How can a group of initially co-located mobile agents perpetually explore an unknown graph, when one stationary node occasionally behaves maliciously, under the control of an adversary?" This malicious node is termed as "Byzantine black hole (BBH)" and at any given round it may choose to destroy all visiting agents, or none of them. While investigating this question, we found out that this subtle power turns out to drastically undermine even basic exploration strategies which have been proposed in the context of a classical, always active, black hole. We study this perpetual exploration problem in the presence of at most one BBH, without initial knowledge of the network size. Since the underlying graph may be 1-connected, perpetual exploration of the entire graph may be infeasible. Accordingly, we define two variants of the problem, termed as PerpExploration-BBH and PerpExploration-BBH-Home. In the former, the agents are tasked to perform perpetual exploration of at least one component, obtained after the exclusion of the BBH. In the latter, the agents are tasked to perform perpetual exploration of the component which contains the home node, where agents are initially co-located. Naturally, PerpExploration-BBH-Home is a special case of PerpExploration-BBH. The mobile agents are controlled by a synchronous scheduler, and they communicate via face-to-face model of communication. The main objective in this paper is to determine the minimum number of agents necessary and sufficient to solve these problems. We first consider the problems in acyclic networks, and we obtain optimal algorithms that solve PerpExploration-BBH with 4 agents, and PerpExploration-BBH-Home with 6 agents in trees. The lower bounds hold even in path graphs. In general graphs, we give a non-trivial lower bound of 2Δ-1 agents for PerpExploration-BBH, and an upper bound of 3Δ+3 agents for PerpExploration-BBH-Home. To the best of our knowledge, this is the first paper that studies a variant of a black hole in arbitrary networks, without initial topological knowledge about the network.

In the treasure hunt problem, a team of mobile agents need to locate a single treasure that is hidden in their environment. We consider the problem in the discrete setting of an oriented infinite rectangular grid, where agents are modeled as synchronous identical deterministic time-limited finite-state automata, originating at a rate of one agent per round from the origin. Agents perish τ rounds after their creation, where τ ≥ 1 is a parameter of the model. An algorithm solves the treasure hunt problem if every grid position at distance τ or less from the origin is visited by at least one agent. Agents may communicate only by leaving indistinguishable traces (pheromone) on the nodes of the grid, which can be sensed by agents in adjacent nodes and thus modify their behavior. The novelty of our approach is that, in contrast to existing literature that uses permanent pheromone markers, we assume that pheromone traces evaporate over µ rounds from the moment they were placed on a node, where µ ≥ 1 is another parameter of the model. We look for uniform algorithms that solve the problem without knowledge of the parameter values, and we investigate the implications of this very weak communication mechanism to the treasure hunt problem. We show that, if pheromone persists for at least two rounds (µ ≥ 2), then there exists a treasure hunt algorithm for all values of agent lifetime. We also develop a more sophisticated algorithm that works for all values of µ, hence also for the fastest possible pheromone evaporation of µ = 1, but only if agent lifetime is at least 16.

Two mobile robots are initially placed at the same point on an infinite line. Each robot may move on the line in either direction not exceeding its maximal speed. The robots need to find a stationary target placed at an unknown location on the line. The search is completed when both robots arrive at the target point. The target is discovered at the moment when either robot arrives at its position. The robot knowing the placement of the target may communicate it to the other robot. We look for the algorithm with the shortest possible search time (i.e. the worst-case time at which both robots meet at the target) measured as a function of the target distance from the origin (i.e. the time required to travel directly from the starting point to the target at unit velocity). We consider two standard models of communication between the robots, namely wireless communication and communication by meeting. In the case of communication by meeting, a robot learns about the target while sharing the same location with a robot possessing this knowledge. We propose here an optimal search strategy for two robots including the respective lower bound argument, for the full spectrum of their maximal speeds. This extends the main result of Chrobak et al. (in: Italiano, Margaria-Steffen, Pokorný, Quisquater, Wattenhofer (eds) Current trends in theory and practice of computer science, SOFSEM, 2015) referring to the exact complexity of the problem for the case when the speed of the slower robot is at least one third of the faster one. In the wireless communication model, a message sent by one robot is instantly received by the other robot, regardless of their current positions on the line. For this model, we design a strategy which is optimal whenever the faster robot is at most $$\sqrt{17}+4\approx 8.123$$ times faster than the slower one. We also prove that otherwise the wireless communication offers no advantage over communication by meeting.

We propose and investigate Selfish Path MultiColoring games as a natural model for noncooperative wavelength assignment in multifiber optical networks. In this setting, we view the wavelength assignment process as a strategic game in which each communication request selfishly chooses a wavelength in an effort to minimize the maximum congestion that it encounters on the chosen wavelength. We measure the cost of a certain wavelength assignment as the maximum, among all physical links, number of parallel fibers employed by this assignment. We start by settling questions related to the existence and computation of and convergence to pure Nash equilibria in these games. Our main contribution is a thorough analysis of the price of anarchy of such games, that is, the worst-case ratio between the cost of a Nash equilibrium and the optimal cost. We first provide upper bounds on the price of anarchy for games defined on general network topologies. Along the way, we obtain an upper bound of 2 for games defined on star networks. We next show that our bounds are tight even in the case of tree networks of maximum degree 3, leading to nonconstant price of anarchy for such topologies. In contrast, for network topologies of maximum degree 2, the quality of the solutions obtained by selfish wavelength assignment is much more satisfactory: We prove that the price of anarchy is bounded by 4 for a large class of practically interesting games defined on ring networks.

Abstract We are interested in the problem of satisfying a maximum‐profit subset of undirected communication requests in an optical ring that uses the Wavelength Division Multiplexing technology. We present four deterministic and purely combinatorial algorithms for this problem, and give theoretical guarantees for their worst‐case approximation ratios. Two of these algorithms are novel, whereas the rest are adaptation of earlier approaches. An experimental evaluation of the algorithms in terms of attained profit and execution time reveals that the theoretically best algorithm performs only marginally better than one of the new algorithms, while at the same time being several orders of magnitude slower. Furthermore, an extremely fast greedy heuristic with nonconstant approximation ratio performs reasonably well and may be favored over the other algorithms whenever it is crucial to minimize execution time. © 2011 Wiley Periodicals, Inc. NETWORKS, 2011