Dispersion of Mobile Robots: A Study of Memory-Time Trade-offs

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

John Augustine∗

William K. Moses Jr.†

Abstract
We introduce a new problem in the domain of mobile robots, which we term dispersion. In this
problem, n robots are placed in an n node graph arbitrarily and must coordinate with each other to
reach a final configuration such that exactly one robot is at each node. We study this problem through
the lenses of minimizing the memory required by each robot and of minimizing the number of rounds
required to achieve dispersion.
Dispersion is of interest due to its relationship to the problems of scattering on a graph, exploration
using mobile robots, and load balancing on a graph. Additionally, dispersion has an immediate real world
application due to its relationship to the problem of recharging electric cars, as each car can be considered
a robot and recharging stations and the roads connecting them nodes and edges of a graph respectively.
Since recharging is a costly affair relative to traveling, we want to distribute these cars amongst the
various available recharge points where communication should be limited to car-to-car interactions.
We provide lower bounds on both the memory required for robots to achieve dispersion and the
minimum running time to achieve dispersion on any type of graph. We then analyze the trade-offs
between time and memory for various types of graphs. We provide time optimal and memory optimal
algorithms for several types of graphs and show the power of a little memory in terms of running time.

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

1
1.1

Introduction
Background & Motivation

The use of mobile robots to solve global problems in a distributed manner is a new and interesting paradigm
in problem solving. In it, each robot acts individually, but collectively the robots accomplish some goal
that would be infeasible to solve using a global centralized approach. Many important real world problems
such as toxic hazard clean-up, large maze exploration, and gathering at one place can be modeled in this
paradigm. We introduce a new problem in the domain of mobile robots, which we term dispersion. In this
problem, n robots are placed in an n node graph arbitrarily and must coordinate with each other to reach a
ﬁnal conﬁguration such that exactly one robot is at each node.
A practical application of this idea comes from the area of self-driving electric cars and recharging stations.
Typically recharging an electric car is a time-intensive task (as public recharging centers take hours) and
when multiple recharge stations are located nearby, it is better in terms of time to simply ﬁnd the nearest
free station instead of waiting. With self-driving cars becoming a reality, it is advantageous to ﬁgure out
strategies to automate this process and furthermore leverage knowledge, if available, about the larger spread
of available stations.
∗ 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.

1

We now look at the relation of dispersion to other well-known problems in literature, namely scattering,
exploration with mobile robots, and load balancing.
This problem is very similar to the robot scattering or uniform-deployment problem on graphs [3, 16, 24],
where robots must spread out evenly in the graph. When the number of robots is equal to the number of
nodes in the graph, the problems are exactly the same assuming the model is the same.
Dispersion is also very similar to the problem of n robot collaborative graph exploration using mobile
robots [15, 7, 8, 11], where n robots start at a given node and must explore the graph in as few rounds as
possible. Since any solution to a problem of dispersion acts as a solution to n robot exploration under the
same conditions, any possibility results achieved for dispersion apply to n robot exploration. Furthermore,
results in exploration are usually of two types, either trying to achieve exploration in a ring or tree in as few
rounds as possible, or else trying to show the possibility of exploration with as few bits as possible. We feel
that by showing the interplay of memory and running time for not just rings and trees, but also arbitrary
graphs, we add meaningful contributions to that area of work.
This problem may also be considered a variant of load balancing on graphs [6, 10, 22, 25, 20, 5, 23, 4],
where typically the nodes start with some arbitrary amount of load and must transfer load using edges
until each node has more or less the same amount. We can think of dispersion in this context if we assume
that the loads have memory, computational power, and are labeled while the nodes do not have memory or
computational power and are unlabeled. This is of interest as studying load balancing in this way acts as a
sort of bridge between the vastly diﬀerent ﬁelds of mobile robots and load balancing and may pave the way
to an exchange of ideas and techniques between the two areas.

1.2

Related Work

Dispersion is similar to the problem of scattering or uniform deployment of k robots on an n node graph
when k = n. Scattering requires k robots to uniformly deploy themselves in a given network with n nodes.
[3] looked into this problem on grids while [16, 24] looked into this problem on rings under diﬀerent settings
than the current paper.
The problem of dispersion is very close to that of k robot collective exploration of an n node graph when
k = n. The problem states that, given k robots initially all located on a given node, we want an algorithm
run by all robots such that all nodes are visited in the least amount of time. Typically the nodes are labeled.
Much work has been done on this problem [15, 7, 8, 11], especially for rooted trees [14, 17, 7, 18, 21]. Of
particular interest to us are the results of [21] and [14], which both use k robots to explore a rooted tree in
O(D2 ) rounds and O(D2−1/p ) rounds respectively, where p is a property of the graph called its “density”.
Note that [14] achieves a bound better than O(D2 ) by requiring robots to have knowledge of the value of
p and leveraging that knowledge. Furthermore, under their setting each node is labeled and robots have
unlimited memory.
The notion of limiting the robots’ memory was raised in [12] where they proved that exploration with
stopping on a tree with unlabeled nodes by a single robot was possible with O(log2 n) bits of memory. [2]
improved this by showing that it was possible to explore with stopping a tree with unlabeled nodes with
one robot having O(log n) bits of memory. Other attempts at limiting robots memory were also explored
in [9, 19, 26] where nodes were allowed to have some memory as well. [9] allowed nodes to have 1 − 3 bits
and showed that it was possible for a single robot to explore such graphs subject to certain constraints. [19]
studied exploration of a graph under a slightly diﬀerent model by a single robot when both robots and nodes
were allowed some bits of memory. Their main result was an exploration algorithm that required each robot
to have 1 bit of memory and each node to have O(log ∆) bits of memory in order to achieve exploration in
O(m) time steps. [26] present various algorithms which trade-oﬀ memory of agents and memory of nodes.
Load balancing requires a total amount of load to be distributed among several processors. If we consider
the robots to be the load, then dispersion is equivalent to load balancing on a graph when “smart” loads are
in play, i.e. the loads make the decisions on where to move and not the nodes. Loads are either discrete
[6, 22] or continuous [20]. Dispersion is closer to load balancing when discrete loads are involved. Load
balancing in graphs has been studied for quite a while now [6, 10, 22, 25, 20, 5, 23, 4]. Work in the area is
usually divided into either work dealing with diﬀusion [10, 25, 20] or dimension exchange [27], which refers
2

