Deterministic Dispersion of Mobile Robots in Dynamic Rings
Ankush Agarwalla∗

John Augustine†

William K. Moses Jr.‡

Madhav Sankar K.§

arXiv:1707.06391v3 [cs.DC] 16 Oct 2017

Arvind Krishna Sridhar¶

Abstract
In this work, we study the problem of dispersion of mobile robots on dynamic rings. The problem of
dispersion of n robots on an n node graph, introduced by Augustine and Moses Jr. [1], requires robots to
coordinate with each other and reach a configuration where exactly one robot is present on each node.
This problem has real world applications and applies whenever we want to minimize the total cost of n
agents sharing n resources, located at various places, subject to the constraint that the cost of an agent
moving to a different resource is comparatively much smaller than the cost of multiple agents sharing
a resource (e.g. smart electric cars sharing recharge stations). The study of this problem also provides
indirect benefits to the study of scattering on graphs, the study of exploration by mobile robots, and the
study of load balancing on graphs.
We solve the problem of dispersion in the presence of two types of dynamism in the underlying graph:
(i) vertex permutation and (ii) 1-interval connectivity. We introduce the notion of vertex permutation
dynamism and have it mean that for a given set of nodes, in every round, the adversary ensures a ring
structure is maintained, but the connections between the nodes may change. We use the idea of 1-interval
connectivity from Di Luna et al. [10], where for a given ring, in each round, the adversary chooses at
most one edge to remove.
We assume robots have full visibility and present asymptotically time optimal algorithms to achieve
dispersion in the presence of both types of dynamism when robots have chirality. When robots do not
have chirality, we present asymptotically time optimal algorithms to achieve dispersion subject to certain
constraints. Finally, we provide impossibility results for dispersion when robots have no visibility.

Keywords: Dispersion, Load balancing, Mobile robots, Collective robot exploration, Scattering, Uniform deployment, Dynamic graph algorithms, Dynamic networks, Deterministic algorithms, Distributed
algorithms

1
1.1

Introduction
Background and Motivation

The paradigm of using mobile robots to study distributed problems in a network is an interesting and much
studied area. Each robot represents a computational machine with the ability to move, either in a geometric
∗ Department of Computer Science & Engineering, National Institute of Technology Rourkela, Rourkela, India.
ankush.agarwalla7@gmail.com. Work done during internship at IIT Madras.
† Department of Computer Science & Engineering, Indian Institute of Technology Madras, Chennai, India.
augustine@iitm.ac.in. Research supported in part by an Extra-Mural Research Grant (file number EMR/2016/003016) funded
by the Science and Engineering Research Board, Department of Science and Technology, Government of India.
‡ Department of Computer Science and Engineering, Indian Institute of Technology Madras, Chennai, India.
wkmjr3@gmail.com. Research supported in part by an Extra-Mural Research Grant (file number EMR/2016/003016) funded
by the Science and Engineering Research Board, Department of Science and Technology, Government of India.
§ Department of Computer Science & Engineering, National Institute of Technology Tiruchirappalli, Tiruchirappalli, India.
madhavsankar@gmail.com. Work done during internship at IIT Madras.
¶ Department of Computer Science & Engineering, National Institute of Technology Tiruchirappalli, Tiruchirappalli, India.
arvindkrishna1997@gmail.com. Work done during internship at IIT Madras.

1

space or in a graph. Typically these robots must coordinate with each other to either achieve some specific
configuration on the graph or else perform some sort of distributed calculation of a property of the graph
(e.g., count the number of nodes of the graph).
The particular problem of dispersion was introduced in [1] and asks n robots on an n node graph to
coordinate and reach a configuration, as quickly as possible, such that exactly one robot is present on each
node. It is generally applicable to any real world scenario where n agents must coordinate and share n
resources, located at various places, where we want to minimize the total cost of solving the problem subject
to the constraint that the cost of agents moving around on the graph is dwarfed by the cost of having
more than one agent share a given resource. For example, consider smart electric cars coordinating amongst
themselves to find recharge stations. It may take 30 minutes to drive to reach any given station, but it takes
hours to recharge a given car. We want all cars to recharge as soon as possible. Thus, it is in the interests
of the car manufacturer to design an algorithm that would allow cars to coordinate with each other and end
up such that at most one car uses any given recharge center, when possible.
In addition to its immediate real world applications, the study of dispersion benefits three other research
areas: (i) the study of scattering or uniform deployment of agents on a graph, (ii) the study of exploration
of mobile robots on a graph, and (iii) the study of load balancing on a graph.
For a given graph with n nodes, the problem of scattering [3, 14, 29] of k ≤ n robots requires robots to
coordinate and move such that they end up uniformly deployed over the graph. When k = n, the problem
of scattering is exactly that of dispersion on the same graph.
For a given graph with n nodes, n robot collaborative exploration [12, 19, 13, 5, 6, 20, 11] asks that these
robots coordinate amongst each other and collectively visit every node of the graph at least once. Notice that
any solution to dispersion immediately applies to n robot collaborative exploration for the same assumptions
and model parameters. Thus any solutions for dispersion can be directly applied to collaborative exploration.
Load balancing on graphs [4, 28, 7, 30, 26] asks that n resources be equally split amongst the n nodes on
the graph in as few rounds as possible. Typically, the nodes control where different resources go and there
are usually constraints on how much load may pass through a given edge in a round. If we consider robots
as the resources, notice that the problem is very similar to dispersion. It is our hope that further study of
dispersion will eventually lead to a mechanism that would allow cross-use of techniques and tools between
the areas of mobile robots and load balancing.
The introduction of dynamism into the network makes the problem very interesting, as modern day
networks change rapidly. Mobile robots themselves as physical robots may have to perform their tasks in
physically changing environments. With the relationship dispersion has to load balancing, it may be possible
to uncover useful strategies to deal with balancing resources when processors go down and are replaced by
others or the connections between different processors change.

1.2

Related Work

The problem of dispersion using mobile robots was first studied in [1], where the authors studied the trade-off
between time to dispersion and memory required by each robot for different types of static graphs.
A related problem is that of scattering or uniform deployment, where k ≤ n robots have to uniformly
deploy themselves in a given network with n nodes. [3] looked into this problem on grids while [14, 29]
looked into this problem on static rings. In [14], they present various possibility and impossibility results in
a synchronous system for oblivious robots with limited visibility and which don’t know the size of the ring
or total number of robots. However, for their algorithms they require that no two robots start on the same
node, which in the case of n robot scattering, implies that scattering is trivial. In [29], they present various
possibility and impossibility results in an asynchronous system.
Another closely related problem to dispersion is exploration, where one or more robots start at a given
node and try to collectively visit all vertices of the graph as quickly as possible. Exploration of rings by
mobile robots has been a long studied problem and there is much literature on it. In particular, several
works have studied deterministic exploration of anonymous, unoriented rings by oblivious robots that relied
on their view of the ring to make decisions [25, 8, 9, 16]. Exploration in an asynchronous setting was studied
in [25, 16, 9] while [8] looked into the synchronous setting.
2

