# On the Computational Power of Energy-Constrained Mobile Robots: Algorithms
and Cross-Model Analysis††thanks: This work was supported in part by JSPS
KAKENHI No. 20K11685 and 21K11748, Israel & Japan Science and Technology
Agency (JST) SICORP (Grant#JPMJSC1806), and by the Natural Sciences and
Engineering Research Council of Canada (NSERC) under Discovery Grants A2415
and 203254.

Kevin Buchin  TU Eindhoven, The Netherlands  Paola Flocchini  University of
Ottawa, Canada  Irina Kostitsyna  TU Eindhoven, The Netherlands  Tom Peters
TU Eindhoven, The Netherlands  Nicola Santoro  Carleton University, Canada
Koichi Wada  Hosei University, Tokyo, Japan

###### Abstract

We consider distributed systems of identical autonomous computational
entities, called robots, moving and operating in the plane in synchronous
$\mathit{Look}$-$\mathit{Compute}$-$\mathit{Move}$ ($\mathit{LCM}$) cycles.
The algorithmic capabilities of these systems have been extensively
investigated in the literature under four distinct models ($\mathcal{OBLOT}$,
$\mathcal{FST\\!A}$, $\mathcal{FCOM}$, $\mathcal{LUMI}$), each identifying
different levels of memory persistence and communication capabilities of the
robots. In spite of their differences, they all always assume that the robots
have unlimited amounts of energy.

In this paper we remove this assumption, and start the study of the
computational capabilities of robots whose energy is limited, albeit
renewable. More precisely, we consider systems where an activated entity uses
all its energy to execute an $\mathit{LCM}$ cycle, and the energy can be
restored through a period of inactivity.

We first study the impact that memory persistence and communication
capabilities have on the computational power of such energy-constrained
systems of robots; we do so by analyzing the computational relationship
between the four models under this energy constraint. We provide a complete
characterization of this relationship. Among the many results of this cross-
model analysis we prove that for energy-constrained robots, $\mathcal{FCOM}$
is more powerful than $\mathcal{FST\\!A}$ (that is, it is better to
communicate than to remember). Integral part of the proof is the design and
analysis of an algorithm that allows robots in $\mathcal{FCOM}$ to execute
correctly any protocol for the more powerful $\mathcal{LUMI}$ model.

We then study the difference in computational power caused by the energy
restriction, and provide a complete characterization of the relationship
between energy-restricted and unrestricted robots in each of the models. We
prove that, within $\mathcal{LUMI}$ there is no difference; integral part of
the proof is the design and analysis of an algorithm that in $\mathcal{LUMI}$
allows energy-constrained robots to execute correctly any protocol for robots
with unlimited energy. We then show the (apparently counter-intuitive) result
that in all other models, the energy constraint actually provides the robots
with a computational advantage.

At the basis of our results is the mapping allowing to represent a system of
energy-constrained robots as a system of robots with unlimited energy but
subject to a special adversarial activation scheduler.

##  1 Introduction

###  1.1 Framework: Background and Cross-Model Analysis

In this paper, we consider distributed systems composed of identical
autonomous computational entities, viewed as points and called robots, moving
and operating in the Euclidean plane in synchronous
$\mathit{Look}$-$\mathit{Compute}$-$\mathit{Move}$ ($\mathit{LCM}$) cycles.

In each synchronous round, a non-empty set of (possibly all) robots is
activated, each performs its $\mathit{LCM}$ cycle simultaneously, and
terminates by the end of the round. Each cycle is composed of three phases; in
the $\mathit{Look}$ phase, an entity obtains a snapshot of the space showing
the positions of the other robots; in the $\mathit{Compute}$ phase, it
executes its algorithm (the same for all robots) using the snapshot as input;
it then moves towards the computed destination in the $\mathit{Move}$ phase.
Repeating these cycles, the robots are able to collectively perform some tasks
and solve some problems.

The selection of which robots are activated in a round is made by an
adversarial scheduler. This general setting is usually called semi-synchronous
(Ssynch); the special restricted setting where every robot is activated in
every round is called fully-synchronous (Fsynch) .

These systems have been extensively investigated within distributed computing.
The research focus has been on understanding the nature and the extent of the
impact that crucial factors, such as memory persistence and communication
capability, have on the solvability of a problem and thus on the computational
power of the system. To this end, four models have been identified and
investigated: $\mathcal{OBLOT}$, $\mathcal{FST\\!A}$, $\mathcal{FCOM}$, and
$\mathcal{LUMI}$.

In the most common (and weakest) model, $\mathcal{OBLOT}$, in addition to the
standard assumptions of anonymity and uniformity (robots have no IDs and run
identical algorithms), the robots are oblivious (they have no persistent
memory to record information of previous cycles) and they are silent (without
explicit means of communication). Computability in this model has been the
object of intensive research since its introduction in [30]; (e.g., see [1, 2,
4, 7, 8, 9, 16, 23, 17, 20, 30, 33, 34, 6, 21, 29]; as well as the recent book
and chapters therein [14]). Clearly, the restrictions created by the absence
of persistent memory and the incapacity of explicit communication severely
limit what the robots can do.

In the stronger $\mathcal{LUMI}$ model, formally introduced and defined in
[10], robots are provided with some (albeit limited) persistent memory and
communication means. In this model, each robot is equipped with a constant-
sized memory (called light), whose value (called color) can be set during the
$\mathit{Compute}$ phase. The light is visible to all the robots and is
persistent in the sense that it does not automatically reset at the end of a
cycle. Hence, these luminous robots are capable in each cycle of both
remembering and communicating a constant number of bits. There is a lot of
research work on the design of algorithms and the feasibility of problems for
luminous robots [3, 10, 18, 22, 12, 24, 25, 31, 26, 27, 32]; for a recent
survey, see [13]. The availability of both persistent memory and
communication, however limited, clearly renders luminous robots more powerful
than oblivious robots (see e.g., [10]).

Models $\mathcal{FST\\!A}$ and $\mathcal{FCOM}$ are sub-models of
$\mathcal{LUMI}$, introduced in [18] and studied in [24, 31]. They are helpful
to understand the individual computational power of persistent memory and
communication. In the first model, $\mathcal{FST\\!A}$, the light of a robot
is “internal”, i.e., visible only to that robot, while in the second model,
$\mathcal{FCOM}$, the light of a robot is visible only to the other robots but
not to the robot itself. Thus in $\mathcal{FST\\!A}$ the color merely encodes
an internal state; hence the robots are finite-state and silent. On the
contrary, in $\mathcal{FCOM}$, a robot can communicate to the other robots
through its colored light but forgets the content of its transmission by the
next cycle; that is, robots are finite-communication and oblivious.

Summarizing, to understand the computational power of these distributed
systems one needs to explore and determine the computational power of the
robots within each of these models, as well as (and more importantly) with
respect to each other.

This type of cross-model investigation has been taking place but rather
limited in scope (e.g., [18]). Recently, a substantial step has been taken in
[19] where, by integrating existing bounds and establishing new results, a
comprehensive map has been drawn of the computational relationship between the
four models, $\mathcal{OBLOT}$, $\mathcal{FST\\!A}$, $\mathcal{FCOM}$,
$\mathcal{LUMI}$, (and hence of the computational impact of the
presence/absence of persistent memory and/or communication capabilities) for
the two fundamental synchronous settings: fully-synchronous and semi-
synchronous.

###  1.2 The Energy Problem

In the vast existing literature on these systems of autonomous mobile
computational entities, surprisingly, no consideration has been made so far on
the energy required for the robots to be able to operate. In other words, the
existing research share the same implicit assumption, that the robots have an
unlimited amount of energy enabling them to perform their activities.

In this paper we remove this assumption, and start the study of the
computational capabilities of robots whose energy is limited, albeit
renewable. More precisely, we consider systems where an activated entity uses
all its energy to execute an $\mathit{LCM}$ cycle, and that once this happens
the robot is not operational and cannot be activated; the energy however can
be restored through a period of inactivity. This would be for example the case
if the robot’s power is provided by a battery rechargeable by energy
harvesting (as it is done in conceptually related systems such as wireless
mobile sensors [28]).

The immediate natural questions are: what is the computational power of these
energy-constrained robots ? and, in particular, what is the impact of the
crucial factors (memory and communication) in this case ?

In this paper we start investigating these questions.

###  1.3 Contributions

We consider systems where the energy of a robot is sufficient for executing
exactly one $\mathit{LCM}$ cycle, and the depleted energy is restored after
one round of inactivity. We investigate the computational power of the
distributed robotic systems described by the four models when the robots are
subject to such an energy-constraint.

Table 1: Relationships within Rsynch. | $\mathcal{\mathcal{FCOM}}^{RS}$ | $\mathcal{\mathcal{FST\\!A}}^{RS}$ | $\mathcal{\mathcal{OBLOT}}^{RS}$
---|---|---|---
$\mathcal{\mathcal{LUMI}}^{RS}$ |  $\equiv$ (Th.11) |  $>$ (Th.11) |  $>$ (Th.11)
$\mathcal{\mathcal{FCOM}}^{RS}$ | $-$ |  $>$ (Th.11) |  $>$ (Th.11)
$\mathcal{\mathcal{FST\\!A}}^{RS}$ | $-$ | $-$ |  $>$ (Th.11)

At the basis of our study is the computational correspondence between systems
of energy-restricted robots under Ssynch and those same systems when the
robots have unbounded energy (as traditionally considered in the literature)
but whose activation is under the control of a special adversarial synchronous
scheduler, Rsynch, never studied before, where the sets of robots activated in
any two consecutive rounds are restricted to be disjoint. This direct
correspondence enables us to reduce the cross-model investigation of these
energy-constrained robots to the cross-model investigation of energy-unbounded
robots under the Rsynch scheduler. Furthermore, it allows us to determine the
change (if any) in computational power due to the energy restrictions, by
determining the relationship between Rsynch and the general unrestricted
Ssynch scheduler.

Let $M^{S}$ and $M^{RS}$ denote the systems of unlimited-energy robots defined
by model
${M}\in\\{\mathcal{LUMI},\mathcal{FCOM},\mathcal{FST\\!A},\mathcal{OBLOT}\\}$,
under Ssynch and Rsynch, respectively (the latter being equivalent to the
systems of constrained energy robots under Ssynch).

We first study the impact that memory persistence and communication
capabilities have on the computational power of energy-constrained systems of
robots; we do so by analyzing the computational relationship between the four
models under this energy constraint. We provide a complete characterization of
this relationship proving that (see Table 1):

$\mathcal{\mathcal{LUMI}}^{RS}\equiv\mathcal{FCOM}^{RS}>\mathcal{FST\\!A}^{RS}>\mathcal{OBLOT}^{RS}$

where (as formally defined in Sect. 2.4) $\mathcal{}{X}>\mathcal{}{Y}$ denotes
that $\mathcal{}{X}$ is strictly more powerful than $\mathcal{}{Y}$,
$\mathcal{}{X}\equiv\mathcal{}{Y}$ denotes that $\mathcal{}{X}$ and
$\mathcal{}{Y}$ are computationally equivalent, and
$\mathcal{}{X}\bot\mathcal{}{Y}$, denotes that $\mathcal{}{X}$ and
$\mathcal{}{Y}$ are computationally incomparable.

Integral part of the proof that $\mathcal{FCOM}^{RS}$ is more powerful than
$\mathcal{FST\\!A}^{RS}$ (that is, it is better to communicate than to
remember), is the design and analysis of an algorithm that allows robots in
$\mathcal{FCOM}^{RS}$ to execute correctly any protocol for the more powerful
$\mathcal{LUMI}^{RS}$.

We then study what variation in computational power is created by the presence
of the energy restriction, by comparing the computational difference between
energy- restricted and unrestricted robots in each of the four models (i.e.,
between $M^{RS}$ and $M^{S}$ for each
${M}\in\\{\mathcal{LUMI},\mathcal{FCOM},\mathcal{FST\\!A},\mathcal{OBLOT}\\}$).
We provide a complete characterization (see Table 2). In particular, we prove
that within $\mathcal{LUMI}$, the strongest model, there is no difference;
i.e., $\mathcal{LUMI}^{RS}\equiv\mathcal{LUMI}^{S}$. Integral part of the
proof is the design and analysis of an algorithm that allows energy-
constrained robots to execute in $\mathcal{LUMI}^{RS}$ correctly any protocol
for robots with unlimited energy $\mathcal{LUMI}^{S}$. In all other models, we
prove that the energy constraint actually provides the robots with a definite
computational advantage; this apparently counter-intuitive result is due to
the fact that the energy restriction reduces the adversarial power of the
activation scheduler. Let us stress that the established characterization
covers all the cross-model and cross-scheduler relationships.

Table 2: Relationship between Rsynch and Ssynch. | $\mathcal{\mathcal{LUMI}}^{S}$ | $\mathcal{\mathcal{FCOM}}^{S}$ | $\mathcal{\mathcal{FST\\!A}}^{S}$ | $\mathcal{\mathcal{OBLOT}}^{S}$
---|---|---|---|---
$\mathcal{\mathcal{LUMI}}^{RS}$ $\equiv\mathcal{\mathcal{FCOM}}^{RS}$ |  $\equiv$ (Th.11) |  $>$ (Th.3) |  $>$ (Th.11, Th.3) |  $>$ (Th.11, Th.3)
$\mathcal{\mathcal{FST\\!A}}^{RS}$ |  $<$ (Th.11) |  $\bot$ (Th.4) |  $>$ (Th.3) |  $>$ (Th.11, Th.3)
$\mathcal{\mathcal{OBLOT}}^{RS}$ |  $<$ (Th.11) |  $\bot$ (Th.3) |  $\bot$ (Th.3) |  $>$ (Th.3)
Table 3: Relationship between Fsynch and Rsynch. | $\mathcal{\mathcal{LUMI}}^{RS}\equiv\mathcal{\mathcal{FCOM}}^{RS}$ | $\mathcal{\mathcal{FST\\!A}}^{RS}$ | $\mathcal{\mathcal{OBLOT}}^{RS}$
---|---|---|---
$\mathcal{\mathcal{LUMI}}^{F}$ $\equiv\mathcal{\mathcal{FCOM}}^{F}$ |  $>$ (Th.7) |  $>$ (Th.7, Th.11) |  $>$ (Th.7, Th.11)
$\mathcal{\mathcal{FST\\!A}}^{F}$ |  $\bot$ (Th.8) |  $>$ (Th.7) |  $>$ (Th.7, Th.11)
$\mathcal{\mathcal{OBLOT}}^{F}$ |  $\bot$ (Th.9) |  $\bot$ (Th.9) |  $>$ (Th.7)

Finally, we complete the study of systems of energy-restricted robots by
analyzing the relationship between their computational power and that of
robots with unlimited energy under the most benign synchronous activation
scheduler Fsynch (i.e., fully synchronous). In this case, perhaps not
surprising, we prove that, in each model, energy-constrained robots are
strictly less powerful than fully-synchronous ones with unbounded energy (see
Table 3). Also in this study, the characterization covers all the cross-model
and cross-scheduler relationships.

An interesting consequence of our investigation is that it provides a novel
insight in the landscape of synchronous activation environments. In fact, it
identifies the presence of a novel synchronous environment which lies in
between the semi-synchronous and the fully synchronous ones. It is worth
noting that the computational cross-model “map” of the new scheduler Rsynch
(which includes Round Robin as a particular case) has the same structure as
that of Fsynch. A graphical summary of all results and of these observations
is shown in Figure 1.

Figure 1: Summary of relationships.

##  2 Models and Preliminaries

###  2.1 The Basics

Each robot operates in $\mathit{Look}$-$\mathit{Compute}$-$\mathit{Move}$
($\mathit{LCM}$) cycles: it observes its surroundings, it computes a
destination within the space based on what it sees, and it moves toward the
destination. It can observe its surroundings and move within the space based
on what it sees. The same space may be populated by several mobile robots,
each with its local coordinate system, and static objects.

The system consists of a set $R=\\{r_{0},\cdots,r_{n-1}\\}$ of computational
entities, called robots, modeled as geometric points, that live in
$\mathbb{R}^{2}$, where they can move freely and continuously. The robots are
autonomous without a central control. They are indistinguishable by their
appearance, do not have internal identifiers, and execute the same algorithm.

Let $x_{i}(t)$ denote the location of robot $r_{i}$ at time $t$ in a global
coordinate system (unknown to the robots), and let $X(t)=\\{x_{i}(t):0\leq
i\leq{n-1}\\}=\\{x_{0}(t),x_{1}(t),\ldots,x_{m-1}(t)\\}$; observe that
$|X(t)|=m\leq n$ since several robots might be at the same location at time
$t$.

Each robot has its own local coordinate system and it perceives itself at its
origin. A robot is equipped with devices that allow it to observe the
positions of the other robots in its local coordinate system.

The robots operate in $\mathit{Look}$-$\mathit{Compute}$-$\mathit{Move}$
($\mathit{LCM}$) cycles. When activated, a robot executes a cycle by
performing the following three operations:

  1. 1.

Look: The robot obtains a snapshot of the positions occupied by robots
expressed with respect to its own coordinate system; this operation is assumed
to be instantaneous.

  2. 2.

Compute: The robot executes the algorithm using the snapshot as input; the
result of the computation is a destination point.

  3. 3.

Move: The robot moves towards the computed destination. If the destination is
the current location, the robot stays still.

The system is synchronous; that is, time is divided into discrete intervals,
called rounds. In each round a robot is either active or inactive. The robots
active in a round perform their $\mathit{LCM}$ cycle in perfect
synchronization; if not active, the robot is idle in that round. All robots
are initially idle. In the following, we use round and time interchangeably.

Each robot has a bounded amount of energy, which is totally consumed whenever
it performs a cycle; its energy however is restored after being idle for a
round. A robot with depleted energy cannot be active.

Movements are said to be rigid if the robots always reach their destination.
They are said to be non-rigid if they may be unpredictably stopped by an
adversary whose only limitation is the existence of $\delta>0$, unknown to the
robots, such that if the destination is at distance at most $\delta$ the robot
will reach it, else it will move at least $\delta$ towards the destination.

There might not be consistency between the local coordinate systems and their
unit of distance. The absence of any a-priori assumption on consistency of the
local coordinate systems is called disorientation. The type of disorientation
can range from fixed, where each local coordinate system remains the same
through all the rounds, to variable where the direction, the orientation, and
the unit of distance of a robot may vary between successive rounds. In this
paper we consider only fixed disorientation.

The robots are said to have chirality if they share the same circular
orientation of the plane (i.e., they agree on “clockwise” direction). Notice
that, in presence of chirality, at any time $t$, there would exist a unique
circular ordering of the locations $X(t)$ occupied by the robots at that time;
let suc and pred be the functions denoting the ordering and, without loss of
generality, let suc$(x_{i}(t))=x_{i+1\bmod m}(t)$ and
pred$(x_{i})(t)=x_{i-1\bmod m}(t)$ for $i\in\\{0,1,\ldots,m-1\\}$.

###  2.2 The Computational Models

In the most common model, $\mathcal{OBLOT}$, the robots are silent: they have
no explicit means of communication; furthermore they are oblivious: at the
start of a cycle, a robot has no memory of observations and computations
performed in previous cycles.

In the other common model, $\mathcal{LUMI}$, each robot $r$ is equipped with a
persistent visible state variable $\mathit{Light}[r]$, called light, whose
values are taken from a finite set $C$ of states called colors (including the
color that represents the initial state when the light is off). The colors of
the lights can be set in each cycle by $r$ at the end of its
$\mathit{Compute}$ operation. A light is persistent from one computational
cycle to the next: the color is not automatically reset at the end of a cycle;
the robot is otherwise oblivious, forgetting all other information from
previous cycles. In $\mathcal{LUMI}$, the $\mathit{Look}$ operation produces a
colored snapshot; i.e., it returns the set of pairs
$(\mathit{position},\mathit{color})$ of the other robots111If (strong)
multiplicity detection is assumed, the snapshot is a multi-set.. Note that if
$|C|=1$, then the light is not used; thus, this case corresponds to the
$\mathcal{OBLOT}$ model.

It is sometimes convenient to describe a robot $r$ as having $k\geq 1$ lights,
denoted $r.\mathit{light}_{1},\ldots,\\\ r.\mathit{light}_{k}$, where the
values of $r.\mathit{light}_{i}$ are from a finite set of colors $C_{i}$, and
to consider $\mathit{Light}[r]$ as a $k$-tuple of variables; clearly, this
corresponds to $r$ having a single light that uses $\Pi^{k}_{i=1}|C_{i}|$
colors.

The lights provide simultaneously persistent memory and direct means of
communication, although both limited to a constant number of bits per cycle.
Two sub-models of $\mathcal{LUMI}$ have been defined and investigated, each
offering only one of these two capabilities.

In the first model, $\mathcal{FST\\!A}$, a robot can only see the color of its
own light; that is, the light is an internal one and its color merely encodes
an internal state. Hence the robots are silent, as in $\mathcal{OBLOT}$; but
are finite-state. Observe that a snapshot in $\mathcal{FST\\!A}$ is the same
as in $\mathcal{OBLOT}$.

In the second model, $\mathcal{FCOM}$, the lights are external: a robot can
communicate to the other robots through its colored light but forgets the
color of its own light by the next cycle; that is, robots are finite-
communication but oblivious. A snapshot in $\mathcal{FCOM}$ is like in
$\mathcal{LUMI}$ except that, for the position $x$ where the robot $r$
performing the $Look$ is located, $Light[r]$ is omitted from the set of colors
present at $x$.

In all the above models, a configuration $\textit{C}(t)$ at time $t$ is the
multi-set of the $n$ pairs of the $(x_{i}(t),c_{i}(t))$, where $c_{i}(t)$ is
the color of robot $r_{i}$ at time $t$.

###  2.3 Activation Schedulers and Energy Restriction

In all computational models just described, in each synchronous round, some
robots become active and they execute their $\mathit{LCM}$ cycle in complete
synchrony. The choice of which non-empty subset of the robots is activated in
a specific round is considered to be under the control of an adversarial
activation scheduler constrained to be fair; that is, every robot will become
active infinitely often.

Given a synchronous scheduler $\mathcal{}S$ and a set of robots $R$, an
activation sequence of $R$ by (or, under) $\mathcal{}S$ is an infinite
sequence $E=\langle e_{1},e_{2},\ldots,e_{i},\ldots\rangle$, where
$e_{i}\subseteq R$ denotes the set of robots activated in round $i$,
satisfying the fairness constraint:

$[(\forall r\in R\;\exists e_{i}:r\in e_{i})\textbf{ and}\ (\forall i\geq
1,r\in e_{i}\Rightarrow\exists j>i:r\in e_{j})].$

Let ${\mathcal{}E}({\mathcal{}S},R)$ denote the set of all activation
sequences of $R$ by $\mathcal{}S$.

In the standard synchronous scheduler (Ssynch), first studied in [30] and
often called semi-synchronous, each sequence $E=\langle
e_{1},e_{2},\ldots,e_{i},\ldots\rangle\in{\mathcal{}E}(\textsc{Ssynch},R)$
satisfies the basic condition

$\forall i\geq 1,\varnothing\neq e_{i}\subseteq R.$ (1)

The special fully-synchronous (Fsynch) setting, where every robot is activated
in every round, corresponds to further restricting the activation sequences by
imposing $\forall i\geq 1,e_{i}=R$. Notice that, in this setting, the
activation scheduler has no adversarial power. Another special setting is
defined by the well-known round-robin (RR) scheduler (see, e.g., [11, 31]),
whose generalized definition corresponds to adding the restriction: $[\exists
p>1:(\cup_{1\leq i\leq p}e_{i}=R)\ \textbf{ and}\ (\forall 1\leq i\neq j\leq
p,[e_{i}\cap e_{j}=\varnothing])\ \textbf{ and}\ (\forall i\geq
1,[e_{i}=e_{i+p}])]$.

We study systems of energy-constrained robots under the standard synchronous
activation scheduler. More precisely, we study systems where a robot (i) has
just enough energy to execute a cycle, (ii) it cannot be activated in a round
unless it has full energy, and (iii) its depleted energy is regenerated after
one round.

These three conditions clearly have an impact on the possible activation
sequences of the robots. In particular, since a robot with depleted energy
cannot be activated, the basic condition on $e_{i}$ becomes

$\forall i\geq 1,e_{i}\subseteq R^{*}[i]\textbf{ and
}R^{*}[i]\not=\varnothing\Rightarrow e_{i}\not=\varnothing$ (2)

where $R^{*}[i]\subseteq R$ denotes the set of robots with full energy in
round $i$. Furthermore, since it takes a round to regenerate depleted energy,
$e_{i}$ must also satisfy

$\forall i\geq 1,(e_{i}\cap e_{i+1}=\varnothing)$ (3)

Notice that, since $e_{i}\subseteq R^{*}[i]$, it is possible that ${e}_{i}=R$
when $R^{*}[i]=R$. Should this be the case, since a robot has just enough
energy to execute a cycle, then $R^{*}[i+1]=\varnothing$ and, since a robot
with depleted energy cannot be activated, ${e}_{i+1}=\varnothing$. Further
observe that, due to the conditions imposed by the energy limitations, if
$\varnothing\neq e_{i}\neq R$ then

$\forall j\geq i,[\varnothing\neq e_{j}\neq R\;\textbf{ and}\ (e_{j}\cap
e_{j+1}=\varnothing)]\,.$

that is, if fewer than $|R|$ full energy robots are activated in any round
$i$, then $R^{*}[j]\neq R$ for all $j\geq i$.

In other words, the activation sequences of the energy-constrained robots are
infinite sequences where the prefix is a (possibly empty) alternating sequence
of $R$ and $\varnothing$, and, if the prefix is finite, the rest are non-empty
sets satisfying the constraint $(e_{i}\cap e_{i+1}=\varnothing)$.

Notice that this set of sequences, denoted by
${\mathcal{}E}(\textsc{Ssynch}_{\mathit{res}},R)$, is not a proper subset of
${\mathcal{}E}(\textsc{Ssynch},R)$ since some sequences might have empty sets
in their prefix.

Consider now the synchronous scheduler, we shall call Rsynch, obtained from
Ssynch by adding the following restricted-repetition condition to its
activation sequences:

$\displaystyle[\forall i\geq 1,e_{i}=R]\ \textbf{ or }$ $\displaystyle[\exists
p\geq 0:([\forall i\leq p,(e_{i}=R)]\ \textbf{ and }$
$\displaystyle\phantom{[\exists p\geq 0:(}[\forall i>p,(\varnothing\neq
e_{i}\neq R\ \textbf{ and }\ e_{i}\cap e_{i+1}=\varnothing)])]\,,$

that is, ${\mathcal{}E}(\textsc{Rsynch},R)$ is composed of sequences where the
prefix is a (possibly empty) sequence of $R$ and, if the prefix is finite, the
rest are non-empty sets satisfying the constraint $(e_{i}\cap
e_{i+1}=\varnothing)$.

There is an obvious bijection $\phi$ between
${\mathcal{}E}(\textsc{Ssynch}_{res},R)$ and
${\mathcal{}E}(\textsc{Rsynch},R)$, where $\phi(E)$ corresponds to removing
all empty sets from $E\in{\mathcal{}E}(\textsc{Ssynch}_{res},R)$; to this
corresponds the obvious identity between the computation performed by $R$
under $E$ and that performed under $\phi(E)$. Informally, under
$\textsc{Ssynch}_{res}$, if all robots are activated in the same round $i$,
they will be all idle in round $i+1$, and they will all be with full energy in
round $i+2$. Since no activity takes place in round $i+1$, the selected set
$e_{i+2}$ will perform exactly the same computation as if they had been
activated in round $i+1$.

In other words, the computation by energy-constrained $R$ under the standard
synchronous scheduler Ssynch. is the same as it would be if the robots in $R$
were energy-unbounded but the activation was controlled by scheduler Rsynch.

This restricted-repetition setting has never been studied before; observe that
it includes both fully synchronous Fsynch and round robin RR as special cases.

###  2.4 Computational Relationships

Let
${\mathcal{}M}=\\{\mathcal{LUMI},\mathcal{FCOM},\mathcal{FST\\!A},\mathcal{OBLOT}\\}$
be the set of models under investigation, and
${\mathcal{}S}=\\{\textsc{Fsynch},\textsc{Rsynch},\textsc{Ssynch}\\}$ be the
set of activation schedulers under consideration.

We denote by $\mathcal{R}$ the set of all teams of robots satisfying the core
assumptions (i.e., they are identical, autonomous, and operate in
$\mathit{LCM}$ cycles), and $R\in\mathcal{R}$ a team of robots having
identical capabilities (e.g., common coordinate system, persistent storage,
internal identity, rigid movements etc.). By
$\mathcal{R}_{n}\subset\mathcal{R}$ we denote the set of all teams of size
$n$.

Given a model $M\in{\mathcal{}M}$, a scheduler $S\in{\mathcal{}S}$, and a team
of robots $R\in\mathcal{R}$, let $Task(M,S;R)$ denote the set of problems
solvable by $R$ in $M$ under adversarial scheduler $S$.

Let $M_{1},M_{2}\in{\mathcal{}M}$ and $S_{1},S_{2}\in{\mathcal{}S}$.

  * •

We say that model $M_{1}$ under scheduler $S_{1}$ is computationally not less
powerful than model $M_{2}$ under $S_{2}$, denoted by $M_{1}^{S_{1}}\geq
M_{2}^{S_{2}}$ if $\forall R\in\mathcal{R}$ we have
$Task(M_{1},S_{1};R)\supseteq Task(M_{2},S_{2};R)$.

  * •

We say that $M_{1}$ under $S_{1}$ is computationally more powerful than
$M_{2}$ under $S_{2}$, denoted by $M_{1}^{S_{1}}>M_{2}^{S_{2}}$, if
$M_{1}^{S_{1}}\geq M_{2}^{S_{2}}$ and $\exists R\in\mathcal{R}$ such that
$Task(M_{1},S_{1};R)\setminus Task(M_{2},S_{2};R)\neq\varnothing$.

  * •

We say that $M_{1}$ under $S_{1}$ and $M_{2}$ under $S_{2}$ are
computationally equivalent, denoted by $M_{1}^{S_{1}}\equiv M_{2}^{S_{2}}$, if
$M_{1}^{S_{1}}\geq M_{2}^{S_{2}}$ and $M_{2}^{S_{2}}\geq M_{1}^{S_{1}}$.

  * •

Finally, we say that $M_{1}$ under $S_{1}$ and $M_{2}$ under $S_{2}$ are
computationally orthogonal (or incomparable), denoted by $M_{1}^{S_{1}}\bot
M_{2}^{S_{2}}$, if $\exists R_{1},R_{2}\in\mathcal{R}$ such that
$Task(M_{1},S_{1};R_{1})\setminus Task(M_{2},S_{2};R_{1})\neq\varnothing$ and
$Task(M_{2},S_{2};R_{2})\setminus Task(M_{1},S_{1};R_{2})\neq\varnothing$.

For simplicity of notation, for a model $M\in{\mathcal{}M}$, let $M^{F}$,
$M^{RS}$, and $M^{S}$ denote $M^{\textsc{Fsynch}}$, $M^{\textsc{Rsynch}}$, and
$M^{\textsc{Ssynch}}$, respectively; and let $Task(M,\textsc{Fsynch};R)$,
$Task(M,\textsc{Rsynch};R)$, and $Task(M,\textsc{Ssynch};R)$ be denoted by let
$M^{F}(R),M^{RS}(R),$ and $M^{S}(R)$, respectively.

Trivially, for all $M\in{\mathcal{}M}$,

$M^{F}\geq M^{RS}\geq M^{S}\,,$

also, for all $P\in{\mathcal{}S}$,

$\displaystyle\mathcal{LUMI}^{P}$
$\displaystyle\geq\mathcal{FST\\!A}^{P}\geq\mathcal{OBLOT}^{P}\,,\text{ and }$
$\displaystyle\mathcal{LUMI}^{P}$
$\displaystyle\geq\mathcal{FCOM}^{P}\geq\mathcal{OBLOT}^{P}\,.$

The following theorems, established in [19], summarize the computational
relationship between Ssynch and Fsynch.

######  Theorem 1 ([19]).

  1. 1.

$\mathcal{LUMI}^{F}\equiv\mathcal{FCOM}^{F}>\mathcal{FST\\!A}^{F}>\mathcal{OBLOT}^{F}$,

  2. 2.

$\mathcal{FCOM}^{S}\bot$ $\mathcal{FST\\!A}^{S}$,

  3. 3.

$\mathcal{LUMI}^{S}>\mathcal{FST\\!A}^{S}>\mathcal{OBLOT}^{S}$ and
$\mathcal{LUMI}^{S}>\mathcal{FCOM}^{S}>\mathcal{OBLOT}^{S}$.

######  Theorem 2 ([19]).

  1. 1.

$\mathcal{LUMI}^{F}\equiv$
$\mathcal{FCOM}^{F}>\mathcal{LUMI}^{S}>\mathcal{FCOM}^{S}$,

  2. 2.

$\mathcal{FST\\!A}^{F}\bot$ $\mathcal{LUMI}^{S}$,

  3. 3.

$\mathcal{FST\\!A}^{F}>\mathcal{FST\\!A}^{S}$,

  4. 4.

$\mathcal{OBLOT}^{F}>\mathcal{OBLOT}^{S}$,

  5. 5.

$\mathcal{OBLOT}^{F}\bot$ $\mathcal{LUMI}^{S}$, $\mathcal{OBLOT}^{F}\bot$
$\mathcal{FCOM}^{S}$, and
$\mathcal{OBLOT}^{F}\bot$ $\mathcal{FST\\!A}^{S}$.

These theorems hold assuming rigidity and chirality and these results are
extended and they hold without rigidity and chirality [5].

##  3 Computational Relationship between Rsynch and Ssynch

In this section we analyze the impact that the presence of the energy
constraints has on the computational capability of the robots. We do so by
studying the computational relationship between Rsynch and Ssynch in each of
the four models.

We show that,

$\mathcal{X}^{RS}>\mathcal{X}^{S}(\forall\mathcal{X}\in\\{\mathcal{FCOM},\mathcal{FST\\!A},\mathcal{OBLOT}\\}),$

and $\mathcal{LUMI}^{RS}\equiv\mathcal{LUMI}^{S}$. We also show that the power
of Rsynch makes $\mathcal{FCOM}^{RS}$ as powerful as $\mathcal{LUMI}^{S}$, and
even as $\mathcal{LUMI}^{RS}$ in Section 5.

###  3.1 Power of Rsynch in $\mathcal{FCOM},\mathcal{FST\\!A}$ and
$\mathcal{OBLOT}$

In this section, we study the relationships among the various models in Rsynch
and we show that for
${\mathcal{}X}\in\\{\mathcal{FCOM},\mathcal{FST\\!A},\mathcal{OBLOT}\\}$ we
have ${\mathcal{}X}^{RS}>{\mathcal{}X}^{S}$.

We start by showing that Rendezvous problem (RDV) [15], where two robots $a$
and $b$ must gather in the same location not known in advance, cannot be
solved in Rsynch.

######  Lemma 1.

$\exists R\in\mathcal{R}_{2}$, $\text{RDV}\not\in\mathcal{OBLOT}^{RS}(R)$.
This result holds even in presence of chirality and rigidity of movement.

###### Proof.

Consider two robots $a$ and $b$ with the same chirality. The two robots have
exactly the same view of the universe. Assume by contradiction that $A$ is a
solution protocol. Consider an execution E of $A$ where, in the last round,
only one robot, say $a$, is activated and moves (achieving rendezvous for the
first time) while the other robot does not move in that round (such an
execution can be shown to exist). Consider now the execution up to (and
excluding) the last round; at this point, proceed by activating not just one
(as in E), but both robots. When this happens, $a$ will perform the same move
as in E, whose destination is the observed position of $b$. Since the view of
$b$ is specular, once activated, $a$ will choose the observed position of $b$
as its destination. The result will be just a switch of positions of the
robots. Since the robots are oblivious, in the same conditions they will
repeat the same actions; this means that, if they are both activated in every
turn from now on, they will continue to switch without ever gathering. ∎

The following problem was introduced to show that $\mathcal{OBLOT}^{F}$ is
computationally more powerful than $\mathcal{OBLOT}^{S}$, and that models
$\mathcal{OBLOT}^{F}$ and $\mathcal{FCOM}^{S}$ (or $\mathcal{FST\\!A}^{S}$)
are incomparable [19]. The problem can also take a role to show
$\mathcal{OBLOT}^{RS}>\mathcal{OBLOT}^{S}$ and orthogonality of
$\mathcal{OBLOT}^{RS}$ and $\mathcal{FCOM}^{S}$ (or $\mathcal{FST\\!A}^{S}$).

Figure 2: Shrinking Rotation (SRO). Configurations
$C_{0},C_{1},C_{2},C_{3},\dots$ where $C_{i}=(a_{i},b_{i})$.

######  Definition 1.

SHRINKING ROTATION (SRO) [19]: Two robots $a$ and $b$ are initially placed in
arbitrary distinct points (forming the initial configuration $C_{0}$). The two
robots uniquely identify a square (initially $Q_{0}$) whose diagonal is given
by the segment between them222By square, we means the entire space delimited
by the four sides.. Let $a_{0}$ and $b_{0}$ indicate the initial positions of
the robots, $d_{0}$ the segment between them, and $\mathit{length}(d_{0})$ its
length. Let $a_{i}$ and $b_{i}$ be the positions of $a$ and $b$ in
configuration $C_{i}$ ($i\geq 0$). The problem consists of moving from
configuration $C_{i}$ to $C_{i+1}$ in such a way that either Condition 1 or
Condition 2 is satisfied, and Condition 3 is satisfied in either case:

  * •

Condition 1: $d_{i+1}$ is a $90^{\circ}$ clockwise rotation of $d_{i}$ and
thus $\mathit{length}(d_{i+1})=\mathit{length}(d_{i})$,

  * •

Condition 2: $d_{i+1}$ is a “shrunk” $45^{\circ}$ clockwise rotation of
$d_{i}$ such that
$\mathit{length}(d_{i+1})=\frac{\mathit{length}(d_{i})}{\sqrt{2}}$,

  * •

Condition 3: $a_{i+1}$ and $b_{i+1}$ must be contained in the square
$Q_{i-1}$333We define $Q_{-1}$ to be the whole plane..

Algorithm 1 Alg-SRO for robot $r$. Assumptions: $\mathcal{OBLOT}$, Rsynch
---
State Look
|  $r.\mathit{pos}$, $\mathit{other}.\mathit{pos}$: positions of robot $r$ and
the other robot;
State Compute
|  1:  $r.\mathit{des}\leftarrow$ the point of clockwise rotating by
$90^{\circ}$ around the midpoint of $r.\mathit{pos}$ and
$\mathit{other}.\mathit{pos}$
State Move
|  Move to $r.\mathit{des}$

######  Lemma 2.

$\forall\mathit{R}\in\mathcal{R}_{2},\text{SRO}\in\mathcal{OBLOT}^{RS}(R)$,
assuming common chirality and rigid movement.

###### Proof.

The proof is by construction: Algorithm 1 prescribes a robot to rotate
clockwise by $90^{\circ}$ with respect to the midpoint between the two robots.
Note that any schedule in Rsynch allows consecutive simultaneous activation of
the two robots, but as soon as one of them is activated alone during a round,
the subsequent rounds necessarily consist of an alternation of activations of
each. So, there are only two possible types of executions under Rsynch with
two robots: $(1)$ a perpetual activation of both robots in each round, or
$(2)$ the activation of both for a finite number of rounds, followed by a
perpetual alternation of activations of each. In Case (1), the problem is
clearly solved by Algorithm 1 because the robots keep rotating of $90^{\circ}$
clockwise around their mid-point, fulfilling Conditions 1 and 3. In Case (2),
once the execution becomes an alternation of activations, the robots move
alternately, achieving, at each movement, a $45^{\circ}$ rotation of the
segment between them decreasing its size precisely as required to fulfill
Condition 2 and 3. In fact, in doing so, they move within a shrinking area
where each new square is included in the previous (in a kind of fractal way,
see Figure 2). Then SRO can be solved with $\mathcal{OBLOT}$ in Rsynch. ∎

######  Lemma 3 ([19]).

$\exists\mathit{R}\in\mathcal{R}_{2},\text{SRO}\not\in\mathcal{FCOM}^{S}(R)\cup\mathcal{FST\\!A}^{S}(R)$.
This result holds even in presence of chirality and rigidity of movement.

We have seen that SRO can be solved in $\mathcal{OBLOT}^{RS}$ but cannot be
solved in $\mathcal{FCOM}^{S}$ and $\mathcal{FST\\!A}^{S}$. On the other hand,
RDV can be solved in $\mathcal{FCOM}^{S}$ and $\mathcal{FST\\!A}^{S}$ [18] but
cannot be solved in $\mathcal{OBLOT}^{RS}$ by Lemma 1. Thus
$\mathcal{OBLOT}^{RS}$ and $\mathcal{FCOM}^{S}$ ($\mathcal{FST\\!A}^{S}$) are
orthogonal. Since $\mathcal{FCOM}^{RS}$ and $\mathcal{FST\\!A}^{RS}$ includes
$\mathcal{OBLOT}^{RS}$, we can show that
${\mathcal{}X}^{RS}>{\mathcal{}X}^{S}$ for
${\mathcal{}X}\in\\{\mathcal{FCOM},\allowbreak\mathcal{FST\\!A},\mathcal{OBLOT}\\}$
by Lemmas 2 and 3.

######  Theorem 3.

  1. 1.

$\mathcal{OBLOT}^{RS}\bot$ $\mathcal{FCOM}^{S}$,

  2. 2.

$\mathcal{OBLOT}^{RS}\bot$ $\mathcal{FST\\!A}^{S}$,

  3. 3.

$\mathcal{FCOM}^{RS}>\mathcal{FCOM}^{S}$,

  4. 4.

$\mathcal{FST\\!A}^{RS}>\mathcal{FST\\!A}^{S}$,

  5. 5.

$\mathcal{OBLOT}^{RS}>\mathcal{OBLOT}^{S}$.

It remains to determine the relationship between $\mathcal{FCOM}^{RS}$ and
$\mathcal{LUMI}^{S}$, and between $\mathcal{FST\\!A}^{RS}$ and
$\mathcal{LUMI}^{S}$ or $\mathcal{FCOM}^{S}$. The equality
$\mathcal{FCOM}^{RS}\equiv$ $\mathcal{LUMI}^{S}$ follows from the equalities
$\mathcal{LUMI}^{S}\equiv$ $\mathcal{LUMI}^{RS}$ and
$\mathcal{LUMI}^{S}\equiv$ $\mathcal{FCOM}^{S}$, which we show constructively
in Sections 3.2 and 5. We also show the dominance of $\mathcal{LUMI}^{S}$ over
$\mathcal{FST\\!A}^{RS}$ and the orthogonality of $\mathcal{FST\\!A}^{RS}$
with $\mathcal{FCOM}^{S}$ in the following.

In order to show these results, we use the following problem called Cyclic
circles (CYC).

Figure 3: The configurations of problem CYC.

######  Definition 2.

CYCLIC CIRCLES (CYC): Let $n\geq 3$, $k=2^{n-1}$, and
$d:\mathbb{N}\rightarrow\mathbb{R}$ is a non-invertible function. The problem
is to form a cyclic sequence of patterns
$C,C_{0},C,C_{1},C,C_{2},\ldots,\allowbreak C,C_{k-1}$ where $C$ is a pattern
of $n$ robots forming a “circle” occupied by $n-1$ robots with one in the
center (see Figure 3 (a)), and $C_{i}$ (for $0\leq i\leq k-1$) is a
configuration where the $n-1$ circle robots are in the exact same position,
but the center robot occupies a point at distance $d(i)$ from the center on
the radius connecting the center to the missing robot position on the circle
(see Figure 3 (b)). In other words, the central robot moves to the designed
position at distance $d(i)$ and comes back to the center, and the process
repeats after the $2^{n-1}$ configurations $C_{i}$ have been formed.

######  Lemma 4.

Let $n\geq 3$.
$\exists\mathit{R}\in\mathcal{R}_{n},\text{CYC}\not\in\mathcal{FST\\!A}^{F}(R)$.
This result holds even in presence of chirality and rigid movements.

###### Proof.

Since the locations of the robots $r_{1},\ldots,r_{n-1}$ are the same in the
$2^{n-1}$ configurations $C_{i}$ and $C$, $\mathcal{FST\\!A}$ robot $r_{0}$ in
configuration $C$ must determine which $C_{i}$ must be formed only on the
basis of its own color. Since the number of available colors is constant with
respect to the number of robots $n$, $r_{0}$ cannot recognize, using its
light, the correct distance $d(i)$ from the center of the circle. ∎

We now show that $\mathcal{FCOM}$ robots can solve CYC under Ssynch. The proof
is by construction and the problem is solved by Algorithm 2. Intuitively, the
$n-1$ robots on the circle act as a distributed counter using their lights to
display the binary representation of the index $i$ of the next configuration
to be formed. The increment of the counter is done appropriately changing the
bits and maintaining the carry like in a full-adder addition. Whenever
activated, robot $r_{0}$ “reads” the information and understands when it is
its time to move and what is its destination.

Algorithm 2 Cyclic-Cycles for robot $r_{i}$. Assumptions
---
|  $\mathcal{FCOM}$, Ssynch
|  Let $r_{0}$ be located at the center of the circle and
$r_{1},\ldots,r_{n-1}$ be located on the circle in clockwise, and let ${\tt
suc}(r_{i})=r_{i+1\bmod n}$ and ${\tt pred}(r_{i})=r_{i-1\bmod n}$. Robot
$r_{i}$ has the following lights:
|  |  $\mathit{status}\in\\{\mathit{center},\mathit{final}\\}$, initially set to $\mathit{center}$;
|  |  $b,c,\mathit{suc}_{b}$ $\in\\{0,1\\}$, initially set to $0,0,0$, respectively.
Phase Look
|  Robot $r_{i}$ observes the positions of the other robots and their lights.
|  Note that $r_{i}$ cannot see its own lights due to $\mathcal{FCOM}$.
Phase Compute
|  1: if $i=0$ then // case for robot $r_{0}$
| 2: |  if $\forall(1\leq j\leq n-1):(r_{j}.\mathit{status}=\mathit{center})$
|  |  |  |  and not ($r_{0}$ is at the final position) then
| 3: |  | $r_{0}.\mathit{status}\leftarrow\mathit{final}$
| 4: |  |  $r_{0}.\mathit{des}\leftarrow$ the position at distance $d((r_{n-1}.b)(r_{n-2}.b)\ldots(r_{1}.b))$ from the center of the circle
| 5: |  else if $\forall(1\leq j\leq n-1):(r_{j}.\mathit{status}=\mathit{final})$
|  |  |  |  and not ($r_{0}$ is at the center of the circle) then
| 6: |  |  $r_{0}.\mathit{status}$ $\leftarrow\mathit{center}$
| 7: |  | $r_{0}.b\leftarrow 0$
| 8: |  |  $r_{0}.c\leftarrow 1$ // increment by one
| 9: |  |  $r_{0}.\mathit{suc}_{b}$ $\leftarrow r_{1}.b$ // copy of $r_{1}.b$
| 10: |  |  $r_{0}.\mathit{des}\leftarrow$ the center of the circle
|  11: else // case for robot $r_{i}$ where $i\not=0$
| 12: |  if $r_{0}$ is located at the final position
|  |  |  |  and $r_{0}.\mathit{status}=\mathit{final}$ then
| 13: |  |  $r_{i}.\mathit{status}\leftarrow\mathit{final}$
| 14: |  else if $r_{0}$ is located at the center of the circle
|  |  |  |  and $\forall(0\leq j\leq i-1):(r_{j}.\mathit{status}=\mathit{center})$
|  |  |  |  and $\forall(i+1\leq j\leq n-1):(r_{j}.\mathit{status}=\mathit{final})$ then
| 15: |  |  $r_{i}$.b $\leftarrow{\tt pred}(r_{i}).c\oplus{\tt pred}(r_{i}).\mathit{suc}_{b}$
| 16: |  |  $r_{i}$.c $\leftarrow{\tt pred}(r_{i}).c\cdot{\tt pred}(r_{i}).\mathit{suc}_{b}$
| 17: |  |  $r_{i}.\mathit{suc}_{b}\leftarrow{\tt suc}(r_{i}).b$
| 18: |  |  $r_{i}.\mathit{status}\leftarrow\mathit{center}$
Phase Move
|  Move to $r_{i}.\mathit{des}$

######  Lemma 5.

Let $n\geq 3$. $\forall\mathit{R}\in\mathcal{R}_{n}$,
$\text{CYC}\in\mathcal{FCOM}^{S}(R)$, assuming chirality.

###### Proof.

Each robot $r_{i}$ has 4 lights, $r_{i}.\mathit{status}$, $r_{i}.b$,
$r_{i}.c$, and $r_{i}.\mathit{suc}_{b}$. Let

$\displaystyle\mathit{Status}(t)$
$\displaystyle=(r_{0}.\mathit{status}(t),\ldots,r_{n-1}.\mathit{status}(t))\,,$
$\displaystyle B_{\mathit{value}}(t)$
$\displaystyle=(r_{0}.b(t),r_{1}.b(t),\ldots,r_{n-1}.b(t))\,,$ $\displaystyle
B_{\mathit{carry}}(t)$
$\displaystyle=(r_{0}.c(t),r_{1}.c(t),\ldots,r_{n-1}.c(t))\,,\text{ and }$
$\displaystyle B_{\mathit{suc}}(t)$
$\displaystyle=(r_{0}.\mathit{suc}_{b}(t),r_{1}.\mathit{suc}_{b}(t),\ldots,r_{n-1}.\mathit{suc}_{b}(t))\,.$

The configuration $K(t)$ at time $t$ is defined by $(X(t),\mathit{Status}(t),$
$B_{\mathit{value}}(t),$ $B_{\mathit{carry}}(t),B_{\mathit{suc}})$, where
$X(t)$ is the set of locations of $n$ robots at time $t$. $\mathit{Status}(t)$
differentiates among $C$, $C_{i}$ or intermediate states between $C$ and
$C_{i}$. $B_{\mathit{value}}(t)$ and $B_{\mathit{carry}}(t)$ encode the binary
representation of $i$. Finally, values in $B_{\mathit{suc}}(t)$ are copied
from the lights $b$ of the successor robots along the circle, thus they can be
used by the robots to derive the value of their light $b$ by observing the
color of the predecessor’s light $\mathit{suc}_{b}$.

The initial colors of $\mathit{Status}(0)$, $B_{\mathit{value}}(0)$,
$B_{\mathit{carry}}(0)$, $B_{\mathit{suc}}(0)$ are
$(\mathit{center},\ldots,\mathit{center})$,
$(0,0,\ldots,0)$, $(0,0,\ldots,0)$, $(0,0,\ldots,0)$, and $(0,\allowbreak
0,\ldots,0)$, respectively. The initial locations of robots is shown in Figure
3 (a). Algorithm 2 works as follows:

  * •

When robot $r_{0}$ is activated at $t$, if $r_{0}$ observes

$\mathit{Status}(t)[1..n-1]=(\mathit{center},\ldots,\mathit{center})\,,$

and $r_{0}$ is located at the center of the circle (the pattern $C$ is
formed), $r_{0}$ changes $r_{0}.\mathit{status}$ to $\mathit{final}$ and moves
to the “final” position computed by $d(B_{value}(t)[1..n-1])$. Note that since
rigidity is not assumed, as long as $r_{0}$ does not reach the final position
$r_{0}$ keeps moving towards the final position. When $r_{0}$ reaches the
final position, pattern $C_{p}$ is formed, where $p$ is the integer
represented in binary by $B_{value}(t)[1..n-1]$.

  * •

When a robot $r_{i}$ (for $i\neq 0$) is activated at $t$, if $r_{0}$ is
located at the final position determined by $d(B_{value}(t)[1..n-1])$, $r_{i}$
changes $r_{i}.\mathit{status}$ to $\mathit{final}$. Note that although an
$\mathcal{FCOM}$ robot $r_{i}$ cannot observe its own $r_{i}.b$, since
$r_{i-1}.\mathit{suc}_{b}$ holds $r_{i}.b$, $r_{i}$ can compute
$d(B_{value}(t)[1..n-1])$. Then there is a time $t^{\prime}>t$ such that
$\mathit{Status}(t^{\prime})=(\mathit{final},\ldots,\mathit{final})$ while
$C_{p}$ is not changed.

  * •

When robot $r_{0}$ is activated at $t$, if $r_{0}$ observes

$\mathit{Status}(t)[1..n-1]=(\mathit{final},\ldots,\mathit{final})\,,$

and the current pattern $C_{p}$ corresponds to $B_{value}(t)[1..n-1]$, $r_{0}$
prepares the formation of $C$. That is, it changes $r_{0}.\mathit{status}$ to
$\mathit{center}$ and it sets $(r_{0}.b,r_{0}.c,r_{0}.\mathit{suc}_{b})$ to
$(0,1,r_{1}.b)$, where $r_{0}.c$ means “carry” to the least significant bit,
and setting $r_{0}.c=1$ is a preparation for the increment of the binary value
$B_{value}(t)[1..n-1]$. Then $r_{0}$ moves to the center of the circle.

  * •

When robot $r_{0}$ reaches the center of the circle and

$\mathit{Status}(t)=(\mathit{center},\mathit{final},\ldots,\mathit{final})\,,$

the increment of the binary value $B_{value}(t)[1..n-1]$ is performed
sequentially, like in a full-adder addition. Firstly, $r_{1}$ (when activated)
changes $r_{1}.\mathit{status}$ to $\mathit{center}$ and it computes the least
significant bit ($r_{1}.b$) and the carry to the next bit ($r_{1}.c$) by using
$r_{0}.c$ and $r_{0}.\mathit{suc}_{b}(=r_{1}.b)$. Robot $r_{1}$ also copies
$r_{2}.b$ into $r_{1}.\mathit{suc}_{b}$, which will be used so that $r_{2}$
recognizes its own $b$. In general, when $r_{0}$ is located at the center of
the circle and

$\begin{split}\qquad\mathit{Status}(t)=(r_{0}.\mathit{status}=\mathit{center},\ldots,r_{i-1}.\mathit{status}=\mathit{center},\\\
r_{i}.\mathit{status}=\mathit{final},\ldots,r_{n-1}.\mathit{status}=\mathit{final}),\end{split}$

robot $r_{i}$, upon activation, changes $r_{i}.\mathit{status}$ to
$\mathit{center}$ and the computation of the increment ($r_{i}.b$ and
$r_{i}.c$) by using $r_{i-1}.c$ and $r_{i-1}.\mathit{suc}_{b}(=r_{i}.b)$ and
copy of the next bit ($r_{i}.\mathit{suc}_{b}$). Lastly, $r_{n-1}$ changes
$r_{n-1}.\mathit{status}$ to $\mathit{center}$ and computes the most
significant bit. Then the increment is completed.

Note that when this configuration occurs and $r_{i}$ executes the algorithm,
also $r_{i-1}$ may execute the algorithm, if activated (because it is a
$\mathcal{FCOM}$ robot). However, even if $r_{i-1}$ executes the algorithm in
the same round, the configuration stays unchanged and there is no effect on
the increment of $r_{i}$. Then, there is a time $t$ such that
$\mathit{Status}(t)=(\mathit{center},\ldots,\mathit{center})$ and
$B_{value}(t)[1..n-1]$ has been increment and this configuration forms $C$ and
the next movement of $r_{0}$ will be performed.

It can be easily verified that this algorithm works in Ssynch.

∎

The orthogonality of $\mathcal{FST\\!A}^{RS}$ and $\mathcal{FCOM}^{S}$ follows
from Lemmas 2, 3, 4, and 5, and the dominance of $\mathcal{LUMI}^{S}$ over
$\mathcal{FST\\!A}^{RS}$ follows from Lemmas 4 and 5.

######  Theorem 4.

  1. 1.

$\mathcal{FST\\!A}^{RS}<\mathcal{LUMI}^{S}$,

  2. 2.

$\mathcal{FST\\!A}^{RS}\bot$ $\mathcal{FCOM}^{S}$.

We show next the equivalence of $\mathcal{LUMI}^{S}$ and
$\mathcal{LUMI}^{RS}$.

###  3.2 Power of Rsynch in $\mathcal{LUMI}$

We now show that, in spite of their power for $\mathcal{FCOM}$ and
$\mathcal{FST\\!A}$, Rsynch robots with full lights ($\mathcal{LUMI}$) are not
more powerful than Ssynch robots with full lights. That is,
$\mathcal{LUMI}^{S}$ is computationally equivalent to $\mathcal{LUMI}^{RS}$.

######  Theorem 5.

$\forall R\in\mathcal{R},\mathcal{LUMI}^{RS}(R)\leq\mathcal{LUMI}^{S}(R)$.

We start by describing a simulation algorithm (sim-RS-by-S($A$)) that works in
Ssynch with full lights simulating an algorithm $A$ working in Rsynch with
full lights. Let algorithm $A$ use light with $\ell$ colors:
$C=\\{c_{0},c_{1},\ldots,c_{\ell-1}\\}$. A robot $r$ has available the
following sets of colors for its full lights in sim-RS-by-S($A$):

  1. 1.

$r.\mathit{light}\in C$ indicating its own light used in algorithm $A$,
initially set to $r.\mathit{light}=c_{0}$;

  2. 2.

$r.\mathit{step}\in\\{1,2,3,4,5,m\\}$ indicating the step currently under
execution. Step $i$ begins when $\forall\rho\in R\,(\rho.\mathit{step}=i)$ for
$i\in\\{1,2,3,4,5,m\\}$. Initially $r.\mathit{step}$ is set to $1$ for all
robots, and thus initially the simulation is in Step $1$;

  3. 3.

$r.\mathit{executed}\in\\{\mathit{True},\mathit{False}\\}$ indicating whether
$r$ has executed algorithm $A$ in the current mega-cycle (see below).
Initially $r.\mathit{executed}$ is set to $\mathit{False}$ for all robots; and

  4. 4.

$r.\mathit{charged}\in\\{C,E,M\\}$, where $C$, $E$, and $M$ stand for
“charged”, “empty”, and “just moved” respectively. The flag is used to ensure
the validity of the simulated Rsynch activation sequence, it indicates whether
$r$ is charged and can execute the algorithm $A$. Initially
$r.\mathit{charged}$ is set to $C$ for all robots.

Figure 4: Transition Diagram of sim-RS-by-S($A$). Step 1: first phase; Step 2:
second phase; Step 3: all robots moved in Step 1, reset $\mathit{charged}$ and
$\mathit{executed}$ flags; Step 4: empty robots are charged; Step 5: robots
moved are discharged; Step $\bm{m}$: reset executed flags. Algorithm 3 sim-RS-
by-S(A): predicates and subroutines for robot $r$. predicate all-robots-
executed
---
|  $\forall\rho\,(\rho.\mathit{executed}=True)$
predicate all-robots-reset
|  $\forall\rho\,(\rho.\mathit{executed}=\mathit{False})$
subroutine Reset-All-Flags // in Step $3$
|  if $\exists\rho\,(\rho.\mathit{executed}=\mathit{True}$ and
$\rho.\mathit{charged}=E$) then
|  |  if ($r.\mathit{executed}=\mathit{True}$ and $r.\mathit{charged}=E$) then
|  |  |  $r.\mathit{executed}\leftarrow\mathit{False}$
|  |  |  $r.\mathit{charged}\leftarrow C$
|  else $r.\mathit{step}\leftarrow 1$
subroutine Reset-Execution // in Step $m$
|  if not $\forall\rho\,(\rho.\mathit{executed}=\mathit{False})$ then
|  |  if $r.\mathit{executed}\neq\mathit{False}$ then $r.\mathit{executed}\leftarrow\mathit{False}$
|  else $r.\mathit{step}\leftarrow 2$
subroutine Charge-Empty-Flags // in Step $4$
|  if $\exists\rho\,(\rho.\mathit{charged}=E)$ then
|  |  if $r.\mathit{charged}=E$ then $r.\mathit{charged}\leftarrow C$
|  else $r.\mathit{step}\leftarrow 5$
subroutine Empty-Moved-Flags // in Step $5$
|  if $\exists\rho\,(\rho.\mathit{charged}=M)$ then
|  |  if $r.\mathit{charged}=M$ then $r.\mathit{charged}\leftarrow E$
|  else $r.\mathit{step}\leftarrow 2$
Algorithm 4 sim-RS-by-S(A): for robot $r$. Assumptions:
---
|  $\mathcal{LUMI}$, Ssynch
State Look
|  Robot $r$ takes the snapshot of the configuration, including the colors of
the lights of all the robots.
State Compute
|  1: $r.\mathit{des}\leftarrow(0,0)$ // $r$ does not move
|  2: if $\forall\rho\,(\rho.\mathit{step}=1)$ then // Step 1
| 3: |  Set $r.\mathit{color}$ and $r.\mathit{des}$ by the simulated algorithm A
| 4: | $r.\mathit{executed}\leftarrow\mathit{True}$
| 5: | $r.\mathit{charged}\leftarrow E$
| 6: |  $r.\mathit{step}\leftarrow 2$
|  7: else if $\forall\rho\,(\rho.\mathit{step}=2)$ then // Step 2
| 8: |  if $\forall\rho\,(\rho.\mathit{charged}=E)$ then $r.\mathit{step}\leftarrow 3$ // mega-cycle continues
| 9: |  else if all-robots-executed then $r.\mathit{step}\leftarrow m$ // mega-cycle ends
|  10: else if $(r.\mathit{executed}=\mathit{False})$ and
$(r.\mathit{charged}=C)$ then
| 11: |  |  Set $r.\mathit{color}$ and $r.\mathit{des}$ by the simulated algorithm A
| 12: |  | $r.\mathit{executed}\leftarrow\mathit{True}$
| 13: |  | $r.\mathit{charged}\leftarrow M$
| 14: |  |  $r.\mathit{step}\leftarrow 4$
|  15: else if $\forall\rho\,(\rho.\mathit{step}=3$) then call Reset-All-Flags
// to Step $1$
|  16: else if $\forall\rho\,(\rho.\mathit{step}=4)$ then call Charge-Empty-
Flags // to Step 5
|  17: else if $\forall\rho\,(\rho.\mathit{step}=5$) then call Empty-Moved-
Flags // to Step 2
|  18: else if $\forall\rho\,(\rho.\mathit{step}=m$) then call Reset-Execution
// to Step $2$
|  19: else if $\forall\rho\,(\rho.\mathit{step}=1$ or $\rho.\mathit{step}=2)$
then $r.\mathit{step}\leftarrow 2$
|  20: else if $\forall\rho\,(\rho.\mathit{step}=2$ or $\rho.\mathit{step}=3)$
then $r.\mathit{step}\leftarrow 3$
|  21: else if $\forall\rho\,(\rho.\mathit{step}=2$ or $\rho.\mathit{step}=4)$
then $r.\mathit{step}\leftarrow 4$
|  22: else if $\forall\rho\,(\rho.\mathit{step}=4$ or $\rho.\mathit{step}=5$)
then $r.\mathit{step}\leftarrow 5$
|  23: else if $\forall\rho\,(\rho.\mathit{step}=5$ or $\rho.\mathit{step}=2)$
then $r.\mathit{step}\leftarrow 2$
|  24: else if $\forall\rho\,(\rho.\mathit{step}=3$ or $\rho.\mathit{step}=1)$
then $r.\mathit{step}\leftarrow 1$
|  25: else if $\forall\rho\,(\rho.\mathit{step}=2$ or $\rho.\mathit{step}=m)$
and all-robots-executed then
| 26: |  $r.\mathit{step}\leftarrow m$
|  27: else if $\forall\rho\,(\rho.\mathit{step}=m$ or $\rho.\mathit{step}=2)$
and all-robots-reset then
| 28: | $r.\mathit{step}\leftarrow 2$
State Move
|  Move to $r.\mathit{des}$

The simulating algorithm is presented in Algorithm 3 (predicates and
subroutines used in the algorithm) and 4 (the main algorithm), and Figure 4
shows the transition diagram as the robots change step’s value. Since sim-RS-
by-S($A$) works in Ssynch, it must take care of excluding the prohibited
patterns of Rsynch, if they occur.

The simulation proceeds in two phases. The first phase corresponds to the
first $p\geq 0$ (where $p$ can be $\infty$) activations in a simulated Rsynch
activation schedule where all robots in $R$ are activated at each round. The
second phase corresponds to the remaining activation cycles where a strict
subset of $R$ is activated at each round. The robots execute $A$ in Step $1$
in the first phase, and in Step $2$ in the second phase. The remaining steps
serve for bookkeeping of flags $\mathit{executed}$ and $\mathit{charged}$.

The algorithm is a sequence of mega-cycles, each of which lasts the time it
takes for all robots to execute the simulated algorithm exactly once. The
cycle $\\{1\\}\rightarrow\\{2\\}\rightarrow\\{3\\}\rightarrow\\{1\\}$ of the
transition diagram of sim-RS-by-S($A$) corresponds to one mega-cycle in the
first phase. One mega-cycle in the second phase consists of several cycles
$\\{2\\}\rightarrow\\{4\\}\rightarrow\\{5\\}\rightarrow\\{2\\}$ (until all
robots have executed $A$) with one cycle
$\\{2\\}\rightarrow\\{m\\}\rightarrow\\{2\\}$ to reset the flags and start the
new mega-cycle. Specifically, the states of the simulation are (see Figure 4):

  * •

State $\\{i,j\\}$ (lines 19–28 of Algorithm 4) are the transition states
between Step $i$ and Step $j$. Activated robots do not execute $A$ nor change
the values of the $\mathit{charged}$ and $\mathit{executed}$ flags, but only
set their $r.\mathit{step}$ to either $i$ or to $j$ (depending on the specific
case).

  * •

Step $1$ (lines 2–6) executes one cycle of the simulated algorithm $A$. Note
that when Step $1$ begins execution, it holds that $\forall\rho\in
R\,(\rho.\mathit{executed}=\mathit{False}$ and $\rho.\mathit{charged}=C)$.

  * •

Step $2$ (lines 7–14) checks if all robots have their $\mathit{charged}$ flag
set to $E$, that is, if all robots were activated in Step $1$. If so, the
first condition of Rsynch is satisfied, and the simulation proceeds to Step
$3$ resetting all the $\mathit{charged}$ and $\mathit{executed}$ flags to
prepare for the next move in Step $1$. If there are robots with their
$\mathit{charged}$ flag set to $C$, there are two cases:

(1) If all robots have their $\mathit{executed}$ flag set to $\mathit{True}$,
the mega-cycle has finished. In this case, the simulation proceeds to Step $m$
resetting all the executed flags. When Step $m$ ends, it returns to Step $2$.

(2) If some robots have their $\mathit{executed}$ flag set to
$\mathit{False}$, the mega-cycle has not finished yet. In this case, the
simulation proceeds executing $A$. As soon as among the activated robots there
is a non-empty subset $R^{\prime}$ with $\mathit{charged}=C$ and
$\mathit{executed}=\mathit{False}$, they execute algorithm $A$, set
$\mathit{charged}$ to $M$ and $\mathit{executed}$ to $\mathit{True}$, and
proceed to Step $4$. Afterwards, the remaining robots proceed to Step $4$
without executing $A$ or changing their $\mathit{charged}$ and
$\mathit{executed}$ flags.

  * •

Step $3$ (line 15) resets all the $\mathit{charged}$ and $\mathit{executed}$
flags to prepare the next move in Step $1$. Note that as long as Step $3$ is
executed, full activation continues.

  * •

Step $4$ (line 16) updates the $\mathit{charged}$ flag of the robots that did
not execute $A$ in preceding Step $2$ from $E$ to $C$ (the robots that did not
execute are recharged).

  * •

Step $5$ (line 17) updates the $\mathit{charged}$ flag of the robots that
executed $A$ in preceding Step $2$ from $M$ to $E$ (the robots that executed
are discharged).

  * •

Step $m$ (line 18) executes when the mega-cycle is completed at the beginning
of Step $2$. It resets the $\mathit{executed}$ flags of all robots and goes
back to Step $2$. Note that Step $m$ does not affect the $\mathit{charged}$
flag, thus the robots which executed $A$ in the last activation cycle of the
preceding mega-cycle are discharged in the first activation cycle of the new
mega-cycle and cannot be activated.

The initial configuration of sim-RS-by-S($A$) satisfies $r.\mathit{step}=1$,
$r.\mathit{charged}=C$ and $r.\mathit{executed}=\mathit{False}$ for any robot
$r$. For a configuration $K$, if the set of values of $r.\mathit{step}$
appearing in $K$ is $V$, we say that the step configuration of $K$ is $V$.

Observe that at any moment in time of sim-RS-by-S($A$) the step configuration
$V\in\\{\\{1\\},\\{2\\},\\{3\\},\\{4\\},\\{5\\},\\{m\\},\\{1,2\\},\\{2,3\\},\\{3,1\\},\allowbreak\\{2,4\\},\\{4,5\\},\\{2,5\\},\\{2,m\\}\\}$.
Indeed, the case when $|V|=1$ corresponds to a (sub)set of activated robots
performing the same action (executing $A$, or modifying the flags
$\mathit{charged}$ and $\mathit{executed}$). These robots may update their
$\mathit{step}$ value leading to a new step configuration $V^{\prime}$ of a
size at most two. In the case when $|V|=2$ no actions are performed by the
robots except of updating their $\mathit{step}$ to some value $i\in V$
(remaining robots transition to Step $i$), eventually leading to the next step
configuration $V^{\prime}=\\{i\\}$.

To prove the correctness of sim-RS-by-S($A$) we start with proving the
following properties of the step configurations.

######  Lemma 6.

P$1$

In Step $1$, all the robots have
$(\mathit{charged},\mathit{executed})=(C,\mathit{False})$.

P$2$

In Step $2$, (1) all the robots have flags
$(\mathit{charged},\mathit{executed})\in$
$\\{(C,\mathit{False}),(C,\mathit{True}),(E,\mathit{True})\\}$, (2) a non-
empty subset of robots $R^{\prime}$ have
$(\mathit{charged},\allowbreak\mathit{executed})=(E,\mathit{True})$, and (3)
if $|R^{\prime}|=|R|$ then the preceding Step was $1$.

P$3$

In Step $3$, for all the robots
$(\mathit{charged},\mathit{executed})\in\\{(C,\mathit{False}),$
$(E,\mathit{True})\\}$.

P$4$

In Step $4$, (1) none of the robots have
$(\mathit{charged},\mathit{executed})\in\\{(M,\mathit{False}),(E,\mathit{False})\\}$,
(2) a non-empty subset of robots $R_{m}$ have flags
$(\mathit{charged},\mathit{executed})=(M,\mathit{True})$ with $|R_{m}|<|R|$;
these and only these robots executed a round of algorithm $A$ in the preceding
Step $2$, and (3) a non-empty subset of robots $R_{x}$ have flags
$(\mathit{charged},\mathit{executed})\in\\{(E,\mathit{True}),(C,\mathit{True})\\}$
with $|R_{x}|<|R|$.

P$5$

In Step $5$, (1) none of the robots have
$(\mathit{charged},\mathit{executed})\in\\{(M,\mathit{False}),\allowbreak(E,\mathit{False})\\}$,
(2) a non-empty subset of robots $R_{m}$ have flags
$(\mathit{charged},\allowbreak\mathit{executed})\in\\{(M,\mathit{True}),(E,\mathit{True})\\}$
with $|R_{m}|<|R|$; these and only these robots executed a round of algorithm
$A$ in the preceding Step $2$, and (3) a non-empty subset of robots $R_{x}$
have flags $(\mathit{charged},\allowbreak\mathit{executed})=(C,\mathit{True})$
with $|R_{x}|<|R|$.

P$m$

In Step $m$, (1) none of the robots have their flag $\mathit{charged}=M$, and
(2) a non-empty subset of robots $R^{\prime\prime}$ have $\mathit{charged}=C$
with $|R^{\prime\prime}|<|R|$.

###### Proof.

Initially property P$1$ holds. Below we show that for any transition from Step
$i$ to Step $j$ of sim-RS-by-S($A$), if the corresponding property P$i$ held
before the transition, the property P$j$ holds after the transition. Thus, by
induction the lemma holds.

$\text{P}1\rightarrow\text{P}2$: If property P$1$ holds in Step $1$, in the
succeeding Step $2$ property P$2$ also holds. Indeed, when transiting from
Step $1$ to Step $2$, the robots either set their flags to
$\mathit{charged}=E$ and $\mathit{executed}=\mathit{True}$, or do not update
these flags at all. And a non-empty set of robots does the former. The last
condition trivially holds. Thus P$2$ holds.

$\text{P}2\rightarrow\text{P}2$: If after activation of a set of robots
$R^{\prime}$ in Step $2$ the step configuration remains $\\{2\\}$, then (1)
not all robots in $R$ had their flag $\mathit{charged}=E$, (2) not all robots
in $R$ had their flag $\mathit{executed}=\mathit{True}$, and (3) none of the
robots in $R^{\prime}$ had their flags $\mathit{charged}=C$ and
$\mathit{executed}=\mathit{False}$. Thus, no actions are taken, and no flags
are changed; P$2$ holds.

$\text{P}2\rightarrow\text{P}3$: If property P$2$ holds in Step $2$ and the
succeeding Step is $3$, then in it property P$3$ also holds. From Step $2$
robots can transition to Step $3$ only if all the robots have
$\mathit{charged}=E$. Thus, there were only robots with $\mathit{charged}=E$
and $\mathit{executed}=\mathit{True}$ in Step $2$. They proceed to Step $3$
without changing their flags. Thus P$3$ holds.

$\text{P}2\rightarrow\text{P}4$: If property P$2$ holds in Step $2$ and the
succeeding Step is $4$, then in it property P$4$ also holds. From Step $2$
robots can transition to Step $4$ only if among the activated robots there is
a non-empty subset with
$(\mathit{charged},\mathit{executed})=(C,\mathit{False})$. These robots update
their flags to $(\mathit{charged},\mathit{executed})=(M,\mathit{True})$, and
proceed to Step $4$. The remaining robots proceed to Step $4$ with no changes
to the $\mathit{charged}$ and $\mathit{executed}$ flags. Furthermore, there
were no robots in Step $2$ with $\mathit{charged}=M$ or
$(\mathit{charged},\mathit{executed})=(E,\mathit{False})$, thus P$4$ holds.

$\text{P}3\rightarrow\text{P}3$: In Step $3$ robots with
$(\mathit{charged},\mathit{executed})=(E,\mathit{True})$ update these flags to
$(C,\mathit{False})$. Thus P$3$ continues to hold.

$\text{P}3\rightarrow\text{P}1$: If property P$3$ holds in Step $3$ and the
succeeding Step is $1$, in it property P$1$ also holds. Robots only transition
from Step $3$ to Step $1$ when none of the robots have
$(\mathit{charged},\mathit{executed})=(E,\mathit{True})$. Thus P$1$ holds.

$\text{P}4\rightarrow\text{P}4$: In Step $4$ robots with $\mathit{charged}=E$
update the value of the flag to $C$. Thus P$4$ continues to hold.

$\text{P}4\rightarrow\text{P}5$: If property P$4$ holds in Step $4$ and the
succeeding Step is $5$, then in it property P$5$ also holds. Robots only
transition from Step $4$ to Step $5$ when none of the robots have
$\mathit{charged}=E$. Thus all three conditions of P$5$ hold.

$\text{P}5\rightarrow\text{P}5$: In Step $5$ robots with $\mathit{charged}=M$
update their flag to $E$. Thus P$5$ continues to hold.

$\text{P}5\rightarrow\text{P}2$: If property P$5$ holds in Step $5$, in the
succeeding Step $2$ property P$2$ also holds. Robots only transition from Step
$5$ to Step $2$ when none of the robots have $\mathit{charged}=M$. The last
condition trivially holds. Thus P$2$ holds.

$\text{P}2\rightarrow\text{P}m$: If property P$2$ holds in Step $2$ and the
succeeding Step is $m$, then in it property P$m$ also holds. From Step $2$
robots can transition to Step $m$ only if all the robots have
$\mathit{executed}=\mathit{True}$ and not all the robots have
$\mathit{charged}=E$. In this case none of the robots update their flags
$\mathit{charged}$ and $\mathit{executed}$, and both conditions of P$3$ hold.

$\text{P}m\rightarrow\text{P}m$: In Step $m$ robots with
$\mathit{executed}=\mathit{False}$ update their flag to $\mathit{True}$. Thus
P$m$ continues to hold. ∎

As mentioned above, sim-RS-by-S(A) executes Step $1$ in the first phase when
all the robots are activated at every simulated activation cycle of Rsynch.
Each mega-cycle then consists of one execution of Step $1$. As soon as a
subset of robots is activated in Step $1$, a second phase begins. In it, each
mega-cycle consists of multiple executions of Step $2$. From property P$2$ it
follows that at every simulated activation cycle of Rsynch a non-empty subset
of robots is activated. From properties P$2$, P$4$, and P$5$, it follows that
when a robot executes algorithm $A$ in a mega-cycle, it will not execute in
the same mega-cycle again. The mega-cycle lasts until all the robots have
executed $A$. Furthermore, from properties P$2$, P$4$, P$5$, and P$m$, it
follows that in the beginning of the new mega-cycle in Step $2$, the robots
that executed the algorithm in the last simulated activation cycle of Rsynch
have their flag $\mathit{charged}=E$, and otherwise the robots have
$\mathit{charged}=C$. Thus, simulated activation cycle of Rsynch is valid and
is fair.

Note that, if algorithm $A$ uses $\ell$ colors, the simulating algorithm sim-
RS-by-S(A) uses $O(\ell)$ colors.

######  Lemma 7.

Algorithm sim-RS-by-S(A) correctly simulates execution of algorithm $A$ run on
$\mathcal{LUMI}^{R}$ robots by $\mathcal{LUMI}^{S}$ robots.

We have then obtained Theorem 5 and since the reverse relation is trivial, the
next theorem holds.

######  Theorem 6.

$\mathcal{LUMI}^{S}\equiv$ $\mathcal{LUMI}^{RS}$.

##  4 Relationship between Fsynch and Rsynch

We have seen that Rsynch is more powerful than Ssynch in $\mathcal{FCOM}$,
$\mathcal{FST\\!A}$, $\mathcal{OBLOT}$, and it has the same computational
power in $\mathcal{LUMI}$. To better understand the power of Rsynch among the
classical synchronous schedulers, we now turn our attention to the
relationship between Rsynch and Fsynch.

###  4.1 Dominance of Fsynch over Rsynch

The problem Center of Gravity Expansion (CGE) was used to show dominance of
Fsynch over Ssynch, that is, CGE is solvable in $\mathcal{FCOM}^{F}$ and
$\mathcal{FST\\!A}^{F}$ but is not solvable in $\mathcal{LUMI}^{S}$ [19]. This
problem can also be used to show dominance of Fsynch over Rsynch. In fact, we
can obtain a stronger result showing that CGE is not solvable in
$\mathcal{LUMI}^{F^{\prime}}$, where $F^{\prime}$ is any scheduler such that
the first activation does not contain all robots.

Let $P=\\{(x_{1},y_{1}),(x_{2},y_{2}),\ldots,(x_{n},y_{n})\\}$ be the set of
positions occupied by robots $R=\\{r_{1},r_{2},\ldots,r_{n}\\}$ and let
$c=(c_{x},c_{y})$ be the coordinates of the CoG (Center of Gravity) of $P$ at
time $t=0$. All these values are expressed according to a global coordinate
system not available to the robots, which have their own local ones. The
following problem prescribes the robots to perform a sort of “expansion” of
the initial configuration with respect to their center of gravity;
specifically, each robot must move away from $(c_{x},c_{y})$ to the closest
position with lattice point corresponding to doubling its distance from it.
More precisely:

######  Definition 3.

CENTER OF GRAVITY EXPANSION (CGE): Let $R$ be a set of robots with $|R|\geq
2$. The CGE problem requires each robot $r_{i}\in R$ to move from its initial
position $(x_{i},y_{i})$ directly to $(f(x_{i},c_{x}),f(y_{i},c_{y}))$ where
$f(a,b)=\lfloor 2a-b\rfloor$, away from the Center of Gravity of the initial
configuration so that each robot doubles its initial distance from it and no
longer moves.

Note that, if $f(a,b)=2a-b$, the result would be a perfect expansion of the
initial configuration, doubling the distance of each robot from the center of
gravity; this expansion would clearly preserve the center of gravity. The
presence of the floor makes the configuration expand in a more irregular
fashion, resulting in a new configuration with a different center of gravity.
Also note that each robot $r_{i}$ perceives itself as the center of its own
coordinate system. Expressed in $r_{i}$’s local coordinate system, the center
of gravity is located at point $(c_{i,x},c_{i,y})=(c_{x}-x_{i},c_{y}-y_{i})$.
Applying the appropriate translations, upon looking, the destination of
$r_{i}$ is then given by the local function $f_{i}(c_{i,x},c_{i,y}))=(\lfloor-
c_{i,x}\rfloor,\lfloor-c_{i,y}\rfloor)$ (which is the equivalent of the global
$f$ indicated in the problem definition). For ease of discussion, in the
following we use the global coordinates.

######  Lemma 8.

For a set of points $P=\\{(x_{i},y_{i})|1\leq i\leq n\\}$ there exist infinite
sets of points $Q_{i}(1\leq i\leq n)$ such that $(x_{i},y_{i})\in Q_{i}(1\leq
i\leq n)$ and $\forall(x_{i}^{\prime},y_{i}^{\prime})\in Q_{i}(1\leq i\leq
n)$: $f(x_{i},c_{x})=f(x^{\prime},c_{x}^{\prime})$, and
$f(y_{i},c_{y})=f(y^{\prime},c_{y}^{\prime})$, where
$(c_{x}^{\prime},c_{y}^{\prime})$ is the coordinates of the CoG of
$\\{(x_{i}^{\prime},y_{i}^{\prime})|1\leq i\leq n\\}$.

######  Lemma 9.

Let $n\geq 2$. $\exists\mathit{R}\in\mathcal{R}_{n}$:
$\text{CGE}\not\in\mathcal{LUMI}^{F^{\prime}}(R)$, where $F^{\prime}$ is any
scheduler such that the first activation does not contain all robots.

###### Proof.

Let $k$ be the number of activated robots in the first round. Note that $1\leq
k<n$ by assumption. By contradiction, suppose that the problem is solvable
from an arbitrary initial configuration. Consider two scenarios with
$R=\\{r_{i}|1\leq i\leq n\\}$.

In scenario $A$ the global coordinates of the robots are:
$r_{i}=(c_{i},0)(1\leq i\leq n)$, where $c_{i}(1\leq i\leq n-1)$ are different
negative integers, $c_{n}$ is a natural number, and $\Sigma_{i=1}^{n}c_{i}=0$;
thus, CoG is at $(0,0)$.

In scenario $B$ the global coordinates of the robots are:
$r_{i}=(c_{i}+\epsilon,0)(1\leq i\leq n-1),r_{n}=(c_{n},0)$, where
$c_{i}(1\leq i\leq n-1)$ are different negative integers, $c_{n}$ is a natural
number, $\Sigma_{i=1}^{n}c_{i}=0$ and $1>\epsilon>0$; thus CoG is at
$((n-1)\epsilon/n,0)$.

Consider an execution ${\mathcal{E}}$ where the scheduler activates
$r_{1},r_{2},\ldots,r_{k}$ at time $t_{0}$, where $1\leq k\leq n-1$ by
assumption. In this execution, in scenario $A$, $r_{i}(1\leq i\leq k)$ moves
to $f((c_{i},0),(0,0))=(2c_{i},0)$, possibly changing color; the new
configuration at time $t_{0}+1$ is $r_{i}=(2c_{i},0)(1\leq i\leq
k),r_{i}=(c_{i}+\epsilon,0)(k+1\leq i\leq n-1)$, and $r_{n}=(c_{n},0)$.
Observe that the same configuration would have been obtained by the same
execution also in scenario $B$ where CoG would be at $((n-1)\epsilon/n,0)$ and
$r_{i}(1\leq i\leq k)$ would have moved to
$f(c_{i}+\epsilon,(n-1)\epsilon/n),(0,0))=(c_{i},0)$ (if $(n+1)\epsilon/n<1$)
as well.

In execution ${\mathcal{E}}$, let the scheduler activate $R_{t_{0}+1}$ (it can
be $R$) at time $t_{0}+1$ and let $r_{n}\in R_{t_{0}+1}$. Robot $r_{n}$ may
know that $r_{i}(1\leq i\leq k)$ have already reached their destination by
looking at their colors; that is, they may know that their positions have been
calculated according to the target function $f$. However, by Lemma 8, we know
that $f^{-1}$ corresponds to an infinite set of coordinates which contains, in
particular, both $(c_{i},0)$ and $(c_{i}+\epsilon,0)(1\leq i\leq k)$.

In scenario $A$ the unique correct destination for $r_{n}$ would be
$f((c_{n},0),(0,0))=(2c_{n},0)$. In scenario $B$, on the other hand, to solve
the problem, $r_{n}$ should move to
$f((c_{n},(n-1)\epsilon/n),(0,0))=(2c_{n}-1,0)$. Since robot $r_{n}$ observes
the same configuration at time $t_{0}+1$, $r_{n}$ cannot distinguish the two
scenarios. We have a contradiction. ∎

Since Rsynch contains patterns in $F^{\prime}$, we have the following.

######  Corollary 1.

Let $n\geq 2$. $\exists\mathit{R}\in\mathcal{R}_{n}$,
$\text{CGE}\not\in\mathcal{LUMI}^{RS}(R)$.

As a consequence, we have dominance of Fsynch over Rsynch as follows;

######  Theorem 7.

$\forall\mathcal{X}\in\\{\mathcal{OBLOT},\mathcal{FCOM},\mathcal{FST\\!A},\mathcal{LUMI}\\}$
$\mathcal{X}^{F}>\mathcal{X}^{RS}$.

###  4.2 Orthogonality of Fsynch with Rsynch

In this section, we show the orthogonality of $\mathcal{FST\\!A}^{F}$ with
$\mathcal{X}^{RS}$ for $\mathcal{X}\in\\{\mathcal{LUMI},\mathcal{FCOM}\\}$,
and of $\mathcal{OBLOT}^{F}$ with $\mathcal{X}^{RS}$ for
$\mathcal{X}\in\\{\mathcal{LUMI},\mathcal{FCOM},\mathcal{FST\\!A}\\}$. The
orthogonality of $\mathcal{FST\\!A}^{F}$ with $\mathcal{X}^{RS}$, for
$\mathcal{X}\in\\{\mathcal{LUMI},\mathcal{FCOM}\\}$, can be obtained by (1)
CYC is not in $\mathcal{FST\\!A}^{F}$ (Lemma 4) and is in $\mathcal{FCOM}^{S}$
(Lemma 5), and thus CYC is in $\mathcal{FCOM}^{RS}$ and $\mathcal{LUMI}^{RS}$,
and (2) CGE is in $\mathcal{FST\\!A}^{F}$ ([19]) and is not in
$\mathcal{LUMI}^{RS}$ (Corollary 1), and thus CGE is not in
$\mathcal{FCOM}^{RS}$ .

######  Theorem 8.

  1. 1.

$\mathcal{FST\\!A}^{F}\bot$ $\mathcal{LUMI}^{RS}$,

  2. 2.

$\mathcal{FST\\!A}^{F}\bot$ $\mathcal{FCOM}^{RS}$.

The problems OSP and CGE* were used to show $\mathcal{OBLOT}^{F}\bot$
$\mathcal{LUMI}^{S}$, that is, problem OSP can be solved in
$\mathcal{LUMI}^{S}$, but not in $\mathcal{OBLOT}^{F}$, and problem CoG* can
be trivially solved in $\mathcal{OBLOT}^{F}$, but not in $\mathcal{LUMI}^{S}$
[19].

These problems can be used to show $\mathcal{OBLOT}^{F}\bot$
$\mathcal{X}^{RS}$
($\mathcal{X}\in\\{\mathcal{LUMI},\mathcal{FCOM},\mathcal{FST\\!A}\\}$) by
using the following lemma 10, Corollary 1, and the fact that CGE* can be
solved in $\mathcal{FST\\!A}^{F}$ [19].

######  Lemma 10.

  * •

$\exists\mathit{R}\in\mathcal{R}_{2}$,
$\text{OSP}\not\in\mathcal{OBLOT}^{F}(R)$ [10],

  * •

$\forall\mathit{R}\in\mathcal{R}_{2}$,
$\text{OSP}\in\mathcal{FST\\!A}^{RS}(R)\cap\mathcal{FCOM}^{RS}(R)$.

It follows that

######  Theorem 9.

  1. 1.

$\mathcal{OBLOT}^{F}\bot$ $\mathcal{LUMI}^{RS}$

  2. 2.

$\mathcal{OBLOT}^{F}\bot$ $\mathcal{FCOM}^{RS}$

  3. 3.

$\mathcal{OBLOT}^{F}\bot$ $\mathcal{FST\\!A}^{RS}$

##  5 Power within Rsynch

In this section we determine the relationships among $\mathcal{LUMI}^{RS},\\\
\mathcal{FCOM}^{RS}$, and $\mathcal{FST\\!A}^{RS}$, and we show that:
$\mathcal{FCOM}^{RS}=\mathcal{LUMI}^{RS}>\mathcal{FST\\!A}^{RS}$.

######  Theorem 10.

$\forall
R\in\mathcal{R},\mathcal{LUMI}^{S}(R)\subseteq\mathcal{FCOM}^{RS}(R)$.

Algorithm 5 sim-LUMI-by-FCOM(A): predicates and subroutines for robot $r$ at
location $x$.

predicate checked-all-neighbors-and-me
$\forall\rho\neq r\ (\rho.\mathit{checked}=\mathit{True}$ and $\rho.{\tt
suc}.\mathit{checked}=\mathit{True})$

predicate own-executed
${\tt
pred}(x).\mathit{executed}\setminus\mathit{executed}(x)=\\{\mathit{True}\\}$,

where $\mathit{executed}(x)$ is the set of $\mathit{executed}$ colors seen by
$r$ at its own location $x$ (note that, by definition, this set does not
include $r$’s own color)

predicate all-robots-executed
$\forall\rho\neq r\ (\rho.\mathit{executed}=\mathit{True})\textbf{ and
}r.\mathit{executed}$

predicate all-robots-reset

$\forall\rho\neq r\ (\rho.\mathit{executed}=\mathit{False})$

predicate checked-flags-reset($\rho$)

$\rho.{\tt suc}.\mathit{color}=\varnothing$ and $\rho.{\tt
suc}.\mathit{executed}=\\{\mathit{False}\\}$

and  $\rho.{\tt suc}.\mathit{checked}=\mathit{False}$ and
$\rho.\mathit{checked}=\mathit{False}$

subroutine Copy-Colors-of-Neighbors
$r.{\tt suc}.\mathit{color}\leftarrow{\tt suc}(x).\mathit{color}$

subroutine Copy-Execution-of-Neighbors
$r.{\tt suc}.\mathit{executed}\leftarrow{\tt suc}(x).\mathit{executed}$

subroutine Determine-own-color
$r.\mathit{color}\leftarrow{\tt pred}(x).{\tt
suc}.\mathit{color}\setminus\mathit{color}(x)$,

where $\mathit{color}(x)$ is the set of $\mathit{color}$ colors seen by $r$ at
its own location $x$ (note that, by definition, this set does not include
$r$’s own color)

subroutine Reset-Checking-Flags
$r.{\tt suc}.\mathit{color}\leftarrow\varnothing$

$r.{\tt suc}.\mathit{executed}\leftarrow\\{\mathit{False}\\}$

$r.{\tt suc}.\mathit{checked}\leftarrow$ $\mathit{False}$

$r.\mathit{checked}\leftarrow$ $\mathit{False}$

Algorithm 6 sim-LUMI-by-FCOM(A): for robot $r$ at location $x$.

1:Assumptions: Let $x_{0},x_{1},\ldots,x_{m-1}$ be the circular arrangement on
the configuration $C$, and let ${\tt suc}(x_{i})=x_{i+1\bmod m}$ and ${\tt
pred}(x_{i})=x_{i-1\bmod m}$.

2:State Look

3:Observe, in particular, ${\tt pred}(x).\mathit{step}$, ${\tt
pred}(x).\mathit{color}(\mathit{executed})$, ${\tt
suc}(x).\mathit{color}(\mathit{executed})$, as well as
$r.\mathit{color}.\mathit{here}$ (note that, for this, $r$ cannot see its own
color).

4:State Compute

5:$r.\mathit{des}\leftarrow r.\mathit{pos}$

6:if $\forall\rho\neq\ r(\rho.\mathit{step}=1)$ then // step 1 (CopyColors &
Execution)