to whether a node can balance load with all its neighbors concurrently or just one neighbor at a time in a
given round respectively. Our model is closer to the work done on diﬀusion.
The problem of dispersion, in the setting of time-varying rings, is being looked into in the work of [1].

1.3

Our Results

We provide both lower bounds and upper bounds for the problem of deterministic dispersion on various types
of graphs for diﬀerent memory constraints on the individual robots. A list of our upper bound results may
be found in Table 1. We assume that each robot has no visibility of the graph and can only communicate
with other robots present on their own node. Furthermore, we assume that robots only know the number of
nodes n and number of edges m of the graph, but do not know the maximum degree ∆ or the diameter D.
As any solution to dispersion also solves collaborative graph exploration and also scattering under the same
conditions, our algorithms apply to those problems as well. This is especially interesting, as to the best of
our knowledge, ours is the ﬁrst work analyzing time and memory trade-oﬀs across various types of graphs
for exploration as opposed to merely discussing the possibility of achieving exploration with limited memory.
Table 1: Upper bound results for diﬀerent types of graphs along with the memory requirement of each robot.
For a given graph, n is number of nodes, m is number of edges, ∆ is maximum degree of any node, and D is
diameter. Note that all algorithms terminate in the same time dispersion is achieved, except for algorithm
Graph-LogN, which requires all robots to run the algorithm perpetually.
Serial No.

Type of Graph

Memory Requirement
Algorithm Name
Time Until
of Each Robot
Dispersion Achieved
1.
Path
O(log n) bits
Path-Ring-Tree-LogN
O(n) rounds
2.
Ring
O(log n) bits
Path-Ring-Tree-LogN
O(n) rounds
3.
Tree
O(log n) bits
Path-Ring-Tree-LogN
O(n) rounds
4.
Rooted Tree
O(∆ + log n) bits
Rooted-Tree-Delta-LogN
O(D2 ) rounds
5.
Arbitrary Graph
O(log n) bits
Graph-LogN*
O(∆D ) rounds
6.
Arbitrary Graph
O(n log n) bits
Graph-N-LogN
O(m) rounds
7.
Rooted Graph
O(log n) bits
Rooted-Graph-LogN
O(m) rounds
*Graph-LogN requires all robots to run perpetually. Hence termination is not achieved.
Given any graph, we show that each robot requires at least Ω(log n) bits of memory in order to achieve
deterministic dispersion when all robots have the same amount of memory.
Initially, we restrict robots to have O(log n) bits of memory. We develop the algorithm Path-Ring-TreeLogN for paths, trees, and rings. It takes O(n) rounds to achieve deterministic dispersion. It is asymptotically
optimal in both memory and time for paths and rings but is only asymptotically optimal in memory for trees.
We develop the algorithm Rooted-Graph-LogN for rooted graphs, i.e. graphs where all robots start at one
node. It is asymptotically optimal in terms of memory and requires O(m) rounds to achieve dispersion. We
then relax the restriction that robots must stop running the algorithm eventually and develop Graph-LogN
to achieve dispersion on arbitrary graphs. It is asymptotically optimal in terms of memory and has a running
time of O(∆D ) rounds.
One of our more interesting results is to show that the addition of just a little more memory to each
robot allows vastly improved running time. When we allow robots to have O(∆ + log n) bits of memory,
we develop the algorithm Rooted-Tree-Delta-LogN for rooted trees, i.e. trees where all robots start at one
node. It takes O(D2 ) rounds to achieve dispersion. For the given constraint of lack of knowledge of the exact
topology of the tree, the algorithm appears to be asymptotically optimal in time.1 It is important to note
that our algorithm does not require knowledge of ∆ as long as the memory provisioned to each mobile robot
is O(∆ + log n) bits.
1 An as yet unpublished work [13] claims (Theorem 2.5 in that paper) that the lower bound for n robot collaborative tree
exploration is Ω(D 2 ), rendering our algorithm asymptotically time optimal.

3

Finally, we present the algorithm Graph-M-LogN, which requires O(n log n) bits of memory and achieves
dispersion on any graph in O(m) rounds. This algorithm also illustrates the power of trading oﬀ memory to
achieve faster and more powerful algorithms.

1.4

Organization of Paper

The technical preliminaries are presented in Section 2. Lower bounds for the problem are given in Section 3.
Our results for paths, rings, trees, rooted graphs, and graphs when robots have O(log n) bits of memory
are presented in Section 4. Our result for rooted trees when robots have O(∆ + log n) bits of memory is
presented in Section 5. Our result for an arbitrary graph when robots have O(n log n) bits of memory is
presented in Section 6. Conclusions and some open problems are presented in Section 7.

2

Technical Preliminaries

We now deﬁne the model and subsequently formally state the problem description.

2.1

Model

Parameters of graph:
We consider a graph with n nodes, m edges, maximum degree (of any node) ∆, and diameter D. The edges
are unweighted and undirected. Nodes are anonymous, i.e. they don’t have unique ID’s. For each node, a
unique integer in [0, δ − 1], where δ is the degree of the node, called port number is assigned to each edge
connected to that node. Edges can be thought of as bridges between two nodes, where each node has its
own port to denote the bridge. We do not assume any relation between the two port numbers for a given
edge. Any number of robots are allowed to move along an edge in a given round.
Type of communication:
We consider a synchronous system where rounds are counted according to a global clock. Every round
consists of two steps. In the ﬁrst step, any robot can communicate with other robots co-located with it and
perform local computations2 . In the second step, if the robot has decided to move along a given edge, it will
then move along it. We do not restrict the time for local computations of the robots and communication
that can take place amongst themselves.
Powers of robots:
Each robot has a unique label taken from the range [1, c log n], where c ≥ 1 is a constant. Each robot has no
visibility of the graph and can only communicate with other robots present on the same node using messages.
When a robot moves from node u to node v, it is aware of the port it used to leave u and the port it used
to enter v. Robots only know the values of n and m and don’t know the values of D and ∆.
Complexity measures:
We measure the eﬃciency of our algorithms against the number of rounds taken for dispersion to occur on
the underlying graph.
Another important parameter we would like to understand is the memory complexity required by each
robot. This is the number of bits that each robot is allowed to use to store information and perform local
computation.
Definitions:
We use the notion of assigning a robot to a node. When we assign a given robot to a given node, we
2 Note that for a given robot with O(x) bits of memory, the local computation will not exceed an O(x) space computation.
For example, if all robots only have O(log n) bits of memory, then any robot can only perform local computations in log n space.