In this paper, we prove impossibility results on myopic robots achieving dispersion on a dynamic ring. A
robot is myopic when its visibility is restricted to a subset of nodes of the entire ring. [8] provides positive and
negative results for varied degrees of myopicness of robots for different levels of synchronicity of networks. Of
particular interest, they provide synchronous deterministic algorithms for robots with no visibility to explore
a static ring. For rings of size 3 ≤ n ≤ 6, k = n − 1 robots are required (note when n = 6, only 4 robots are
required) and for rings of size n ≥ 7, 5 robots are required.
When k robots all start at a given node and coordinate to explore a graph, it is referred to as k robot
collaborative graph exploration [12, 19, 13, 5, 6, 20, 11]. When k = n, any solution to dispersion also acts
as a solution to k robot exploration under the same conditions.
Exploration on dynamic rings has been investigated in [22, 10] under different variants of 1-interval
connectivity dynamism. The notion of 1-interval connectivity dynamism was introduced in [27] for complete
graphs and requires an adversary to connect the nodes of the graph such that in every round there must exist
a connected spanning subgraph of the nodes. This model was studied by [27], [22], and [21] for complete
graphs, rings and cactuses respectively. [10] studied the model where for a given ring of nodes, in each round
an adversary chooses at most one edge of the ring and removes it for that round. This definition is restricted
in that it does not allow nodes in the ring to have different neighbors in different rounds. In [10], for a fully
synchronous system they proved that for an anonymous ring if size of ring is not known, then it is impossible
to achieve exploration with termination. They also showed that if termination is not needed, exploration is
possible under those conditions. If ring is anonymous and an upper bound on its size N is known, then if
robots have chirality, exploration with termination can be achieved in 3N time. Whereas without chirality,
exploration with termination can be achieved in 5N time. In [22], they show that for a fully synchronous
system, if an agent knows the entire graph every round, then exploration can be achieved in 2n − 2 rounds.
When the agent only knows its neighborhood each round, exploration is achieved in n + n(δ − 1) ± Θ(δ)
rounds, where δ is the length of the interval such that every edge of the graph is present at least once every
δ rounds.
Exploration of graphs in presence of other types of dynamism has been studied extensively in the literature. Exploration of a dynamic graph where the graph is being modified by an oblivious adversary has been
done in [2]. Exploration on temporal graphs has been studied in [15] where the edge set can change from
step to step. Exploration of periodic time-varying graphs has been studied in [18] and [17].
[24] serves as a good survey on the various models for dynamic networks, both random and adversarial,
and algorithms for these models.
Load balancing is the uniform distribution of load among the nodes. If we think of the robots as load,
then we can think of dispersion as load balancing on graphs with “smart” load. We refer to each load as
smart because it is the load that makes the decisions of where to move as opposed to the nodes. Divergence
in the literature arises from the type of load being balanced (either discrete [4, 28] or continuous [26]) and the
type of model employed (either diffusion or dimension exchange). In the case of diffusion [7, 30, 26], every
node balances its load concurrently with all its neighbors in each round while in the dimension exchange
model [31], each node balances load with at most one neighbor in each round. The work done in this paper
is closer to the diffusion model of load balancing with discrete load. Load balancing on a ring in particular
was looked at in [4, 28].

1.3

Our Results

We develop several deterministic algorithms for robots to achieve dispersion on a ring in the presence of
different types of dynamism and the ability of robots to have chirality or not. All algorithms present have
running time O(n) rounds and are asymptotically time optimal. This is easy to see since if all robots are
present on a given node in some configuration, it takes Ω(n) rounds for any robot to reach the node farthest
away from the given node. We also provide impossibility results when robots have no visibility. To the best
of our knowledge, this is the first work that analyzes dispersion in a dynamic setting.
We consider two types of dynamism: (i) vertex permutation and (ii) 1-interval connectivity. We introduce
the notion of vertex permutation dynamism and use it to mean that for a given set of nodes, in every round,
the adversary may change the order of the nodes while still maintaining a ring structure. We use the restricted
3

definition of 1-interval connectivity from [10] which says that for a given ring of nodes, in every round, the
adversary can choose to remove at most one edge from the ring. Most of our main algorithms are valid in
the presence of both vertex permutation and 1-interval connectivity. The combination of these two types
of dynamism models the more general definition of 1-interval connectivity from [27, 23] for the restricted
setting of rings.
Recall that an algorithm to solve dispersion on a ring also solves collaborative exploration and scattering
on a ring under the same conditions and assumptions. Thus, this paper not only presents solutions to the
problem of dispersion, but shows how multi-robot exploration and also scattering may be carried out in the
presence of vertex permutation and 1-interval connectivity.
We first assume robots have chirality and full visibility and develop deterministic algorithms for increasing levels of dynamism. Algorithm VP-Chain achieves dispersion on a ring in the presence of vertex
permutation dynamism. We extend the ideas present in that algorithm and design algorithm VP-1-IntervalChain to achieve dispersion in the presence of both vertex permutation dynamism and 1-interval connectivity
dynamism.
When robots do not have chirality, we design algorithms to achieve dispersion under certain constraints
in the presence of both vertex permutation and 1-interval connectivity dynamism. If all robots are initially
located at the same node, then by running algorithm No-Chir-Preprocess and then VP-1-Interval-Chain,
they can achieve dispersion. If the ring is an odd size ring, then robots running algorithm Achiral-Odd-VP1-Interval-Chain achieve dispersion. If the ring is of size 4, then robots running algorithm Achiral-Even4VP-1-Interval-Chain achieve dispersion.
We subsequently show that deterministic dispersion is impossible to achieve in the face of either vertex
permutation dynamism or 1-interval connectivity dynamism when robots have no visibility. We also provide
corollaries that show that when the adversary has additional powers, dispersion with no visibility robots in
the face of either type of dynamism is impossible even when algorithm designers have access to random bits.

1.4

Organization of Paper

The rest of this paper is organized as follows. Section 2 provides definitions and technical preliminaries
required for the rest of the paper. Section 3 provides our algorithm for robots with full visibility and
chirality to achieve dispersion in the presence of only vertex permutation dynamism. Section 4 provides
our algorithm for robots with full visibility and chirality to achieve dispersion in the presence of both
vertex permutation and 1-interval connectivity dynamism. Section 5 presents our results for dispersion in
the presence of vertex permutation and 1-interval connectivity when robots have full visibility but do not
have chirality. In Section 6, we present our impossibility results for achieving dispersion for both vertex
permutation dynamism and 1-interval connectivity dynamism when robots have no visibility. Finally, in
Section 7, we present our conclusions and some open questions.

2
2.1

Technical Preliminaries
Structure of Ring

We consider an n node anonymous ring, i.e. each node does not have any label. The multiplicity of a node is
the number of robots present on that node. We classify nodes in each round based on their multiplicities in
that round. A hole is a node not containing any robots. A singleton node is a node containing exactly one
robot. A multinode is a node containing two or more robots. A node containing one or more robots is said
to be occupied. We define a chain as a sequence of nodes in the following order: a multinode followed by zero
or more singleton nodes and finally a hole. When we only consider the order of nodes in the ring in clockwise
order, we call any such chain that occurs a clockwise chain. Similarly, we define an anticlockwise chain.
We define a good chain as a chain where the adversary has not removed an edge between any of the nodes
of the chain. We define a bad chain as a chain where the adversary has removed an edge between two of

4

the nodes of the chain. Examples of a clockwise good chain and a clockwise bad chain are illustrated in
Figures 1 and 2 respectively.

Figure 1: Example of a clockwise good chain

2.2

Figure 2: Example of a clockwise bad chain

Nature of Dynamism

We consider two forms of dynamism: (i) vertex permutation and (ii) 1-interval connectivity. We introduce
the notion of vertex permutation dynamism in this paper and define it as follows. In each round, the nodes
of the ring are shuffled by an adversary such that their relative order may change.
The notion of 1-interval connectivity dynamism was introduced in [27] for complete graphs and requires
an adversary to connect the nodes of the graph such that in every round there must exist a connected
spanning subgraph of the nodes. [27] studied it for complete graphs, [22] studied it for the case of rings, and
[21] looked into it for cactuses. Note that the connections between nodes need not remain from round to
round. In this paper, we use a restricted version of 1-interval connectivity, proposed in [10], which requires
that for a given ring of nodes, in each round an adversary chooses at most one edge of the ring and removes
it for that round. This definition is restricted in that it does not allow nodes in the ring to have different
neighbors in different rounds. When we allow both vertex permutation and restricted 1-interval connectivity,
it is equivalent to the more general version of 1-interval connectivity from [27, 23] when restricted to rings.