7: call Copy-Colors-of-Neighbors

8: call Copy-Execution-of-Neighbors

9: if $\forall\rho\in{\tt suc}(x)(\rho.\mathit{checked}=\mathit{True})$ then
$r.{\tt suc}.\mathit{checked}\leftarrow\mathit{True}$

10: $r.\mathit{checked}\leftarrow\mathit{True}$

11: if not checked-all-neighbors-and-me then

12: $r.\mathit{step}\leftarrow 1$

13: else

14: $r.\mathit{step}\leftarrow 2$

15:else if $\forall\rho\neq r\ (\rho.\mathit{step}=2)$ then // start step $2$
(PerformSimulation)

16: if all-robots-executed then $r.\mathit{step}\leftarrow m$ // if mega-cycle
ends

17: else if own-executed then $r.\mathit{step}\leftarrow 2$

18: else

19: call Determine-own-color

20: Execute the Compute of $A$ // with my color $r.\mathit{color}$,
determining destination $r.\mathit{des}$

21: $r.\mathit{executed}\leftarrow\mathit{True}$

22: $r.\mathit{step}\leftarrow 3$

23:else if $\forall\rho\neq r\ (\rho.\mathit{step}=3)$ then // step $3$
(ResetCheckingFlags)

24: if $\forall\rho\neq r\,($checked-flags-reset$(\rho))$ then

