Search

Consider a group of autonomous mobile computational entities, called agents, arbitrarily placed at some nodes of a dynamic but always connected ring. The agents neither have any knowledge about the size of the ring nor have a common notion of orientation. We consider the Exploration problem where the agents have to collaboratively explore the graph and terminate, with the requirement that each node has to be visited by at least one agent. It has been shown by Luna et al. (2020) [22] that the problem is solvable by two anonymous agents if there is a single observably different node in the ring called landmark node. The problem is unsolvable by any number of anonymous agents in absence of a landmark node. We consider the problem with non-anonymous agents (agents with distinct identifiers) in a ring with no landmark node. The assumption of agents with distinct identifiers is strictly weaker than having a landmark node as the problem is unsolvable by two agents with distinct identifiers in absence of a landmark node. This setting has been recently studied by Mandal et al. (2020) [6]. There it is shown that the problem is solvable in this setting by three agents assuming that they have edge crossing detection capability. Edge crossing detection capability is a strong assumption which enables two agents moving in opposite directions through an edge in the same round to detect each other and also exchange information. In this paper we give an algorithm that solves the problem with three agents without the edge crossing detection capability. • Exploration of a dynamic but always connected ring by autonomous agents is studied. • A deterministic protocol is given that solves the problem with explicit termination. • The agents have unique identifiers, but do not have chirality or edge crossing detection capability. • The algorithm solves the problem with optimum number of agents. • A new problem called Contiguous Agreement is introduced and solved. [ABSTRACT FROM AUTHOR]

• We study the problem of pebble-guided treasure hunt by a mobile agent in anonymous graphs. • The mobile agent, starting from a node, must find a treasure located on an unknown node at a distance D. • The time of treasure hunt is defined as the number of edges the agent visits before it finds the treasure. • We propose an algorithm that solves treasure hunt in time O (D log ⁡ Δ) using O (D log ⁡ Δ) pebbles. • We prove a lower bound of Ω (D log ⁡ Δ) on time of treasure hunt regardless of the number of pebbles used. We study the problem of treasure hunt in a graph by a mobile agent. The nodes in the graph are anonymous and the edges at any node v of degree d e g (v) are labeled arbitrarily as 0 , 1 , ... , d e g (v) − 1. A mobile agent, starting from a node, must find a stationary object, called treasure that is located on an unknown node at a distance D from its initial position. The agent finds the treasure when it reaches the node where the treasure is present. The time of treasure hunt is defined as the number of edges the agent visits before it finds the treasure. The agent does not have any prior knowledge about the graph or the position of the treasure. An Oracle, that knows the graph, the initial position of the agent, and the position of the treasure, places some pebbles on the nodes, at most one per node, of the graph to guide the agent towards the treasure. We target to answer the question: what is the fastest possible treasure hunt algorithm regardless of the number of pebbles are placed? We show an algorithm that uses O (D log ⁡ Δ) pebbles to find the treasure in a graph G in time O (D log ⁡ Δ) , where Δ is the maximum degree of a node in G and D is the distance from the initial position of the agent to the treasure. We show a matching lower bound of Ω (D log ⁡ Δ) on time of the treasure hunt using any number of pebbles. [ABSTRACT FROM AUTHOR]

We study the problem of exploration by a mobile entity (agent) of a class of highly dynamic networks, namely the carrier graphs (the C-graphs, modeling public transportation systems, among others). These are defined by a set of carriers following infinitely their prescribed route along the stations of the network. Flocchini, Mans, and Santoro [9] studied this problem in the case when the agent must always travel on the carriers and thus cannot wait on a station. They described the necessary and sufficient conditions for the problem to be solvable and proved that the optimal worst-case number of time units (and thus of moves) to explore a n -node C-graph of k carriers and maximal period p is in Θ (k p 2) in the general case. In this paper, we study the impact of the ability to wait at the stations. We exhibit the necessary and sufficient conditions for the problem to be solvable in this context, and we prove that waiting at the stations allows the agent to reduce the optimal worst-case number of moves by a multiplicative factor of at least Θ (p) , while the worst-case time complexity is reduced to Θ (n p). (In any connected carrier graph, we have n ≤ k p.) We also show some complementary optimal results in specific cases (same period for all carriers, highly connected C-graphs). Finally this new ability allows the agent to completely map the C-graph, in addition to just exploring it. [ABSTRACT FROM AUTHOR]