2.3

Powers of Robots

We consider n robots, each having a unique label. Each robot has the ability to detect, in each round,
the robot with the least label among all robots co-located with it on its node and know what that label
is. For results in Sections 3, 4, and 6, robots possess chirality, i.e. they share the same notion of clockwise
and anticlockwise directions and can determine which edge to leave a node in order to move in the required
direction. In Section 5, robots do not possess chirality. Finally, robots have the ability to perform weak global
multiplicity detection and strong local multiplicity detection. Weak global multiplicity detection means that
robots can detect if zero, one, or more than one robot is present on a given node within their visibility range.
Strong local multiplicity detection means that robots can detect exactly how many robots are present on the
node they are at. Robots do not require any memory for most algorithms in our paper with the exception
of those presented in Sections 5.1 and 5.3.
For a given robot u in a given round, the node the robot is located on in that round is denoted by u.node.
In each round, each robot performs a look operation which allows it to update its view of the robots present
in the ring. Robots have k-visibility, where 0 ≤ k ≤ n, which constrains how many nodes away from u.node
a robot u can see.
For a given direction, the distance between two nodes is defined as the number of edges between them.
The view of a robot u with k-visibility is given by the vector < CLOCKW ISE, AN T I − CLOCKW ISE,
M U LT IP LICIT Y , M ISSIN G − EDGE >. CLOCKW ISE and AN T I − CLOCKW ISE are vectors
whose elements are the distances between consecutive occupied nodes starting from u.node and at distance
at most k away from u.node along clockwise and anticlockwise directions respectively. M U LT IP LICIT Y is
a vector whose elements are the distances of multinodes at distance at most k from u.node in the clockwise
direction. If there are no multinodes at distance at most k from u.node (including the node itself), then
5

M U LT IP LICIT Y contains just one element whose value is −1. M ISSIN G−EDGE contains one element
representing the distance of the closest node in the clockwise direction having a missing edge. In the case
that no edge is missing, the value of M ISSIN G − EDGE is ⊥. When k = 0, we say that robots have
no visibility, i.e. a robot u can only observe other robots present in u.node. When k ≥ n/2, we say that
robots have full visibility, i.e. they will have information about which nodes are holes, singleton nodes,
and multinodes for every node in the ring.

2.4

Synchronicity

Robots execute algorithms in a synchronous manner, where each round of execution is characterized by
the following four stages. Initially, an adversary performs some form of dynamism in the ring. Then each
robot performs a look operation, where it updates its view. Subsequently, each robot may perform some
computations and detect the robot with least label among all robots co-located on the same node as it.
Finally, each robot either moves to a new node or stays in its current node. Note that a given robot u can
only move to a node that is (i) adjacent to u.node in the given round and (ii) for which the adversary has
not removed the edge connecting that node and u.node.

2.5

Problem Description

Given an initial arbitrary configuration of n robots present on the nodes of an n node ring, the problem of
dispersion requires the robots to coordinate and move such that they reach a configuration where exactly
one robot is present on each node.

3

Dispersion with Vertex Permutation

The algorithm VP-Chain works as follows. VP-Chain is used by robots to check if they are a part of a
clockwise chain in the given round. If they are, then they move to fill the hole in the clockwise chain without
creating any new holes. Repeatedly performing this process allows the robots to achieve a state of dispersion,
at which point no multinodes will exist and the robots will stop executing the algorithm. Thus, we arrive at
the following theorem.
Algorithm 1 VP-Chain, run by each robot u
while there exists a multinode in the ring do
if (u.node is part of a clockwise chain) and (u has least label among robots in u.node) then
Move clockwise.
else
5:
Don’t move.

1:
2:
3:
4:

Theorem 1. When robots have chirality and full visibility, Algorithm VP-Chain achieves dispersion on a
ring in the presence of vertex permutation dynamism in O(n) rounds.
Proof. We prove that dispersion is achieved in O(n) by first showing that the number of holes decreases in
each round. We subsequently bound the number of possible holes in the ring.
Lemma 1. In each round where dispersion has not yet been achieved, the number of holes in the ring
decreases by at least 1.
Proof. In each round, if there is at least one hole, there will definitely be a multinode. Furthermore, it is
clear that there will exist a clockwise chain. The algorithm directs every robot occupying a singleton node
in this clockwise chain to move towards the hole. The algorithm directs exactly one robot in the multinode
(the robot with the least label) to move towards the hole. Thus, for this clockwise chain, the hole is filled
and no new holes are made.
6

For every round where there exists a hole, a clockwise chain exists. Thus, in every round where dispersion
hasn’t yet occurred, the number of holes decreases by at least 1.
There can be at most n − 1 holes in the initial configuration. From Lemma 1, it is clear that the upper
bound on the number of rounds it takes to achieve dispersion is n − 1 rounds. Hence VP-Chain achieves
dispersion in O(n) rounds.

4

Dispersion with Vertex Permutation and 1-Interval Connectivity

We now describe how algorithm VP-1-Interval-Chain works.
If a robot is part of a multinode, then it is possible it might be part of either zero, one, or two good
chains. If it’s not part of a good chain, the robot doesn’t move. If it’s part of exactly one good chain, then
the robot (if it has least label among robots on node) moves such that the hole of the chain is filled without
creating any new holes. If it’s part of two good chains, then the robots on the multinode coordinate to fill
in the hole in the clockwise chain.
If a robot’s node is a singleton node, then it checks if it is part of a good chain. If it’s not, the robot
doesn’t move. If it is, then the robot checks if the multinode of that chain belongs to two good chains. If so,
then if the robot belongs to the anticlockwise chain, then it doesn’t move, else it moves closer to the hole.
Thus, we arrive at the following theorem.
Algorithm 2 VP-1-Interval-Chain, run by each robot u
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:

while there exists a multinode in the ring do
if u.node is singleton node and part of good chain then
if the multinode of the chain is also part of another good chain that is a clockwise chain then
Don’t move.
else
Move towards the hole of u.node’s chain.
else if (u.node is a multinode) and (u has least label among robots in u.node) then
if u.node is part of two good chains then
Move clockwise.
else if u.node is part of one good chain then
Move towards the hole of the good chain.
else
Don’t move.

Theorem 2. When robots have chirality and full visibility, Algorithm VP-1-Interval-Chain achieves dispersion on a ring in the presence of vertex permutation dynamism and 1-interval connectivity dynamism in
O(n) rounds.
Proof. We will show that in every round prior to dispersion being achieved, there exists at least one good
chain. We then argue that this implies that the number of holes in each round decreases by at least 1. Using
this, we are then able to bound the number of rounds it takes to achieve dispersion.
Lemma 2. In a round where dispersion has not yet been achieved, there exists a good chain.
Proof. In a given round, if the robots have not completed dispersion, then there exists at least one hole and
at least one multinode. Thus, there exist at least two chains. As the adversary can remove at most one edge,
there will be at least one good chain in the ring.
Lemma 3. In a round where dispersion has not yet been achieved, the number of holes decreases by at least
1.
7