25: $r.\mathit{step}\leftarrow 1$

26: call Reset-Checking-Flags

27: else if $\exists\rho\neq r\,($ not checked-flags-reset$(\rho))$) then

28: $r.\mathit{step}\leftarrow 3$

29: call Reset-Checking-Flags

30:else if $\forall\rho\neq r\,(\rho.\mathit{step}=m)$ then // step $m$
(ResetExecutionFlags)

31: if not $\forall\rho\neq r\,((\rho.\mathit{executed}=\mathit{False})$

32: and $(\rho.\mathit{suc}.\mathit{executed}=\\{\mathit{False}\\}))$ then

33: $r.\mathit{step}\leftarrow m$

34: $r.\mathit{executed}\leftarrow\mathit{False}$

35: $r.{\tt suc}.\mathit{executed}\leftarrow\\{\mathit{False}\\}$

36: else

37: $r.\mathit{step}\leftarrow 2$

38: $r.\mathit{executed}\leftarrow\mathit{False}$

39: $r.{\tt suc}.\mathit{executed}\leftarrow\\{\mathit{False}\\}$

40:else if $\forall\rho\neq r\,((\rho.\mathit{step}=1)$ or
($\rho.\mathit{step}=2))$ then $r.\mathit{step}\leftarrow 2$