In this paper, we consider the partial gathering problem of mobile agents in asynchronous unidirectional ring networks. The partial gathering problem is a generalization of the (well-investigated) total gathering problem, which requires that all the k agents distributed in the network terminate at a single node. The partial gathering problem requires, for a given positive integer g (< k) , that all the agents terminate in a configuration such that either at least g agents or no agent exists at each node. The requirement for the partial gathering problem is strictly weaker than that for the total gathering problem, and thus it is interesting to clarify the difference on the move complexity between them. In this paper, we aim to solve the partial gathering problem for agents without identifiers or any global knowledge such as the number k of agents or the number n of nodes. We consider deterministic and randomized cases. First, in the deterministic case, we show that the set of unsolvable initial configurations is the same as that for the case of agents with knowledge of k. In addition, we propose an algorithm that solves the problem from any solvable initial configuration in a total number of O (g n) moves. Next, in the randomized case, we propose an algorithm that solves the problem in a total number of O (g n) moves in expectation from any initial configuration. Note that g < k holds and agents require a total number of Ω (g n) (resp., Ω (k n)) moves to solve the partial (resp., total) gathering problem. Thus, our algorithms can solve the partial gathering problem in asymptotically optimal total number of moves without identifiers or global knowledge, and the total number of O (g n) moves is strictly smaller than that for the total gathering problem. [ABSTRACT FROM AUTHOR]

In this paper, we consider the uniform deployment problem of mobile agents in asynchronous unidirectional ring networks. This problem requires agents to spread uniformly in the network. In this paper, we focus on the memory space per agent required to solve the problem. We consider two problem settings. The first setting assumes that agents have no multiplicity detection, that is, agents cannot detect whether another agent is staying at the same node or not. In this case, we show that each agent requires Ω (log ⁡ n) memory space to solve the problem, where n is the number of nodes. In addition, we propose an algorithm to solve the problem with O (k + log ⁡ n) memory space per agent, where k is the number of agents. The second setting assumes that each agent is equipped with the weak multiplicity detection, that is, agents can detect whether another agent is staying at the same node or not, but cannot get any other information about the number of the agents. Then, we show that the memory space per agent can be reduced to O (log ⁡ k + log ⁡ log ⁡ n). To the best of our knowledge, this is the first research considering the effect of the multiplicity detection on memory space required to solve problems. [ABSTRACT FROM AUTHOR]

The rendezvous task calls for two mobile agents, starting from different nodes of a network modeled as a graph to meet at the same node. Agents have different labels which are integers from a set { 1 , ... , L }. They wake up at possibly different times and move in synchronous rounds. In each round, an agent can either stay idle or move to an adjacent node. We consider deterministic rendezvous algorithms. The time of such an algorithm is the number of rounds since the wakeup of the earlier agent till the meeting. In most of the literature concerning rendezvous in graphs, the graph is finite and the time of rendezvous depends on its size. This approach is impractical for very large graphs and impossible for infinite graphs. For such graphs it is natural to design rendezvous algorithms whose time depends on the initial distance D between the agents. In this paper we adopt this approach and consider rendezvous in infinite trees. All our algorithms work in finite trees as well. Our main goal is to study the impact of orientation of a tree on the time of rendezvous. We first design a rendezvous algorithm working for unoriented regular trees, whose time is in O (z (D) log ⁡ L) , where z (D) is the size of the ball of radius D , i.e., the number of nodes at distance at most D from a given node. The algorithm works for arbitrary delay between waking times of agents and does not require any initial information about parameters L or D. Its disadvantage is its complexity: z (D) is exponential in D for any degree d > 2 of the tree. We prove that this high complexity is inevitable: Ω (z (D)) turns out to be a lower bound on rendezvous time in unoriented regular trees, even for simultaneous start and even when agents know L and D. Then we turn attention to oriented trees. While for arbitrary delay between waking times of agents the lower bound Ω (z (D)) still holds, for simultaneous start the time of rendezvous can be dramatically shortened. We show that if agents know either a polynomial upper bound on L or a linear upper bound on D , then rendezvous can be accomplished in oriented trees in time O (D log ⁡ L) , which is optimal. If no such extra knowledge is available, a significant speedup is still possible: in this case we design an algorithm working in time O (D 2 + log 2 ⁡ L). [ABSTRACT FROM AUTHOR]