Proof. A new hole is created when all robots on an occupied node leave that node and no new robots occupy
it. Robots will only move if (i) they identify that they are in a good chain and the multinode of the chain
doesn’t belong to any other good chain or (ii) they identify that they are in a good clockwise chain.
These robots move such that every robot in a singleton moves towards the hole and one robot from the
multinode moves towards the hole. Because no edge is missing in a good chain, the situation where robots
leave one node and no robots move into that node does not occur.
Thus, when robots in a good chain move, they fill a hole. By Lemma 2, we know that in every round
until dispersion occurs there exists a good chain. Robots not in a good chain don’t move and thus can’t
create new holes. Thus, in every round, the number of holes decreases by at least 1.
By Lemma 3, we see in each round until dispersion is achieved, at least one hole is filled. Since there can
be at most n − 1 holes, it takes O(n) rounds to achieve dispersion.

5

Dispersion without Chirality

5.1

Dispersion on Rings with Restricted Initial Configurations

Let us assume that we start with a configuration where all the robots are in the same node. Algorithm NoChir-Preprocess causes all robots to develop the same sense of chirality. First all robots identify a common
robot, in this case the robot with the least label. This robot will serve as the key to unifying the directions
among all robots. This is achieved by making every robot move “clockwise” and then checking if their sense
of “clockwise” matches the least label robot’s sense of “clockwise”. All robots that are in the same node as
the robot with the least label have the same directions as that of the least label robot. If a robot is not in
the same node, then that robot’s sense of directions will be subsequently flipped so that they match those
of the least label robot’s.
Note that even in the face of vertex permutation dynamism or 1-interval connectivity dynamism, the
previous ideas hold true. All that matters is that the condition that robots with the same sense of direction
as the least label robot end up in the same node and those with the opposite sense of direction end up in
a different node holds true. In the case of vertex permutation dynamism, the adversary permutes the ring
after the robots have moved and thus the required condition holds true. In case that the edge adjacent to the
initial node with all the robots is removed by the adversary, those robots that tried to move along that edge
will remain in the initial node and the other robots will move to a different node. Once again, the required
condition holds true.
Algorithm 3 No-Chir-Preprocess, run by each robot u
1:
2:
3:

Remember robot with least label among robots in u.node. Call it x.
Move clockwise.
If x is not present in your node, reverse your clockwise and counterclockwise directions.

Lemma 4. Algorithm No-Chir-Preprocess ensures that robots starting on the same node will gain chirality,
even in the presence of both vertex permutation dynamism and 1-interval connectivity dynamism.
Proof. No-Chir-Preprocess has all robots identify the robot with the least label x and set their directions to
match that robots sense of directions. It does this by having robots perform one round of movement and
checking if x moves in the same direction they did. For a given robot, this can be easily checked as if x
moved in the same direction, then it will be present on the same node as the robot. If x and the robot did
not move in the same direction, then the robot switches its sense of clockwise and anticlockwise directions.
Thus, all robots will have the same sense of clockwise and anticlockwise.
Due to Lemma 4, if all robots start in the same node and run No-Chir-Preprocess, all robots will subsequently have chirality. Thus, we can then use algorithm VP-1-Interval-Chain, developed in Section 4,
8

to achieve dispersion in O(n) rounds in the presence of both vertex permutation dynamism and 1-interval
connectivity dynamism.
Theorem 3. When robots have full visibility, are initially present on the same node, and do not have
chirality, we can achieve dispersion in O(n) rounds in the presence of vertex permutation dynamism and
1-interval connectivity dynamism by running first No-Chir-Preprocess and then VP-1-Interval-Chain.
Proof. We are given that robots initially start in the same node. Thus, by Lemma 4, robots develop chirality
in one round by running No-Chir-Preprocess. By Theorem 2, robots will then achieve dispersion in O(n)
rounds by running VP-1-Interval-Chain. Thus, all robots achieve dispersion in O(n) rounds.

5.2

Dispersion on Rings with Odd Number of Nodes

If the ring has an odd number of nodes, then even with an arbitrary initial distribution of robots to nodes,
we are able to achieve dispersion. Robots running Achiral-Odd-VP-1-Interval-Chain achieve dispersion in
O(n) rounds even in the presence of both vertex permutation and 1-interval connectivity dynamism.
This algorithm is similar to the algorithm VP-1-Interval-Chain in Section 4 with two key differences.
The first difference is that if a robot is on a multinode that is part of two good chains and must move,
tie-breaking is done first based on which chain is shorter in length and only then if needed on direction. The
second difference is that if a robot is on a singleton node in a good chain, it checks if the multinode of the
chain it belongs to belongs to another shorter or equal length good chain before deciding to move. These
differences are the result of robots relying on chain size instead of a common sense of direction to unify their
movements.
The result achieved by the algorithm is characterized by the following theorem.
Algorithm 4 Achiral-Odd-VP-1-Interval-Chain, run by each robot u
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:

while there exists a multinode in the ring do
if u.node is singleton node and part of good chain then
if multinode of the chain is also part of another good chain that is shorter or same in length then
Don’t move.
else
Move towards the hole of u.node’s chain.
else if (u.node is a multinode) and (u has least label among robots in u.node) then
if u.node is a part of two good chains then
if both chains have same length then
Move clockwise.
else
Move towards the hole of the shorter chain.
else if u.node is a part of one good chain then
Move towards the hole of the good chain.
else
Don’t move.

Theorem 4. When robots have full visibility and do not have chirality, Algorithm Achiral-Odd-VP-1Interval-Chain achieves dispersion on a ring of odd length in the presence of vertex permutation dynamism
and 1-interval connectivity dynamism in O(n) rounds.
Proof. We first argue that the number of holes will eventually decrease until none are left and subsequently
bound the time this will take.
We argue the eventual decrease in holes as follows. We show, by Lemma 5, that in each round, either (i)
the number of holes decreases or (ii) the number of holes remains constant and the number of multinodes
increases. Since there is an upper bound of n/2 to the number of multinodes that can exist in an n node
9

ring, eventually it will become impossible for the number of multinodes to increase. Thus, the number of
holes can only decrease from that round onwards and eventually dispersion will be achieved.
Lemma 5. In each round, either (i) the number of holes decreases or (ii) the number of holes remains
constant and the number of multinodes increases.
Proof. We show that if the lemma does not hold, it implies that the ring is of even size. Because the ring
is not of even size and by the contrapositive of the previous statement, our lemma holds true. We first
enumerate the different types of movements possible by robots and subsequently show that only one type of
movement will lead to the lemma not holding.
We know that there will exist at least one multinode and one hole if dispersion has not occurred and
hence at least one good chain. From the algorithm, it is seen that the least label robot u of a multinode that
is part of at least one good chain executes a move in every round. This robot either moves towards the hole
of one of its good chains or moves clockwise.
u moves towards the hole of a given good chain c if either u.node is part of exactly one good chain c or
u.node is part of two good chains and c is shorter in length. In either case, all robots in singleton nodes, if
any, in c move towards the hole too and hence a hole gets occupied without creating any new holes. This
decreases the number of holes.
If u.node belongs to two good chains of equal length, then u moves clockwise. However, the robots of the
singleton nodes, if any, of both good chains remain stationary. This means that u moves into its neighboring
node which could be a hole or a singleton node. If it is a hole, it gets filled and hence the number of holes
decreases. If it is a singleton, it becomes a multinode. If the multinode u was initially on had more than
2 robots, then this movement of u leads to an increase in the number of multinodes, else the number of
multinodes remains the same.
The lemma does not hold if either (i) the number of holes increases or (ii) the number of holes does not
decrease and the number of multinodes does not increase. Condition (i) can never occur as robots move
only if their nodes are part of a good chain. When the robots on the nodes of a good chain move, it is
not possible to create a hole. Thus, we only consider condition (ii). Now, the only configurations where
condition (ii) occurs in a round is when all the multinodes belong to two equal length good chains and have
multiplicity exactly two. This follows from our previous enumeration of the different types of movements of
robots possible. As the number of holes doesn’t decrease, each multinode should belong to two equal length
good chains. And as the number of multinodes remains constant, each multinode should have exactly two
robots.
Let us assume that there are k multinodes initially. Since each multinode has exactly two robots, there
are k holes in the ring. Each multinode has two choices of holes to fill. Hence k multinodes on a whole have
2k choices but there are only k holes in ring. This condition can only be satisfied if each hole is shared by
two multinodes. Hence there needs to be an alternating pattern of multinodes and holes, i.e. every pair of
holes must be separated by at least one multinode and every pair of multinodes must be separated by at
least one hole. Since each multinode must belong to two equal length chains, the number of singleton nodes
s must be even due to this alternating pattern of multinodes and holes. Thus, the total number of nodes of
the ring s + 2k is an even number. However, we assume that the ring is of odd size and thus the lemma will
hold.
We now bound the running time of the algorithm. In each round, either the number of multinodes
increases and number of holes remains constant, or the number of holes decreases. Let rds multi inc be the
number of rounds that the number of multinodes can increase while the number of holes remains constant.
Let rds hole dec be the number of rounds that the number of holes decreases. The running time of the
algorithm is ≤ rds multi inc + rds hole dec. We bound each of these terms to get an asymptotic value for
the running time.
We can easily see that rds hole dec ≤ n−1. We show that rds multi inc is upper bounded by two values,
which we bound in turn. Let dif f initial max multi be the difference between the number of multinodes in
the initial configuration and the maximum number of multinodes possible. Let total multi dec be the total
decrease in the number of multinodes over the course of the algorithm. The number of multinodes can only
10

