# Asynchronous Gathering in a Dangerous Ring +
## 1 Introduction
### Background  
**Gathering.** The _gathering_ problem consists in having the agents meet at the same node and enter a terminal state within a finite amount of time; there is no a priori restriction on which node will become the gathering point. The gathering problem has been extensively investigated under a large variety of settings and communication mechanisms. In anonymous and symmetric settings, like the one considered here, the possibility (and difficulty) of a solution is related to the possibility (and difficulty) to deterministically find or create an asymmetry in the system, enabling the agents to agree on a meeting point.  
The majority of investigations have focused on the case of _two_ agents, very few results are known for anonymous ring networks (see [4] for a recent survey). Almost all these investigations have assumed _synchronous_ agents: the agents are synchronized and the amount of time required by an agent for processing and for movement along a link is one unit; this assumption is crucial for the correctness of their solutions.  
In the _asynchronous_ setting, interestingly, the link between gather and symmetry breaking is even more clear: gathering is in fact equivalent to the _election_ problem [5]. Few papers have examined gathering in the asynchronous setting (see [6; 7; 8]) usually assuming two agents with distinct IDs.  
Recall that, in our setting, both nodes and agents are _anonymous_, and the system is fully _asynchronous_.  
**Black Hole Search.** Among the severe security threats faced in systems supporting mobile agents, a particularly troublesome one is a _harmful host_; that is, the presence at a network site of harmful stationary processes. The problem posed by the presence of a harmful host has been intensively studied from a programming point of view (e.g., see [9; 10; 11]), and also from an algorithmic prospective [12]. Obviously, the first step in any solution to such a problem must be to _identify_, if possible, the harmful host determining its location. Depending on the nature of the danger, the task to identify the harmful host might be difficult, if not impossible, to perform.  
A particularly harmful host is a _black hole_: a host that disposes of visiting agents upon their arrival, leaving no observable trace of such a destruction. Note that this type of highly harmful host is not rare; for example, the undetectable crash failure of a site in an asynchronous network transforms that site into a black hole [3].  
The _Black Hole Search_ problem is to determine the location of the black hole; it is solved if, within a finite amount of time, at least one agent survives and knows the location of the black hole. This problem has been extensively investigated, both in synchronous and asynchronous networks (e.g., [13; 14; 15; 16; 17; 18; 19; 20; 21; 22; 23; 24; 25]; see [26] for a recent survey). The case when the network is an _asynchronous ring_ (the setting considered here) has been investigated (e.g., [13; 27; 28]); however, with the exception of [28], these investigations assume that all agents start from the same node (i.e., they are initially gathered). The best known bounded time complexity for this problem is \(O(n\log n)\)[13].  
Summarizing, in spite of the literature on both gathering and black hole search in asynchronous settings (see [4; 26] for recent surveys on the two topics), no results exist on gathering in the presence of a black hole.