# Asynchronous Gathering in a Dangerous Ring +
## 2 Definitions, Basic Properties, and Techniques  
### Model  
The network environment is a ring \(\mathcal{R}\) of \(n\)_anonymous_ (i.e., identical) nodes. Each node has two labeled ports and a bounded amount of storage, called _a whiteboard_. In this network there is a set \(\mathcal{A}=\{a_{1},\ldots,a_{k}\}\) of \(k\)_anonymous_ (i.e., identical) mobile agents. The agents can move from node to neighboring node in \(\mathcal{R}\), have computing capabilities and bounded storage, obey the same set of behavioral rules (the \"algorithm\"), and all their actions (e.g., computation, movement, etc.) take a finite, but otherwise unpredictable, amount of time (i.e., they are _asynchronous_). Agents communicate by reading from and writing on the whiteboard in the node where they currently are; access to a whiteboard uses fair mutual exclusion. The agents execute an algorithm (the same for all agents) that specifies the computational and navigational steps. Each agent has a local orientation that allows them to distinguish \"left\" from \"right\". If the orientation is the same for all agents, we say that the ring is _oriented_, otherwise it is _unoriented_. Given an agent \(a\) on a node \(u\) of the ring, we will denote by \(right_{a}(u)\) and \(left_{a}(u)\) the port labels of \(u\), according to the local orientation of agent \(a\). Initially, each agent is placed at a distinct node, called its _homebase_, and has a predefined state variable set to _available_. Let us denote by \(x_{i}\) the homebase of agent \(a_{i}\). Each homebase is initially marked (in the whiteboard) as such by the corresponding agent. Agents can move from node to neighboring node; while crossing an edge, an agent can detect whether there is another agent crossing that edge in the opposite direction at the same time. The agents are aware of the fact that, in the network there is a _black hole_ (BH), a node that _disposes_ of visiting agents upon their arrival, leaving _no observable trace_ of such a destruction; its location is unknown. The initial location of the agents, the location of the black hole, the duration of each operation of the agents, and, in the case of unoriented rings, the sense of orientation of each agent, are assumed to be under the control of a worst-case adversary. In this environment, we are going to consider the _gathering_ problem and the _close-gathering_ problem defined below. The _gathering_ problem \(RV(f(k))\) requires having at least \(f(k)\leq k\) agents gathering in the same site, with \(f\) being an arbitrary monotonic and non-decreasing function. There is no a priori restriction on which node will become the gathering point. The problem is solved if at least \(f(k)\) agents are at the same node in a terminal state, denoted by _arrived_. The _close-gathering_ problem \(G(f(k),d)\) requires having at least \(f(k)\) agents within distance \(d\) from each other. The problem is solved if at least \(f(k)\) agents are within distance \(d\) from each other and are in a terminal state. Clearly, \(G(f(k),0)=RV(f(k))\). The efficiency of a solution algorithm is first and foremost measured in the _size_ of the solution, i.e., the number of agents that the algorithm will make gather at the same location in the case of _gathering_, and the number of agents that will be at distance \(d\) from each other in the case of _close-gathering_. A secondary but important cost measure is the amount of _time_ elapsed from the beginning to the termination of the algorithm. Since the agents are asynchronous, \"real\" time cannot be measured. We will use the traditional measure of _bounded time_, where it is assumed that the traversal of a link takes at most one time unit. Usually, the time is measured from the moment the first agent wakes up. However, in our setting, the first agent to wake up might immediately enter the black hole, and an indeterminate amount of time may pass before other agents wake up.