increase up to a certain maximum value. However, every time the number of multinodes decreases, they
can subsequently increase in the future. Thus, it is clear that rds multi inc ≤ dif f initial max multi +
total multi dec. We now individually bound these two terms.
The total number of multinodes that can exist in an n node ring is n/2. Thus dif f initial max multi ≤
n/2. We now focus on bounding total multi dec. When the number of holes decreases, the number of
multinodes can either increase, decrease, or stay the same. We show, by Lemma 6, if in a given round the
number of holes decreases by some number x, the number of multinodes can also decrease by at most x.
Therefore, over the course of the algorithm, the maximum decrease in the number of multinodes is ≤ n − 1.
Thus, total multi dec ≤ n − 1.
Therefore, the running time of the algorithm is
≤ rds multi inc + rds hole dec
≤ dif f initial max multi + total multi dec + rds hole dec
≤ n/2 + n − 1 + n − 1
= O(n) rounds.
Lemma 6. In each round, for every hole that becomes occupied, there can be at most a decrease of one
multinode.
Proof. Any hole will be a part of at most two good chains since the graph is a ring. It can become occupied
by either receiving a robot from exactly one good chain or from both good chains. If it receives a robot
from exactly one good chain, it is possible for only the multinode in that chain to become a singleton node.
If it receives a robot from both good chains, then the hole itself becomes a multinode and at most both
multinodes of the chains become singletons. Thus, for every hole that becomes occupied in a given round,
the number of multinodes in the graph decreases by at most one.
Thus the theorem is proved true.

5.3

Dispersion on a Ring of Size 4

We now present algorithm Achiral-Even4-VP-1-Interval-Chain to achieve dispersion on a ring of size 4 when
robots start in an arbitrary initial configuration. This algorithm bears a strong similarity to Achiral-OddVP-1-Interval-Chain as in most configurations the algorithms work similarly.
However, the key difference is the handling of the configuration where a multinode has two singleton
nodes adjacent to it, and the edges between the multinode and both singleton nodes are present in the
round. This situation, when presented to the algorithm Achiral-Odd-VP-1-Interval-Chain, would result in a
configuration that can be manipulated by the adversary to again reach this situation. In other words, the
adversary could then force the robots to run the algorithm forever without ever achieving dispersion. We
handle this particular situation by having robots in the singleton nodes move to the multinode and then
subsequently having all robots run No-Chir-Preprocess and VP-1-Interval-Chain.
Thus we are able to achieve dispersion in O(1) rounds on a ring of size 4, as captured by the following
theorem.
Theorem 5. When robots have full visibility and do not have chirality, Algorithm Achiral-Even4-VP-1Interval-Chain achieves dispersion on a ring of size 4 in the presence of vertex permutation dynamism and
1-interval connectivity dynamism in O(1) rounds.
Proof. Recall that we are dealing with a ring of size 4 and by extension, only 4 robots. Let us characterize
the state of the system by the number of multinodes and singleton nodes present in the system. Any system
where dispersion has not yet been achieved will be in one of the following four states:
1. There is one multinode with 4 robots on it.
2. There is one multinode with 3 robots on it and one singleton node.
11

Algorithm 5 Achiral-Even4-VP-1-Interval-Chain, run by each robot u
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:

while there exists a multinode in the ring do
if u.node has all 4 robots on it then
No-Chir-Preprocess
VP-1-Interval-Chain
else if u.node is singleton node then
if u.node is part of a good chain then
if the multinode of the chain is also part of another good chain that is shorter then
Don’t move.
else if multinode of the chain is also part of another good chain that is same in length then
Move towards the multinode.
else
Move towards the hole of u.node’s chain.
else if (u.node is a multinode) and (u has least label among robots in u.node) then
if u.node is a part of two good chains then
if chains have different length then
Move towards the hole of the shorter chain.
else if u.node is adjacent to two holes then
Move clockwise.
else if u.node is a part of one good chain then
Move towards the hole of the good chain.
else
Don’t move.

3. There is one multinode with 2 robots on it and two singleton nodes.
4. There are two multinodes with 2 robots on each.
We prove that dispersion is achieved in O(1) rounds from any of these four states using Achiral-Even4VP-1-Interval-Chain. Note that our goal is dispersion and so a system already in that state implies our
algorithm achieves dispersion in O(1) rounds.
It is clear to see that when the system is in state 1, the condition in Line 2 of the algorithm is satisfied
and No-Chir-Preprocess and VP-1-Interval-Chain will be executed. By Theorems 3, and given n = 4, robots
in state 1 achieve dispersion in O(1) rounds.
For states 2-4, we first show, in Lemma 7, that any system in state 2 or 4 changes to state 3 or a state
of dispersion in one round. We then show, in Lemma 8, that a system in state 3 achieves dispersion in O(1)
rounds.
Lemma 7. If the configuration of robots on nodes is characterized by state 2 or 4, then after robots run
Achiral-Even4-VP-1-Interval-Chain for one round, the system will reach state 3 or a state of dispersion.
Proof. We consider each state in turn, and show that in one round of executing Achiral-Even4-VP-1-IntervalChain, we arrive at state 3 or a state of dispersion.
Consider a system in state 2. There is one multinode and one singleton node. Either these two nodes are
(i) opposite to each other or (ii) adjacent to each other.
If the multinode and singleton node are opposite, then only the least label robot in the multinode will
move in the round. Regardless of if the adversary makes one of the chains of the multinode a bad chain, the
least label robot will move to the hole in one of the chains and state 3 will be reached in one round.
If the multinode and singleton node are adjacent to each other, then depending on which edge the
adversary removes, if any, there will either be exactly one good chain or there will be a smaller good chain
and a bigger good chain. In both cases, exactly one hole will be filled in the round and the system will
change to state 3.
12