In this paper, we consider the partial gathering problem of mobile agents in asynchronous tree networks. The partial gathering problem is a generalization of the classical gathering problem, which requires that all the agents meet at the same node. The partial gathering problem requires, for a given positive integer g , that each agent should move to a node and terminate so that at least g agents should meet at each of the nodes they terminate at. The requirement for the partial gathering problem is weaker than that for the (well-investigated) classical gathering problem, and thus, we clarify the difference on the move complexity between them. We consider two multiplicity detection models: weak multiplicity detection and strong multiplicity detection models. In the weak multiplicity detection model, each agent can detect whether another agent exists at the current node or not but cannot count the exact number of the agents. In the strong multiplicity detection model, each agent can count the number of agents at the current node. In addition, we consider two token models: non-token model and removable token model. In the non-token model, agents cannot mark the nodes or the edges in any way. In the removable-token model, each agent initially leaves a token on its initial node, and agents can remove the tokens. Our contribution is as follows. First, we show that for the non-token model agents require Ω ( k n ) total moves to solve the partial gathering problem, where n is the number of nodes and k is the number of agents. Second, we consider the weak multiplicity detection and non-token model. In this model, for asymmetric trees, by a previous result agents can achieve the partial gathering in O ( k n ) total moves, which is asymptotically optimal in terms of total moves. In addition, for symmetric trees we show that there exist no algorithms to solve the partial gathering problem. Third, we consider the strong multiplicity detection and non-token model. In this model, for any trees we propose an algorithm to achieve the partial gathering in O ( k n ) total moves, which is asymptotically optimal in terms of total moves. At last, we consider the weak multiplicity detection and removable-token model. In this model, we propose an algorithm to achieve the partial gathering in O ( g n ) total moves. Note that in this model, agents require Ω ( g n ) total moves to solve the partial gathering problem. Hence, the second proposed algorithm is also asymptotically optimal in terms of total moves. [ABSTRACT FROM AUTHOR]

In this paper, we consider the partial gathering problem of mobile agents in asynchronous unidirectional rings equipped with whiteboards on nodes. The partial gathering problem is a new generalization of the total gathering problem. The partial gathering problem requires, for a given integer g , that each agent should move to a node and terminate so that at least g agents should meet at the same node. The requirement for the partial gathering problem is weaker than that for the (well-investigated) total gathering problem, and thus, we have interests in clarifying the difference on the move complexity between them. We propose three algorithms to solve the partial gathering problem. The first algorithm is deterministic but requires unique ID of each agent. This algorithm achieves the partial gathering in O ( g n ) total moves, where n is the number of nodes. The second algorithm is randomized and requires no unique ID of each agent (i.e., anonymous). This algorithm achieves the partial gathering in expected O ( g n ) total moves. The third algorithm is deterministic and requires no unique ID of each agent. For this case, we show that there exist initial configurations in which no algorithm can solve the problem and agents can achieve the partial gathering in O ( k n ) total moves for solvable initial configurations, where k is the number of agents. Note that the total gathering problem requires Ω ( k n ) total moves, while the partial gathering problem requires Ω ( g n ) total moves in each model. Hence, we show that the move complexity of the first and second algorithms is asymptotically optimal. [ABSTRACT FROM AUTHOR]