4

imply that in the ﬁnal dispersed conﬁguration that robot will be present on that node. We also call a node
an assigned node or unassigned node when a robot is assigned to it or not respectively.

2.2

Problem Description

The problem of dispersion is that given an initial conﬁguration of n robots arbitrarily assigned to an n
node graph, we want robots to move around such that we arrive at a conﬁguration where exactly one robot
is present on each node. We attempt to come up with algorithms to perform dispersion on various types
of graphs while minimizing the number of rounds taken to achieve dispersion and minimizing the memory
requirement for each robot.

3
3.1

Lower Bounds on Time & Memory
Lower Bound on Running Time

It is clear to see that the lower bound for any algorithm to perform dispersion on any graph is Ω(D). This
is because of the initial conﬁguration where all robots are located on the same node and there exists a node
at a distance of D away from that node. It takes at least D − 1 rounds to reach that node. Note that in the
case of paths and rings, D = Θ(n), so we have a lower bound of Ω(n) on running time.

3.2

Lower Bound on Memory of Robots

Theorem 1. Assuming all robots are given the same amount of memory, robots require Ω(log n) bits of
memory each for any deterministic algorithm to achieve dispersion on a graph.
Proof. We prove this theorem by showing that if robots have o(log n) bits of memory each, then dispersion
is impossible.
Suppose all robots have o(log n) bits of memory. Each robot’s state space is then 2o(log n) = no(1) . Since
there are n robots, by pigeonhole principle, there exist two robots u and v with the same state space.
Let us suppose that that all robots are initially on the same node. Since all robots run the same
deterministic algorithm and u and v are co-located initially, they will perform the same moves. In essence,
they can be considered “sticky” robots, in that they will always mirror each other’s move and will never do
anything diﬀerent. Since dispersion requires a conﬁguration where there is exactly one robot per node, we
will never achieve dispersion since there is no way for u and v to settle down on two diﬀerent nodes.
Thus, assuming all robots have the same amount of memory, robots require Ω(log n) bits of memory each
in order to achieve dispersion on a graph.

4

Dispersion with O(log n) Bits of Memory

When each robot has O(log n) bits of memory, we look at dispersion on rings, trees, and rooted graphs. All
three algorithms presented in this section are variants of basic depth-ﬁrst search.

4.1

Dispersion on a Path, Ring, or Tree

We present an O(n) round dispersion algorithm for paths, rings, or trees. Note that since the lower bound
on running time of dispersion for rings and paths is Ω(n), this algorithm is asymptotically optimal for those
two types of graphs.
The algorithm Path-Ring-Tree-LogN works by having each robot see if it can get assigned to the node it
is on at the start of every round. If not and it entered the node through port i, it leaves through port (i + 1)
mod degree of node. If a robot is at a leaf node or one end of a path, then it exits the node through the
same port it entered. Note that this algorithm closely mirrors the algorithm proposed by Ambühl et al. [2]
to solve single robot exploration in a tree with O(log n) bits of memory.
5

The algorithm uses three variables, port entered, settled, and rnd cntr. port entered denotes the port
through which a robot entered the current node. settled is a boolean variable which indicates if the robot
has assigned itself to a node or not. rnd cntr is used to keep track of the rounds.
Note that though we will prove that the algorithm achieves dispersion in ≤ 2n rounds, we still require
each robot to maintain a round counter and count up to 2n rounds before explicitly terminating. This is
required because every time an exploring robot moves to a new node, it must conﬁrm that that node doesn’t
already have another robot settled on it. This is done by having all co-located robots communicate in a
round and establish if one robot has already settled there or not. If a robot terminates early, it may happen
that another robot may also choose to settle at that node later on and then dispersion can never be achieved.
This logic applies to many of the algorithms in the subsequent sections with the exceptions of algorithm
Graph-LogN in Section 4.3 and algorithm Rooted-Tree-Delta-LogN in Section 5.1. In the former, robots
never terminate. In the latter, robots choose when to terminate, not based on a round counter.
Algorithm 1 Path-Ring-Tree-LogN, run by each robot u
1: Initialize the following values: port entered ← 0, settled ← F ALSE.
2: for rnd cntr ← 1, 2n do
3:
Set port entered to the port entered through.
4:
if Node doesn’t have robot assigned to it and u is robot with lowest label presently on node then
5:
u assigns itself to node and sets settled ← T RU E.
6:
if settled = F ALSE then
7:
port entered ← (port entered + 1) mod degree of node.
8:
Move through port entered.

Theorem 2. Algorithm Path-Ring-Tree-LogN can be run by robots with O(log n) bits of memory to ensure
dispersion occurs in O(n) rounds on paths, rings and trees.
Proof. Each robot performs the algorithm for 2n rounds, so it easy to see that the time complexity is O(n).
The memory limit on robots is easy to see as we only need robots to remember the port through which they
entered (O(log ∆) bits), the current round (O(log n) bits) and if they are settled (1 bit). Additionally, all
robots require O(log n) bits to compare their labels with other robots in order to decide which robots are
assigned to which nodes for a total of O(log n) bits of memory.
We now need to show that dispersion is achieved in 2n rounds. It is clear to see that no more than
one robot will be assigned to any given node because robot labels are unique and once one robot has been
assigned to a given node, no other robot may then be assigned to it. All that remains is to argue that
in 2n rounds each robot is assigned to a node. This is achieved if we can upper bound the time taken by
any robot to visit all nodes as 2n. In a path, ring or tree, the number of edges is at most n. It takes at
most 2n rounds to perform depth-ﬁrst search on these structures. Since Path-Ring-Tree-LogN is essentially
performing depth-ﬁrst search, we have it that all nodes will be visited by a given robot if it hasn’t settled in
at most 2n rounds.

4.2

Dispersion on a Rooted Graph