Consider a system in state 4. Either the two multinodes are (i) opposite to each other or (ii) adjacent to
each other.
If the multinodes are opposite to each other, then depending on if the adversary removes an edge or not,
the condition of either Line 17 or Line 19 is satisfied for exactly one robot on each multinode. Now either
dispersion is achieved or the system changes to state 3 in one round.
If the multinodes are adjacent to each other, then depending on which edge the adversary removes, if
any, either one or both multinodes will be a part of a good chain. If only one multinode belongs to a good
chain, then state 3 is reached in one round. If both multinodes belong to good chains, then dispersion is
achieved in one round.
Thus it is clear that, whether the system is in state 2 or 4, in one round, the system will change to state
3 or a state of dispersion.
Now that we’ve shown that systems in state 2 or 4 change to state 3 or a state of dispersion in one round,
all that’s left to show is that we can achieve dispersion in O(1) rounds once we reach state 3.
Lemma 8. If the configuration of robots on nodes is characterized by state 3, then after robots run AchiralEven4-VP-1-Interval-Chain for O(1) rounds, they will achieve dispersion.
Proof. We show that state 3 reaches either a state of dispersion or state 1 in one round of executing AchiralEven4-VP-1-Interval-Chain. When the system is in state 3, either (i) the multinode will either be adjacent
to both singleton nodes or (ii) the multinode will be adjacent to one singleton node and a hole.
Consider case (i). Now, the adversary can either cause one of the chains the multinode belongs to be a
bad chain or allow both chains to be good. If both chains are good chains, the robots in the multinode won’t
move and the robots in the singleton nodes will move towards the multinode, thus bringing the system to
state 1 in one round. If only one chain is a good chain, then the robot on the singleton of the bad chain
remains stationary while the least label robot of the multinode and the robot on the singleton node of the
good chain move toward the hole. Thus a state of dispersion is reached in one round.
Consider case (ii). Now, the adversary can either cause one of the chains the multinode belongs to be be
a bad chain or allow both chains to be good. If both chains are good chains, then since one chain is shorter
than the other, the least label robot in the multinode moves to the hole and a state of dispersion is reached
in one round. If only one chain is a good chain, then still, the least label robot of the multinode and the
robots in the singleton nodes in the good chain, if any, move toward the hole and a state of dispersion is
reached in one round.
Thus we see that robots in a configuration characterized by state 3 reach either a state of dispersion or
state 1 in one round of executing Achiral-Even4-VP-1-Interval-Chain. As we saw earlier, once the system is
in state 1, robots will achieve dispersion in O(1) rounds. Thus, the lemma is proved.
Thus, the robots on a ring of size 4 will achieve dispersion in O(1) rounds, regardless of the starting
configuration of the robots on the nodes.

6

Impossibility of Dispersion with No Visibility

In this section we look at the impossibility of dispersion in the face of the two types of dynamism when robots
have no visibility. Note that these impossibility results hold even if the robots possess chirality. Furthermore,
we even allow the robots a little more power than our model for the possibility results in previous sections.
We allow robots co-located on a node to detect not just the robot with the least label among them, but also
the robot with the second least label among them. Even with this added power, dispersion is still impossible.
The key idea to the impossibility results is that the adversary is able to predict the robots’ movements in a
given round before they move and so modify the ring to prevent dispersion from being achieved. First, we
note the following observation about the dependence of a robot’s move on only local information.
Observation 1. If robots have no visibility, then in a given round, for every robot u, its choice of move
depends only on information present in u.node.
13

Observation 1 implies that any robot u’s move in a given round does not depend on information from nodes
other than u.node. Thus, the adversary may change the ring, either by permuting the nodes or removing an
edge, and u’s choice of movement wouldn’t be affected. This allows the adversary to predict how the robots
will move and prevent dispersion from occurring by ensuring the presence of either a multinode or a hole in
every round.

6.1

With Vertex Permutation

Theorem 6. If robots have no visibility, it is impossible to achieve deterministic dispersion in a ring with
≥ 3 nodes in the presence of vertex permutation dynamism.
Proof. We argue the impossibility result as follows. Recall that the connections in the graph change in every
round. When the adversary permutes the ring, only the positions of robots relative to other robots in the
graph changes, but there is no change to robots co-located on the same node. We first note that for a given
robot u, by Observation 1, its choice of move depends only on information accessible to it on u.node. Thus,
the adversary knows each robot’s plan to move before permuting the ring. The adversary leverages this
information to ensure the presence of at least one multinode in every round, which prevents dispersion of
robots. Due to a slight difference in possible configurations of the ring to avoid, we divide the proof into two
parts: for those rings of size 3 and those of size ≥ 4.
Lemma 9. If robots have no visibility, it is impossible to achieve deterministic dispersion in a ring with 3
nodes in the presence of vertex permutation dynamism.
Proof. For rings of size 3, it is not enough to ensure that a multinode exists in each round. We must also
ensure that all 3 robots do not end up on the same node, henceforth called a gathering configuration, else
the adversary will be unable to prevent dispersion from occurring. This is because once such a configuration
is reached, all robots are present in the same node and permuting the nodes does not change that. After the
vertex permutation, the robots can coordinate such that one robot goes through each edge and one robot
stays in the node, thus achieving dispersion.
Thus, the adversary should ensure that only ring configurations where there exists one hole, one multinode
and one singleton node occur in every round. Let us call all such configurations neutral configurations.
Let us assume the ring is initially in one such neutral configuration. We now show that regardless of how
the robots plan to move, the adversary has a way to permute the ring so that robots are always in a neutral
configuration.
If the movement of robots will lead to a neutral configuration, the adversary does not need to permute
the ring.
In case the movement of robots will lead to a gathering configuration, the adversary performs the following
operations. There are three possible ways to achieve a gathering configuration: (i) the robot from the
singleton node moves towards the multinode, (ii) both robots of the multinode move towards the singleton
(iii) all robots move towards the hole. Cases (i) and (ii) are similar and require the adversary to swap
the multinode and the singleton node. This results in the robot(s) which performs the move operation to
move towards the hole and a neutral configuration being maintained. In case (iii), the adversary swaps the
multinode and singleton. This results in the robot of the singleton node moving towards the multinode and
the robots of the multinode moving towards the singleton. Hence, a neutral configuration is still maintained.
In case the movement of robots will lead to dispersion, the adversary performs the following operations.
In order to achieve dispersion one robot should move into the hole and there should be one robot less in the
multinode at the end of the round. This is possible if (i) one robot moves out of the multinode while the
other stays in it and the robot in the singleton node does not move or (ii) both robots in the multinode move
out of it and the robot in the singleton node moves into the multinode. In case (i), the adversary can stay in
a neutral configuration by swapping the multinode and the hole. The robot leaving the multinode will move
into the singleton node and make it a multinode with exactly 2 robots in it. In case (ii), the adversary can
stay in a neutral configuration by swapping the singleton node and the hole. This results in the multinode
becoming a hole, the singleton node becoming a multinode, and the hole becoming a singleton.
14

Figure 3: Adversary swapping nodes to address case (ii).a of 1-hole impossibility.