41:else if $\forall\rho\neq r\,((\rho.\mathit{step}=2)$ or
($\rho.\mathit{step}=3))$ then $r.\mathit{step}\leftarrow 3$

42:else if $\forall\rho\neq r\,((\rho.\mathit{step}=2)$ or
($\rho.\mathit{step}=m))$ and all-robots-executed then
$r.\mathit{step}\leftarrow m$

43:else if $\forall\rho\neq r\,((\rho.\mathit{step}=3)$ or
($\rho.\mathit{step}=1))$ then $r.\mathit{step}\leftarrow 1$

44:else if $\forall\rho\neq r\,((\rho.\mathit{step}=m)$ or
($\rho.\mathit{step}=2))$ and all-robots-reset then $r.\mathit{step}\leftarrow
2$

45: State Move

46:Move to $r.\mathit{des}$

Let A be an algorithm in Ssynch by $\mathcal{LUMI}$ with Disorientation and
non-rigid movement, and let A use light with $\ell$ colors:
$C=\\{c_{0},c_{1},\ldots c_{\ell-1}\\}$. We now extend the simulation
algorithm of $\mathcal{LUMI}$ robots by $\mathcal{FCOM}$ robots in Fsynch
described in [19], designing a more complex simulation algorithm sim-LUMI-by-
FCOM(A)(Algorithms 5 and 6) by $\mathcal{FCOM}$ robots in Rsynch. The main
ideas will stay the same. Robots first copy the lights of their neighbors.
This in turn allows them to look at their neighbors to gain information about
the color of their own light. Next, some robots activate and have enough
information to execute a step in A. Lastly, the robots reset their states such
that they can start copying the lights of their neighbors again. This cycle
repeats itself and every time some robots execute algorithm A. Contrary to the
simulation algorithm in Fsynch, we need to take extra care here to ensure that
the resulting schedule is fair and every robot executes a step in A infinitely
often. After all, the same subset of robots might execute algorithm A each
time the robots perform this cycle. As with sim-RS-by-S(A), we consider the
concept of mega-cycles, in which every robot executes a step in A exactly
once. To facilitate this, each robot gets a flag indicating if the robot has
executed A already this mega-cycle. To give a robot information about its own
execute status, we let the robots copy this flag in the same way as they copy
the other lights of their neighbors. As soon as all robots have executed A in
a certain mega-cycle, these flags get reset and the next mega-cycle starts.