The exploration problem has been extensively studied in unsafe networks containing malicious hosts of a highly harmful nature, called black holes , which completely destroy mobile agents that visit them. In a recent work, Královič and Miklík (SIROCCO 2010, LNCS 6058, pp. 157–167) [20] considered various types of malicious host behavior in the context of the Periodic Data Retrieval problem in asynchronous ring networks with exactly one malicious host. In this problem, a team of initially co-located agents must report data from all safe nodes of the network to the homebase, infinitely often. The malicious host can choose whether to kill visiting agents or allow them to pass through (gray hole). In another variation of the model, the malicious host can, in addition, alter its whiteboard contents in order to deceive visiting agents. The goal is to design a protocol for Periodic Data Retrieval using as few agents as possible. In this paper, we present the first nontrivial lower bounds on the number of agents for Periodic Data Retrieval in asynchronous ring networks. Specifically, we show that at least 4 agents are needed when the malicious host is a gray hole, and at least 5 agents are needed when the malicious host whiteboard is unreliable. This improves the previous lower bound of 3 in both cases and answers an open question posed in the aforementioned paper. On the positive side, we propose an optimal protocol for Periodic Data Retrieval in asynchronous rings with a gray hole, which solves the problem with only 4 agents. This improves the previous upper bound of 9 agents and settles the question of the optimal number of agents in the gray-hole case. Finally, we propose a protocol with 7 agents when the whiteboard of the malicious host is unreliable, significantly improving the previously known upper bound of 27 agents. Along the way, we set forth a detailed framework for studying networks with malicious hosts of varying capabilities. [ABSTRACT FROM AUTHOR]

We investigate the parallel traversal of a graph with multiple robots unaware of each other. All robots traverse the graph in parallel forever and the goal is to minimize the time needed until the last node is visited ( first visit time ) and the time between revisits of a node ( revisit time ). We also want to minimize the visit time , i.e. the maximum of the first visit time and the time between revisits of a node. We present randomized algorithms for uncoordinated robots, which can compete with the optimal coordinated traversal by a small factor, the so-called competitive ratio . For any number of robots ring and path graph simple traversal strategies allow constant competitive factors even in the worst case. For grid and torus graphs with n nodes and any number of robots there is an O ( log ⁡ n ) -competitive algorithm for both visit problems succeeding with high probability, i.e. with probability 1 − n − O ( 1 ) . For general graphs we present an O ( log 2 ⁡ n ) -competitive algorithm for the first visit problem, while for the visit problem we show an O ( log 3 ⁡ n ) -competitive algorithm both succeeding with high probability. [ABSTRACT FROM AUTHOR]

Two mobile agents, starting from different nodes of an n -node network at possibly different times, have to meet at the same node. This problem is known as rendezvous . Agents move in synchronous rounds using a deterministic algorithm. In each round, an agent decides to either remain idle or to move to one of the adjacent nodes. Each agent has a distinct integer label from the set { 1 , … , L } , which it can use in the execution of the algorithm, but it does not know the label of the other agent. The main efficiency measure of a rendezvous algorithm's performance is its time , i.e., the number of rounds from the start of the earlier agent until the meeting. If D is the distance between the initial positions of the agents, then Ω ( D ) is an obvious lower bound on the time of rendezvous. However, if each agent has no initial knowledge other than its label, time O ( D ) is usually impossible to achieve. We study the minimum amount of information that has to be available a priori to the agents to achieve rendezvous in optimal time Θ ( D ) . Following the standard paradigm of algorithms with advice , this information is provided to the agents at the start by an oracle knowing the entire instance of the problem, i.e., the network, the starting positions of the agents, their wake-up rounds, and both of their labels. The oracle helps the agents by providing them with the same binary string called advice , which can be used by the agents during their navigation. The length of this string is called the size of advice . Our goal is to find the smallest size of advice which enables the agents to meet in time Θ ( D ) . We show that this optimal size of advice is Θ ( D log ⁡ ( n / D ) + log ⁡ log ⁡ L ) . The upper bound is proved by constructing an advice string of this size, and providing a natural rendezvous algorithm using this advice that works in time Θ ( D ) for all networks. The matching lower bound, which is the main contribution of this paper, is proved by exhibiting classes of networks for which it is impossible to achieve rendezvous in time Θ ( D ) with smaller advice. [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]