A rooted graph is a graph where all robots are initially located at the same node. We are able to achieve
dispersion in O(m) rounds using ideas we used in the prior section and a technique to prevent robots from
getting caught in cycles. A robot will get caught in a cycle if it is exploring the graph and cannot ﬁgure out
if it has already visited a node or not. Note that this problem arises only due to our constraint on every
robot’s memory.
Our technique to solve this problem is as follows. Since all robots follow the same path, it is easy to tell
if we have previously visited a given node by checking if that node has a robot already assigned to it. If
so, the exploring robot can backtrack and visit some other node. However, a robot must be able to discern
6

whether it is exploring or backtracking. In order to know which one it is doing, we require every settled
robot to maintain a pointer to the port it used to enter its assigned node. This acts as a parent pointer. If
some other exploring robot leaves the node through this same port, then it is backtracking. This can easily
be found out by having every settled node transmit its parent pointer to other robots co-located on the same
node as it during the communication part of a round. The reason we require all robots to start at the same
node initially is because this method to keep track of backtracking fails if we have robots starting at multiple
places.
The algorithm uses four variables, port entered, parent ptr, state, and rnd cntr. port entered denotes
the port through which a robot entered the current node. parent ptr is used by a settled robot to indicate
the port that that robot used to reach the current node. state indicates the current state of the robot:
exploring, settled, or backtracking. rnd cntr is used to keep track of the rounds.
Algorithm 2 Rooted-Graph-LogN, run by each robot u
1: Initialize the following values: port entered ← −1, parent ptr ← ⊥, state ← explore.
2: for rnd cntr ← 1, 2m do
3:
Set port entered to the port entered through.
4:
if state = explore then
5:
if Node has robot assigned to it then
6:
state ← backtrack. Move through port entered.
7:
else
8:
if u is lowest label robot on node then
9:
u assigns itself to node, state ← settled, parent ptr ← port entered.
10:
if state 6= settled then
11:
port entered ← (port entered + 1) mod degree of node.
12:
if port entered = parent ptr of robot assigned to node then
13:
state ← backtrack.
14:
Move through port entered
15:
else if state = backtrack then
16:
port entered ← (port entered + 1) mod degree of node.
17:
if port entered 6= parent ptr of node then
18:
state ← explore.
19:
Move through port entered.

Theorem 3. Algorithm Rooted-Graph-LogN can be run by robots with O(log n) bits of memory to ensure
dispersion occurs in O(m) rounds on rooted graphs.
Proof. Since each robot performs the algorithm for 2m rounds, it is clear to see that running time is O(m)
rounds. Regarding memory, port entered, parent ptr, and rnd cntr each take O(log n) bits of memory,
state takes two bits of memory (recall O(log m) = O(log n2 ) = O(log n)), and each robot needs O(log n) bits
of memory to compare labels in order to decide which robot will be assigned to a given node. Thus every
robot requires O(log n) bits of memory to run the algorithm.
We now need to show that dispersion is achieved in 2m rounds. Because every robot starts at the same
node and follows the same path as other unsettled robots until it is assigned to a node, we just need to
show that the last robot is settled within 2m rounds. Algorithm Rooted-Graph-LogN represents a depth-ﬁrst
search of the graph and thus every edge is traversed at most twice. There are m edges and thus within 2m
rounds, all edges will be traversed at least once and by extension all nodes will be visited and all robots will
be settled.

7

4.3

Dispersion without Stopping on an Arbitrary Graph

In this section, we describe an algorithm that can be run by robots with O(log n) bits of memory to achieve
dispersion in O(∆D ) rounds. However, robots must perform this algorithm forever and won’t stop.
The approach we use in this section bears similarity to the approach in Path-Ring-Tree-LogN in Section 4.1. We still have every robot perform a DFS until it ﬁnds a node it can settle down at. However, the
key to this approach is that we have the robot run multiple restricted depth DFS’s. For any given robot
running a d-restricted DFS, we only allow it to perform a DFS up to depth at most d. Each robot performs
multiple d-restricted DFS’s, for increasing values of d, until it assigns itself to a node.
With such limited memory and robots starting at arbitrary nodes, it is not easy to check if the robot is
in a cycle as was done in the Section 4.2. Instead, we utilize the fact that a robot performing a D-restricted
DFS will eventually visit every node. Thus it is guaranteed that every robot will ﬁnd a node it can assign
itself to.
The reason that the robots must perform this algorithm forever and cannot stop is because even after
a robot settles down, it must still be available to communicate and exchange information with exploring
robots. A settled robot must be active until all exploring robots that might possibly need information from
it have settled down themselves. However, in order for a robot to continue running the algorithm even after
it has settled at a node, we would need a method to eventually signal to the robot that it should stop. One
such method is having every robot maintain a round counter that would require an extra O(n log n) bits of
memory for each robot, which is too much. A possible way around this is to have robots, once settled, inform
other robots of this fact. However, this particular algorithm requires robots to not move once they’re settled.
This can be contrasted against the algorithm Rooted-Tree-Delta-LogN, which we present in Section 5.1, where
robots use such movement to signal to other robots that they may stop running the algorithm.
The algorithm uses seven variables, port entered, parent ptr, state, DF S cntr, DF S done, starting node,
and dist f rom start node. port entered denotes the port through which a robot entered the current node.
parent ptr is used by a settled robot to indicate the port that that robot used to reach the current node. state
indicates the current state of the robot: exploring, settled, or backtracking. DF S cntr is used by exploring
robots to know the current value of d for the d-restricted DFS it’s running. DF S done is a boolean variable
denoting whether the current restricted DFS is over or not. starting node denotes the robot assigned to
the root node from which DFS starts. dist f rom start node is used by unassigned robots to indicate the
current distance of the robot from the starting node of the DFS.
Theorem 4. Algorithm Graph-LogN can be perpetually run by robots with O(log n) bits of memory to ensure
dispersion occurs in O(∆D ) rounds on arbitrary graphs.
Proof. Regarding memory complexity of robots, port entered, parent ptr, starting node, and dist f rom start node
each take O(log n) bits of memory, DF S done takes one bit of memory, state takes two bits of memory, and
each robot needs O(log n) bits of memory to compare labels in order to decide which robot will be assigned
to a given node. DF S cntr will only need O(log n) bits of memory because it is only incremented when a
robot has not assigned itself to a node yet. After running a D-restricted DFS, it is guaranteed that all nodes
will be visited and thus no more than O(log D) = O(log n) bits are required for it. Thus every robot requires
O(log n) bits of memory to run the algorithm.
We now need to show that dispersion is achieved in O(∆D ) rounds. We show that any robot will
eventually assign itself to a node. We then bound the total running time until a every robot assigns itself to
a node.
Consider a D-restricted DFS on a graph. Since the distance between any two nodes is at most D, all
nodes on the graph will be visited at least once in the course of the DFS. A robot which has not assigned
itself to a node will eventually run a D-restricted DFS and will assign itself to a node.
We now bound the time taken to run up to D restricted DFS’s. A d-restricted DFS takes maximum time
when each node has maximum degree ∆. The time taken to perform such a DFS would be ≤ 4∆d rounds.
D
P
4∆d = O(∆d )
Thus, in order to run D such d-restricted DFS’s with increasing values of d, it will take ≤
i=0