Figure 4: Adversary swapping nodes to address case (ii).b of 1-hole impossibility.
Lemma 10. If robots have no visibility, it is impossible to achieve deterministic dispersion in a ring with
≥ 4 nodes in the presence of vertex permutation dynamism.
Proof. All ring configurations where dispersion hasn’t occurred can be reduced to three types, based on the
number of holes in the ring. The three cases are when the number of holes are 1, 2, and ≥ 3. In each of these
three cases, we show that if the robots can move given the current ring configuration and achieve dispersion,
the adversary has a way to permute the nodes such that dispersion won’t occur. We do this by showing that
the adversary can always maintain a multinode or a hole.
Note that if the movement of robots does not lead to dispersion, the adversary can just maintain the
ring as it is. Only in case the movement might lead to dispersion should the adversary perform the following
operations.
For 1 hole case:
When there is exactly 1 hole in the network, there will be exactly one multinode with exactly 2 robots
on it. In order to achieve dispersion in a given round from this configuration, robots should move such that
the following two conditions are satisfied: (i) exactly one robot moves into the hole from a neighboring node
of the hole and (ii) the total number of robots present on the multinode at the end of the round should be
exactly 1.
Condition (ii) can be satisfied in one of two ways. Either (ii.a) both robots in the multinode move out of
the node and a robot in a neighboring node moves into the node or (ii.b) one robot stays in node, the other
robot moves to a neighboring node, and no robot from a neighboring node moves into the multinode. If the

15

Figure 5: Adversary swapping nodes to address case 2.a of 2-hole impossibility when one multinode has three
robots.

Figure 6: Adversary swapping nodes to address case 2.b of 2-hole impossibility when one multinode has
three robots.
planned robot movements satisfy condition (ii.a), then the adversary swaps the hole with the neighboring
node specified in the condition, as illustrated in Figure 3. No robot will move into the multinode and it will
become a hole. Hence dispersion will not be achieved. If the planned robot movements satisfy condition
(ii.b), then the adversary swaps the multinode and the hole, as illustrated in Figure 4. Since no robot moves
into the hole, it will remain a hole and dispersion will not be achieved.
For 2 holes case:
Two holes present in the system arise when either (i) a multinode has three robots or (ii) two multinodes
have two robots each. We look at each case in turn.
(i) A multinode has three robots:
In order to achieve dispersion in a given round the following two conditions should be satisfied: (1) two
robots on the multinode should be move in different directions while one stays on the node and (2) there
should be one incoming robot into each of the holes. The reason for this specific movement of robots on the
multinode is that if more than one robot moves in either direction or stays on the node, a multinode will
definitely exist at the end of the round and dispersion will not be achieved. Condition (2) can be satisfied
in one of two ways: (2.a) at least one of the robots that move into the holes comes from a singleton node or
(2.b) both holes receive a robot from the multinode.
If robot movements satisfy condition (2.a), the adversary swaps the multinode with a hole that would

16

Figure 7: Adversary swapping nodes to address case 2.a of 2-hole impossibility when two multinodes have
two robots each.
have received a robot from a singleton node, as illustrated in Figure 5. If both holes would have received a
robot from a singleton node, the adversary choose one arbitrarily. After the swap operation, the robot from
the singleton node will move into the multinode. And since there will already be a robot in the multinode
after robots in it move in order to satisfy condition (1), it still remains a multinode. Thus, dispersion is not
achieved at the end of the round.
If robot movements satisfy condition (2.b), the adversary swaps the multinode with any one of the holes,
as illustrated in Figure 6. The hole which was not swapped does not have an incoming robot from any other
node and remains a hole. Thus, dispersion is not achieved at the end of the round.
(ii) Two multinodes have two robots each:
In order to achieve dispersion in a given round, the following two conditions should be satisfied: (1) for
each hole, there should be one robot that will move into it and (2) for each multinode, either the robots
move in opposite directions or one robot moves and the other stays on the node. The reason for the specific
movements in condition (2) is that if more both robots decide to move in the same direction or stay, then
the adjacent node in that direction will become a multinode or the original multinode will stay a multinode
respectively. Let the two multinodes be m1 and m2 . There are four ways condition (2) may be satisfied:
(2.a) for both m1 and m2 , the robots move in opposite directions, (2.b) for both m1 and m2 , one robot
moves and the other stays on the node, (2.c) for m1 , one robot moves and one stays and for m2 , both robots
move in opposite directions or (2.d) for m1 , both robots move in opposite directions and for m2 , one robot
moves and one stays.
If robot movements satisfy condition (2.a), the adversary can permute nodes so that the three node
sequence consisting of m1 , a hole, and m2 in that clockwise order arises, as illustrated in Figure 7. Since the
robots of both m1 and m2 move in opposite directions, the hole which is adjacent to both of them becomes
a multinode. Thus, dispersion is not achieved at the end of the round.
If robot movements satisfy condition (2.b), the adversary can make m1 and m2 adjacent to each other.
The exact order of m1 and m2 depends on the relative directions of the moving robots. If the moving robots
move in same direction, it doesn’t matter since either m1 will have a robot enter it from m2 or vice-versa,
as illustrated in Figure 8. Since m1 and m2 both retain one robot, the addition of this robot ensures a
multinode exists. If the moving robots move in opposite directions, then we place m1 and m2 next to each
other such that the moving robot from m1 moves into m2 and vice-versa, as illustrated in Figure 8. This
ensures that both nodes remain multinodes. Thus, dispersion is not achieved at the end of the round.
If robot movements satisfy either condition (2.c) or (2.d), the adversary can move m1 and m2 so that
they are adjacent to each other, as illustrated in Figure 10. Since one of the nodes retains a robot and a
robot will move into that node from the other node, a multinode will exist. Thus, dispersion is not achieved
at the end of the round.

17

Figure 8: Adversary swapping nodes to address case 2.b of 2-hole impossibility when two multinodes have
two robots each. Both robots that choose to move, move in the same direction.

Figure 9: Adversary swapping nodes to address case 2.b of 2-hole impossibility when two multinodes have
two robots each. The robots that choose to move, move in opposite directions.

Figure 10: Adversary swapping nodes to address cases 2.c & 2.d of 2-hole impossibility when two multinodes
have two robots.

18

For ≥ 3 holes case:
In this case the adversary can permute the nodes in such a way that all the holes are consecutive. This
ensures that there exists a hole with two adjacent holes. This hole can never be filled by any movement of
the robots.
Putting together Lemmas 9 and 10, we see that the theorem is true.
Note that this proof hinges heavily on Observation 1 that the adversary is able to predict the movement of
the robots in a given round prior to them moving. In the case where robots are allowed to use randomization
to determine movements, if we give the adversary extra powers to see those bits, then dispersion even with
the allowance of randomness is impossible. This is captured by the following corollary.
Corollary 1. At the beginning of any round, if the adversary is allowed to know the random bits, if any, that
robots will use to determine movement in that round, then the following holds. If robots have no visibility, it
is impossible to achieve dispersion in a ring with ≥ 3 nodes in the presence of vertex permutation dynamism.

6.2

With 1-Interval Connectivity

Theorem 7. If robots have no visibility, it is impossible to achieve deterministic dispersion in a ring with
≥ 2 nodes in the presence of 1-interval connectivity dynamism.
Proof. From Observation 1, the adversary can predict the movement of the robots in a given round at
the beginning of that round. We show that in any round, regardless of the movements of the robots, the
adversary can remove at most a single edge to prevent dispersion from being achieved in that round. Thus,
in all rounds dispersion will be prevented from being achieved.
In a given round, if the movement of robots does not lead to dispersion, the adversary need not remove
any edge.
We need to consider only the movement of robots that leads to dispersion at the end of a given round.
In order for dispersion to occur, all holes in the ring must have an incoming robot from exactly one of their
neighboring nodes. This is because if robots came from both the neighboring nodes of the hole, the hole will
become a multinode and dispersion will not occur.
Consider one such hole and the neighboring node from which a robot will move to the hole. The adversary
can just remove the edge connecting the hole and that neighboring node. Thus, at the end of that round,
the hole remains and dispersion does not occur.
Similar to Corollary 1, when we have a stronger adversary that can predict the moves the robots will make
in the current round, even when randomness is involved, dispersion is impossible in the face of 1-interval
connectivity.
Corollary 2. At the beginning of any round, if the adversary is allowed to know the random bits, if any, that
robots will use to determine movement in that round, then the following holds. If robots have no visibility,
it is impossible to achieve dispersion in a ring with ≥ 2 nodes in the presence of 1-interval connectivity
dynamism.

