Uniform Deployment of Mobile Agents in Asynchronous Rings
Masahiro Shibata, Toshiya Mega, Fukuhito Ooshita, Hirotsugu Kakugawa, Toshimitsu Masuzawa · 2016
In this paper, we consider the uniform deployment problem of mobile agents in asynchronous unidirectional rings, which requires the agents to uniformly spread in the ring. The uniform deployment problem is striking contrast to the rendezvous problem which requires the agents to meet at the same node. While the rendezvous aims to break the symmetry, the uniform deployment aims to attain the symmetry. Hence, we are interested in clarifying how easily the uniform deployment problem can be solved compared to the rendezvous problem. We consider two problem settings. First, we consider agents with knowledge of k, where k is the number of agents. In this case, our proposed algorithm solves the uniform deployment problem with termination detection. This algorithm requires O(log n) memory per agent, O(n log k) time, and O(kn) total moves, where n is the number of nodes. Next, we consider agents with no knowledge of k or n. In this case, we show that, when termination detection is required, there exists no algorithm to solve the uniform deployment problem. For this reason, we consider the relaxed uniform deployment problem that does not require termination detection, and we propose an algorithm to solve the relaxed uniform deployment problem. This algorithm requires O(k/l log (n/l)) memory per agent, O(n/l) time, and O(kn/l) total moves, where l is the symmetry degree of the initial configuration (l ≥ 1). Note that both the algorithms achieve the uniform deployment from any initial configuration, which is a striking difference from the rendezvous problem because the rendezvous problem is not solvable from some initial configurations.