rounds.
8

Algorithm 3 Graph-LogN, run by each robot u
1: Initialize the following values: port entered ← −1, parent ptr ← ⊥, state ← explore, DF S cntr ← 0,
DF S done ← F ALSE, starting node ← u, dist f rom start node ← −1.
2: if u is lowest label robot on node then
3:
state ← settled.
4: else
5:
starting node ← label of lowest label robot.
6: while TRUE do
7:
if state 6= settled then
8:
Increment DF S cntr.
9:
DF S done ← F ALSE.
10:
while DF S done = f alse do
11:
Set port entered to the port entered through.
12:
if state = explore then
13:
Increment dist f rom start node.
14:
if dist f rom start node = DF S cntr then
15:
if Node is unassigned and u is lowest label robot on node then
16:
u assigns itself to node, state ← settled, parent ptr ← port entered.
17:
else
18:
state ← backtrack. Move through port entered.
19:
else
20:
if Node is unassigned and u is lowest label robot on node then
21:
u assigns itself to node, state ← settled, parent ptr ← port entered.
22:
if state 6= settled then
23:
port entered ← (port entered + 1) mod degree of node.
24:
if port entered = parent ptr of robot assigned to node then
25:
state ← backtrack.
26:
Move through port entered.
27:
else if state = backtrack then
28:
Decrement dist f rom start node.
29:
if Robot at current node is starting node
and port entered = degree −1 of starting node then
30:
DF S done ← T RU E, state ← explore.
31:
else
32:
port entered ← (port entered + 1) mod degree of node.
33:
if port entered 6= parent ptr of node then
34:
state ← explore.
35:
Move through port entered.

9

5

Dispersion with O(∆ + log n) Bits of Memory

We look at dispersion on a rooted tree when the memory of each robot is O(∆ + log n) bits. This result is
particularly interesting because we show that the addition of a few bits of memory dramatically reduces the
time needed to achieve dispersion.

5.1

Dispersion on a Rooted Tree

A rooted tree is a tree where all robots start at one node called the root. We look at dispersion on a rooted
tree and show that when the memory of each robot is O(∆ + log n) bits, we can achieve dispersion in O(D2 )
rounds.
We deﬁne a fully dispersed subtree rooted at a node to be a subtree with that node as the root
where every node has a robot assigned to it. We use the term settled robot to denote a robot which is
assigned to a node.
Our algorithm works in stages. Each stage corresponds to (i) the unassigned robots located at the root
exploring the tree one level deeper than the previous stage and assigning themselves to empty nodes when
possible, and (ii) settled robots updating their information about which ports lead to fully dispersed subtrees.
Once a settled robot decides that the subtree rooted at the node it’s been assigned to has been fully dispersed,
it stops executing the algorithm.
Each robot is in one of four states: (i) root, (ii) explore, (iii) wait, or (iv) settled. Only one robot will
be in state root and this is the robot that has been assigned to the root of the tree. This robot executes the
algorithm until the subtree rooted at its node is fully dispersed.
A robot in the settled state is essentially assigned to a given node. It maintains a pointer to the port
it used to reach this node initially. It also maintains up to ∆ bits of memory, one bit per port, to denote
whether a given port has been completely dispersed. We say that a port has been completely dispersed
when the subtree rooted at the node attached to the port has been fully dispersed. For the remainder of this
section, we use level and depth to mean the same thing.
For a given node, deﬁne an unassigned leaf of the node as a descendant v of the node in the tree
such that (i) v is unassigned and (ii) v’s immediate parent is assigned a robot. If the given node is itself
unassigned a robot but its parent is assigned a robot, we deﬁne the number of unassigned leaves of the node
as 1. If the given node and its parent are both unassigned robots, we deﬁne its number of unassigned leaves
as 0.
The algorithm uses nine variables, port entered, parent ptr, state, dist f rom root, f ully dispersed port[∆],
f ully dispersed, num robots reqd, lvl cntr, and rnd cntr. port entered denotes the port through which a
robot entered the current node. parent ptr is used by a settled robot to indicate the port that that robot
used to reach the current node. state indicates the current state of the robot: exploring, settled, or backtracking. dist f rom root indicates the distance of the current node from the root. f ully dispersed port[∆]
is an array used by settled robots indicating if a given port leads to a fully dispersed subtree or not (an entry
of 1 or 0 respectively for that port’s index). f ully dispersed is a boolean variable used by settled robots
indicating whether the subtree rooted at the robot’s node is fully dispersed or not. num robots reqd is used
by a settled robot to indicate how many robots are currently needed to ﬁll its unassigned leaves. lvl cntr is
used to denote the current maximum level to which robots will explore the tree. rnd cntr is used to denote
the current round for a given stage.
We would like to make an important note regarding the lack of requirement of knowledge of ∆ for this
algorithm. The variable f ully dispersed port[∆] requires at least ∆ bits of memory, but does not require
the explicit knowledge of the value of ∆. Rather, so long as ≥ ∆ bits are provided to store the array, the
algorithm works properly.
Every stage lvl cntr consists of 2 ∗ lvl cntr + 1 rounds. The ﬁrst lvl cntr rounds are used by robots in
state explore to traverse the tree to depth lvl cntr − 1 with the help of procedure Further-Explore. FurtherExplore guarantees the following property: in the given stage, if a given node has x unassigned leaves,
exactly x robots will be sent to the node in the course of the exploration. This is achieved as follows through
Further-Explore. For a given node v with children that are settled, in the round where robots reach v, the
10