To facilitate copying the lights of neighbors, we define a circular ordering
on the locations of the robots. When chirality is assumed, this defines for
each location $x$ a successor location ${\tt suc}(x)$ and a predecessor
location ${\tt pred}(x)$. The assumption of chirality will later be lifted.

Figure 5 shows the transition diagram as the robots change steps’ values.

Robot $r$ at location $x$ has available the following colors of
$\mathcal{FCOM}$.

Figure 5: Transition Diagram of sim-LUMI-by-FCOM(A). Step 1: copy colors and
activation; step 2: check if the mega-cycle ends; step 3: reset check flags;
step $\bm{m}$: reset activation.

  1. 1.

$r.\mathit{light}\in C$ indicating its own light used in algorithm A,
initially set to $r.\mathit{light}=c_{0}$,

  2. 2.

$r.{\tt suc}.\mathit{light}$ indicating a set of colors from $2^{C}$ at
suc(x), initially set to $r.{\tt suc}.\mathit{light}=\varnothing$,

  3. 3.

$r.\mathit{step}\in\\{1,2,3,m\\}$ indicating the step of the algorithm, where
step $1,2,3$ and $m$ are CopyColors&Execution, PerformSimulation,
ResetCheckingFlags and ResetExecutionFlags, respectively, initially set to
$r.phase=1$,

  4. 4.

