Gathering identical autonomous systems on a circle using stigmergy

In this paper we provide a protocol solving the problem of gathering of identical autonomous systems (aka ants) on a circle. In our biologically inspired model the autonomous systems are unable to communicate directly, instead they employ the mechanism of pheromone marking. The gathering on a circle is not always solvable, however our protocol will terminate in finite time if ants are in a general initial position. Since the gathering problem on a line is unsolvable for obvious reasons for any non-degenerate initial position, this implies that if the ants are in generic initial position they will be able to decide in finite time whether they are on a line or on a circle. We give asymptotic bounds for the time our protocol needs to terminate, and show that for fixed number of ants, the termination time of any protocol can be arbitrarily long. Finally, our protocol may be adopted to the case of asynchronous drop-downs and starting times of the autonomous systems.