robots assigned to v’s children would have moved up to v as well and transmitted the number of unassigned
leaves (i.e. number of robots required to be sent through each port). In the subsequent round, these children
of v return to their assigned nodes and the robots in state explore know exactly which port to traverse. Once
robots reach the parent of an unassigned node, one robot goes to each unassigned node and gets assigned to
that node using procedure Robot-Assignment.
A robot in explore state not sent from the root changes its state to wait and waits for the beginning of
the next stage. Just before the start of a new stage, all nodes in state wait change their state to explore.
The second lvl cntr rounds of a stage are used by robots in state settled to propagate information up
to their parents about whether the subtree rooted at the corresponding node is fully dispersed or not. This
propagation of information occurs in a bottom up fashion with robots at level lvl cntr − 1 moving up to
inform robots at their parents about this information. Subsequently robots at level lvl cntr − 1 move up
and inform their parents and so on.
The last round in the stage is used by robots at depth 1 to move to the root in preparation for the next
stage.
Algorithm 4 Robot-Assignment, a procedure run by each robot u
1: Let δ be degree of node.
2: if state = root then
3:
num robots reqd ← δ.
4: else
5:
num robots reqd ← δ − 1, parent ptr ← port entered.
6: Set entries in f ully dispersed port from index δ to ∆ − 1 to 1.

Algorithm 5 Further-Explore, a procedure run by each robot u
1: Let δ be degree of node. Order ports in increasing order of port numbers excluding node’s robot’s
parent ptr port and any fully dispersed ports. Every robot on the node knows this same order p1 , . . . , pk
now.
2: Coordinate with other robots to calculate your position in the order of increasing labels of exploring
robots.
3: if Nodes from one level down are present on this node and communicating their num robots reqd values
then
4:
Robots are assigned to ports in increasing label order until all port’s num robots reqd requirements
are ﬁlled. Remaining robots stay unassigned.
5: else
6:
Robots are assigned to ports in increasing label order such that one robot is assigned per port.
Remaining robots stay unassigned.
7: if u was assigned to a given port pi then
8:
u moves through port pi .
9:
Increment dist f rom root.
10: else
11:
state ← wait.

Theorem 5. Algorithm Rooted-Tree-Delta-LogN can be run by robots with O(∆ + log n) bits of memory to
ensure dispersion occurs in O(D2 ) rounds on rooted trees.
Proof. We ﬁrst show that algorithm Rooted-Tree-Delta-LogN only requires every robot to have O(∆ + log n)
bits of memory and then we subsequently prove the correctness and running time guarantees of the algorithm.
Every robot requires O(log ∆) bits of memory for port entered, O(log ∆) bits of memory for parent ptr, 2 bits
11

Algorithm 6 Rooted-Tree-Delta-LogN, run by each robot u
1: Initialize the following values: port entered ← 0, parent ptr ← ⊥, state ← explore, dist f rom root ←
0, f ully dispersed port[∆] ← [0, 0, . . . , 0], f ully dispersed ← F ALSE, num robots reqd ← 0,
lvl cntr ← 0.
2: if u is lowest label robot on node then
3:
state ← root.
4:
Robot-Assignment.
5: while f ully dispersed = F ALSE do
6:
Increment lvl cntr.
7:
for rnd cntr ← 1, 2 ∗ lvl cntr + 1 do
8:
if state = root then
9:
if A robot enters through a given port and its f ully dispersed bit = T RU E then
10:
Set the corresponding port entry in f ully dispersed port to 1.
11:
If all bits in f ully dispersed port set to 1, set f ully dispersed ← T RU E.
12:
else
13:
Do nothing this round.
14:
else if state = explore then
15:
Set port entered ← port entered through.
16:
if No robot assigned to node then
17:
state ← settled
18:
Robot-Assignment.
19:
if state 6= settled then
20:
Further-Explore.
21:
else if state = wait then
22:
Do nothing for round.
23:
if rnd cntr = 2 ∗ lvl cntr + 1 then
24:
state ← explore
25:
else if state = settled then
26:
if (rnd cntr = dist f rom root − 1) OR (rnd cntr = 2 ∗ lvl cntr − dist f rom root) OR
(dist f rom root = 1 AND rnd cntr = 2 ∗ lvl cntr + 1 AND f ully dispersed = F ALSE)
then
27:
If all but parent ptr port of f ully dispersed port is set to 1, set f ully dispersed ← T RU E.
28:
Move through parent ptr port.
29:
else if (rnd cntr = dist f rom root) OR (rnd cntr = 2 ∗ lvl cntr − dist f rom root + 1) then
30:
Set port entered ← port entered through.
31:
Communicate with robot(s) at current node and inform them about u’s f ully dispersed,
port entered, and num robots reqd values.
32:
Move through port entered port.
33:
else
34:
If any robots inform u about f ully dispersed and port entered values, update the
corresponding values in f ully dispersed port. If robots inform u about their
num robots reqd values, update u’s num robots reqd value with the sum of all values
heard.

12

