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 in striking contrast to the rendezvous problem which requires the agents to meet at the same node. While rendezvous aims to break the symmetry, uniform deployment aims to attain the symmetry. It is well known that the symmetry breaking is difficult in distributed systems and the rendezvous problem cannot be solved from some initial configurations . Hence, we are interested in clarifying what difference the uniform deployment problem has on the solvability and the number of agent moves compared to the rendezvous problem. We consider two problem settings, with knowledge of k (or n ) and without knowledge of k or n where k is the number of agents and n is the number of nodes. First, we consider agents with knowledge of k (or n since k and n can be easily obtained if one of them is given). In this case, we propose two algorithms. The first algorithm solves the uniform deployment problem with termination detection. This algorithm requires O ( k log n ) memory space per agent, O ( n ) time, and O ( k n ) total moves. The second algorithm also solves the uniform deployment problem with termination detection. This algorithm reduces the memory space per agent to O ( log n ) , but uses O ( n log k ) time, and requires O ( k n ) total moves. Both algorithms are asymptotically optimal in terms of total moves since there are some initial configurations such that agents require Ω ( k n ) total moves to solve the problem. 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 space per agent, O ( n ∕ l ) time, and O ( k n ∕ l ) total moves when the initial configuration has symmetry degree l . This means that the algorithm can solve the problem more efficiently when the initial configuration has higher symmetric degree (i.e., is closer to uniform deployment). Note that all the proposed algorithms achieve 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 .

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.