7

Conclusions and Future Work

In this work, we have developed asymptotically time optimal algorithms to achieve dispersion when robots
have full visibility, with and without chirality, in the face of vertex permutation dynamism and 1-interval
connectivity dynamism. We have also proved the impossibility of achieving dispersion when robots have no
visibility. Recall that any solution to dispersion acts as a solution to n robot collaborative exploration and n
robot scattering under the same assumptions and model. Thus all our algorithms also solve the problems of n

19

robot collaborative exploration and n robot scattering on a ring of size n for the given model and constraints
of the algorithms.
Two interesting open questions arise from this work.
Open Question 1: What can be said of the possibility or impossibility of achieving dispersion when
visibility is limited to more than no visibility but less than full visibility?
Open Question 2: Is dispersion of achiral robots on an even node ring of size ≥ 6, in the presence of both
vertex permutation and 1-interval connectivity dynamism, possible or impossible?

Acknowledgements
We thank the anonymous reviewers of a previous version of this paper for pointing us to several relevant
references and for other comments that improved the presentation of this paper.

References
[1] J. Augustine and W. K. Moses Jr. Dispersion of mobile robots: A study of memory-time trade-offs. In
Proceedings of the 19th International Conference on Distributed Computing and Networking. ACM, To
appear in 2018.
[2] C. Avin, M. Kouckỳ, and Z. Lotker. How to explore a fast-changing world (cover time of a simple
random walk on evolving graphs). Automata, languages and programming, pages 121–132, 2008.
[3] L. Barriere, P. Flocchini, E. Mesa-Barrameda, and N. Santoro. Uniform scattering of autonomous mobile
robots in a grid. International Journal of Foundations of Computer Science, 22(03):679–697, 2011.
[4] H. L. Bodlaender and J. van Leeuwen. Distribution of Records on a Ring of Processors, volume 86.
Unknown Publisher, 1986.
[5] P. Brass, F. Cabrera-Mora, A. Gasparri, and J. Xiao. Multirobot tree and graph exploration. IEEE
Transactions on Robotics, 27(4):707–717, 2011.
[6] P. Brass, I. Vigan, and N. Xu. Improved analysis of a multirobot graph exploration strategy. In Control
Automation Robotics & Vision (ICARCV), 2014 13th International Conference on, pages 1906–1910.
IEEE, 2014.
[7] G. Cybenko. Dynamic load balancing for distributed memory multiprocessors. Journal of parallel and
distributed computing, 7(2):279–301, 1989.
[8] A. K. Datta, A. Lamani, L. L. Larmore, and F. Petit. Ring exploration by oblivious agents with local
vision. In Distributed Computing Systems (ICDCS), 2013 IEEE 33rd International Conference on, pages
347–356. IEEE, 2013.
[9] A. K. Datta, A. Lamani, L. L. Larmore, and F. Petit. Enabling ring exploration with myopic oblivious
robots. In Parallel and Distributed Processing Symposium Workshop (IPDPSW), 2015 IEEE International, pages 490–499. IEEE, 2015.
[10] G. A. Di Luna, S. Dobrev, P. Flocchini, and N. Santoro. Live exploration of dynamic rings. In Distributed
Computing Systems (ICDCS), 2016 IEEE 36th International Conference on, pages 570–579. IEEE, 2016.
[11] Y. Disser, F. Mousset, A. Noever, N. Škorić, and A. Steger. A general lower bound for collaborative
tree exploration. arXiv preprint arXiv:1610.01753, 2016.
[12] M. Dynia, J. Kutylowski, F. M. auf der Heide, and C. Schindelhauer. Smart robot teams exploring
sparse trees. In International Symposium on Mathematical Foundations of Computer Science, pages
327–338. Springer, 2006.
20

[13] M. Dynia, J. LopuszaŃski, and C. Schindelhauer. Why robots need maps. Structural Information and
Communication Complexity, pages 41–50, 2007.
[14] Y. Elor and A. M. Bruckstein. Uniform multi-agent deployment on a ring. Theoretical Computer Science,
412(8-10):783–795, 2011.
[15] T. Erlebach, M. Hoffmann, and F. Kammer.
arXiv:1504.07976, 2015.

On temporal graph exploration.

arXiv preprint

[16] P. Flocchini, D. Ilcinkas, A. Pelc, and N. Santoro. Computing without communicating: Ring exploration
by asynchronous oblivious robots. Algorithmica, 65(3):562–583, 2013.
[17] P. Flocchini, B. Mans, and N. Santoro. Exploration of periodically varying graphs. In International
Symposium on Algorithms and Computation, pages 534–543. Springer, 2009.
[18] P. Flocchini, B. Mans, and N. Santoro. On the exploration of time-varying networks. Theoretical
Computer Science, 469:53–68, 2013.
[19] P. Fraigniaud, L. Gasieniec, D. R. Kowalski, and A. Pelc. Collective tree exploration. Networks,
48(3):166–177, 2006.
[20] Y. Higashikawa, N. Katoh, S. Langerman, and S.-i. Tanigawa. Online graph exploration algorithms for
cycles and trees by multiple searchers. Journal of Combinatorial Optimization, 28(2):480–495, 2014.
[21] D. Ilcinkas, R. Klasing, and A. M. Wade. Exploration of constantly connected dynamic graphs based
on cactuses. In International Colloquium on Structural Information and Communication Complexity,
pages 250–262. Springer, 2014.
[22] D. Ilcinkas and A. M. Wade. Exploration of the t-interval-connected dynamic graphs: The case of the
ring. In SIROCCO, pages 13–23. Springer, 2013.
[23] F. Kuhn, N. Lynch, and R. Oshman. Distributed computation in dynamic networks. In Proceedings of
the forty-second ACM symposium on Theory of computing, pages 513–522. ACM, 2010.
[24] F. Kuhn and R. Oshman. Dynamic networks: models and algorithms. ACM SIGACT News, 42(1):82–96,
2011.
[25] A. Lamani, M. Potop-Butucaru, and S. Tixeuil. Optimal deterministic ring exploration with oblivious
asynchronous robots. Structural Information and Communication Complexity, pages 183–196, 2010.
[26] S. Muthukrishnan, B. Ghosh, and M. H. Schultz. First-and second-order diffusive methods for rapid,
coarse, distributed load balancing. Theory of computing systems, 31(4):331–354, 1998.
[27] R. O’Dell and R. Wattenhofer. Information dissemination in highly dynamic graphs. In Proceedings of
the 2005 joint workshop on Foundations of mobile computing, pages 104–110. ACM, 2005.
[28] D. Peleg and A. Van Gelder. Packet distribution on a ring. Journal of Parallel and Distributed Computing, 6(3):558–567, 1989.
[29] M. Shibata, T. Mega, F. Ooshita, H. Kakugawa, and T. Masuzawa. Uniform deployment of mobile
agents in asynchronous rings. In Proceedings of the 2016 ACM Symposium on Principles of Distributed
Computing, pages 415–424. ACM, 2016.
[30] R. Subramanian and I. D. Scherson. An analysis of diffusive load-balancing. In Proceedings of the sixth
annual ACM symposium on Parallel algorithms and architectures, pages 220–225. ACM, 1994.
[31] C.-Z. Xu and F. C. M. Lau. Analysis of the generalized dimension exchange method for dynamic load
balancing. Journal of Parallel and Distributed Computing, 16(4):385–393, 1992.

21