of memory for state, O(log D) bits of memory for dist f rom root, ∆ bits of memory for f ully dispersed port,
1 bit of memory for f ully dispersed, O(log D) bits for rnd cntr, O(log n) bits for num robots reqd, O(log D)
bits of memory for lvl cntr, and O(log n) bits of memory to compare labels when deciding which robots will
be assigned to a given node. Thus each robot requires O(∆ + log n) bits of memory in order to successfully
run Rooted-Tree-Delta-LogN.
We prove the correctness of the algorithm by showing that the following induction hypothesis holds true
for all 1 ≤ i ≤ d + 1.
Lemma 1. At the end of stage i of Rooted-Tree-Delta-LogN, all nodes at depth ≤ i − 1 have robots assigned
to them, for all 1 ≤ i ≤ d + 1.
Proof. At the end of stage 1, the only node at depth 0, the root, has a robot assigned to it. So the base case
of the induction holds true.
Let us assume that the induction hypothesis holds true for some stage i, i.e. at the end of stage i all
nodes at depth ≤ i − 1 have robots assigned to them. We now must show that at the end of stage i + 1,
all nodes at depth ≤ i have robots assigned to them. We show this by showing that for every unassigned
leaf of the root at the beginning of stage i + 1, we send exactly one robot to it by the end of stage i + 1.
This implies that all nodes at depth i at the end of stage i + 1 will have robots assigned to them. Note that
once a node has a robot assigned to it, that robot will never be unassigned from that node, so all nodes at
previous depth levels continue to have robots assigned to them.
In a given stage i, the ﬁrst i rounds are used for exploration and the second i rounds are used to update
robots assigned to nodes about the number of their assigned leaves. Thus at the end of stage i, each robot
knows the total number of assigned leaves it has, even if it doesn’t know which ports lead to how many
unassigned leaves. During the ﬁrst i + 1 rounds of stage i + 1, in every round r the following three types of
robots will be present in nodes at depth r − 1: (i) exploring robots, (ii) robots assigned to nodes at depth
r − 1, and (iii) any robots assigned to children of nodes at depth r − 1 if those children themselves have
unassigned leaves.
For any node at depth r − 1 at round r, one of two cases may occur. Either its children are all unassigned
nodes or they are assigned nodes. In the former case, one robot moves down each port leading to an
unassigned node. In the latter case, the robots are able to communicate with each other in round r and
coordinate such that the number of robots that move down each port is equivalent to the exact number of
unassigned leaves of the node attached to that port.
Thus for a given stage i + 1, after i + 1 rounds, all nodes at levels ≤ i have robots assigned to them.
Thus, for a depth d tree, after d + 1 stages, all nodes will have robots assigned to them. Furthermore,
for a given node v, if the subtree rooted at that node is fully dispersed by the end of a given stage i, then by
the end of stage i the robot assigned to v will be present on v and will stop executing the algorithm. Thus
at the end of stage d + 1, all robots stop executing the algorithm and dispersion is achieved.
As for running time, since there are d + 1 stages and each stage takes O(d) rounds, each robot executes
a total of O(d2 ) = O(D2 ) rounds. Thus the running time of Rooted-Tree-Delta-LogN is O(D2 ) rounds.

6

Dispersion with O(n log n) Bits of Memory

We look at dispersion on an arbitrary graph and present an O(m) round algorithm to achieve it when the
memory of each robot is O(n log n) bits. We use a mixture of the ideas from algorithms Rooted-Graph-LogN
and Graph-LogN in Sections 4.2 and 4.3 respectively.

6.1

Dispersion on a Graph

Brieﬂy recall that a d-restricted DFS is a depth ﬁrst search performed by a robot where the depth of the
search is restricted to at most d. In Graph-LogN, we used the idea of using a sequence of d-restricted DFS’s
with increasing value of d which guaranteed that all nodes in the graph would be visited. However, we were

13

Algorithm 7 Graph-N-LogN, run by each robot u
1: Initialize the following values:
port entered ← −1, parent ptr ← ⊥, state ← explore,
dist f rom start node ← −1, labels seen so f ar[n].
2: if u is lowest label robot on node then
3:
state ← settled.
4: else
5:
Add u to labels seen so f ar.
6: for rnd cntr ← 1, 2m do
7:
Set port entered to the port entered through.
8:
if state = explore then
9:
Increment dist f rom start node.
10:
if (dist f rom start node = n) OR (Node has robot v assigned to it and v in labels seen so f ar)
then
11:
if Node is unassigned and u is lowest label robot on node then
12:
u assigns itself to node, state ← settled, parent ptr ← port entered.
13:
else
14:
state ← backtrack. Move through port entered.
15:
else
16:
if Node has robot v assigned to it then
17:
Add v to labels seen so f ar.
18:
else
19:
if u is lowest label robot on node then
20:
u assigns itself to node, state ← settled, parent ptr ← port entered.
21:
else
22:
Add lowest label seen among robots on node to labels seen so f ar.
23:
if state 6= settled then
24:
port entered ← (port entered + 1) mod degree of node.
25:
if port entered = parent ptr of robot assigned to node then
26:
state ← backtrack.
27:
Move through port entered.
28:
else if state = backtrack then
29:
Decrement dist f rom start node
30:
port entered ← (port entered + 1) mod degree of node.
31:
if port entered 6= parent ptr of node then
32:
state ← explore.
33:
Move through port entered.

14

unable to have robots stop performing the algorithm. We can ﬁx this and have robots stop by performing
just one n-restricted DFS and by using the cycle checking idea from Rooted-Graph-LogN. In that algorithm,
robots checked if they were exploring a cycle by checking if the current node had been previously visited.
Due to limited memory, our cycle checking mechanism relied on identifying a previously visited node by the
fact that a robot was already assigned to it. By allowing each robot to have O(n log n) bits of memory,
robots can check for cycles of length up to n. Since there are n nodes, we are guaranteed to never land up
in a cycle.
The algorithm uses six variables, port entered, parent ptr, state, dist f rom start node, labels seen so f ar[n],
and rnd cntr. port entered denotes the port through which a robot entered the current node. parent ptr is
used by a settled robot to indicate the port that that robot used to reach the current node. state indicates the
current state of the robot: exploring, settled, or backtracking. dist f rom start node is used by unassigned
robots to indicate the current distance of the robot from the starting node of the DFS. labels seen so f ar[n]
is an array of size n which is used by exploring robots to store the labels of robots assigned to nodes they’ve
already traversed in the DFS. rnd cntr is used to keep track of the rounds.
Theorem 6. Algorithm Graph-N-LogN can be run by robots with O(n log n) bits of memory to ensure
dispersion occurs in O(m) rounds on rooted graphs.
Proof. Every robot is active for 2m rounds, so it is clear to see that the running time is O(m) rounds.
port entered, parent ptr, dist f rom start node, and rnd cntr each take O(log n) bits of memory (recall
O(log m) = O(log n2 ) = O(log n)), state takes one bit of memory, labels seen so f ar[n] takes O(n log n)
bits of memory, and each robot needs O(log n) bits of memory to compare labels in order to decide which
robot will be assigned to a given node. Thus every robot requires O(n log n) bits of memory to run the
algorithm.
We now need to show that dispersion is achieved in 2m rounds. Recall that an n-restricted DFS will visit
all nodes at least once and thus all robots will eventually assign themselves to one node each. Our goal is to
now bound the time taken to perform this DFS.
Consider a given robot u. The labels of robots stored in its labels seen so f ar correspond to nodes that
u has passed through every port of. Thus Graph-N-LogN represents a depth-ﬁrst search of the graph and
thus every edge is traversed at most twice. There are m edges and thus within 2m rounds, all edges will be
traversed at least once and by extension all nodes will be visited and all robots will be settled.
Notice an interesting property of the algorithm. The reason robots are required to have O(n log n) bits
of memory is in order to store the values of labels seen so f ar. We store n labels as we allow up to an
n-restricted DFS. However, recall that if a robot executes a D-restricted DFS, it is guaranteed that all robots
will be visited in the graph. Therefore, if robots know the value of D, it is enough to have labels seen so f ar
only hold at most D labels. If we subsequently changed Line 10 of the algorithm so that the condition checked
is changed from dist f rom start node = n to dist f rom start node = D, then we can achieve dispersion
using less memory, as captured by the following corollary.
Corollary 1. If the value of the diameter of the graph, D, is known to all robots, then with minor changes
to algorithm Graph-N-LogN, robots can achieve dispersion in O(m) rounds and will only require O(D log n)
bits of memory.

