Search

Consider a set of k identical asynchronous mobile agents located in an anonymous ring of n nodes. The classical Gather (or Rendezvous) problem requires all agents to meet at the same node, not a priori decided, within a finite amount of time. This problem has been studied assuming that the network is safe for the agents. In this paper, we consider the presence in the ring of a stationary process located at a node that disables any incoming agent without leaving any trace. Such a dangerous node is known in the literature as a black hole, and the determination of its location has been extensively investigated. The presence of the black hole makes it deterministically unfeasible for all agents to gather. So, the research concern is to determine how many agents can gather and under what conditions. In this paper we establish a complete characterization of the conditions under which the problem can be solved. In particular, we determine the maximum number of agents that can be guaranteed to gather in the same location depending on whether k or n is unknown (at least one must be known). These results are tight: in each case, gathering with one more agent is deterministically unfeasible. All our possibility proofs are constructive: we provide mobile agent algorithms that allow the agents to gather within a predefined distance under the specified conditions. The analysis of the time costs of these algorithms show that they are optimal. Our gathering algorithm for the case of unknown k is also a solution for the black hole location problem. Interestingly, its bounded time complexity is Θ (n) ; this is a significant improvement over the existing O (n log n) bounded time complexity. [ABSTRACT FROM AUTHOR]

We consider, for the first time, the exploration of dynamic graphs of arbitrary unknown topology. We study the number of agents necessary and sufficient to explore such graphs under the fully synchronous (Fsync) and the semi-synchronous (Ssync) activation schedulers. We prove that, under the minimal assumption on the dynamics, temporal connectivity , the number of agents sufficient to perform exploration depends on a parameter we call evanescence of the graph, and this number is tight. We then consider the stronger well-known assumption of 1-interval connectivity when the number of edges missing at each time is bounded. We provide tight bounds also in this setting, proving the existence of a difference between Fsync and Ssync , as well as between anonymous and non-anonymous agents. [ABSTRACT FROM AUTHOR]

The gathering (or multi-agent rendezvous) problem requires a set of mobile agents, arbitrarily positioned at different nodes of a network to group within finite time at the same location, not fixed in advanced. The extensive existing literature on this problem shares the same fundamental assumption: the topological structure does not change during the rendezvous or the gathering; this is true also for those investigations that consider faulty nodes. In other words, they only consider static graphs. In this paper we start the investigation of gathering in dynamic graphs , that is networks where the topology changes continuously and at unpredictable locations. We study the feasibility of gathering mobile agents, identical and without explicit communication capabilities, in a dynamic ring of anonymous nodes; the class of dynamics we consider is the classic 1-interval-connectivity ; i.e., dynamic graphs that are however connected at any point in time. We focus on the impact that factors such as chirality (i.e., a common sense of orientation) and cross detection (i.e., the ability to detect, when traversing an edge, whether some agent is traversing it in the other direction), have on the solvability of the problem; and we establish several results. We provide a complete characterization of the classes of initial configurations from which the gathering problem is solvable in presence and in absence of cross detection and of chirality. The feasibility results of the characterization are all constructive: we provide distributed algorithms that allow the agents to gather within low polynomial time. In particular, the algorithms for gathering with cross detection are time optimal. We also show that cross detection is a powerful computational element. Indeed, we prove that, without chirality, knowledge of the ring size n is strictly more powerful than knowledge of the number k of agents; on the other hand, with chirality, knowledge of n can be substituted by knowledge of k , yielding the same classes of feasible initial configurations. From our investigation it follows that, for the gathering problem, the computational obstacles created by the dynamic nature of the ring can be overcome by the presence of chirality or of cross-detection. [ABSTRACT FROM AUTHOR]

Abstract: We study the computability and complexity of the exploration problem in a class of highly dynamic networks: carrier graphs, where the edges between sites exist only at some (unknown) times defined by the periodic movements of mobile carriers among the sites. These graphs naturally model highly dynamic infrastructure-less networks such as public transports with fixed timetables, low earth orbiting (LEO) satellite systems, security guards’ tours, etc. We focus on the opportunistic exploration of these graphs, that is by an agent that exploits the movements of the carriers to move in the network. We establish necessary conditions for the problem to be solved. We also derive lower bounds on the amount of time required in general, as well as for the carrier graphs defined by restricted classes of carrier movements. We then prove that the limitations on computability and complexity we have established are indeed tight. In fact we prove that all necessary conditions are also sufficient and all lower bounds on costs are tight. We do so constructively by presenting two optimal solution algorithms, one for anonymous systems, and one for those with distinct node IDs. [Copyright &y& Elsevier]