Abstract: We consider the problem of gathering identical, memoryless, mobile agents in one node of an anonymous graph. Agents start from different nodes of the graph. They operate in Look-Compute-Move cycles and have to end up in the same node. In one cycle, an agent takes a snapshot of its immediate neighborhood (Look), makes a decision to stay idle or to move to one of its adjacent nodes (Compute), and in the latter case makes an instantaneous move to this neighbor (Move). Cycles are performed asynchronously for each agent. The novelty of our model with respect to the existing literature on gathering asynchronous oblivious agents in graphs is that the agents have very restricted perception capabilities: they can only see their immediate neighborhood. An initial configuration of agents is called gatherable if there exists an algorithm that gathers all the agents of the configuration in one node and keeps them idle from then on, regardless of the actions of the asynchronous adversary. (The algorithm can be even tailored to gather this specific configuration.) The gathering problem is to determine which configurations are gatherable and find a (universal) algorithm which gathers all gatherable configurations. We give a complete solution of the gathering problem for regular bipartite graphs. Our main contribution is the proof that the class of gatherable initial configurations is very small: it consists only of “stars” (an agent with all other agents adjacent to it) of size at least 3. On the positive side we give an algorithm accomplishing gathering for every gatherable configuration. [Copyright &y& Elsevier]

Abstract: Two mobile agents (robots) have to meet in an a priori unknown bounded terrain modeled as a polygon, possibly with polygonal obstacles. Robots are modeled as points, and each of them is equipped with a compass. Compasses of robots may be incoherent. Robots construct their routes, but the actual walk of each robot is decided by the adversary that may, e.g., speed up or slow down the robot. We consider several scenarios, depending on three factors: (1) obstacles in the terrain are present, or not, (2) compasses of both robots agree, or not, (3) robots have or do not have a map of the terrain with their positions marked. The cost of a rendezvous algorithm is the worst-case sum of lengths of the robots’ trajectories until they meet. For each scenario, we design a deterministic rendezvous algorithm and analyze its cost. We also prove lower bounds on the cost of any deterministic rendezvous algorithm in each case. For all scenarios these bounds are tight. [Copyright &y& Elsevier]

Abstract: In an effort to understand the algorithmic limitations of computing by a swarm of robots, the research has focused on the minimal capabilities that allow a problem to be solved. The weakest of the commonly used models is Asynch where the autonomous mobile robots, endowed with visibility sensors (but otherwise unable to communicate), operate in Look-Compute-Move cycles performed asynchronously for each robot. The robots are often assumed (or required to be) oblivious: they keep no memory of observations and computations made in previous cycles. We consider the setting when the robots are dispersed in an anonymous and unlabeled graph, and they must perform the very basic task of exploration: within finite time every node must be visited by at least one robot and the robots must enter a quiescent state. The complexity measure of a solution is the number of robots used to perform the task. We study the case when the graph is an arbitrary tree and establish some unexpected results. We first prove that, in general, exploration cannot be done efficiently. More precisely we prove that there are -node trees where robots are necessary; this holds even if the maximum degree is . On the other hand, we show that if the maximum degree is , it is possible to explore with only robots. The proof of the result is constructive. We also prove that the size of the team used in our solution is asymptotically optimal: there are trees of degree , whose exploration requires robots. Our final result shows that the difficulty in tree exploration comes in fact from the symmetries of the tree. Indeed, we show that, in order to explore trees that do not have any non-trivial automorphisms, 4 robots are always sufficient and often necessary. [Copyright &y& Elsevier]