7

Conclusions and Future Work

We proposed a new problem, called dispersion, for mobile robots on graphs which is closely related to the
problems of scattering on graphs, collective mobile robot exploration, and load balancing on graphs. We
provided a lower bound for the memory required by each robot to achieve dispersion. We also developed
algorithms to solve this problem for various types of graphs given diﬀerent constraints on memory. We list
open problems of interest below.
Open Problem 1: Can we develop a o(n) round algorithm to achieve dispersion in arbitrary trees?

15

Open Problem 2: Can we develop an algorithm to achieve dispersion with stopping in arbitrary graphs
when robots have o(n log n) bits of memory?

Acknowledgements
We would like to thank Vishvajeet Nagargoje for useful discussions at various stages of this work.

References
[1] A. Agarwalla, J. Augustine, W. K. Moses Jr., M. Sankar K., and A. K. Sridhar. Deterministic dispersion
of mobile robots in dynamic rings. CoRR, abs/1707.06391, 2017.
[2] C. Ambühl, L. Gasieniec,
A. Pelc, T. Radzik, and X. Zhang. Tree exploration with logarithmic memory.
֒
ACM Transactions on Algorithms (TALG), 7(2):17, 2011.
[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] P. Berenbrink, C. Cooper, T. Friedetzky, T. Friedrich, and T. Sauerwald. Randomized diﬀusion for
indivisible loads. Journal of Computer and System Sciences, 81(1):159–185, 2015.
[5] P. Berenbrink, T. Friedetzky, and Z. Hu. A new analytical method for parallel, diﬀusion-type load
balancing. Journal of Parallel and Distributed Computing, 69(1):54–61, 2009.
[6] H. L. Bodlaender and J. van Leeuwen. Distribution of Records on a Ring of Processors. Department of
Computer Science, University of Utrecht, 1986.
[7] P. Brass, F. Cabrera-Mora, A. Gasparri, and J. Xiao. Multirobot tree and graph exploration. IEEE
Transactions on Robotics, 27(4):707–717, 2011.
[8] 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.
[9] R. Cohen, P. Fraigniaud, D. Ilcinkas, A. Korman, and D. Peleg. Label-guided graph exploration by a
ﬁnite automaton. ACM Transactions on Algorithms (TALG), 4(4):42, 2008.
[10] G. Cybenko. Dynamic load balancing for distributed memory multiprocessors. Journal of Parallel and
Distributed Computing, 7(2):279–301, 1989.
[11] D. Dereniowski, Y. Disser, A. Kosowski, D. Pajak,
֒ and P. Uznański. Fast collaborative graph exploration.
Information and Computation, 243:37–49, 2015.
[12] K. Diks, P. Fraigniaud, E. Kranakis, and A. Pelc. Tree exploration with little memory. In Proceedings
of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, pages 588–597. Society for
Industrial and Applied Mathematics, 2002.
[13] 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.
[14] 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.
[15] M. Dynia, J. LopuszaŃski, and C. Schindelhauer. Why robots need maps. In International Colloquium
on Structural Information and Communication Complexity, pages 41–50. Springer, 2007.
16

[16] Y. Elor and A. M. Bruckstein. Uniform multi-agent deployment on a ring. Theoretical Computer Science,
412(8-10):783–795, 2011.
[17] P. Fraigniaud, L. Gasieniec, D. R. Kowalski, and A. Pelc. Collective tree exploration. Networks,
48(3):166–177, 2006.
[18] 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.
[19] A. Menc, D. Pajak, and P. Uznanski. On the power of one bit: How to explore a graph when you cannot
backtrack? arXiv preprint, 2015.
[20] S. Muthukrishnan, B. Ghosh, and M. H. Schultz. First-and second-order diﬀusive methods for rapid,
coarse, distributed load balancing. Theory of computing systems, 31(4):331–354, 1998.
[21] C. Ortolf and C. Schindelhauer. A recursive approach to multi-robot exploration of trees. In International
Colloquium on Structural Information and Communication Complexity, pages 343–354. Springer, 2014.
[22] D. Peleg and A. Van Gelder. Packet distribution on a ring. Journal of Parallel and Distributed Computing, 6(3):558–567, 1989.
[23] T. Sauerwald and H. Sun. Tight bounds for randomized load balancing on arbitrary network topologies.
In Foundations of Computer Science (FOCS), 2012 IEEE 53rd Annual Symposium on, pages 341–350.
IEEE, 2012.
[24] 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.
[25] R. Subramanian and I. D. Scherson. An analysis of diﬀusive load-balancing. In Proceedings of the sixth
annual ACM symposium on Parallel algorithms and architectures, pages 220–225. ACM, 1994.
[26] Y. Sudo, D. Baba, J. Nakamura, F. Ooshita, H. Kakugawa, and T. Masuzawa. A single agent exploration
in unknown undirected graphs with whiteboards. IEICE Transactions on Fundamentals of Electronics,
Communications and Computer Sciences, 98(10):2117–2128, 2015.
[27] 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.

17

