Deterministic rendezvous for two anonymous mobile agents navigating synchronously in an anonymous connected graph calls for their meeting at some node. This is a distributed symmetry breaking task equivalent to the fundamental task of leader election between the agents. An instance of the rendezvous problem is the underlying graph, together with two distinct nodes that are initial positions of the agents. Such an instance is feasible if there is a deterministic algorithm, possibly valid only for this instance, that guarantees rendezvous for it. A rendezvous algorithm is universal for a class of instances, if it is valid for all feasible instances from this class.

Abstract The $k$-circle formation problem requires a swarm of robots to divide themselves into groups of equal sizes and to form disjoint circles by each group. Each circle must be centered at one of the pre-fixed points given in the plane and should contain exactly $k$ distinct robot positions. The $k$-circle formation problem has already been studied for dimensionless robots represented by points in the plane. In all the reported results, the circles need not be uniform. In this paper, we investigate the uniform $k$-circle formation problem for a swarm of robots with dimensional extent in the plane. The robots are represented by transparent unit disks. The robots are autonomous, anonymous, homogeneous, and silent. They are oblivious and they execute Look-Compute-Move cycle under a fair asynchronous scheduler. The robots are assumed to have an agreement on the direction and orientation of one of the axes. First, all the initial configurations and values of $k$ for which the uniform $k$-circle formation problem is deterministically unsolvable have been characterized. Next, a deterministic distributed algorithm has been proposed that solves the uniform $k$-circle formation problem for the remaining configurations and values of $k$. Also, we have characterized all the deterministically solvable initial configurations when $n\neq km$.

The gathering over meeting nodes problem asks the robots to gather at one of the pre-defined meeting nodes. The robots are deployed on the nodes of an anonymous two-dimensional infinite grid, which has a subset of nodes marked as meeting nodes. Robots are identical, autonomous, anonymous and oblivious. They operate under an asynchronous scheduler. They do not have any agreement on a global coordinate system. All the initial configurations for which the problem is deterministically unsolvable have been characterized. A deterministic distributed algorithm has been proposed to solve the problem for the remaining configurations. The efficiency of the proposed algorithm is studied in terms of the number of moves required for gathering. A lower bound concerning the total number of moves required to solve the gathering problem has been derived.