$r.\mathit{executed}\in\\{\mathit{True},\mathit{False}\\}$ indicating whether
$r$ has executed the algorithm $A$ or not in a mega-cycle, initially set to
$r.\mathit{executed}=\mathit{False}$.

  5. 5.

$r.{\tt suc}.\mathit{executed}$ indicating a set from
$2^{\\{\mathit{True},\mathit{False}\\}}$ at suc(x) and having the same role of
$r.{\tt suc}.\mathit{light}$, initially set to $r.{\tt
suc}.\mathit{executed}=\varnothing$,

  6. 6.

$r.me.checked$, $r.{\tt suc}.checked$, $\in\\{\mathit{True},\mathit{False}\\}$
indicating whether all ‘light’s and ‘executed’s are correctly set, initially
set to $r.me.checked$, $r.{\tt suc}.checked=\mathit{False}$.

The algorithm is a sequence of mega-cycles, each of which lasts until all
robots execute the simulated algorithm exactly once, and the end of mega-
cycles is checked at the beginning of Step $2$. During each mega-cycle, this
algorithm is composed of the following three steps:

  * •

In Step $1$, every robot obtains the neighbor’s information so that robots can
recognize their own lights.

  * •

In Step $2$, activated robots in it execute algorithm A using the color of
light obtained.

  * •

In Step $3$, every robot resets check flags to prepare the next simulation of
algorithm A. Repeating the three steps, the end of the current mega-cycle is
checked at the beginning of Step $2$ and if the megacycle is finished, each
robot $r$ proceeds to Step $m$ to reset.

  * •

