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$.

Abstract We consider two finite and disjoint sets of homogeneous robots deployed at the nodes of an infinite grid graph. The grid graph also comprises two finite and disjoint sets of prefixed meeting nodes located over the nodes of the grid. The objective of our study is to design a distributed algorithm that gathers all the robots belonging to the first team at one of the meeting nodes belonging to the first type, and all the robots in the second team must gather at one of the meeting nodes belonging to the second type. The robots can distinguish between the two types of meeting nodes. However, a robot cannot identify its team members. This paper assumes the strongest adversarial model, namely the asynchronous scheduler. We have characterized all the initial configurations for which the gathering problem is unsolvable. For the remaining initial configurations, the paper proposes a distributed gathering algorithm. Assuming the robots are capable of global-weak multiplicity detection, the proposed algorithm solves the problem within a finite time period. The algorithm runs in $\Theta (dn)$ moves and $O(dn)$ epochs, where $d$ is the diameter of the minimum enclosing rectangle of all the robots and meeting nodes in the initial configuration, and $n$ is the total number of robots in the system.

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.

We propose a scheme for evaluating four commonly used functions namely, (1) inverse trigonometric functions, (2) trigonometric functions, (3) the exponential function, and (4) the logarithmic function with the help of a logarithmic number system (LNS) processor. A novel idea of series folding has been introduced for computing the above functions, expressed in the form of infinite series. We also show that with a suitable choice of the radix for the LNS we can evaluate exponential and logarithmic functions without using any extra hardware.>

The ring network is a popular network topology for implementation in local area networks and other configurations. But it has a disadvantage of high diameter and large communication delay. So loop networks were introduced with fixed-jump links added over the ring. In this paper, we characterize some values for the number of nodes for which the lower bound on the diameter of loop networks is achieved. We also give an O(/spl delta/) time algorithm (where /spl delta/ is the diameter of the graph) for finding a shortest path between any two nodes of a general loop network. We also propose a scheme to find a near optimal path (not more than one over the optimal) in case of a single node or link failure.

We show that by adding eight extra edges, referred to as bridges, to an n-cube (n/spl ges/4) its diameter can be reduced by 2, and by adding sixteen bridges to an n-cube (n/spl ges/6) its diameter can be reduced by 3. We also show that by adding (/sub m+1sup 4m/)+1(m/spl ges/2) bridges to an n-cube (n/spl ges/4m and n/spl ges/8) its diameter can be reduced by 2m and by adding 2(/sub msup 4m-3/)+1, (m>2) to an n-cube (n/spl ges/4m-2 and n/spl ges/10) its diameter can be reduced by 2m-1. We also consider the reduction of diameter of an n-cube by exchanging some independent edges (twisting), where two edges are called independent if they are not incident on a common node. We have shown that by exchanging four pairs of independent edges in a d-cube (d/spl ges/5), we can reduce its diameter by 2. By exchanging sixteen pairs of independent edges, the diameter of a d-cube (d/spl ges/7) can be reduced by 3. By exchanging 57 pairs of independent edges, the diameter can be reduced by 4 for d/spl ges/9. To reduce the diameter by lower bound [d/2], (d/spl ges/10) we need to exchange (/sub r+1sup d-1/) pairs of independent edges, where r=lower bound [d/4]+1.>