We introduce a new combinatorial game between two players: Magnus and Derek. Initially, a token is placed at position 0 on a round table with positions. In each round of the game Magnus chooses the number of positions for the token to move, and Derek decides in which direction, + (clockwise) or − (counterclockwise), the token will be moved. Magnus aims to maximize the total number of positions visited during the course of the game, while Derek aims to minimize this quantity. We define to be the eventual size of the set of visited positions when both players play optimally. We prove a closed form expression for in terms of the prime factorization of , and provide algorithmic strategies for Magnus and Derek to meet this bound. We note the relevance of the game for a mobile agent exploring a ring network with faulty sense of direction, and we pose variants of the game for future study. [Copyright &y& Elsevier]

Abstract: Mobile-agent-based distributed systems are attracting widespread attention because of their adaptability and flexibility; mobile agents traverse the system and carry out a task at each node. In mobile-agent-based systems, gossip is a fundamental task in cooperation among mobile agents. It requires one to accomplish all-to-all information exchange over all agents so that each agent can obtain the information each agent initially has. While rendezvous algorithms, which require that all agents rendezvous on a node at the same time, can achieve this requirement, it takes excessive cost for our objective. In this paper, we introduce the mobile agent gossip problem, in which each agent must obtain the information all other agents have. Each agent can obtain the information of by meeting itself or any agent that already has information of . Thus, the gossip is expected to accomplish the all-to-all information exchange with a smaller number of agents’ moves than the rendezvous algorithms. In this paper, we investigate the complexity of the mobile agent gossip problem in terms of the total number of moves performed by agents. For several network topologies, we show the asymptotically tight upper and lower bounds for move complexity. This result is obtained from the fact that the mobile agent gossip problem and the node leader election problem is reducible to each other. [Copyright &y& Elsevier]

A black hole is a highly harmful stationary process residing in a node of a network and destroying all mobile agents visiting the node without leaving any trace. The Black Hole Search is the task of locating all black holes in a network by exploring it with mobile agents. We consider the problem of designing the fastest Black Hole Search, given the map of the network and the starting node. We study the version of this problem that assumes that there is at most one black hole in the network and there are two agents, which move in synchronized steps. We prove that this problem is NP-hard in arbitrary graphs (even in planar graphs), solving an open problem stated in [J. Czyzowicz, D. Kowalski, E. Markou, A. Pelc, Searching for a black hole in tree networks, in: Proc. 8th Int. Conf. on Principles of Distributed Systems, OPODIS 2004, 2004, pp. 34–35. Also: Springer LNCS, vol. 3544, pp. 67–80]. We also give a -approximation algorithm, showing the first non-trivial approximation ratio upper bound for this problem. Our algorithm follows a natural approach of exploring networks via spanning trees. We prove that this approach cannot lead to an approximation ratio bound better than 3/2. [Copyright &y& Elsevier]

Abstract: A finite automaton, simply referred to as a robot, has to explore a graph whose nodes are unlabeled and whose edge ports are locally labeled at each node. The robot has no a priori knowledge of the topology of the graph or of its size. Its task is to traverse all the edges of the graph. We first show that, for any K-state robot and any , there exists a planar graph of maximum degree d with at most nodes that the robot cannot explore. This bound improves all previous bounds in the literature. More interestingly, we show that, in order to explore all graphs of diameter D and maximum degree d, a robot needs memory bits, even if we restrict the exploration to planar graphs. This latter bound is tight. Indeed, a simple DFS up to depth enables a robot to explore any graph of diameter D and maximum degree d using a memory of size bits. We thus prove that the worst case space complexity of graph exploration is bits. [Copyright &y& Elsevier]