In Step $m$, every robot resets flag $r.\mathit{executed}$ indicating whether
$r$ has executed in this mega-cycle or not to $\mathit{False}$ and the control
returns to Step $2$.

The details of these steps are as follows:

  * •

Step 1-Copy Colors and Activation ($\forall\rho\neq r(\rho.\mathit{step}=1)$).

In the Look phase, $r$ understands to be in Step $1$ by detecting
$\rho.\mathit{step}=1$ for any other robots $\rho$. Every robot $r$ stores
(and displays) in variable $r.{\tt suc}.\mathit{light}$ and $r.{\tt
suc}.\mathit{executed}$, respectively, its successors’ sets of colors and also
their sets of executed flags indicating whether the successors’ robots have
been activated in this mega-cycle. None of the robots move in this step. Note
that every robot can recognize its own color of light and its activated flags
in the configuration after Step $1$ is completed. This step ends when all
robots store their neighbors’ sets of colors and sets of executed flags. To be
able to detect this, every robot sets $r.checked$ to $\mathit{True}$,
indicating that it has executed Step $1$. Moreover, whenever all successors of
$r$ have set their $checked$ flags to $\mathit{True}$, $r$ also sets $r.{\tt
suc}.checked$ to $\mathit{True}$. Now every robot can determine the end of
Step $1$ when the two checked flags ($\rho.me.checked$, $\rho.{\tt
suc}.checked$) of every robot $\rho$ become $\mathit{True}$. When this
condition is satisfied, $r$ changes $r.\mathit{step}$ to $2$.

  * •

Step 2-Perform Simulation ($\forall\rho\neq r(\rho.\mathit{step}=2)$).

In the Look phase, $r$ recognises to be in Step 2 by observing
$\rho.\mathit{step}=2$ of any other robots $\rho$. Robot $r$ can calculate
$r.\mathit{light}$ and $r.\mathit{executed}$ by using its predecessor’s ${\tt
suc}.\mathit{light}$ and ${\tt suc}.\mathit{executed}$. The rest of Step $2$
consists of two phases: checking the end of mega-cycles, and execution of the
simulation phase.

Checking End of Mega-Cycles: After calculating $r.\mathit{light}$ and
$r.\mathit{executed}$, $r$ will check if the current mega-cycle has ended. If
all robots have executed algorithm A in this mega-cycle (all robots have
$r.\mathit{executed}$ set to $\mathit{True}$, then it moves to Step $m$
(resetting all the executed flags) without changing colors of lights except
for the executed flags.

Execution of Simulation : If the mega-cycle has not ended yet, the robots
activated in this round will perform a step in A. The activated robots
(indicated by set $S_{2}$) at this time, actually perform their cycle
according to algorithm A if they have not performed algorithm A in this mega-
cycle yet ($r.\mathit{executed}$ is $\mathit{False}$). The robots that
executed algorithm A update $r.\mathit{executed}$ and furthermore update
$r.\mathit{light}$ and move according to algorithm A. After the actual
execution of algorithm A, each robot $r$ performing the simulation sets
$r.\mathit{step}=3$ to reset all checking flags (Step $3$) to prepare for the
next Step $1$.

If all robots in $S_{2}$ have performed algorithm A so far in this mega-cycle,
no light is changed, and Step $2$ is also performed at the next time. This
situation repeats until some robots not having executed algorithm A appear.
The appearance of these robots is guaranteed from the fairness of the
scheduler.

  * •

Step 3-Reset Check flags ($\forall\rho\neq r(\rho.\mathit{step}=3)$).

In the Look phase, $r$ understands to be in Step $3$ by observing
$\rho.\mathit{step}=3$ for any other robots $\rho$. In Step $3$, all robots
reset $r.checked$, $r.{\tt suc}.checked$ to $\mathit{False}$, and $r.{\tt
suc}.\mathit{executed}$ to $\\{\mathit{False}\\}$, enabling the robots to
perform another round in this cycle. Each robot resetting its flags changes
$r.\mathit{step}$ to $1$.

  * •

Step $m$-Reset Mega-Cycle ($\forall\rho\neq r(\rho.\mathit{step}=m)$). In the
Look phase, $r$ understands to be in Step $m$ by observing
$\rho.\mathit{step}=m$ of any other robots $\rho$. In Step $m$, each robot $r$
sets $r.\mathit{executed}=\mathit{False}$ and $r.{\tt
suc}.\mathit{executed}=\\{\mathit{False}\\}$ and the step returns to $2$ to
begin a new mega-cycle after all robots reset their activated flags.

Algorithm 7 Scheme-for-modification-flags for robot $r$ at location $x$.
Assumptions
---
|  Let configuration be $same(\mathit{step}=\alpha)$ or
$except1(\mathit{step}=\alpha;\gamma)$
State Compute
|  1: if $\forall\rho\neq r\,(\rho.\mathit{step}=\alpha$) then // step
$\alpha$
| 2: |  if not $\forall\rho\neq r\,(\rho.\mathit{flag}=\mathit{True}$) then
| 3: |  | $r.\mathit{step}\leftarrow\alpha$
| 4: |  | $r.\mathit{flag}\leftarrow\mathit{True}$
| 5: |  else if $\forall\rho\neq r\,(\rho.\mathit{flag}=\mathit{True})$ then
| 6: |  | $r.\mathit{flag}\leftarrow\mathit{True}$
| 7: |  | $r.\mathit{step}\leftarrow\beta$
|  8: else if $\forall\rho\neq r\,(\rho.\mathit{step}=\beta$) then
$r.\mathit{step}\leftarrow\beta$ // step $\beta$
|  9: else if $\forall\rho\neq r\,((\rho.\mathit{step}=\alpha)$ or
$(\rho.\mathit{step}=\beta))$ then $r.\mathit{step}\leftarrow\beta$

Now we show that this simulation algorithm works correctly for
$\mathcal{FCOM}$ robots in Rsynch. Note that since Rsynch may start with all
robots activated, it is easily validated that this algorithm works well in
Fsynch (see Appendix for the details).

Since we consider $\mathcal{FCOM}$ robots, when a robot $r$ checks a
predicate, for example $\forall\rho(\rho.\mathit{step}=\alpha)$, $r$ cannot
see its own $r.\mathit{step}$. Therefor, $r$ only checks $\forall\rho\neq
r(\rho.\mathit{step}=\alpha)$ and observes that the predicate may be satisfied
although $r.\mathit{step}$ is not $\alpha$. This means that predicates
appearing in the $\mathcal{FCOM}$ algorithm must be of the form $\forall$
$\rho\neq r$ ($\ldots$) and we must consider configurations on which only one
robot $r$ observes that some predicate holds but any of the other robots
observe that the predicate does not hold.

In order to understand our algorithm, consider a simple example where every
robot $\rho$ has two lights $\rho.\mathit{step}(\in\\{\alpha,\beta,\gamma\\})$
and $\rho.flag(\in\\{\mathit{True},\mathit{False}\\})$. Let us consider a
configuration where $\rho.\mathit{step}=\alpha$ for any robot $\rho$ and a
configuration where there exists just one robot $r_{e}$ with
$r_{e}.\mathit{step}=\gamma$ while $\rho.\mathit{step}=\alpha$ for any other
robot $\rho$. The former configuration is denoted by $same(step=\alpha)$
(because all robots are the same step) and the latter is denoted by
$except1(step=\alpha;\gamma)$ (because all robots are step $\alpha$ except one
which is step $\gamma$).

The next Lemma shows the following: if a step configuration is
$same(step=\alpha)$ or $except1(step=\alpha;\gamma)$ with
$\rho.flag=\mathit{False}$ for any robot $\rho$, Algorithm 7 transforms the
step configuration into one of type $same(step=\beta)$ or
$except1(step=\beta;\alpha)$ with $\rho.flag$ changed to $\mathit{True}$ for
all robots $\rho$. The idea is that as long as a robot still observes other
robots with $flag=\mathit{False}$, robots just keep on setting their $flag$ to
$\mathit{True}$, while staying with $step=\alpha$. As soon as a robot notices
all other robots having $flag=\mathit{True}$, the robots need to progress to
$step=\beta$. However, the activated robot may not have been active before and
therefore still needs to set $flag$ to $\mathit{True}$. Now any robot active
that sees another robot with $step=\beta$ knows that all $flags$ are
$\mathit{True}$, including its own.

######  Lemma 11.

Let $C(t_{a})$ be a step configuration either of type $same(step=\alpha)$ or
$except1(step=\alpha,\gamma\neq\beta)$ at time $t_{a}$, and let
$\forall\rho(\rho$.flag =$\mathit{False}$) hold at $t_{a}$. If Algorithm 7 is
executed on $C(t_{a})$, then there is a time $t_{b}>t_{a}$ when $C(t_{b})$
satisfies the following conditions:

  1. (a)

The step configuration $C(t_{b})$ is either $same(step=\beta)$ or
$except1(step=\beta;\alpha)$.

  2. (b)

$\forall\rho(\rho.flag=\mathit{True})$ holds at $t_{b}$.

###### Proof.

Consider the two cases: (1) $same(step=\alpha)$ and (2)
$except1(step=\alpha,\gamma\neq\beta)$ at $t_{a}$.

(1) $same$(step=$\alpha$) at $t_{a}$: Since line 1 holds and line 2 holds
until $\forall\rho(\rho.flag=\mathit{True})$ holds, the number of robots
$\rho$ with $\rho.flag=\mathit{False}$ (denoted as $\\#(flag=\mathit{False}))$
decreases. As long as $\\#(flag=\mathit{False})\geq 2$, since line 1 and line
2 hold and the schedule is fair, $\\#(flag=\mathit{False})$ decreases. Let $t$
be the first time when $\\#(flag=\mathit{False})\leq 1$.

  * •

If $\\#(flag=\mathit{False})=0$, since $\forall\rho(\rho.flag=\mathit{True})$
holds, the robots activated at $t$ execute lines 6 and 7 and the step
configuration becomes $\\{\alpha,\beta\\}$ at $t+1$. If $\\#(step=\alpha)\geq
2$, the robots activated after $t+1$ execute line 9 and $\\#(step=\alpha)$
decreases. As long as $\\#(step=\alpha)\geq 2$, when robots $r$ with
$r.\mathit{step}=\alpha$ are activated, they observe
$\rho.\mathit{step}=\alpha$ and $\rho^{\prime}.\mathit{step}=\beta$. Then,
since there is a time when $\\#(step=\alpha)\leq 1$, letting $t_{b}$ be such
time, the lemma holds.

  * •

Otherwise ($\\#(flag=\mathit{False})=1$), let $r_{e}$ be the robot with
$r_{e}.flag=\mathit{False}$. In this case, since $r_{e}$ observes
$\forall\rho\neq r_{e}(\rho.flag=\mathit{True})$, it will execute lines 5-7,
changing $r_{e}.\mathit{step}$ to $\beta$, but also setting $r_{e}.flag$ to
$\mathit{True}$. The next time, $\forall\rho(\rho.flag=\mathit{True})$ holds.
Therefore, the same actions as in the previous situation of
$\\#(flag=\mathit{False})=0$ are taken, and the lemma holds.

(2) $except1(step=\alpha,\gamma\neq\beta)$ at $t_{a}$: Let $r_{e}$ be the
robot with $r_{e}.\mathit{step}=\gamma$ and let $t$ be the first time $r_{e}$
is activated after $t_{a}$. Any activated robot except re between $t_{a}$ and
$t$ does not change the color of its own lights, because it observes
$r_{e}.\mathit{step}=\gamma$. Since only $r_{e}$ observes $\forall\rho\neq
r_{e}(\rho.\mathit{step}=\alpha$) and not $\forall\rho\neq
r(\rho.flag=\mathit{True})$, $r_{e}$ changes $r_{e}.\mathit{step}=\alpha$ and
the step configuration becomes $same(step=\alpha)$ at $t+1$. Then, this case
can be reduced to case (1) and the lemma holds.∎

This scheme of transitions between step configurations is used in the
algorithm.In particular, transitions from Step $1$ to Step $2$, from Step $2$
to Step $m$, from Step $m$ to Step $2$, and from Step $3$ to Step $1$ (Lemmas
12, 13, 14 and 15). Note that the condition of Rsynch is not used in the proof
of Lemma 11, that is, Algorithm 7 works also in Ssynch correctly. The
prohibited pattern in Rsynch is necessary only for the actual simulation (Step
2).

Let $\pi_{1}(X,t)$ denote the predicate checked-all-neighbors-and-me:
$\forall$ $\rho\in X$($\rho.me.checked=\mathit{True}$ and $\rho.{\tt
suc}.checked=\mathit{True}$), at time $t$.

######  Lemma 12.

Assume that step configuration is $same(step=1)$ or $except1(step=1;3)$ and it
holds that $\forall\rho\in R(\rho.checked=\mathit{False}$ and $\rho.{\tt
suc}.checked=\mathit{False})$ at time $t_{1}$. Then there exists a time
$t_{2}>t_{1}$ such that the following (1) and (2) hold.

  1. (1)

The step configuration at $t_{2}$ is $same(step=2)$ or $except1(step=2;1)$.

  2. (2)

$\pi_{1}(R,t_{2})$ holds and for every robot $r\in R$ at any location $x$,
$r.{\tt suc}.\mathit{light}=\\{\rho.\mathit{color}\mid\rho\in{\tt suc}(x)\\}$
and $r.{\tt suc}.\mathit{executed}=\\{\rho.\mathit{executed}\mid\rho\in{\tt
suc}(x)\\}$ at $t_{2}$.

Lemma 12 implies that each robot $r$ can calculate its own color
($r.\mathit{light}$) and whether $r$ has executed algorithm A in the current
mega-cycle or not ($r.\mathit{executed}$) by looking at the neighbor’s
corresponding lights.

The color of robot $r$ ($r.\mathit{color}$) used in the execution of algorithm
A is determined as follows: Assuming all robots have correctly set $r.{\tt
suc}.\mathit{light}$, $\rho.{\tt suc}.\mathit{light}$ for any $\rho\in{\tt
pred}(x)$ contains all colors at location $x$. Let
$r.\mathit{light}.\mathit{here}$ be the set of colors seen at $x$. Note that
this by definition does not include the color of $r.\mathit{light}$, since $r$
is on location $x$ and it cannot see its own light. Now $r$ can calculate the
color of $r.\mathit{light}$ in the following way:

$r.\mathit{light}={\tt pred}(x).{\tt
suc}.\mathit{light}-x.\mathit{light}.\mathit{here}.$

Since the executed flag of robot $r$ contains 2 colors, $r.\mathit{executed}$
can be determined similarly to the case of determining $r.\mathit{light}$ by
using ${\tt pred}(x).{\tt suc}.\mathit{executed}$ instead of ${\tt
pred}(x).{\tt suc}.\mathit{light}$. We can remove the assumption of chirality
by using the method of [19]. Although without chirality a unique circular
ordering of the locations $X(t)$ occupied by the robots cannot be obtained, we
can still define a set of neighboring locations. Instead of having a single
flag $r.{\tt suc}.\mathit{light}$ indicating a single set of colors seen at
${\tt suc}(x)$, every robot has a flag $r.neigh.\mathit{light}$, which is a
pair of sets. One of those sets contains the colors at ${\tt suc}(x)$, and the
other one the colors at ${\tt pred}(x)$. In this way, every robot can still
determine its own color.

The following Lemmas 13, 14 and 15 show that transitions from Step $2$ to Step
$m$, from Step $m$ to Step $2$, and from Step $3$ to Step $1$ work correctly,
respectively due to Lemma 11.

######  Lemma 13.

Assume that step configuration is $same(step=2)$ or $except1(step=2;1)$ and it
holds that $\forall\rho\in R(\rho.\mathit{executed}=\mathit{True})$ at time
$t_{2}$. Then there exists a time $t_{m}>t_{2}$ such that the following (1)
and (2) hold.

  1. (1)

The step configuration at $t_{m}$ is $same(step=m)$ or $except1(step=m;2)$.

  2. (2)

$\forall$ $\rho\in R$($\rho.\mathit{executed}=\mathit{True}$) at time $t_{m}$

######  Lemma 14.

Assume that step configuration is $same(step=m)$ or $except1(step=m;2)$ and it
holds that $\forall\rho\in R(\rho.\mathit{executed}=\mathit{True})$ at time
$t_{m}$ Then there exists a time $t_{2}>t_{m}$ such that the following (1) and
(2) hold.

  1. (1)

The step configuration at $t_{2}$ is $same(step=2)$ or $except1(step=2;m)$.

  2. (2)

$\forall$ $\rho\in R$($\rho.\mathit{executed}=\mathit{False}$) and $(\rho.{\tt
suc}.\mathit{executed}=\\{\mathit{False}\\})$ at time $t_{2}$

######  Lemma 15.

Assume that step configuration is $same(step=3)$ or $except1(step=3;2)$ Then
there exists a time $t_{1}>t_{3}$ such that the following (1)-(3) hold.

  1. (1)

The step configuration at $t_{1}$ is $same(step=1)$ or $except1(step=1;3)$.

  2. (2)

$\forall\rho\in R(\rho.\mathit{color}$ and $\rho.activated$ at $t_{1}$ are the
same as these at $t_{3}$).

  3. (3)

$\forall$ $\rho\in R$( the lights except $\rho.$light and $\rho.$executed are
reset to $\mathit{False}$ at $t_{1}$).

Therefore, remaining is the correctness of the transition from Step $2$ to
Step $3$, including the execution of algorithm A. In Step $2$, if this mega-
cycle is not finished, the step configuration is either ($same(step=2)$ or
$except1(step=2;1)$), or ($same(step=2)$ or $except1(step=2;m)$). We show that
the actual execution of the simulated algorithm A is performed correctly in
Step $2$ if Rsynch is assumed in the following lemma.

######  Lemma 16.

Assume that step configuration is $same(step=2)$ or $except1(step=2;1))$ or
($same(step=2)$ or $except1(step=2;m))$ at time $t_{2}$. If it does not hold
that $\forall\rho\in R(\rho.\mathit{executed}=\mathit{True})$, then there
exists a time $t_{3}>t_{2}$ such that the following (1)-(3) hold. Let
$R_{\mathit{True}}(t)$ be $\\{r|r.\mathit{executed}=\mathit{True}\text{ at
time }t\\}$.

  1. (1)

The step configuration at $t_{3}$ is $same(step=3)$ or $except1(step=3;2)$.

  2. (2)

There exists just one time $t_{a}\in[t_{2},t_{3})$ at which all robots $r$
that are element of the non-empty set $S\subseteq R\setminus
R_{\mathit{True}}(t_{2})$ execute algorithm A.

  3. (3)

$R_{\mathit{True}}(t_{3})=R_{\mathit{True}}(t_{2})\cup S$.

###### Proof.

Let $S_{2}$ be a set of robots activated at $t_{2}$. Note that
$n>|R_{\mathit{True}}(t_{2})|\geq 0$. There are two cases for the step
configuration: (Case 1) $same(\mathit{step}=2)$, and (Case 2)
($except1(\mathit{step}=2;1))$ or $except1(\mathit{step}=2;m))$.

Case 1: The step configuration is $same(\mathit{step}=2)$.

If $S_{2}=R$ (called full activation), full activation must have always
occurred from the starting time to $t_{2}$ because of the definition of
Rsynch. Then, since it holds that $|R_{\mathit{True}}(t_{2})|=0$ and any robot
$r$ in $S_{2}$ observes that $r.\mathit{executed}=\mathit{False}$ (Lemma 14),
$r$ executes algorithm $A$ and sets $r.\mathit{executed}$ and
$r.\mathit{step}$ to $\mathit{True}$ and $3$, respectively. Thus, all robots
activated at the next time $t_{2}+1$ observe some robot $\rho$ with
$\rho.\mathit{step}=3$, and there exists a time $t_{3}$ such that the step
configuration at $t_{3}$ is $all(\mathit{step}=3)$ or
$except1(\mathit{step}=3;2)$ by a similar way as in the proof of Lemma 11.
Setting $t_{a}=t_{2}$, the conditions of the lemma hold.

Otherwise ($S_{2}\subset R$). Some robots in $S_{2}$ have their $execute$ flag
set to $\mathit{True}$, while some have it set to $\mathit{False}$. Let
$\tilde{S_{2}}$ be a set of robots that executed algorithm $A$ at time
$t_{2}$, i.e. the subset of robots from $S_{2}$ that had their $execute$ flag
set to $\mathit{False}$. There are two cases depending on whether
$\tilde{S_{2}}$ is empty or not. If $\tilde{S_{2}}\neq\varnothing$, since the
set of robots activated at $t_{2}+1$ (denoted as $S^{\prime}_{2}$) and $S_{2}$
are disjoint due to Rsynch, all robots in $S^{\prime}_{2}$ observe some robot
$\rho$ with $\rho.\mathit{step}=3$. Now, due to Lemma 11, there exists a time
$t_{3}$ such that the step configuration at $t_{3}$ is $all(\mathit{step}=3)$
or $except1(\mathit{step}=3;2)$. Setting $t_{a}=t_{2}$, the conditions of the
lemma are satisfied.

If $\tilde{S_{2}}=\varnothing$, since the configuration at $t_{2}$ will not be
changed after $t_{2}$ and the scheduler is fair, there exists a time $t>t_{2}$
such that $\tilde{(}S_{t})\neq\varnothing$, where $S_{t}$ is a set of robots
activated at $t$. Then the lemma holds similarly to the former case.

Case 2: The step configuration is $except1(\mathit{step}=2;1))$ or
$except1(\mathit{step}=2;m))$.

Let $r$ be a robot such that $r.\mathit{step}=1$ or $r.\mathit{step}=m$. None
of the robots (except $r$) can execute Step $2$ because they observe $r$ with
$r.\mathit{step}\neq 2$. As long as $r$ is not activated, the configuration is
unchanged. Let $t$ be the first time when $r$ is activated after $t_{2}$ and
let $S_{t}$ be a set of robots activated at $t$. If
$r.\mathit{executed}=\mathit{True}$ at $t$, $r,\mathit{step}$ becomes $2$ and
the step configuration becomes $same(\mathit{step}=2)$. Then, this case is
reduced to Case 1. Otherwise ($r.\mathit{executed}=\mathit{False}$), $r$
executes algorithm $A$ and sets $r.activated$ and $r.\mathit{step}$ to
$\mathit{False}$ and $3$. Note that any robot in $S_{t}\setminus\\{r\\}$
cannot execute Step $2$ at $t$. Setting $t_{a}=t$, the Lemma 11 holds.

∎

By Lemmas 12-16, sim-LUMI-by-FCOM(A) executes Step $1$-Step $3$ and Step $m$
in infinite rounds in Rsynch and the execution of A obeys Ssynch. Let $E$ be
the sequence of the set of activated robots that execute simulated algorithm A
in Algorithm sim-LUMI-by-FCOM(A). Since, by Lemma 16, any mega-cycle is
completed and every robot executes exactly once in every mega-cycle, $E$ is
fair. Then we have obtained Theorem 10. Note that, if algorithm A uses $\ell$
colors, the simulating algorithm sim-LUMI-by-FCOM(A) uses $O(\ell 2^{\ell})$
colors.

Therefore it holds that $\mathcal{FCOM}^{RS}\geq\mathcal{LUMI}^{S}$. Since
$\mathcal{LUMI}^{S}\equiv\mathcal{LUMI}^{RS}$ by Theorem 6, we have that:
$\mathcal{FCOM}^{RS}\geq\mathcal{LUMI}^{RS}$. Moreover, since the reverse
relation is trivial and $\mathcal{FST\\!A}^{RS}<\mathcal{LUMI}^{S}$ (Theorem
4(1)), the next theorem follows.

######  Theorem 11.

$\mathcal{FCOM}^{RS}\equiv\mathcal{LUMI}^{RS}\equiv\mathcal{LUMI}^{S}$, and
$\mathcal{FCOM}^{RS}>\mathcal{FST\\!A}^{RS}>\mathcal{OBLOT}^{RS}$.

###### Proof.

The equality follows from Theorems 6 and 10.
$\mathcal{FCOM}^{RS}>\mathcal{FST\\!A}^{RS}$ follows from that
$\mathcal{LUMI}^{S}\equiv\mathcal{FCOM}^{RS}$ and
$\mathcal{LUMI}^{S}>\mathcal{FST\\!A}^{RS}$ (Theorem 4(1)).
$\mathcal{FST\\!A}^{RS}>\mathcal{OBLOT}^{RS}$ follows from RDV can be solved
in $\mathcal{FST\\!A}^{RS}$ and Lemma 1. ∎

##  6 Concluding Remarks

In this paper, we have started the investigation of the algorithmic and
computational issues arising in distributed systems of autonomous mobile
entities in the Euclidean plane where their energy is limited, albeit
renewable.

We have studied the difference in computational power caused by the energy
restriction, and provided a complete characterization of the computational
difference between energy-restricted and unrestricted robots in all four
models considered in the literature:
$\mathcal{OBLOT},\mathcal{FST\\!A},\mathcal{FCOM},\\\ \mathcal{LUMI}$ (see
Fig. 6). We have also examined the difference with energy-unrestricted robots
operating under a fully-synchronous scheduler (see Fig. 7). Furthermore, we
have studied the impact that memory persistence and communication capabilities
have on the computational power of such energy-constrained systems of robots.
Some of these results have been obtained through the design and analysis of
novel simulators: algorithms that allow a set of robots with a given set of
capabilities to execute correctly any protocol designed for robots with more
powerful capabilities.

The current contribution provides a complete answer to the problems
considered. At the same time, it opens an entirely new research area. Indeed,
many other forms of energy constrains can be considered, and their
computational impact analyzed. In particular, the case considered here, of a
robot consuming all its energy after $p=1$ activity cycles and requiring $q=1$
idle rounds for energy restoration, opens the investigation for $(p,q)$-energy
constrained robots.

Figure 6: Relationship among $\mathcal{LUMI}$, $\mathcal{FCOM}$,
$\mathcal{FST\\!A}$ and $\mathcal{OBLOT}$ in Rsynch and Ssynch assuming
chirality and rigidity, where TAR(d) is defined in [19]. Figure 7:
Relationship among $\mathcal{LUMI}$, $\mathcal{FCOM}$, $\mathcal{FST\\!A}$ and
$\mathcal{OBLOT}$ in Fsynch and Rsynch assuming chirality and rigidity.

## References

  * [1] N. Agmon and D. Peleg.  Fault-tolerant gathering algorithms for autonomous mobile robots.  SIAM Journal on Computing, 36(1):56–82, 2006.
  * [2] H. Ando, Y. Osawa, I. Suzuki, and M. Yamashita.  A distributed memoryless point convergence algorithm for mobile robots with limited visivility.  IEEE Transactions on Robotics and Automation, 15(5):818–828, 1999\.
  * [3] S. Bhagat and K. Mukhopadhyaya.  Optimum algorithm for mutual visibility among asynchronous robots with lights.  In Proc. 19th Int. Symp. on Stabilization, Safety, and Security of Distributed Systems (SSS), pages 341–355, 2017.
  * [4] Z. Bouzid, S. Das, and S. Tixeuil.  Gathering of mobile robots tolerating multiple crash faults.  In the 33rd Int. Conf. on Distributed Computing Systems, pages 334–346, 2013.
  * [5] K. Buchin, P. Flocchini, I. Kostitsyna, T. Peters, N. Santoro, and K. Wada.  Autonomous mobile robots: Refining the computational landscape.  In APDCM 2021, pages 576–585, 2021.
  * [6] D. Canepa and M. Potop-Butucaru.  Stabilizing flocking via leader election in robot networks.  In Proc. 10th Int. Symp. on Stabilization, Safety, and Security of Distributed Systems (SSS), pages 52–66, 2007.
  * [7] S. Cicerone, Di Stefano, and A. Navarra.  Gathering of robots on meeting-points.  Distributed Computing, 31(1):1–50, 2018.
  * [8] M. Cieliebak, P. Flocchini, G. Prencipe, and N. Santoro.  Distributed computing by mobile robots: Gathering.  SIAM Journal on Computing, 41(4):829–879, 2012.
  * [9] R. Cohen and D. Peleg.  Convergence properties of the gravitational algorithms in asynchronous robot systems.  SIAM J. on Computing, 34(15):1516–1528, 2005.
  * [10] S. Das, P. Flocchini, G. Prencipe, N. Santoro, and M. Yamashita.  Autonomous mobile robots with lights.  Theoretical Computer Science, 609:171–184, 2016.
  * [11] X. Défago, M. Potop-Butucaru, and Philippe Raipin-Parvédy.  Self-stabilizing gathering of mobile robots under crash or byzantine faults.  Distributed Computing, 33(5):393–421, 2020.
  * [12] G.A. Di Luna, P. Flocchini, S.G. Chaudhuri, F. Poloni, N. Santoro, and G. Viglietta.  Mutual visibility by luminous robots without collisions.  Information and Computation, 254(3):392–418, 2017.
  * [13] G.A. Di Luna and G. Viglietta.  Robots with lights.  Ch. 11 of [13], pages 252–277, 2019.
  * [14] P. Flocchini, G. Prencipe, and N. Santoro (Eds).  Distributed Computing by Mobile Entities.  Springer, 2019.
  * [15] P. Flocchini, G. Prencipe, and N. Santoro.  Distributed Computing by Oblivious Mobile Robots.  Morgan & Claypool, 2012.
  * [16] P. Flocchini, G. Prencipe, N. Santoro, and P. Widmayer.  Gathering of asynchronous robots with limited visibility.  Theoretical Computer Science, 337(1–3):147–169, 2005.
  * [17] P. Flocchini, G. Prencipe, N. Santoro, and P. Widmayer.  Arbitrary pattern formation by asynchronous oblivious robots.  Theoretical Computer Science, 407:412–447, 2008.
  * [18] P. Flocchini, N. Santoro, G. Viglietta, and M. Yamashita.  Rendezvous with constant memory.  Theoretical Computer Science, 621:57–72, 2016.
  * [19] P. Flocchini, N. Santoro, and K. Wada.  On memory, communication, and synchronous schedulers when moving and computing.  In Proc. 23rd Int. Conference on Principles of Distributed Systems (OPODIS), pages 25:1–25:17, 2019.
  * [20] N. Fujinaga, Y. Yamauchi, H. Ono, S. Kijima, and M. Yamashita.  Pattern formation by oblivious asynchronous mobile robots.  SIAM Journal on Computing, 44(3):740–785, 2015.
  * [21] V. Gervasi and G. Prencipe.  Coordination without communication: The case of the flocking problem.  Discrete Applied Mathematics, 144(3):324–344, 2004.
  * [22] A. Hériban, X. Défago, and S. Tixeuil.  Optimally gathering two robots.  In Proc. 19th Int. Conference on Distributed Computing and Networking (ICDCN), pages 1–10, 2018.
  * [23] T. Izumi, S. Souissi, Y. Katayama, N. Inuzuka, X. Défago, K. Wada, and M. Yamashita.  The gathering problem for two oblivious robots with unreliable compasses.  SIAM Journal on Computing, 41(1):26–46, 2012.
  * [24] T. Okumura, K. Wada, and X. Défago.  Optimal rendezvous $\mathcal{L}$-algorithms for asynchronous mobile robots with external-lights.  In Proc. 22nd Int. Conference on Principles of Distributed Systems (OPODIS), pages 24:1–24:16, 2018.
  * [25] T. Okumura, K. Wada, and Y. Katayama.  Brief announcement: Optimal asynchronous rendezvous for mobile robots with lights.  In Proc. 19th Int. Symp. on Stabilization, Safety, and Security of Distributed Systems (SSS), pages 484–488, 2017.
  * [26] G. Sharma, R. Alsaedi, C. Bush, and S. Mukhopadyay.  The complete visibility problem for fat robots with lights.  In Proc. 19th Int. Conference on Distributed Computing and Networking (ICDCN), pages 21:1–21:4, 2018.
  * [27] G. Sharma, R. Vaidyanathan, C. Bush, S. Rai, and B. Borzoo.  Complete visibility for robots with lights in $o(1)$ time.  In Proc. 18th Int. Symp. on Stabilization, Safety, and Security of Distributed Systems (SSS), pages 327–345, 2016.
  * [28] H. Sharma, H. Ahteshamul, and J. Zainul A.  Solar energy harvesting wireless sensor network nodes: A survey.  Journal of Renewable and Sustainable Energy, 10(2):023704, 2018\.
  * [29] S. Souissi, T. Izumi, and K. Wada.  Oracle-based flocking of mobile robots in crash-recovery model.  In Proc. 11th Int. Symp. on Stabilization, Safety, and Security of Distributed Systems (SSS), pages 683–697, 2009.
  * [30] I. Suzuki and M. Yamashita.  Distributed anonymous mobile robots: Formation of geometric patterns.  SIAM Journal on Computing, 28:1347–1363, 1999.
  * [31] S. Terai, K. Wada, and Y. Katayama.  Gathering problems for autonomous mobile robots with lights.  arXiv.org, cs(ArXiv:1811.12068), 2018.
  * [32] G. Viglietta.  Rendezvous of two robots with visible bits.  In 10th Int. Symp. on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics (ALGOSENSORS), pages 291–306, 2013.
  * [33] M. Yamashita and I. Suzuki.  Characterizing geometric patterns formable by oblivious anonymous mobile robots.  Theoretical Computer Science, 411(26–28):2433–2453, 2010.
  * [34] Y. Yamauchi, T. Uehara, S. Kijima, and M. Yamashita.  Plane formation by synchronous mobile robots in the three-dimensional euclidean space.  J. ACM, 64:3(16):16:1–16:43, 2017.