A Characterization of Semi-Synchrony for Asynchronous Robots with Limited Visibility, and its Application to Luminous Synchronizer Design

Paola Flocchini University of Ottawa, Canada. E-mail: [email protected] Nicola Santoro Carleton University, Canada. E-mail. [email protected] Masafumi Yamashita Kyushu University, Japan. E-mail. [email protected] Yukiko Yamauchi Kyushu University, Japan. E-mail. [email protected]

Abstract

A mobile robot system consists of anonymous mobile robots, each of which autonomously performs sensing, computation, and movement according to a common algorithm, so that the robots collectively achieve a given task. There are two main models of time and activation of the robots. In the semi-synchronous model (SSYNC), the robots share a common notion of time; at each time unit, a subset of the robots is activated, and each performs all three actions (sensing, computation, and movement) in that time unit. In the asynchronous model (ASYNC), there is no common notion of time, the robots are activated at arbitrary times, and the duration of each action is arbitrary but finite.

In this paper, we investigate the problem of synchronizing ASNYC robots with limited sensing range, i.e., limited visibility. We first present a sufficient condition for an ASYNC execution of a common algorithm $\mathcal{A}$ to have a corresponding SSYNC execution of $\mathcal{A}$ ; our condition imposes timing constraints on the activation schedule of the robots and visibility constraints during movement. Then, we prove that this condition is necessary (with probability $1$ ) under a randomized ASYNC adversary. Finally, we present a synchronization algorithm for luminous ASYNC robots with limited visibility, each equipped with a light that can take a constant number of colors. Our algorithm enables luminous ASYNC robots to simulate any algorithm $\mathcal{A}$ , designed for the (non-luminous) SSYNC robots and satisfying visibility constraints.

Keywords. mobile robots, synchronization, limited visibility, light.

1 Introduction

Distributed computing by mobile computing entities has attracted much attention in the past two decades and many distributed system models have been considered, for example, the autonomous mobile robot system [17] modeled after cheap hardware robots with very weak capabilities, the population protocol model [1] motivated by delay tolerant networks, the programmable particle model [4] inspired by movement of amoebae, and the metamorphic robotic system [9, 10] considering modular robots. The computational power of these distributed systems has been investigated in distributed computing theory and many fundamental problems have been proposed that require a degree of agreement among the mobile computing entities. Typical problems are leader election [5, 8], which requires the entities to agree on a single entity, gathering [2, 11, 17], which requires the entities to gather at a point not known apriori, and shape formation [7, 9, 15, 17, 19, 20] (also called the transformability problem), which requires the entities to form a specified shape. These results are considered as theoretical foundations in several related areas like ad-hoc networks, sensor networks, robotics, molecular computing, chemical reaction circuits, and so on.

In this paper, we focus on the autonomous mobile robot system. Let $\mathcal{R}=\{r_{1},r_{2},\ldots,r_{n}\}$ be a set of $n$ robots. Each robot is an anonymous (indistinguishable) point moving in the 2D space. The robots are silent (communication-less) and do not have access to a global coordinate system. A robot’s behavior is a repetition of Look-Compute-Move cycles: in the Look phase, it observes the positions of the other robots within its visibility range; in the Compute phase, it computes its next position and a continuous route to the next position with a common deterministic algorithm; in the Move phase, it moves to the computed position along the computed route. The essential properties of mobile robot systems are the visibility range, obliviousness, and the timing and activation models. A robot $r_{i}$ is equipped with its own local coordinate system $\mathcal{Z}_{i}$ , which is a right-handed $x$ - $y$ coordinate system. The origin of $\mathcal{Z}_{i}$ is always the current position of $r_{i}$ , while the unit distance and the directions and orientations of the $x$ and $y$ axes are arbitrary. The observation at $r_{i}$ is a snapshot in $\mathcal{Z}_{i}$ containing no additional information other than the positions of the robots. If the visibility range of a robot is unlimited, it can observe all robots, otherwise it can observe the robots within its visibility. In Compute, when the input to the common algorithm is the snapshot taken in the preceding Look, we say the robots are oblivious. When the input includes past observations and computations, we say the robots are non-oblivious. In Move, the movement of a robot is rigid when the robot always reaches the next position, and non-rigid when the robot may stop en route after moving a minimum distance $\delta$ (in $\mathcal{Z}_{0}$ ) (if the length of the route to the destination is smaller than $\delta$ , the destination is reached).

Three different types of timing and activation models have been proposed: In the fully-synchronous model (FSYNC), at each discrete time $t=0,1,2,\ldots$ , all robots execute a Look-Compute-Move cycle with each of the Look, Compute, and Move completely synchronized. In the semi-synchronous model (SSYNC), at each discrete time $t=0,1,2,\ldots$ , a non-empty subset of robots are activated and execute a Look-Compute-Move cycle with each of the Look, Compute, and Move completely synchronized. For fairness, we assume that each robot executes infinitely many cycles. In the asynchronous model (ASYNC), the robots do not have a common notion of time and the length of each cycle is arbitrary but finite. We also assume fairness in ASYNC. The main difference between SSYNC (thus, FSYNC) and ASYNC is that in SSYNC, all robots simultaneously take a snapshot in Look, while in ASYNC a robot may observe moving robots although the robot cannot recognize which robots are moving.

The effect of obliviousness, asynchrony, and visibility on the computational power of autonomous mobile robot systems has been extensively investigated [8, 12, 15, 17, 19]. Since the only output by the oblivious robots is their geometric positions, a fundamental problem is the pattern formation problem, that requires the robots to form a target pattern from an initial configuration. Existing literature [15, 17, 19]¹¹1 An erratum of [15] is available at [16]. showed that the initial symmetry among the anonymous robots determines the set of formable patterns, irrespective of obliviousness and asynchrony. The only exception is the point formation problem of two robots, also called the rendezvous problem. In fact, Suzuki and Yamashita have shown that the rendezvous problem is solved by oblivious FSYNC robots, but cannot be solved by oblivious SSYNC robots [17]. In other words, the rendezvous problem demonstrates the difference between FSYNC and SSYNC (thus, ASYNC). These results consider the robots with unlimited visibility. Yamauchi and Yamashita have shown that limited visibility substantially shrinks the set of formable patterns by oblivious ASYNC robots because the robots do not know their global symmetry [20].

The robots can overcome the limits by distributed coordination or additional capabilities. Di Luna et al. have shown that a constant number of oblivious ASYNC robots can simulate a single non-oblivious ASYNC robot by encoding the memory contents to the geometric positions of the robots [6]. Das et al. have shown that oblivious ASYNC robots with lights can simulate oblivious SSYNC robots [3]. A luminous robot is equipped with a light whose color is changed in every Look-Compute-Move cycle at the end of Compute and observed by other robots. The authors showed that luminous ASYNC robots with a constant number of colors can simulate an algorithm $\mathcal{A}$ designed for oblivious SSYNC robots. They presented a synchronizer that makes an activated robot accept or reject the current cycle so that the snapshot of an accepted cycle does not contain any moving robot. In an accepted cycle, the robot changes the color of its light to “moving” and moves to the next position computed by $\mathcal{A}$ . The synchronizer guarantees fairness by making all robots wait with the “waiting” color after it accepts a cycle until all the other robots accept a cycle. All these techniques are heavily based on the fact that robots have unlimited visibility.

In this paper, we investigate synchronization by oblivious ASYNC robots with limited visibility and we make some fundamental contributions.

We start with a formal definition of simulation by mobile robots. A configuration is the set of positions of the robots in $\mathcal{Z}_{0}$ and an execution of algorithm $\mathcal{A}$ from an initial configuration $I$ is an infinite sequence of configurations. In SSYNC, an execution is a sequence of configurations $C_{0}(=I),C_{1},C_{2},\ldots$ , where $C_{t}$ is the configuration at time $t$ . An ASYNC execution is the sequence of configurations $C_{t_{0}}(=I),C_{t_{1}},C_{t_{2}},\ldots$ where at least one robot takes a snapshot, with $t_{i}<t_{i+1}$ for all $i=1,2,\ldots$ . Then, the footprint of a robot is the sequence of the positions of the robot in each configuration. We say that two executions $E$ and $E^{\prime}$ (possibly in different timing and activation models) are similar when the footprints and local observations at the robots are identical.

We then present a sufficient condition for an ASYNC execution to have a similar SSYNC execution, and we also show that the condition is necessary with probability $1$ under a randomized ASYNC adversary. The randomized impossibility result is novel, based on a Borel probability measure space for non-rigid movement and asynchronous observations, and it provides a stronger argument than a worst-case (deterministic) analysis. Our condition not only requires snapshots of static robots but also considers a chain of concurrent observations, that cannot be treated separately in a SSYNC execution. The transitive closure with respect to the concurrent observations forms an equivalence relation and cycles of the ASYNC execution are decomposed into equivalence classes. We then introduce a “happened-before” relation among the equivalence classes based on the local happened-before relation at a single robot or a pair of visible robots. Our condition also requires the happened-before relation to form a directed acyclic graph so that we construct a similar SSYNC execution by applying the equivalence classes one by one in the order of one of their topological sort.

We then present a synchronizer for oblivious ASYNC luminous robots to simulate an execution of an algorithm for oblivious (non- luminous) SSYNC robots satisfying those conditions, as well as some limitations of synchronizers that make use of visible lights.

Related work. Existing literature established a rich class of distributed problems for mobile robot systems. The pattern formation problem [17] is one of the most important static problems, that is, the robots stop moving once they reach a terminal configuration. Suzuki and Yamashita showed the oblivious FSYNC robots can solve the rendezvous problem, while the oblivious SSYNC robots cannot [17]. Flocchini et al. further discussed the rendezvous problem to show the power of lights. A robot with externally visible light can change but cannot see the color of its own light, while the other robots can observe it. A robot with internally visible light can change and see the color of its own light, while the other robots cannot observe it. They showed that the ASYNC robots with externally visible lights can solve the rendezvous problem, while the SSYNC robots with internally visible lights cannot [13]. To demonstrate computational power of the luminous robots, many dynamic problems has been proposed. Das et al. proposed the oscillating points problem, that requires the robots to alternately come closer and go farther from each other [3]. This problem shows the difference between luminous ASYNC robots and (non-luminous) FSYNC robots. Flocchini et al. examined the power of internally visible lights and that of externally visible lights in FSYNC and SSYNC with a variety of static problems such as triangle rotation, center of gravity expansion, and dynamic problems such as the perpetual center of gravity expansion and shrinking rotation [14].

Synchronization was first presented in [3] to overcome the limit of the ASYNC robots with unlimited visibility. In this paper, we further investigate synchronization to demonstrate the difference between ASYNC and SSYNC with limited visibility.

Organization. We provide detailed definitions of ASYNC and SSYNC executions and the similarity between two executions in Section 2. We then provide a sufficient condition for an ASYNC execution to have a similar SSYNC execution, and investigate its necessity under a randomized ASYNC adversary in Section 3. Section 4 provides a synchronizer algorithm for oblivious luminous ASYNC robots that satisfy the necessary and sufficient conditions. We conclude our paper in Section 5.

2 Preliminary

We investigate a system $\mathcal{R}$ of $n$ anonymous oblivious mobile robots $\{r_{1},r_{2},\ldots,r_{n}\}$ in the 2D space. We use $r_{i}$ just for notation. We assume that at most one robot can occupy any given position at any time.²²2 We can remove this assumption with multiplicity detection capability.

We consider SSYNC and ASYNC as the semi-synchronous scheduler $\cal{SSYNC}$ and the asynchronous scheduler $\cal{ASYNC}$ , respectively. We regard a scheduler as a set of schedules that it can produce. Consider an infinite execution $E$ of a deterministic algorithm $\mathcal{A}$ from an initial configuration $I$ under $\cal{ASYNC}$ . Independently of $\mathcal{A}$ and $I$ ,³³3 Thus, $ASYNC$ produces any schedule including the worst-case schedule for $\mathcal{A}$ and $I$ . $\cal{ASYNC}$ nondeterministically produces a schedule $\Omega$ , which specifies for each $r_{i}$ when it is activated and executes Look-Compute-Move cycles.

Formally, $\Omega$ is a set of schedules $\Omega_{i}$ for each robot $r_{i}$ , where $\Omega_{i}$ is an infinite sequence of Look-Compute-Move cycles. The $j$ th cycle $\omega_{i}(j)$ of $\Omega_{i}$ is denoted by a triple $(o_{i}(j),s_{i}(j),f_{i}(j))$ , where $o_{i}(j)$ , $s_{i}(j)$ , and $f_{i}(j)$ are the time instants that $r_{i}$ takes a snapshot in the Look, starts and ends the Move, respectively. We assume that the time interval assigned to $\omega_{i}(j)$ is $[o_{i}(j),f_{i}(j)]$ , and $o_{i}(j)<s_{i}(j)<f_{i}(j)<o_{i}(j+1)$ for all $j=1,2,\ldots$ . Scheduler $\Omega$ is fair in the sense that each $\Omega_{i}$ satisfies that, for any $t\in\mathbf{R}^{+}$ , there is a $j\in\mathbf{N}$ such that $o_{i}(j)>t$ , where $\mathbf{R}^{+}$ and $\mathbf{N}$ are the sets of positive real numbers and non-negative integers, respectively. The execution is not uniquely determined by $I$ , $\mathcal{A}$ , and $\Omega$ , due to the only source of non-determinism, that is, non-rigid movement of robots. The set of possible executions of $\mathcal{R}$ given $I$ , $\mathcal{A}$ , and $\Omega$ is denoted by $\mathcal{E}(\Omega,\mathcal{A},I)$ .

The visibility range of each robot is the unit distance of the global coordinate system $\mathcal{Z}_{0}$ .⁴⁴4The common visibility range does not promise common unit distance among the robots. The snapshot $P_{i}(j)$ taken by $r_{i}$ at $o_{i}(j)$ in $\omega_{i}(j)$ is the set of positions of robots in $\mathcal{Z}_{i}$ visible from $r_{i}$ at $o_{i}(j)$ . $P_{i}(j)$ always contains its origin, because it is the position of $r_{i}$ in $\mathcal{Z}_{i}$ . The number of robots visible from $r_{i}$ at $o_{i}(i)$ is denoted by $|P_{i}(j)|$ . Let $P_{i}(E)=\{P_{i}(j)\mid j\in{\mathbf{N}}\}$ and $P(E)=\{P_{i}(E)\mid r_{i}\in\mathcal{R}\}$ .

The position of $r_{i}$ at $o_{i}(j)$ in the global coordinate system $\mathcal{Z}_{0}$ is denoted by $\pi_{i}(j)$ . Note that $r_{i}$ cannot recognize its position $\pi_{i}(j)$ . The footprint of $r_{i}$ in $E$ is $\Pi_{i}(E)=\{\pi_{i}(j)\mid j\in{\mathbf{N}}\}$ and let $\Pi(E)=\{\Pi_{i}(E)\mid r_{i}\in\mathcal{R}\}$ be the set of footprints of all robots of $\mathcal{R}$ . Since the system is not rigid, $\pi_{i}(j+1)$ is not uniquely determined by $\pi_{i}(j)$ , $P_{i}(j)$ , $\mathcal{Z}_{i}$ , $\mathcal{A}$ , and $I$ .

Let $E\in\mathcal{E}(\Omega,\mathcal{A},I)$ and $\tilde{E}\in\mathcal{E}(\tilde{\Omega},\mathcal{A},I)$ . If the system is rigid, $\Pi(E)=\Pi(\tilde{E})$ if $P(E)=P(\tilde{E})$ . Otherwise, for some $\Omega$ , $\mathcal{A}$ , and $I$ , there are executions $E,\tilde{E}\in\mathcal{E}(\Omega,\mathcal{A},I)$ such that $P(E)=P(\tilde{E})$ and $\Pi(E)\neq\Pi(\tilde{E})$ .

Example 1

When $n=1$ , no matter where $r_{1}$ goes, $P_{1}(j)=\{(0,0)\}$ . When $n=2$ , suppose that $r_{1}$ and $r_{2}$ are initially at $(0,0)$ and $(0,1)$ , respectively, and synchronously move in parallel along the $x$ -axis of $\mathcal{Z}_{0}$ at the same speed. As long as their tracks are truncated at the same $x$ -coordinate, independently of where they are truncated, $P_{i}(j)=P_{i}(j^{\prime})$ for all $i\in\{1,2\}$ and $i,j^{\prime}\in\mathbf{N}$ .

We say two executions $E\in\mathcal{E}(\Omega,\mathcal{A},I)$ and $\tilde{E}\in\mathcal{E}(\Omega,\mathcal{A},I)$ are similar, denoted by $E\sim\tilde{E}$ , if $P(E)=P(\tilde{E})$ and $\Pi(E)=\Pi(\tilde{E})$ .

Without loss of generality, we assume that $\cal{SSYNC}$ produces a schedule $\Omega$ such that every cycle $\omega_{i}(j)$ has a form $(t,t+1/4,t+3/4)$ for some $t\in\mathbf{N}$ .

3 ASYNC execution with a similar SSYNC execution

We provide a necessary and sufficient condition for an ASYNC execution $E\in\mathcal{E}(\Omega,\mathcal{A},I)$ to have an SSYNC execution $\tilde{E}\in\mathcal{E}(\tilde{\Omega},\mathcal{A},I)$ such that $P(E)=P(\tilde{E})$ and $\Pi(E)=\Pi(\tilde{E})$ for some $\tilde{\Omega}\in\cal{SSYNC}$ .

3.1 Sufficiency

In an SSYNC execution, at each discrete time $t=0,1,2,\ldots$ the activated robots execute a Look-Compute-Move cycle with each of the three phases completely synchronized. From this definition, we directly obtain the following three assumptions on an ASYNC execution to have a corresponding SSYNC execution. (i) No robot observes other robots moving. (ii) When two robots observe each other, they are activated at the same time in a SSYNC execution. (iii) Due to limited visibility, the above “mutually observed” relationship is transitive. We formally describe these assumptions.

Let $S_{i}(j)$ be the set of robots visible from $r_{i}$ at time $o_{i}(j)$ . Then, $|S_{i}(j)|=|P_{i}(j)|$ and $r_{i}\in S_{i}(j)$ . Recall that $r_{i}$ cannot recognize the correspondence between $S_{i}(j)$ and $P_{i}(j)$ . We say that $E$ is stationary, if every snapshot $P_{i}(j)$ in $E$ is “stationary” in the sense that $r_{i}$ does not observe another robot $r_{i^{\prime}}$ in its move phase. Formally, $E\in\mathcal{E}(\Omega,\mathcal{A},I)$ is stationary if $o_{i}(j)\not\in(s_{i^{\prime}}(j^{\prime}),f_{i^{\prime}}(j^{\prime}))$ holds for any pair of cycles $\omega_{i}(j)$ and $\omega_{i^{\prime}}(j^{\prime})\in\Omega$ such that $r_{i^{\prime}}\in S_{i}(j)$ .⁵⁵5We exclude $s_{i^{\prime}}(j^{\prime})$ and $f_{i^{\prime}}(j^{\prime})$ , because $r_{i^{\prime}}$ is not moving at these time instants.

Assumption 1

We assume that $E$ is stationary.

Let $\omega_{i}(j)$ and $\omega_{i^{\prime}}(j^{\prime})\in\Omega$ be two cycles such that $i\neq i^{\prime}$ and $o_{i}(j)\leq o_{i^{\prime}}(j^{\prime})$ . If $[o_{i}(j),f_{i}(j)]\cap[o_{i^{\prime}}(j^{\prime}),f_{i^{\prime}}(j^{\prime})]\neq\emptyset$ and $r_{i}\in S_{i^{\prime}}(j^{\prime})$ , we say that $\omega_{i}(j)$ and $\omega_{i^{\prime}}(j^{\prime})$ overlap each other.

We say $\omega_{i}(j)$ and $\omega_{i^{\prime}}(j^{\prime})$ are concurrent, denoted by $\omega_{i}(j)\parallel\omega_{i^{\prime}}(j^{\prime})$ , if one of the following conditions holds:

1.

$i=i^{\prime}$ and $j=j^{\prime}$ .
2.

$i\neq i^{\prime}$ , $o_{i}(j)\in(f_{i^{\prime}}(j^{\prime}-1),o_{i^{\prime}}(j^{\prime})]$ , $o_{i^{\prime}}(j^{\prime})\in[o_{i}(j),s_{i}(j)]$ , and $r_{i^{\prime}}\in S_{i}(j)$ (thus, $r_{i}\in S_{i^{\prime}}(j^{\prime})$ ).
3.

$i\neq i^{\prime}$ , $o_{i^{\prime}}(j^{\prime})\in(f_{i}(j-1),o_{i}(j)]$ , $o_{i}(j)\in[o_{i^{\prime}}(j^{\prime}),s_{i^{\prime}}(j^{\prime})]$ , and $r_{i}\in S_{i^{\prime}}(j^{\prime})$ (thus, $r_{i^{\prime}}\in S_{i}(j)$ ).

The concurrency relation $\parallel$ is symmetric and reflexive, but is not always transitive. By definition, we have the following proposition.

Proposition 1

For any $i$ , $j$ , and $j^{\prime}$ , $\omega_{i}(j)\parallel\omega_{i}(j^{\prime})$ if and only if $j=j^{\prime}$ .

If $i\neq i^{\prime}$ and $\omega_{i}(j)$ and $\omega_{i^{\prime}}(j^{\prime})$ are concurrent, then they overlap each other. Moreover, both $r_{i}$ and $r_{j}$ observe each other in $\omega_{i}(j)$ and $\omega_{i^{\prime}}(j^{\prime})$ , respectively. If $\omega_{i}(j)$ and $\omega_{i^{\prime}}(j^{\prime})$ overlap each other, the two robots do not always observe each other. However, at least one of them observes the other.

We say that $E$ is pairwise aligned, if two cycles $\omega_{i}(j)$ and $\omega_{i^{\prime}}(j^{\prime})$ that overlap each other are always concurrent.

Assumption 2

We assume that $E$ is pairwise aligned.

Let $\stackrel{{\scriptstyle*}}{{\parallel}}$ be the transitive closure of $\parallel$ , that is an equivalence relation on $\Omega$ . We abuse the term so that $\omega_{i}(j)$ and $\omega_{i^{\prime}}(j^{\prime})$ are concurrent if $\omega_{i}(j)\stackrel{{\scriptstyle*}}{{\parallel}}\omega_{i^{\prime}}(j^{\prime})$ . Since $\parallel$ is not always transitive, $\parallel\neq\stackrel{{\scriptstyle*}}{{\parallel}}$ may hold. Let $\Omega=\Omega_{0},\Omega_{1},\Omega_{2},\ldots$ be the equivalence class partition of $\Omega$ with respect to $\stackrel{{\scriptstyle*}}{{\parallel}}$ . Intuitively, the cycles in each $\Omega_{i}$ must be executed at the same time in the corresponding SSYNC execution. However, because $\stackrel{{\scriptstyle*}}{{\parallel}}$ is transitive, we need to consider observations, i.e., $S_{i}(j)$ and $S_{i^{\prime}}(j^{\prime})$ for each $\omega_{i}(j),\omega_{i^{\prime}}(j^{\prime})\in\Omega_{i}$ .

Let $dist(p,q)$ denote the Euclidean distance between two points $p$ and $q$ in $\mathcal{Z}_{0}$ . We say that $E$ is consistent, if the following conditions hold for any pair of cycles $\omega_{i}(j)$ and $\omega_{i^{\prime}}(j^{\prime})$ such that $\omega_{i}(j)\stackrel{{\scriptstyle*}}{{\parallel}}\omega_{i^{\prime}}(j^{\prime})$ :

1.

$r_{i^{\prime}}\in S_{i}(j)$ if and only if $r_{i}\in S_{i^{\prime}}(j^{\prime})$ .
2.

If $r_{i^{\prime}}\in S_{i}(j)$ , or equivalently $r_{i}\in S_{i^{\prime}}(j^{\prime})$ , $\omega_{i}(j)\parallel\omega_{i^{\prime}}(j^{\prime})$ .
3.

If $r_{i^{\prime}}\not\in S_{i}(j)$ , or equivalently $r_{i}\not\in S_{i^{\prime}}(j^{\prime})$ , $dist(\pi_{i}(j),\pi_{i^{\prime}}(j^{\prime}))>1$ .

Assumption 3

We assume that $E$ is consistent.

The following proposition is an extension of Proposition 1.

Proposition 2

Suppose that $E$ is stationary, pairwise aligned, and consistent. For any $i$ , $j$ , and $j^{\prime}$ , $\omega_{i}(j)\stackrel{{\scriptstyle*}}{{\parallel}}\omega_{i}(j^{\prime})$ if and only if $j=j^{\prime}$ .

Proof. If $j=j^{\prime}$ , $\omega_{i}(j)\stackrel{{\scriptstyle*}}{{\parallel}}\omega_{i}(j^{\prime})$ for any $i$ . Otherwise, suppose that $\omega_{i}(j)\stackrel{{\scriptstyle*}}{{\parallel}}\omega_{i}(j^{\prime})$ holds. Since $r_{i}\in S_{i}(j^{\prime})$ for any $i$ and $j^{\prime}$ , $\omega_{i}(j)\parallel\omega_{i}(j^{\prime})$ by the consistency, which is a contradiction by Proposition 1. Thus, if $j\neq j^{\prime}$ , then $\omega_{i}(j)\not\stackrel{{\scriptstyle*}}{{\parallel}}\omega_{i}(j^{\prime})$ . $\Box$

Let $\omega_{i}(j),\omega_{i^{\prime}}(j^{\prime})\in\Omega$ be two cycles. We say that $\omega_{i}(j)$ happens immediately before $\omega_{i^{\prime}}(j^{\prime})$ , denoted by $\omega_{i}(j)\rightarrow\omega_{i^{\prime}}(j^{\prime})$ , if one of the following conditions holds:

1.

$i^{\prime}=i$ and $j^{\prime}=j+1$ .
2.

$i^{\prime}\neq i$ , $r_{i}\in S_{i^{\prime}}(j^{\prime})$ and $o_{i^{\prime}}(j^{\prime})\in(f_{i}(j),s_{i}(j+1)]$ .
3.

$i^{\prime}\neq i$ , $r_{i^{\prime}}\in S_{i}(j)$ and $f_{i^{\prime}}(j^{\prime}-1)<o_{i}(j)<f_{i}(j)<o_{i^{\prime}}(j^{\prime})$ .

We may call $\rightarrow$ a “happened-before” relation on $\Omega$ , because $\omega_{i}(j)\rightarrow\omega_{i^{\prime}}(j^{\prime})$ denotes the fact that $\omega_{i}(j)$ happens before $\omega_{i^{\prime}}(j^{\prime})$ . Thus, $\rightarrow$ is neither reflexive nor symmetric. It is worth emphasizing that in general, $\rightarrow$ is not transitive either, because it is defined based on the visibility relation between robots like $\parallel$ .

Note that if $\omega_{i}(j)\rightarrow\omega_{i^{\prime}}(j^{\prime})$ , then $\omega_{i}(j)\not\parallel\omega_{i^{\prime}}(j^{\prime})$ , because they do not overlap each other. Note also that either $r_{i}\in S_{i^{\prime}}(j^{\prime})$ or $r_{i^{\prime}}\in S_{i}(j)$ holds, but generally not both.

Proposition 3

Suppose that $E$ is stationary, pairwise aligned, and consistent. No equivalence class $\Omega_{k}$ of $\Omega$ contains cycles $\omega_{i}(j)$ and $\omega_{i^{\prime}}(j^{\prime})$ such that $\omega_{i}(j)\rightarrow\omega_{i^{\prime}}(j^{\prime})$ .

Proof. Let $\omega_{i}(j)$ and $\omega_{i^{\prime}}(j^{\prime})$ be any cycles in $\Omega_{k}$ , i.e., $\omega_{i}(j)\stackrel{{\scriptstyle*}}{{\parallel}}\omega_{i^{\prime}}(j^{\prime})$ . We assume that $\omega_{i}(j)\rightarrow\omega_{i^{\prime}}(j^{\prime})$ .

If $i^{\prime}=i$ , then $j^{\prime}=j$ by Proposition 2, which is a contradiction. Thus, $i^{\prime}\neq i$ . Since $\omega_{i}(j)\rightarrow\omega_{i^{\prime}}(j^{\prime})$ , either $r_{i}\in S_{i^{\prime}}(j^{\prime})$ or $r_{i^{\prime}}\in S_{i}(j)$ holds. This implies $\omega_{i}(j)\parallel\omega_{i^{\prime}}(j^{\prime})$ by the consistency. This is a contradiction. $\Box$

Let $\Omega_{k}$ and $\Omega_{k^{\prime}}$ be two equivalence classes of $\Omega$ . If there are cycles $\omega_{i}(j)\in\Omega_{k}$ and $\omega_{i^{\prime}}(j^{\prime})\in\Omega_{k^{\prime}}$ such that $\omega_{i}(j)\rightarrow\omega_{i^{\prime}}(j^{\prime})$ , we use the notation $\Omega_{k}\Rightarrow\Omega_{k^{\prime}}$ . By Proposition 3, binary relation $\Rightarrow$ is not reflexive. We say that $E$ is serializable if the infinite graph $\mathcal{G}=(\{\Omega_{0},\Omega_{1},\Omega_{2},\ldots\},\Rightarrow)$ is acyclic.

Assumption 4

We assume that $E$ is serializable.

While $\rightarrow$ can be considered as a “happened-before” relation on cycles, it is not adequate to consider $\Rightarrow$ as a “happened-before” relation on the equivalence classes. There can be cycles $\omega_{i}(j)\in\Omega_{k}$ and $\omega_{i^{\prime}}(j^{\prime})\in\Omega_{k^{\prime}}$ such that $f_{i^{\prime}}(j^{\prime})<o_{i}(j)$ even if $\Omega_{k}\Rightarrow\Omega_{k^{\prime}}$ . In fact, $\Omega_{k}\Rightarrow\Omega_{k^{\prime}}$ and $\Omega_{k}\Leftarrow\Omega_{k^{\prime}}$ may hold at the same time. There is a stationary, pairwise aligned, and consistent execution which is not serializable.

The following proposition is clear by definition.

Proposition 4

Suppose that $E$ is stationary, pairwise aligned, consistent, and serializable. If $\omega_{i}(j)$ and $\omega_{i}(j^{\prime})$ are in an equivalence class $\Omega_{k}$ for some $i$ , $j$ , and $j^{\prime}$ , then $j=j^{\prime}$ . That is, each $\Omega_{k}$ contains at most one cycle for every robot $r_{i}$ .

Let $E\in\mathcal{E}(\Omega,\mathcal{A},I)$ be an execution of algorithm $\mathcal{A}$ from initial configuration $I$ under a schedule $\Omega\in\cal{ASYNC}$ and assume that $E$ is stationary, pairwise aligned, consistent, and serializable. Let $\mathcal{G}=(\{\Omega_{0},\Omega_{1},\Omega_{2},\ldots\},\Rightarrow)$ be the acyclic graph obtained from $E$ . Without loss of generality, let $T=(\Omega_{0},\Omega_{1},\Omega_{2},\ldots)$ be a topological sort of $\mathcal{G}$ . Let $A_{k}=\{r_{i}\mid\omega_{i}(j)\in\Omega_{k}\ \text{for some $j$}\}$ , keeping in mind that $\omega_{i}(j)$ is unique for each $r_{i}\in A_{k}$ by Proposition 4.

We construct a schedule $\tilde{\Omega}\in\cal{SSYNC}$ from $T$ . Intuitively, $\tilde{\Omega}$ activates all robots in $A_{k}$ at time $k$ for all $k\in\mathbf{N}$ . Formally, $\tilde{\Omega}=\{\tilde{\omega}_{i}(j)\mid i=1,2,\ldots,n,\ j\in\mathbf{N}\}$ , where $\tilde{\omega}_{i}(j)=(\tilde{o}_{i}(j),\tilde{s}_{i}(j),\tilde{f}_{i}(j))=(k,k+1/4,k+3/4)$ if $\omega_{i}(j)\in\Omega_{k}$ for $k\in\mathbf{N}$ . Obviously, $\tilde{\Omega}$ is well-defined and $\tilde{\Omega}\in\cal{SSYNC}$ .

Consider $\tilde{E}\in\mathcal{E}(\tilde{\Omega},\mathcal{A},I)$ . Let $\tilde{S}_{i}(j)$ and $\tilde{P}_{i}(j)$ be the set of robots visible from $r_{i}$ at $\tilde{o}_{i}(j)$ and the snapshot that $r_{i}$ takes at $\tilde{o}_{i}(j)$ , respectively. Then, $P(\tilde{E})=\{\tilde{P}_{i}(j)\mid i=1,2,\ldots,n,\ \text{and}\ j\in\mathbf{N}\}$ . Let $\tilde{\pi}_{i}(j)$ be the position of $r_{i}$ in $\mathcal{Z}_{0}$ at $\tilde{o}_{i}(j)$ . Then, $\Pi(\tilde{E})=\{\tilde{\pi}_{i}(j)\mid i=1,2,\ldots,n,\ \text{and}\ j\in{\mathbf{N}}\}$ .

Finally, we need to examine each pair of cycles $\omega_{i}(j)$ and $\omega_{i^{\prime}}(j^{\prime})$ assigned to different discrete time in $\tilde{\Omega}$ . Thus, $\omega_{i}(j)\not\stackrel{{\scriptstyle*}}{{\parallel}}\omega_{i^{\prime}}(j^{\prime})$ . Consider the case where $\omega_{i}(j)\in\Omega_{k}$ and $\omega_{i^{\prime}}(j^{\prime})\in\Omega_{k^{\prime\prime}}$ for $k<k^{\prime\prime}$ and $r_{i^{\prime}}$ executes no cycle during $\Omega_{k},\Omega_{k+1},\ldots,\Omega_{k^{\prime\prime}-1}$ . Thus, $r_{i^{\prime}}$ does not move during the time period $[k,k^{\prime\prime}-1]$ in $\tilde{\Omega}$ . If $r_{i}$ observes $r_{i^{\prime}}$ in $\omega_{i}(j)$ , $\omega_{i}(j)$ and $\omega_{i^{\prime}}(j^{\prime})$ do not overlap each other. Otherwise, $\Omega_{k}$ contains $\omega_{i^{\prime}}(j^{\prime})$ . If $r_{i}$ does not observe $r_{i^{\prime}}$ in $\omega_{i}(j)$ , $dist(\pi_{i}(j),\pi_{i^{\prime}}(j^{\prime}))>1$ . Otherwise, $r_{i^{\prime}}$ need to move during the time period $[k,k^{\prime\prime}-1]$ in $\tilde{\Omega}$ . We describe this situation with the notion of naturality.

For any $\omega_{i}(j)$ and $i^{\prime}(\neq i)$ , there is a $j^{\prime}$ such that $k^{\prime}\leq k<k^{\prime\prime}$ , where $\omega_{i}(j)\in\Omega_{k}$ , $\omega_{i^{\prime}}(j^{\prime}-1)\in\Omega_{k}^{\prime}$ , and $\omega_{i^{\prime}}(j^{\prime})\in\Omega_{k^{\prime\prime}}$ .⁶⁶6We consider $k^{\prime}=-1$ if $j^{\prime}=1$ and $\omega_{i^{\prime}}(j^{\prime})$ is not defined. A topological sort $T=(\Omega_{0},\Omega_{1},\Omega_{2},\ldots)$ is natural if the following conditions hold for any pair of such cycles $\omega_{i}(j)$ and $\omega_{i^{\prime}}(j^{\prime})$ :

1.

Suppose that $r_{i^{\prime}}\in S_{i}(j)$ . Thus $\omega_{i}(j)$ and $\omega_{i^{\prime}}(j^{\prime})$ do not overlap each other. Then $o_{i}(j)<o_{i^{\prime}}(j^{\prime})$ .
2.

Suppose that $r_{i^{\prime}}\not\in S_{i}(j)$ . Then $dist(\pi_{i}(j),\pi_{i^{\prime}}(j^{\prime}))>1$ .

We say that $E$ is natural if $E$ has a natural topological sort.

Assumption 5

We assume that $E$ is natural.

Theorem 1

If an execution $E\in\mathcal{E}(\Omega,\mathcal{A},I)$ satisfies Assumptions 1, 2, 3, 4, 5, there is an execution $\tilde{E}\in\mathcal{E}(\tilde{\Omega},\mathcal{A},I)$ for some $\tilde{\Omega}\in\cal{SSYNC}$ such that $E\sim\tilde{E}$ , i.e., $P(E)=P(\tilde{E})$ and $\Pi(E)=\Pi(\tilde{E})$ .

Proof. We construct an execution $\tilde{E}\in\mathcal{E}(\tilde{\Omega},\mathcal{A},I)$ as follows: If $r_{i}$ moves in $\omega_{i}(j)$ from $\pi_{i}(j)$ to $\pi_{i}(j+1)$ in $E$ , we move $r_{i}$ in $\tilde{\omega}_{i}(j)$ from $\pi_{i}(j)$ to $\pi_{i}(j+1)$ to construct $\tilde{E}$ that satisfies the conditions. We guarantee its feasibility by showing that $P_{i}(j)=\tilde{P}_{i}(j)$ and $\pi_{i}(j)=\tilde{\pi}_{i}(j)$ . Indeed, if $P_{i}(j)=\tilde{P}_{i}(j)$ , $\pi_{i}(j)=\tilde{\pi}_{i}(j)$ , and $r_{i}$ can move from $\pi_{i}(j)$ to $\pi_{i}(j+1)$ during $\omega_{i}(j)$ in $E$ , then it can move to the same position in $\tilde{\omega}_{i}(j)$ .

Suppose that a topological sort $T=(\Omega_{0},\Omega_{1},\Omega_{2},\ldots)$ is natural. It suffices to show the following claim for all $k=0,1,2,\ldots$ : For any robot $r_{i}\in A_{k}$ , $S_{i}(j)=\tilde{S}_{i}(j)$ , $P_{i}(j)=\tilde{P}_{i}(j)$ , $\pi_{i}(j)=\tilde{\pi}_{i}(j)$ , and $\pi_{i}(j+1)=\tilde{\pi}_{i}(j+1)$ hold. The proof is by induction on $k$ .

Base case ( $k=0$ ). Let $r_{i}\in A_{0}$ be any robot. Then, $\omega_{i}(j)\in\Omega_{0}$ holds for some $j$ and obviously $j=1$ . We show that $S_{i}(1)=\tilde{S}_{i}(1)$ . Recall that $\tilde{o}_{i}(j)=0$ .

Let $r_{i^{\prime}}$ be any robot. Suppose that $r_{i^{\prime}}\in A_{0}$ , i.e., $\omega_{i^{\prime}}(1)\in\Omega_{0}$ and $\omega_{i}(1)\stackrel{{\scriptstyle*}}{{\parallel}}\omega_{i^{\prime}}(1)$ . If $r_{i^{\prime}}\in S_{i}(1)$ , then $\omega_{i}(1)\parallel\omega_{i^{\prime}}(1)$ by the consistency, which implies $r_{i^{\prime}}\in\tilde{S}_{i}(1)$ . Otherwise, i.e., $r_{i^{\prime}}\not\in S_{i}(1)$ , $r_{i}\not\in S_{i^{\prime}}(1)$ , and thus $dist(\pi_{i}(1),\pi_{i^{\prime}}(1))>1$ by the consistency. Thus, $r_{i^{\prime}}\not\in\tilde{S}_{i}(1)$ .

Next, suppose that $r_{i^{\prime}}\not\in A_{0}$ . Then, $\omega_{i^{\prime}}(1)\in\Omega_{k^{\prime}}$ for some $k^{\prime}>0$ . If $r_{i^{\prime}}\in S_{i}(1)$ , then $o_{i}(1)<o_{i^{\prime}}(1)$ by the naturality. Since $r_{i}$ and $r_{i^{\prime}}$ do not move until $o_{i}(1)$ , $r_{i^{\prime}}\in\tilde{S}_{i}(1)$ . Otherwise, i.e., $r_{i^{\prime}}\not\in S_{i}(1)$ , $dist(\pi_{i}(1),\pi_{i^{\prime}}(1))>1$ by the naturality. Thus, $r_{i^{\prime}}\not\in\tilde{S}_{i}(1)$ .

Since $E$ and $\tilde{E}$ start with the same initial configuration $I$ , for any $r_{i}\in A_{0}$ , $\pi_{i}(1)=\tilde{\pi}_{i}(1)$ , and hence $P_{i}(1)=\tilde{P}_{i}(1)$ since $S_{i}(1)=\tilde{S}_{i}(1)$ . Since $\pi_{i}(2)$ is reachable from $\pi_{i}(1)$ by algorithm $\mathcal{A}$ when the snapshot is $P_{i}(1)$ , $\tilde{\pi}_{i}(2)(=\pi_{i}(2))$ is reachable from $\tilde{\pi}_{i}(1)(=\pi_{i}(1))$ by algorithm $\mathcal{A}$ when the snap shot is $\tilde{P}_{i}(1)(=P_{i}(1))$ . Thus, to construct $\tilde{E}$ , we move $r_{i}$ to $\tilde{\pi}_{i}(2)(=\pi_{i}(2))$ from $\tilde{\pi}_{i}(1)(=\pi_{i}(1))$ in $\tilde{\omega_{i}}(1)$ .

Induction step. Assume that the claim holds for all $0\leq k<K$ , and we show that the claim folds for $k=K$ . Let $r_{i}\in A_{k}$ be any robot such that $\omega_{i}(j)\in\Omega_{K}$ .

If $\omega_{i}(j-1)\in\Omega_{k}$ , then $k<K$ and $\pi_{i}(j)=\tilde{\pi}_{i}(j)$ by the induction hypothesis. Indeed, for all $i^{\prime}$ and $j^{\prime}$ , if $\omega_{i^{\prime}}(j^{\prime})\in\Omega_{k}$ for some $k\leq K$ , $\pi_{i^{\prime}}(j^{\prime})=\tilde{\pi}_{i^{\prime}}(j^{\prime})$ by the induction hypothesis.

Consider any robot $r_{i^{\prime}}\in S_{i}(j)$ . Since $E$ is stationary, $r_{i^{\prime}}$ is not in move phase at $o_{i}(j)$ . Suppose $o_{i}(j)\in(f_{i^{\prime}}(j^{\prime}),o_{i^{\prime}}(j^{\prime}+1))$ for some $j^{\prime}$ . Then, $\omega_{i^{\prime}}(j^{\prime})\rightarrow\omega_{i}(j)$ and $\Omega_{K^{\prime}}\Rightarrow\Omega_{K}$ , where $\omega_{i^{\prime}}(j^{\prime})\in\Omega_{K^{\prime}}$ for some $K^{\prime}<K$ . Since (i) $\pi_{i}(j)=\tilde{\pi}_{i}(j)$ , (ii) $\pi_{i^{\prime}}(j^{\prime}+1)=\tilde{\pi}_{i^{\prime}}(j^{\prime}+1)$ because $K^{\prime}<K$ , and (iii) the position of $r_{i^{\prime}}$ (in $\mathcal{Z}_{0}$ ) at $o_{i}(j)$ is $\pi_{i^{\prime}}(j^{\prime}+1)$ , we have $r_{i^{\prime}}\in\tilde{S}_{i}(j)$ and $p_{i^{\prime}}=\tilde{p}_{i^{\prime}}$ , where $p_{i^{\prime}}$ and $\tilde{p}_{i^{\prime}}$ are positions of $r_{i^{\prime}}$ (in $\mathcal{Z}_{i}$ ) in $P_{i}(j)$ and $\tilde{P_{i}(j)}$ , respectively. Here we use the fact that either $\omega_{i}(j)\parallel\omega_{i^{\prime}}(j^{\prime}+1)$ or $\omega_{i}(j)\rightarrow\omega_{i^{\prime}}(j^{\prime}+1)$ holds, and $K\leq K^{\prime\prime}$ holds, where $\omega_{i^{\prime}}(j^{\prime}+1)\in\Omega_{K^{\prime\prime}}$ .

Suppose otherwise $o_{i}(j)\in[o_{i^{\prime}}(j^{\prime}),s_{i^{\prime}}(j^{\prime})]$ for some $j^{\prime}$ . Then $\omega_{i}(j)\parallel\omega_{i^{\prime}}(j^{\prime})$ and $\omega_{i^{\prime}}(j^{\prime})\in\Omega_{K}$ . Let $\omega_{i}(j-1)\in\Omega_{k}$ and $\omega_{i^{\prime}}(j^{\prime}-1)\in\Omega_{k^{\prime}}$ . Then, $k,k^{\prime}<K$ . Thus, $\pi_{i^{\prime}}(j^{\prime})=\tilde{\pi}_{i}(j)$ by the induction hypothesis. Since $\pi_{i^{\prime}}(j^{\prime})$ is the position of $r_{i^{\prime}}$ at $o_{i}(j)$ and $\pi_{i}(j)=\tilde{\pi}_{i}(j)$ , $r_{i^{\prime}}\in\tilde{S}_{i^{\prime}}(j^{\prime})$ , and $p_{i^{\prime}}=\tilde{p}_{i^{\prime}}$ .

Finally, consider any robot $r_{i^{\prime}}\in\tilde{S}_{i}(j)$ to confirm $S_{i}(j)=\tilde{S}_{i}(j)$ . If there is a $j^{\prime}$ such that $\omega_{i}(j)\stackrel{{\scriptstyle*}}{{\parallel}}\omega_{i^{\prime}}(j^{\prime})$ , $dist(\pi_{i}(j),\pi_{i^{\prime}}(j^{\prime}))>1$ by the consistency. This implies that $r_{i^{\prime}}\not\in\tilde{S}_{i}(j)$ by the induction hypothesis.

Otherwise, $\omega_{i}(j)\not\stackrel{{\scriptstyle*}}{{\parallel}}\omega_{i^{\prime}}(\ell)$ for all $\ell\in\mathbf{N}$ . Let $j^{\prime}$ be an integer such that $K^{\prime}<K<K^{\prime\prime}$ , where $\omega_{i}(j)\in\Omega_{K}$ , $\omega_{i^{\prime}}(j^{\prime}-1)\in\Omega_{K^{\prime}}$ , and $\omega_{i^{\prime}}(j^{\prime})\in\Omega_{K^{\prime\prime}}$ . By the naturality, $dist(\pi_{i}(j),\pi_{i^{\prime}}(j^{\prime}))>1$ , which implies that $r_{i^{\prime}}\not\in S_{i}(j)$ by the induction hypothesis.

Since $\pi_{i}(j)=\tilde{\pi}_{i}(j)$ , the position of $r_{i^{\prime}}$ in $\tilde{P}_{i}(j)$ and $\tilde{P}_{i}(j)$ (both in $\mathcal{Z}_{i}$ ) are the same, i.e., $P_{i}(j)=\tilde{P}_{i}(j)$ . By the same reason as the base case, to construct $\tilde{E}$ , we move $r_{i}$ to $\tilde{\pi}(j+1)(=\pi_{i}(j+1))$ from $\tilde{\pi}_{i}(j)(=\pi_{i}(j))$ in $\tilde{\omega}_{i}(j)$ . $\Box$

3.2 Necessity

The conjunction of conditions in Assumptions 1, 2, 3, 4, and 5 is a sufficient condition for an ASYNC execution $E\in\mathcal{E}(\Omega,\mathcal{A},I)$ to have a similar SSYNC execution for some $\tilde{\Omega}\in\cal{SSYNC}$ . However, it is not necessary in general. Suppose that $\mathcal{A}$ does not move any robot. Then, the robot system is at its initial configuration $I$ forever, and every execution $E$ has a similar SSYNC execution $\tilde{E}$ , regardless of whether or not $E$ satisfies each of the five assumptions. We will show the necessity of the five assumptions assuming a randomized adversary that determines rigid movement and when moving robots are observed.

Let $\tau_{i}(j)$ in $\mathcal{Z}_{0}$ be the route of $r_{i}$ computed by $\mathcal{A}$ in $\omega_{i}(j)$ given snapshot $P_{i}(j)$ in $\mathcal{Z}_{i}$ as input. We assume that $\tau_{i}(j)$ is a simple curve such that $|\tau_{i}(j)|>\delta$ , where a curve is said to be simple if it does not contain an intersection. Recall that $r_{i}$ never stops en route if $|\tau_{i}(j)|\leq\delta$ . Otherwise, $r_{i}$ travels an arbitrary initial part $\hat{\tau}_{i}(j)$ of $\tau_{i}(j)$ such that $|\hat{\tau}_{i}(j)|>\delta$ at an arbitrary (possibly variable) speed during Move in $\omega_{i}(j)$ . Thus, another robot $r_{i^{\prime}}$ can observe $r_{i}$ at any position $y$ in $\hat{\tau}_{i}(j)$ (thus, $\tau_{i}(j)$ ) at $o_{i^{\prime}}(j^{\prime})$ if $r_{i}\in S_{i^{\prime}}(j^{\prime})$ and $o_{i^{\prime}}(j^{\prime})\in(s_{i}(j),f_{i}(j))$ .

Intuitively, we assume that $\hat{\tau}_{i}(j)$ satisfying $|\hat{\tau}_{i}(j)|>\delta$ is chosen “uniformly at random” and that $y$ is chosen “uniformly at random” from $\tau_{i}(j)$ (provided that $\hat{\tau}_{i}(j)=\tau_{i}(j)$ ). Then, we show that if an execution $E\in\mathcal{E}(\Omega,\mathcal{A},I)$ has a similar execution $\tilde{E}\in\mathcal{E}(\tilde{\Omega},\mathcal{A},I)$ for some $\tilde{\Omega}\in\cal{SSYNC}$ , then $E$ satisfies each of the five conditions in Assumptions 1, 2, 3, 4, and 5 with “probability” $1$ .

3.2.1 Stationarity

For a fixed algorithm $\mathcal{A}$ and initial configuration $I$ , we show that the stationarity is necessary. To make the argument simple, we assume that the system is rigid. Then, $E\in\mathcal{E}(\Omega,\mathcal{A},I)$ is uniquely determined by $\Omega\in\cal{ASYNC}$ if $E$ is stationary.

Consider any schedule $\Omega\in\cal{ASYNC}$ that contains a unique pair of cycles $\omega_{i}(j)$ and $\omega_{i^{\prime}}(j^{\prime})$ such that $o_{i}(j)\in(s_{i^{\prime}}(j^{\prime}),f_{i^{\prime}}(j^{\prime}))$ . Let $\tau_{i^{\prime}}(j^{\prime})$ be the route (in $\mathcal{Z}_{0}$ ) that $\mathcal{A}$ at $r_{i^{\prime}}$ computes given $P_{i^{\prime}}(j^{\prime})$ (in $\mathcal{Z}_{i^{\prime}}$ ). Then, $E\in\mathcal{E}(\Omega,\mathcal{A},I)$ is uniquely determined by the position $y\in\tau_{i^{\prime}}(j^{\prime})$ of $r_{i^{\prime}}$ at $o_{i}(j)$ (regardless of whether or not $y$ is visible from $r_{i}$ at $o_{i}(j)$ ). We normalize $y$ by $z=|\hat{\tau}_{i^{\prime}}(j^{\prime})|/|\tau_{i^{\prime}}(j^{\prime})|\in[0,1]$ , where $\hat{\tau}_{i^{\prime}}(j^{\prime})$ is the prefix of $\tau_{i^{\prime}}(j^{\prime})$ before (and including) $y$ . Then, there is a one-to-one correspondence between $y\in\tau_{i^{\prime}}(j^{\prime})$ and $z\in[0,1]$ , because $\tau_{i^{\prime}}(j^{\prime})$ is a simple curve. We use the notation $E(z)$ to emphasize that $E$ is determined by $z$ .

We use a Borel measurable space $([0,1],\mathcal{B}([0,1]))$ , where $\mathcal{B}([0,1])$ is the Borel $\sigma$ -algebra on $[0,1]$ , i.e., the smallest $\sigma$ -algebra containing all open intervals in $[0,1]$ . Then, the probability measure $\lambda(\cdot)$ for each element of $\mathcal{B}([0,1])$ is the (1-dimensional) Lebesgue probability measure on $[0,1]$ , that satisfies, for all intervals $(a,b)$ where $0\leq a<b\leq 1$ , $\lambda({(a,b)})=b-a$ . Thus, $\{[a,a]\}$ and $\{[a,a],[b,b]\}$ are $\lambda$ -null sets. In the following, we consider a probability space $([0,1],\mathcal{B}([0,1]),\lambda)$ .

Let $\mathcal{Y}=\{y\in\tau_{i^{\prime}}(j^{\prime})\mid dist(y,\pi_{i}(j))\leq 1\}$ be the set of positions $y$ in $\tau_{i^{\prime}}(j^{\prime})$ visible from $r_{i}$ at $o_{i}(j)$ , and let $\mathcal{D}$ be the set of $z^{\prime}$ s corresponding to the $y$ ’s in $\mathcal{Y}$ . Then, $E(z)$ is not stationary if and only if $z\in\mathcal{D}$ . Since $\tau_{i^{\prime}}(j^{\prime})$ is continuous, $\mathcal{D}\in\mathcal{B}([0,1])$ . We assume that the probability that $z\in\mathcal{D}$ is $\lambda(\mathcal{D})$ . Thus $\lambda(\mathcal{D})=0$ means that $r_{i^{\prime}}$ is not visible from $r_{i}$ at $o_{i}(j)$ and hence the stationarity is not violated with probability 1 (since we assume that the value of $z$ is chosen uniformly at random from $[0,1]$ ). Here and in the rest of this section, whenever we say that an execution violates a condition, we assume that the condition is violated with positive probability. That is, we assume here that $\lambda(\mathcal{D})>0$ ; the violation occurs with a positive probability.

Lemma 2

Suppose that $\lambda(\mathcal{D})>0$ . Then, $E(z)\not\sim\tilde{E}\in\mathcal{E}(\tilde{\Omega},\mathcal{A},I)$ for any $\tilde{\Omega}\in\cal{SSYNC}$ $\lambda$ -almost everywhere on $\mathcal{D}$ , i.e., $E(z)$ does not have a similar SSYNC execution $\tilde{E}$ for all $z\in\mathcal{D}$ , except for a countable number of exceptions.

Proof. Clearly, $E(z)\not\sim E(z^{\prime})$ if $z\neq z^{\prime}$ provided $z,z^{\prime}\in\mathcal{D}$ . Thus, $\{E(z)\mid z\in\mathcal{D}\}$ is uncountable since $\lambda(\mathcal{D})>0$ .

On the other hand, $\cal{SSYNC}$ is a countable set. Since the system is rigid, $\tilde{E}\in\mathcal{E}(\tilde{\Omega},\mathcal{A},I)$ is uniquely determined by $\tilde{\Omega}\in\cal{SSYNC}$ (because $\mathcal{A}$ and $I$ are fixed), $\{\tilde{E}\in\mathcal{E}(\tilde{\Omega},\mathcal{A},I)\mid\tilde{\Omega}\in\cal{SSYNC}\}$ is countable. Thus, only for a countable number of executions $E(z)$ , there are similar SSYNC executions $\tilde{E}$ . $\Box$

The above lemma states the following: If the probability that $r_{i^{\prime}}$ is visible from $r_{i}$ at $o_{i}(j)$ is not $0$ , then the probability that $E$ has a similar SSYNC execution $\tilde{E}$ is $0$ , under the condition that $r_{i^{\prime}}$ is indeed visible from $r_{i}$ at $o_{i}(j)$ and the stationarity is indeed violated.

We extend Lemma 2 to the case in which $\Omega$ contains more than one pair of cycles $\omega_{i}(j)$ and $\omega_{i^{\prime}}(j^{\prime})$ such that $o_{i}(j)\in(s_{i^{\prime}}(j^{\prime}),f_{i^{\prime}}(j^{\prime}))$ . We order the pairs $W_{h}=(\omega_{i}(j),\omega_{i^{\prime}}(j^{\prime}))$ of cycles in the increasing order of $o_{i}(j)$ , where a tie is resolved arbitrarily. We use the concepts and notations above, let $y_{h}$ and $z_{h}$ be the position of $r_{i^{\prime}}$ in $\tau_{i^{\prime}}(j^{\prime})$ at $o_{i}(j)$ and its normalization, respectively. Let $\mathcal{D}_{h}$ be the set of $z_{h}$ ’s such that $y_{h}$ is visible from $\pi_{i}(j)$ , i.e., $r_{i^{\prime}}$ is visible from $r_{i}$ at $o_{i}(j)$ . Note that $\mathcal{D}_{h}$ depends on some of $z_{1},z_{2},\ldots,z_{h-1}$ in general. Since the system is rigid, $E\in\mathcal{E}(\Omega,\mathcal{A},I)$ is uniquely determined by $Z=(z_{1},z_{2},\ldots)$ . We use the notation $E(Z)$ to emphasize this fact.

Suppose that $\lambda(\mathcal{D}_{h})>0$ in $E(Z)$ when $z_{i}=a_{i}$ for $i=1,2,\ldots,h-1$ . By assumption the value of $z_{h}$ is chosen uniformly at random from $[0,1]$ . If $z_{h}$ randomly chooses a value in $\mathcal{D}_{h}$ , by Lemma 2, regardless of the values chosen for $z_{h+1},z_{h+2},\ldots$ , $E(Z)\not\sim\tilde{E}\in\mathcal{E}(\tilde{\Omega},\mathcal{A},I)$ for any $\tilde{\Omega}\in\cal{SSYNC}$ $\lambda$ -almost everywhere on $\mathcal{D}_{h}$ , i.e., $E(Z)$ does not have a similar SSYNC execution $\tilde{E}$ for all $z_{h}\in\mathcal{D}$ , except for a countable number of exceptions.

Thus, if $E$ violates the stationarity, it is unlikely that $E$ has a similar SSYNC execution (even under rigid system). In the following, we then assume that $E$ is stationary, and investigate the non-rigid system.

3.2.2 Pairwise alignment

To treat the non-rigid system, we use an infinite product measure space $([0,1]^{\infty},\mathcal{B}^{\infty}([0,1]),\lambda^{\infty})$ . Here $[0,1]^{\infty}$ is the Cartesian product of a countable infinity of copies of $[0,1]$ . The family of events $\mathcal{B}^{\infty}([0,1])$ is the Cartesian product of a countable infinity of copies of the Borel $\sigma$ -field $\mathcal{B}([0,1])$ , which is the $\sigma$ -algebra generated by all sets in $[0,1]^{\infty}$ represented by a finite union of cylinders, where a cylinder is a set in $[0,1]^{\infty}$ with a form $B_{1}\times B_{2}\times\ldots B_{n}\prod_{i=n+1}^{\infty}[0,1]$ for some natural number $n$ and $B_{i}\in\mathcal{B}([0,1])$ for all $i=1,2,\ldots n$ . Finally $\lambda^{\infty}(\cdot)$ is the product measure on $([0,1]^{\infty},\mathcal{B}^{\infty}([0,1]))$ , which is defined by $\lambda^{\infty}(B)=\prod_{i=1}^{\infty}\lambda(B_{i})$ , for all $B=B_{1}\times B_{2}\times\ldots\in\mathcal{B}^{\infty}([0,1])$ .⁷⁷7 We can construct $\lambda^{\infty}$ by the Kolmogorov extension theorem in the same manner as Theorem 2.4.4 of the book [18] by Tao.

Let $\Phi$ be a property (i.e., predicate) on $[0,1]^{\infty}$ and let $\Gamma=\{X\mid\Phi(X)\ \text{is true}\}\in\mathcal{B}^{\infty}([0,1])$ . If $\mathcal{D}\setminus\Gamma$ is a $\lambda^{\infty}$ -null set for $\mathcal{D}\in\mathcal{B}^{\infty}([0,1])$ , we say that $\Phi$ holds $\lambda^{\infty}$ -almost everywhere on $\mathcal{D}$ , which means that $\Phi$ holds with probability $1$ under $\lambda^{\infty}$ on $\mathcal{D}$ .

We associate a random variable $y_{m}$ with the $m$ th dimension of $[0,1]^{\infty}$ . If in $\mathcal{D}\in\mathcal{B}^{\infty}([0,1])$ , there is a finite set $\{i_{1},i_{2},\ldots,i_{k}\}\subset{\mathbf{N}}$ such that $y_{i_{k}}$ is uniquely determined by $y_{i_{1}},y_{i_{2}},\ldots,y_{i_{k}-1}$ , then $\lambda^{\infty}(\mathcal{D})=0$ .

Let $\Omega\in\cal{ASYNC}$ be any schedule and consider $E\in\mathcal{E}(\Omega,\mathcal{A},I)$ . Suppose that in cycle $\omega_{i}(j)$ , a robot $r_{i}$ , which is located at $\pi_{i}(j)$ (in $\mathcal{Z}_{0}$ ) at time $o_{i}(j)$ , takes a snapshot $P_{i}(j)$ (in $\mathcal{Z}_{i}$ ), computes a route $\tau_{i}(j)$ (in $\mathcal{Z}_{0}$ ) by $\mathcal{A}$ , and moves along $\tau_{i}(j)$ in its Move. Since the system is not rigid, it may stop en route after tracing an initial part $\hat{\tau}_{i}(j)$ of $\tau_{i}(j)$ such that $|\hat{\tau}_{i}(j)|\geq\delta$ . Then, the end point of $\hat{\tau}_{i}(j)$ is $\pi_{i}(j+1)$ of $r_{i}$ when $\omega_{i}(j+1)$ starts. Thus, $\hat{\tau}_{i}(j)$ may affect the rest of execution including $\pi_{i}(j+1)$ and $\tau_{i}(j+1)$ .

The initial part $\hat{\tau}_{i}(j)$ can be denoted by a real number $z_{i}(j)\in[0,1]$ , i.e., $z_{i}(j)$ represents $\hat{\tau}_{i}(j)$ such that $|\hat{\tau}_{i}(j)|=|\tau_{i}(j)|z_{i}(j)-\delta(z_{i}(j)-1)$ . Here $z_{i}(j)$ is well-defined, since $\tau_{i}(j)$ is a simple curve and $|\tau_{i}(j)|>\delta$ . Since the system is non-rigid, any value $z_{i}(j)\in[0,1]$ can occur, as assumed. More carefully, each of $z_{i}(j)$ ’s takes a value in $[0,1]$ uniformly at random, and the probability that $z_{i}(j)\in B$ is $\lambda(B)$ for any $B\in\mathcal{B}([0,1])$ .

We order $z_{i}(j)$ in the increasing order of $o_{i}(j)$ , where a tie is broken arbitrarily, and fix the ordering. By associating the $m$ th $z_{i}(j)$ with the $m$ th variable $z^{(m)}$ , we identify $Z=\{z_{i}(j)\mid r_{i}\in\mathcal{R},j\in{\mathbf{N}}\}$ with an infinite vector $(z^{(1)},z^{(2)},\ldots)\in[0,1]^{\infty}$ . Then, $E$ is determined uniquely by $Z\in[0,1]^{\infty}$ since $E$ is stationary. We use notation $E(Z)$ to emphasize that $E$ is determined by $Z$ . It is easy to observe that $Z=Z^{\prime}$ if and only if $E(Z)\sim E(Z^{\prime})$ .

Suppose that $E(Z)\in\mathcal{E}(\Omega,\mathcal{A},I)$ contains a unique triple of cycles $\omega_{i}(j)$ , $\omega_{i^{\prime}}(j^{\prime})$ , and $\omega_{i^{\prime}}(j^{\prime}+1)$ such that $\omega_{i}(j)$ and $\omega_{i^{\prime}}(j^{\prime}+\ell)$ overlap each other and $r_{i}$ and $r_{i^{\prime}}$ are mutually visible for $\ell=0,1$ . Thus, $E(Z)$ does not satisfy the pairwise alignment condition. Let $\mathcal{D}$ be the set of $Z$ ’s such that $E(Z)$ does not satisfy the pairwise alignment condition. We assume $\lambda^{\infty}(\mathcal{D})>0$ by the same reason we mentioned immediately above Lemma 2.

Lemma 3

Suppose that $\lambda^{\infty}(\mathcal{D})>0$ . Then, $E(Z)$ does not have a similar execution $\tilde{E}\in\mathcal{E}(\tilde{\Omega},\mathcal{A},I)$ for any $\Omega\in\cal{SSYNC}$ $\lambda^{\infty}$ -almost everywhere on $\mathcal{D}$ .

Proof. Let $\Gamma$ be the set of vectors $Z\in\mathcal{D}$ such that $E(Z)$ has a similar SSYNC execution $\tilde{E}$ . We show that $\lambda^{\infty}(\Gamma)=0$ .

Suppose that $E(Z)$ has a similar SSYNC execution $\tilde{E}\in\mathcal{E}(\tilde{\Omega},\mathcal{A},I)$ for some $\tilde{\Omega}\in\cal{SSYNC}$ . Let $k=\tilde{o}_{i}(j)$ , $k^{\prime}=\tilde{o}_{i^{\prime}}(j^{\prime})$ , and $k^{\prime\prime}=\tilde{o}_{i^{\prime}}(j^{\prime}+1)$ , where $k^{\prime}<k^{\prime\prime}$ . We have the following four cases: (i) $k^{\prime}<k\leq k^{\prime\prime}$ , (ii) $k^{\prime}\leq k<k^{\prime\prime}$ , (iii) $k^{\prime}<k^{\prime\prime}<k$ , and (iv) $k<k^{\prime}<k^{\prime\prime}$ .

When $k^{\prime}<k\leq k^{\prime\prime}$ . At $o_{i}(j)$ , $r_{i}$ is at $\pi_{i}(j)$ and $r_{i^{\prime}}$ is at $\pi_{i^{\prime}}(j^{\prime})$ in $E(Z)$ , and at $k=\tilde{o}_{i}(j)$ , $r_{i}$ is at $\tilde{\pi}_{i}(j)(=\pi_{i}(j))$ and $r_{i^{\prime}}$ is at $\tilde{\pi}_{i^{\prime}}(j^{\prime}+1)(=\pi_{i^{\prime}}(j^{\prime}+1))$ in $\tilde{E}(Z)$ . Since $P_{i}(j)=\tilde{P}_{i}(j)$ , $\pi_{i^{\prime}}(j^{\prime})\neq\pi_{i^{\prime}}(j^{\prime}+1)$ , $E(Z)$ does not have a similar SSYNC execution $E$ , since $r_{i^{\prime}}$ moves at least distance $\delta$ and $\tau_{i^{\prime}}(j^{\prime})$ is simple.

When $k^{\prime}\leq k<k^{\prime\prime}$ . By the argument above, $E(Z)$ does not have a similar SSYNC execution $\tilde{E}$ unless $k^{\prime}=k$ . Let $\ell\geq 1$ be the minimum integer such that $\tilde{o}_{i}(j+\ell)\geq k^{\prime\prime}$ . At $o_{i^{\prime}}(j^{\prime}+1)$ , $r_{i}$ is at $\pi_{i}(j)$ and $r_{i^{\prime}}$ is at $\pi_{i^{\prime}}(j^{\prime}+1)$ in $E(Z)$ , and at $k^{\prime\prime}=\tilde{o}_{i^{\prime}}(j^{\prime}+1)$ , $r_{i}$ is at $\tilde{\pi}_{i}(j+\ell)(=\pi_{i}(j+\ell))$ and $r_{i^{\prime}}$ is at $\tilde{\pi}_{i^{\prime}}(j^{\prime}+1)(=\pi_{i^{\prime}}(j^{\prime}+1))$ in $E(Z)$ . Since $P_{i^{\prime}}(j^{\prime}+1)=\tilde{P}_{i^{\prime}}(j^{\prime}+1)$ , $\pi_{i}(j)=\pi_{i}(j+\ell)$ . That is, $z_{i}(j+\ell-1)$ is uniquely determined by $\pi_{i}(j+\ell-1)$ . (If there is no such $z_{i}(j+\ell-1)$ , $E(Z)$ does not have a similar SSYNC execution $\tilde{E}$ .) Thus, $\lambda^{\infty}(\Gamma)=0$ .

When $k^{\prime}<k^{\prime\prime}<k$ . Let $\ell$ be the minimum integer such that $\tilde{o}_{i^{\prime}}(j^{\prime}+1+\ell)\geq k$ . By the same argument above, we have $\pi_{i^{\prime}}(j^{\prime})=\pi_{i^{\prime}}(j^{\prime}+1+\ell)$ . That is, $z_{i^{\prime}}(j^{\prime}+\ell)$ must be uniquely determined by $\pi_{i^{\prime}}(j^{\prime}+\ell)$ . (If there is no such $z_{i^{\prime}}(j^{\prime}+\ell)$ , $E(Z)$ does not have a similar SSYNC execution $\tilde{E}$ .) Thus, $\lambda^{\infty}(\Gamma)=0$ .

When $k<k^{\prime}<k^{\prime\prime}$ . By the same argument above, we have $\lambda^{\infty}(\Gamma)=0$ .

Thus, the proof completes. $\Box$

In order for $Z$ to be in $\mathcal{D}$ , $E(Z)$ needs to satisfy both $r_{i^{\prime}}\in S_{i}(j)$ and $r_{i}\in S_{i^{\prime}}(j^{\prime}+1)$ , or equivalently, $dist(\pi_{i}(j),\pi_{i^{\prime}}(j^{\prime}))\leq 1$ and $dist(\pi_{i}(j),\pi_{i^{\prime}}(j^{\prime}+1))\leq 1$ . However, unlike the proof for stationarity, $\lambda^{\infty}(\mathcal{D})>0$ does not follow in general, since there may be a pair of an algorithm $\mathcal{A}$ and an initial configuration $I$ such that for any $Z\in[0,1]^{\infty}$ , in $E(Z)$ , either $r_{i^{\prime}}\not\in S_{i}(j)$ or $r_{i}\not\in S_{i^{\prime}}(j^{\prime}+1)$ holds. If $\lambda^{\infty}(\mathcal{D})=0$ , $E(Z)$ satisfies the pairwise alignment condition with probability $1$ , and we do not consider $\mathcal{E}(\Omega,\mathcal{A},I)$ as an instance that does not satisfy the pairwise alignment condition, even though there is a $Z\in[0,1]^{\infty}$ such that $r_{i^{\prime}}\in S_{i(j)}$ and $r_{i}\in S_{i^{\prime}}(j^{\prime}+1)$ in $E(Z)$ .

Note that the same claim as Lemma 3 holds for $E(Z)$ such that there are more than one triple $\omega_{i}(j)$ , $\omega_{i^{\prime}}(j^{\prime})$ , and $\omega_{i^{\prime}}(j^{\prime}+1)$ that violates the pairwise alignment condition. Suppose that $E(Z)\in\mathcal{E}(\Omega,\mathcal{A},I)$ contains a pair of cycles $\omega_{i}(j)$ and $\omega_{i^{\prime}}(j^{\prime})$ such that $\omega_{i}(j)\parallel\omega_{i^{\prime}}(j^{\prime})$ . Let $\mathcal{D}$ be the set of $Z$ ’s such that $E(Z)$ satisfies this condition.

Proposition 5

Suppose that $\lambda^{\infty}(\mathcal{D})>0$ . If $E(Z)$ has a similar execution $\tilde{E}\in\mathcal{E}(\Omega,\mathcal{A},I)$ for some $\tilde{\Omega}\in\cal{SSYNC}$ , then $\tilde{o}_{i}(j)=\tilde{o}_{i^{\prime}}(j^{\prime})$ $\lambda^{\infty}$ -almost everywhere on $\mathcal{D}$ .

Proof. Let $\Gamma$ be the set of vectors $Z\in\mathcal{D}$ such that there is a $\tilde{\Omega}\in\cal{SSYNC}$ satisfying

1.

$\tilde{o}_{i}(j)\neq\tilde{o}_{i^{\prime}}(j^{\prime})$ , and
2.

$E(Z)\sim\tilde{E}\in\mathcal{E}(\Omega,\mathcal{A},I)$ .

Then, by the same argument in the proof of Lemma 3, we have $\lambda^{\infty}(\Gamma)=0$ . $\Box$

3.2.3 Consistency

Throughout this section, we assume that $E(Z)\in\mathcal{E}(\Omega,\mathcal{A},I)$ contains a pair of cycles $\omega_{i}(j)$ and $\omega_{i^{\prime}}(j^{\prime})$ such that $\omega_{i}(j)\stackrel{{\scriptstyle*}}{{\parallel}}\omega_{i^{\prime}}(j^{\prime})$ , and that $E(Z)$ has a similar execution $\tilde{E}\in\mathcal{E}(\tilde{\Omega},\mathcal{A},I)$ for some $\tilde{\Omega}\in\cal{SSYNC}$ . Let $\mathcal{D}$ be the set of $Z$ ’s such that $E(Z)$ satisfies this condition.

Lemma 4

Suppose that $\lambda^{\infty}(\mathcal{D})>0$ . If $E(Z)\in\mathcal{E}(\Omega,\mathcal{A},I)$ which contains a pair of cycles $\omega_{i}(j)$ and $\omega_{i^{\prime}}(j^{\prime})$ such that $\omega_{i}(j)\stackrel{{\scriptstyle*}}{{\parallel}}\omega_{i^{\prime}}(j^{\prime})$ holds has a similar execution $\tilde{E}\in\mathcal{E}(\tilde{\Omega},\mathcal{A},I)$ for some $\tilde{\Omega}\in\cal{SSYNC}$ , then $\tilde{o}_{i}(j)=\tilde{o}_{i^{\prime}}(j^{\prime})$ $\lambda^{\infty}$ -almost everywhere on $\mathcal{D}$ .

Proof. Since $\omega_{i}(j)\stackrel{{\scriptstyle*}}{{\parallel}}\omega_{i^{\prime}}(j^{\prime})$ , there are cycles $\omega_{i_{\ell}}(j_{\ell})$ ( $\ell=0,1,\ldots,m$ ) such that $(i_{0},j_{0})=(i,j)$ and $(i_{m},j_{m})=(i^{\prime},j^{\prime})$ , and $\omega_{i_{\ell-1}}(j_{\ell-1})\parallel\omega_{i_{\ell}}(j_{\ell})$ for all $\ell=1,2,\ldots,m$ . By Proposition 5, if $E(Z)$ has a similar SSYNC execution $\tilde{E}$ , then, for $\ell=1,2,\ldots,m$ , $\tilde{o}_{i_{\ell-1}}(j_{\ell-1})=\tilde{o}_{i_{\ell}}(j_{\ell})$ $\lambda^{\infty}$ -almost everywhere on $\mathcal{D}$ , which implies that $\tilde{o}_{i}(j)=\tilde{o}_{i^{\prime}}(j^{\prime})$ $\lambda^{\infty}$ -almost everywhere on $\mathcal{D}$ . $\Box$

Lemma 5

Suppose that $\lambda^{\infty}(\mathcal{D})>0$ . If $E(Z)$ has a similar execution $\tilde{E}\in\mathcal{E}(\tilde{\Omega},\mathcal{A},I)$ for some $\tilde{\Omega}\in\cal{SSYNC}$ , then $r_{i^{\prime}}\in S_{i}(j)$ if and only if $r_{i}\in S_{i^{\prime}}(j^{\prime})$ , $\lambda^{\infty}$ -almost everywhere on $\mathcal{D}$ .

Proof. Since $\lambda^{\infty}(\mathcal{D})>0$ , $E(Z)$ has a similar execution $\tilde{E}\in\mathcal{E}(\tilde{\Omega},\mathcal{A},I)$ for some $\tilde{\Omega}\in\cal{SSYNC}$ such that $\tilde{o}_{i}(j)=\tilde{o}_{i^{\prime}}(j^{\prime})$ $\lambda^{\infty}$ -almost everywhere on $\mathcal{D}$ by Lemma 4.

Suppose that $o_{i^{\prime}}(j^{\prime})<o_{i}(j)$ . Let $\omega_{i^{\prime}}(j^{\prime}+\ell^{\prime}-1)$ (resp. $\omega_{i}(j-\ell-1)$ ) be the cycle of $r_{i^{\prime}}$ (resp. $r_{i}$ ) such that $\pi_{i^{\prime}}(j^{\prime}+\ell^{\prime})$ (resp. $\pi_{i}(j+\ell)$ ) be the position of $r_{i^{\prime}}$ (resp. $r_{i}$ ) at $o_{i}(j)$ (resp. $o_{i^{\prime}}(j^{\prime})$ ). Since $\pi_{i}(j)=\tilde{\pi}_{i}(j)$ , $\pi_{i}(j-\ell)=\tilde{\pi}_{i}(j-\ell)$ , $\pi_{i^{\prime}}(j^{\prime})=\tilde{\pi}_{i^{\prime}}(j^{\prime})$ , $\pi_{i^{\prime}}(j^{\prime}+\ell)=\tilde{\pi}_{i^{\prime}}(j^{\prime}+\ell)$ , $\pi_{i}(j)=\tilde{\pi}_{i}(j-\ell)$ , and $\pi_{i^{\prime}}(j^{\prime})=\tilde{\pi}_{i^{\prime}}(j^{\prime}+\ell)$ , provided that $\tilde{o}_{i}(j)=\tilde{o}_{i^{\prime}}(j^{\prime})$ . Obviously, the set of $Z\in\mathcal{D}$ satisfying $\pi_{i}(j)=\pi_{i}(j-\ell)$ (resp. $\pi_{i^{\prime}}(j^{\prime})=\pi_{i^{\prime}}(j^{\prime}+\ell^{\prime})$ ) is the $\lambda^{\infty}$ -null set when $\ell>0$ (resp. $\ell^{\prime}>0$ ). Thus, $r_{i^{\prime}}\in S_{i}(j)$ if and only if $r_{i}\in S_{i^{\prime}}(j^{\prime})$ $\lambda^{\infty}$ -almost everywhere on $\mathcal{D}$ .

The case $o_{i^{\prime}}(j^{\prime})>o_{i}(j)$ is analogous and the case $o_{i^{\prime}}(j^{\prime})=o_{i}(j)$ is trivial. $\Box$

By the proof of above lemma, we have the following corollary.

Corollary 1

Suppose that $\lambda^{\infty}(\mathcal{D})>0$ . If $E(Z)$ has a similar execution $\tilde{E}\in\mathcal{E}(\tilde{\Omega},\mathcal{A},I)$ for some $\tilde{\Omega}\in\cal{SSYNC}$ , and $r_{i^{\prime}}\in S_{i}(j)$ and $r_{i}\in S_{i^{\prime}}(j^{\prime})$ hold, then $\omega_{i}(j)\parallel\omega_{i^{\prime}}(j^{\prime})$ $\lambda^{\infty}$ -almost everywhere on $\mathcal{D}$ .

Lemma 6

Suppose that $\lambda^{\infty}(\mathcal{D})>0$ . If $E(Z)$ has a similar execution $\tilde{E}\in\mathcal{E}(\tilde{\Omega},\mathcal{A},I)$ for some $\tilde{\Omega}\in\cal{SSYNC}$ , and $r_{i^{\prime}}\not\in S_{i}(j)$ and $r_{i}\not\in S_{i^{\prime}}(j^{\prime})$ hold, then $dist(\pi_{i}(j),\pi_{i^{\prime}}(j^{\prime}))>1$ $\lambda^{\infty}$ -almost everywhere on $\mathcal{D}$ .

Proof. Since $\lambda^{\infty}(\mathcal{D})>0$ , $E(Z)$ has a similar execution $\tilde{E}\in\mathcal{E}(\tilde{\Omega},\mathcal{A},I)$ for some $\tilde{\Omega}\in\cal{SSYNC}$ , such that $\tilde{o}_{i}(j)=\tilde{o}_{i^{\prime}}(j^{\prime})$ $\lambda^{\infty}$ -almost everywhere on $\mathcal{D}$ by Lemma 4.

If $dist(\pi_{i}(j),\pi_{i^{\prime}}(j^{\prime}))\leq 1$ , since $\pi_{i}(j)=\tilde{\pi}_{i}(j)$ , $\pi_{i^{\prime}}(j^{\prime})=\tilde{\pi}_{i^{\prime}}(j^{\prime})$ , and $\tilde{o}_{i}(j)=\tilde{o}_{i^{\prime}}(j^{\prime})$ $\lambda^{\infty}$ -almost everywhere on $\mathcal{D}$ , there is a robot $r_{i^{\prime\prime}}$ and cycle $\omega_{i^{\prime\prime}}(j^{\prime\prime})$ such that $r_{i^{\prime\prime}}$ is at position $\pi_{i^{\prime}}(j^{\prime})$ at time $o_{i}(j)$ , since $P_{i}(j)=\tilde{P}_{i}(j)$ . Such event does not occur $\lambda^{\infty}$ -almost everywhere on $\mathcal{D}$ . Thus, $dist(\pi_{i}(j),\pi_{i^{\prime}}(j^{\prime}))>1$ $\lambda^{\infty}$ -almost everywhere on $\mathcal{D}$ . $\Box$

3.2.4 Serializability

Lemma 7

If $E(Z)\in\mathcal{E}(\Omega,\mathcal{A},I)$ which contains a pair of cycles $\omega_{i}(j)$ and $\omega_{i^{\prime}}(j^{\prime})$ such that $\omega_{i}(j)\rightarrow\omega_{i^{\prime}}(j^{\prime})$ holds has a similar execution $\tilde{E}\in\mathcal{E}(\Omega,\mathcal{A},I)$ for some $\tilde{\Omega}\in\cal{SSYNC}$ , then $\tilde{o}_{i}(j)<\tilde{o}_{i^{\prime}}(j^{\prime})$ $\lambda^{\infty}$ -almost everywhere on $\mathcal{D}$ .

Proof. If $i=i^{\prime}$ , since $j<j^{\prime}$ , $\tilde{o}_{i}(j)<\tilde{o}_{i^{\prime}}(j^{\prime})$ by definition.

Suppose that $i\neq i^{\prime}$ . Then, $r_{i}\in S_{i^{\prime}}(j^{\prime})$ and $o_{i^{\prime}}(j^{\prime})\in(f_{i}(j),o_{i}(j+1))$ . Then, by a similar argument in the proof of Lemma 3, $E(Z)$ does not have a similar execution $\tilde{E}\in\mathcal{E}(\Omega,\mathcal{A},I)$ for any $\tilde{\Omega}\in\cal{SSYNC}$ such that $\tilde{o}_{i}(j)>\tilde{o}_{i^{\prime}}(j^{\prime})$ $\lambda^{\infty}$ -almost everywhere on $\mathcal{D}$ . $\Box$

The following corollary immediately holds by Lemma 4 and Lemma 7.

Corollary 2

If $E(Z)$ does not satisfy the serializability, then $E(Z)$ does not have a similar execution $\tilde{E}\in\mathcal{E}(\tilde{\Omega},\mathcal{A},I)$ for any $\tilde{\Omega}\in\cal{SSYNC}$ $\lambda^{\infty}$ -almost everywhere on $\mathcal{D}$ .

3.2.5 Naturality

Recall that $\mathcal{G}=(\{\Omega_{0},\Omega_{1},\ldots\},\Rightarrow)$ and the set $\mathcal{T}$ of topological sorts of $\mathcal{G}$ are determined by execution $E(Z)\in\mathcal{E}(\Omega,\mathcal{A},I)$ . We sometimes associate $E(Z)$ with $\mathcal{G}$ and $\mathcal{T}$ to emphasize that they are uniquely determined by $E(Z)$ . Let $\mathcal{TS}(E(Z))(\subset\cal{SSYNC})$ be the set of schedules constructed from topological sorts in $\mathcal{T}(E(Z))$ . By Lemma 4 and Lemma 7, if $\tilde{E}\in\mathcal{E}(\tilde{\Omega},\mathcal{A},I)$ is similar to $E(Z)\in\mathcal{E}(\Omega,\mathcal{A},I)$ , then $\tilde{\Omega}\in\mathcal{TS}(E(Z))$ $\lambda^{\infty}$ -almost everywhere on $\mathcal{D}$ , provided that $\lambda^{\infty}(\mathcal{D})>0$ . Here $\mathcal{D}$ is the set of $U\in[0,1]^{\infty}$ such that $\mathcal{G}(E(U))=\mathcal{G}(E(Z))$ .

Consider any schedule $\tilde{\Omega}\in\mathcal{TS}(E(Z))$ . Suppose that there is a pair of cycles $\omega_{i}(j)$ and $\omega_{i^{\prime}}(j^{\prime})$ such that $k^{\prime}\leq k<k^{\prime\prime}$ , where, under $\tilde{\Omega}$ , $\tilde{o}_{i}(j)=k$ , $\tilde{o}_{i^{\prime}}(j^{\prime}-1)=k^{\prime}$ , and $\tilde{o}_{i^{\prime}}(j^{\prime})=k^{\prime\prime}$ . Obviously, $\omega_{i}(j)\not\stackrel{{\scriptstyle*}}{{\parallel}}\omega_{i^{\prime}}(j^{\prime})$ .

First assume that $r_{i^{\prime}}\in S_{i}(j)$ in $E(Z)$ , and let $\mathcal{D^{\prime}}\subseteq\mathcal{D}$ be the set of $Z\in\mathcal{D}$ such that $E(Z)$ satisfies this condition.

Lemma 8

Suppose that $\lambda^{\infty}(\mathcal{D^{\prime}})>0$ . If $E(Z)$ has a similar execution $\tilde{E}\in\mathcal{E}(\Omega,\mathcal{A},I)$ , then $o_{i}(j)<o_{i^{\prime}}(j^{\prime})$ $\lambda^{\infty}$ -almost everywhere on $\mathcal{D^{\prime}}$ .

Proof. By definition, $r_{i^{\prime}}$ is at position $\tilde{\pi}_{i^{\prime}}(j^{\prime})$ at time $\tilde{o}_{i}(j)=k$ in $\tilde{E}$ . Since $\omega_{i}(j)\not\stackrel{{\scriptstyle*}}{{\parallel}}\omega_{i^{\prime}}(j^{\prime})$ , $o_{i}(j)\neq o_{i^{\prime}}(j^{\prime})$ . Suppose that $o_{i}(j)>o_{i^{\prime}}(j^{\prime})$ . There is a cycle $\omega_{i^{\prime}}(j^{\prime}+\ell^{\prime})$ such that $r_{i^{\prime}}$ is at $\pi_{i^{\prime}}(j^{\prime}+\ell^{\prime})$ at $o_{i}(j)$ for some $\ell^{\prime}\geq 1$ . Since $\pi_{i}(j)=\tilde{\pi}_{i}(j)$ , $P_{i}(j)=\tilde{P}_{i}(j)$ , and $r_{i^{\prime}}\in S_{i}(j)$ , there is a robot $r_{i^{\prime\prime}}$ (which may be $r_{i^{\prime}}$ ) and a cycle $\omega_{i^{\prime\prime}}(j^{\prime\prime})$ such that $\tilde{\pi}_{i^{\prime\prime}}(j^{\prime\prime})=\pi_{i^{\prime}}(j^{\prime}+\ell^{\prime})$ . Thus, $E(Z)$ does not have a similar execution $\tilde{E}\in\mathcal{E}(\tilde{\Omega},\mathcal{A},I)$ $\lambda^{\infty}$ -almost everywhere on $\mathcal{D^{\prime}}$ . $\Box$

Next assume that $r_{i^{\prime}}\not\in S_{i}(j)$ in $E(Z)$ , and let $\mathcal{D}^{\prime\prime}\subseteq\mathcal{D}$ be the set of $Z\in\mathcal{D}$ such that $E(Z)$ satisfies this condition.

Lemma 9

Suppose that $\lambda^{\infty}(\mathcal{D^{\prime\prime}})>0$ . If $E(Z)$ has a similar execution $\tilde{E}\in\mathcal{E}(\Omega,\mathcal{A},I)$ , then $dist(\pi_{i}(j),\pi_{i^{\prime}}(j^{\prime}))>1$ $\lambda^{\infty}$ -almost everywhere on $\mathcal{D^{\prime\prime}}$ .

Proof. Suppose that $dist(\pi_{i}(j),\pi_{i^{\prime}}(j^{\prime}))\leq 1$ . Since $r_{i^{\prime}}$ is at $\tilde{\pi}_{i^{\prime}}(j^{\prime})$ at $\tilde{o}_{i}(j)=k$ in $\tilde{E}$ , $\tilde{\pi}_{i^{\prime}}(j^{\prime})=\pi_{i^{\prime}}(j^{\prime})$ and $\tilde{\pi}_{i}(j)=\pi_{i}(j)$ , $r_{i^{\prime}}\in\tilde{S}_{i}(j)$ . There is a robot $r_{i^{\prime\prime}}$ for some $i^{\prime\prime}(\neq i)$ and a cycle $\omega_{i^{\prime\prime}}(j^{\prime\prime})$ such that $r_{i^{\prime\prime}}$ is at $\pi_{i^{\prime}}(j^{\prime})$ at $o_{i}(j)$ in $E(Z)$ , since $\tilde{P}_{i}(j)=P_{i}(j)$ . Thus, $E(Z)$ does not have a similar execution $\tilde{E}\in\mathcal{E}(\tilde{\Omega},\mathcal{A},I)$ $\lambda^{\infty}$ -almost everywhere on $\mathcal{D^{\prime\prime}}$ . $\Box$

Consequently, we have the following theorem.

Theorem 10

Each of the five properties, stationarity, pairwise alignment, consistency, serializability, and naturality is necessary for an execution $E(Z)\in\mathcal{E}(\Omega,\mathcal{A},I)$ to have a similar execution $\tilde{E}\in\mathcal{E}(\tilde{\Omega},\mathcal{A},I)$ for some schedule $\tilde{\Omega}\in\cal{SSYNC}$ with probability $1$ .

4 Luminous synchronizer for ASYNC robots

In this section, we present a synchronizer for oblivious luminous ASYNC robots, that produces ASYNC executions satisfying Assumptions 1, 2, 3, 4, and 5. When the robots are not equipped with lights, each robot cannot recognize which robots are moving. We compensate for this weak capability by a single light at each robot.⁸⁸8 Remember that the color of a light is changed at the end of a Compute, and it is kept until the end of the Compute of the next cycle.

Let $C$ be the set of colors that a light can take. Each light initially takes Black ( $Bk\in C$ ). When robot $r_{i}$ takes a snapshot $Q_{i}$ at time $t$ , $Q_{i}$ is the set of pairs $(p_{i^{\prime}},c_{i^{\prime}})$ for each $r_{i^{\prime}}$ visible for $r_{i}$ at $t$ , where $p_{i^{\prime}}$ is the the position of $r_{i^{\prime}}$ at $t$ in $\mathcal{Z}_{i}$ and $c_{i^{\prime}}$ is the color of $r_{i^{\prime}}$ ’s light at $t$ . Let $P(Q_{i})=\{p_{i^{\prime}}\mid(p_{i^{\prime}},c_{i^{\prime}})\in Q_{i}\}$ , and $C(Q_{i})=\{c_{i^{\prime}}\mid(p_{i^{\prime}},c_{i^{\prime}})\in Q_{i}\}$ . That is, $P(Q_{i})$ is the set of positions occupied by robots visible for $r_{i}$ in $\mathcal{Z}_{i}$ , and $C(Q_{i})$ is the set of colors visible for $r_{i}$ . Recall that $r_{i}$ is aware of its color, i.e., the color of its light $c_{i}$ since $p_{i}=(0,0)$ and the robots occupy distinct points.

For an initial configuration $I$ of the system of non-luminous robots, let $\hat{I}=\{(p,Bk)\mid p\in I\}$ be an initial configuration of the system of luminous robots. By definition, $P(\hat{I})=I$ and $C(\hat{I})=\{Bk\}$ .

We now define a luminous synchronizer $\mathcal{S}$ on a robot $r_{i}$ under any schedule $\Omega\in\cal{ASYNC}$ . Given any algorithm $\mathcal{A}$ and initial configuration $I$ for non-luminous robots, the initial configuration for $\mathcal{S}$ is the corresponding configuration $\hat{I}$ . Luminous synchronizer $\mathcal{S}$ on $r_{i}$ inhibits on-the-fly $r_{i}$ ’s motion in some cycle so that the resulting execution have a similar SSYNC execution. Precisely, $\mathcal{S}$ works as follows: In a cycle $\omega=(o,s,f)$ of robot $r$ , $r$ takes a snapshot $Q$ at time $o$ in Look. In Compute, depending on $Q$ , $\mathcal{S}$ on $r$ first decides whether or not it “accepts” $\omega$ , and then computes a move route $\tau$ . If it accepts $\omega$ , $\tau$ is the one that $\mathcal{A}$ computes given $P(Q)$ ; otherwise, if it “rejects” $\omega$ , $\tau$ is the point $(0,0)$ . Finally, it decides a color $c\in C$ and the color of $r_{i}$ ’s light is changed to $c$ at the end of Compute. Thus, the color $c$ is visible from other robots at $s$ and thereafter. In Move, $r$ traces $\tau$ but it may stop en route after moving distance $\delta$ .

The set of executions $F$ of $\mathcal{S}$ for $\mathcal{A}$ and $I$ under scheduler $\Omega$ is denoted by $\mathcal{E}(\Omega,\mathcal{S}(\mathcal{A}),\hat{I})$ . Let $\Lambda$ be the set of cycles accepted by $\mathcal{S}$ in $F$ . Note that $\Lambda$ depends on $F$ . From $F$ (and $\Lambda$ ), we can construct an execution $\check{F}\in\mathcal{E}(\Lambda,\mathcal{A},I)$ for non-luminous robots by first extracting the behaviors of the robots for cycles in $\Lambda$ and then ignoring the colors of lights. Since the next position is computed from $P(Q)$ (not from $Q$ ) and the robots do not change their positions in rejected cycles, indeed $\check{F}\in\mathcal{E}(\Lambda,\mathcal{A},I)$ .

We say that luminous synchronizer $\mathcal{S}$ is correct if the following conditions hold for any $\Omega$ , $\mathcal{A}$ , $I$ , and $F\in\mathcal{E}(\Omega,\mathcal{S}(\mathcal{A}),\hat{I})$ .

1.

$\Lambda$ is fair.
2.

$\check{F}$ satisfies Assumptions 1, 2, 3, 4, and 5, which implies that $\check{F}\in\mathcal{E}(\Lambda,\mathcal{A},I)$ has a similar execution $\tilde{E}\in\mathcal{E}(\tilde{\Lambda},\mathcal{A},I)$ for some $\tilde{\Lambda}\in\cal{SSYNC}$ .

4.1 Limit of color-based synchronizer

The visibility graph of a configuration of the robots consists of a set of vertices corresponding to the robots and a set of edges between any pair of robots within distance $1$ (in $\mathcal{Z}_{0}$ ). A visibility preserving algorithm guarantees that the visibility graph does not change in any execution. Formally, an execution $E\in\mathcal{E}(\Omega,\mathcal{A},I)$ for non-luminous robots is visibility preserving, if the following condition holds: For any $r_{i}$ and $r_{i^{\prime}}$ , and for any time $t\in{\mathbf{R}}^{+}$ , $dist(p_{i}(t),p_{i^{\prime}}(t))\leq 1$ if and only if $dist(p_{i}(0),p_{i^{\prime}}(0))\leq 1$ , where $p_{j}(u)$ is the position of $r_{j}$ at time $u$ in $\mathcal{Z}_{0}$ . We say that an algorithm $\mathcal{A}$ is visibility preserving, if every execution $E\in\mathcal{E}(\Omega,\mathcal{A},I)$ is visibility preserving for any $\Omega\in\cal{SSYNC}$ and $I$ .

Let $Q_{i}(j)=\{(p_{i^{\prime}},c_{i^{\prime}})\mid r_{i^{\prime}}\in S_{i}(j)\}$ be the snapshot taken by a robot $r_{i}$ at $o_{i}(j)$ in $\omega_{i}(j)$ . Clearly, $p_{i}=(0,0)$ . Let $X_{i}(j)=\{c_{i^{\prime}}\mid i^{\prime}\neq i,r_{i^{\prime}}\in S_{i}(j)\}$ . In general, a luminous synchronizer on $r_{i}$ can use the full information on $Q_{i}(j)$ to decide whether it accepts $\omega_{i}(j)$ or not. A luminous synchronizer $\mathcal{S}$ is color-based if it uses $c_{i}$ and $X_{i}(j)$ for the selection. A color-based synchronizer $\mathcal{S}$ is greedy if it accepts $\omega_{i}(j)$ if and only if $C(Q_{i}(j))=\{Bk\}$ , i.e., $c_{i}=Bk$ and $X_{i}(j)$ is either $\{Bk\}$ or $\emptyset$ . We show that any greedy synchronizer is not powerful enough in general.

Lemma 11

There exists a rigid system of five luminous robots such that for any greedy synchronizer $\mathcal{S}$ , there is a triple $(\Omega,\mathcal{A},I)$ such that, for some execution $F\in\mathcal{E}(\Omega,\mathcal{S}(\mathcal{A}),\hat{I})$ , $\check{F}$ is not consistent.

Proof. Consider a system of five luminous robots. We illustrate an initial part of an execution $F\in\mathcal{E}(\Omega,\mathcal{S}(\mathcal{A}),I)$ . Initially, $r_{1},r_{2},\ldots,r_{5}$ are at $(0,0)$ , $(0,1)$ , $(1,1)$ , $(1,0)$ , and $(2,0)$ , respectively in $\mathcal{Z}_{0}$ . Thus, $\hat{I}=\{((0,0),Bk),((0,1),Bk),((1,1),Bk),((1,0),Bk),((2,0),Bk)\}$ . Since the visibility range is $1$ , $r_{2}$ and $r_{4}$ are visible from $r_{1}$ , but $r_{5}$ and $r_{3}$ are not visible from $r_{1}$ . The first cycles in $\Omega$ are $\omega_{1}(1)=(0,3/4,1)$ , $\omega_{2}(1)=(1/2,5/4,3/2)$ , $\omega_{3}(1)=(1,7/4,2)$ , $\omega_{4}(1)=(3/2,9/4,5/2)$ , and $\omega_{5}(1)=(3,15/4,4)$ . Recall that the initial color of light is $Bk$ . Since $\mathcal{S}$ is greedy, it accepts $\omega_{1}(1)$ , $\omega_{2}(1)$ , and $\omega_{3}(1)$ .

Suppose that $\mathcal{A}$ moves $r_{1}$ to $(0,3/4)$ in $\omega_{1}(1)$ . Then, at time $3/2$ , $r_{1}$ is not visible from $r_{4}$ . Thus, all robots visible from $r_{4}$ is still have color $Bk$ , and $\mathcal{S}$ on $r_{4}$ accepts $\omega_{4}(1)$ .

Observe that $\omega_{1}(1)\stackrel{{\scriptstyle*}}{{\parallel}}\omega_{4}(1)$ . Then, $\check{F}$ is not consistent regardless of the rest of $F$ , because $r_{4}\in S_{1}(1)$ but $r_{1}\not\in S_{4}(1)$ . $\Box$

We extend Lemma 11 to the color-based synchronizer. A fully synchronous scheduler $\cal{FSYNC}$ produces a schedule $\Omega$ such that $\omega_{i}(j)=(j-1,j-3/4,j-1/4)$ for all $i$ and $j$ . Thus, $\cal{FSYNC}\subset\cal{SSYNC}$ in the sense that if $\Omega\in\cal{FSYNC}$ , $\Omega\in\cal{SSYNC}$ holds.

Theorem 12

There exists a rigid system of five luminous robots such that for any color-based synchronizer $\mathcal{S}$ , there is a triple $(\Omega,\mathcal{A},I)$ such that, for some execution $F\in\mathcal{E}(\Omega,\mathcal{S}(\mathcal{A}),\hat{I})$ , $\check{F}$ is not consistent.

Proof. Remember the execution $F\in\mathcal{E}(\Omega,\mathcal{S}(\mathcal{A}),I)$ for five luminous robots in the proof of Lemma 11. The counter example relies on the assumptions that $\mathcal{S}$ is greedy and that the initial color of each robot is $Bk$ . We show that there is a $\Lambda$ which changes the configuration to a one such that $\mathcal{S}$ on each robot accepts the current cycle.

Consider an execution $F\in\mathcal{E}(\Lambda,\mathcal{S}(\mathcal{A}),\hat{I})$ , where $\Lambda\in\cal{FSYNC}$ . Then, all lights have the same color $c_{j}$ when the robots simultaneously start their $j$ th cycles for any $j\in{\mathbf{N}}$ since $\mathcal{S}$ is color-based. Hence, there is a $j_{0}$ such that each robot $r_{i}$ accepts $\omega_{i}(j_{0})$ since $\mathcal{S}$ is fair. That is, $\mathcal{S}$ on each robot $r_{i}$ accepts $\omega_{i}(j_{0})$ , since it accepts a cycle when $c=c_{j_{0}-1}$ and $X=\{C_{j_{0}-1}\}$ . We assume without loss of generality that $\omega_{i}(j_{0})$ is the first cycle accepted by $\mathcal{S}$ .

Now the configuration is $\{(p,c_{j_{0}-1})\mid(p,Bk)\in\hat{I}\}$ immediately before the $j_{0}$ th cycle starts at time $j_{0}-1$ . We replace $\omega_{i}(j_{0})$ for each $r_{i}\in\Lambda$ with

•

$\omega_{1}(j_{0})=(j_{0}-1,(j_{0}-1)+3/4,(j_{0}-1)+1)$ ,
•

$\omega_{2}(j_{0})=((j_{0}-1)+1/2,(j_{0}-1)+5/4,(j_{0}-1)+3/2)$ ,
•

$\omega_{3}(j_{0})=((j_{0}-1)+1,(j_{0}-1)+7/4,(j_{0}-1)+2)$ ,
•

$\omega_{4}(j_{0})=((j_{0}-1)+3/2,(j_{0}-1)+9/4,(j_{0}-1)+5/2)$ , and
•

$\omega_{2}(j_{0})=((j_{0}-1)+3,(j_{0}-1)+15/4,(j_{0}-1)+4)$ .

Then, the same argument as the proof of Lemma 11 concludes the theorem. $\Box$

The above example shows that there exists no color-based synchronizer that works correctly if the algorithm is not visibility preserving.

4.2 Color-based synchronizer for vicinity preserving algorithms

Lemma 11 and Theorem 12 demonstrate that there is no color-based synchronizer for an arbitrary visibility preserving algorithm. Moreover, it is difficult for oblivious luminous robots to satisfy the second condition of naturality, because it requires remembering the positions of other robots. In this section, we consider algorithms with more restricted changes in the visibility graph and propose a color-based synchronizer for such algorithms.

An execution $E\in\mathcal{E}(\Omega,\mathcal{A},I)$ for non-luminous robots is vicinity preserving, if the following condition holds: For any $r_{i}$ , $r_{i^{\prime}}$ , and for any time $t,t^{\prime}\in{\mathbf{R}}^{+}$ , $dist(p_{i}(t),p_{i^{\prime}}(t^{\prime}))\leq 1$ if and only if $dist(p_{i}(0),p_{i^{\prime}}(0))\leq 1$ . In other words, $r_{i}$ has to stay in the vicinity of its initial position. We say that an algorithm $\mathcal{A}$ is vicinity preserving, if every execution $E\in\mathcal{E}(\Omega,\mathcal{A},I)$ is vicinity preserving for any $\Omega\in\cal{SSYNC}$ and $I$ . In this section, we propose a color-based synchronizer $\mathcal{S}_{VP}$ that uses a set $C=\{Bk,R,B,G,W\}$ of colors and show its correctness provided that $\mathcal{A}$ is vicinity preserving and designed for non-luminous SSYNC robots. We describe $\mathcal{S}_{VP}$ as a finite-state machine with a state set $C$ , an input alphabet $2^{C}$ , and an output alphabet $\{\text{accept},\text{reject}\}$ . When $\mathcal{S}_{VP}$ is executed on $r_{i}$ , the sate of $r_{i}$ is the color (of the light) of $r_{i}$ and the input is the set $X$ of colors of the robots visible from $r_{i}$ , excluding $r_{i}$ ’s color. Table 1 shows the transition function and the output function of $\mathcal{S}_{VP}$ , where

•

$\exists c$ means any $X$ such that $c\in X$ ,
•

$\forall(c_{1},c_{2},\ldots,c_{k})$ means any $X$ such that $X\subseteq\{c_{1},c_{2},\ldots,c_{k}\}$ , and
•

$\exists c\ \wedge\ \forall(c_{1},c_{2},\ldots,c_{k})$ means any $X$ such that $c\in X$ and $X\subseteq\{c_{1},c_{2},\ldots,c_{k}\}$ .

The initial state of each robots is $Bk$ . We assume that without loss of generality, the visibility graph of the initial configuration $I$ is connected. Since $\mathcal{A}$ is vicinity preserving, let $S_{i}$ be the set of neighbors of $r_{i}$ in the visibility graph which is defined by $I$ .

Table 1: Finite-state machine

\mathcal{S}_{VP}

Current state	Input	Next state	Output
Bk	$\forall(Bk,B,W)$	$R$	accept
	$\exists R\wedge\forall(Bk,R,B,W)$	$W$	reject
R	$\forall(R,B,W)$	$B$	reject
B	$\forall(B,G)$	$G$	reject
G	$\forall(Bk,G)$	$Bk$	reject
W	$\forall(B,W)$	$Bk$	reject

Robot $r_{i}$ is waiting when its state is $Bk$ (Black) and moving when its state is $R$ (Red). It rejects the current cycle when its state is $Bk$ and observes another robot in state $R$ , and changes its state to $W$ (White). It changes its state from $W$ to $Bk$ when it does not observe any robot in state $R$ . Robot $r_{i}$ has finished moving when its state is $B$ (Blue) and it changes its state to $G$ (Green) when the states of robots in $S_{i}$ are $B$ and $G$ . Finally, it changes its state to $Bk$ when the states of robots in $S_{i}$ are $G$ and $Bk$ .

Let $F\in\mathcal{E}(\Omega,\mathcal{S}_{VP}(\mathcal{A}),\hat{I})$ be any execution of $\mathcal{S}_{VP}$ for a vicinity preserving algorithm $\mathcal{A}$ , and let $\Lambda\subseteq\Omega$ be the set of accepted cycles (which depends on $F$ ). Then, $\check{F}\in\mathcal{E}(\Lambda,\mathcal{A},I)$ is an execution of non-luminous robots. We will show that $\check{F}$ has a corresponding SSYNC execution for non-luminous robots. We demonstrate that (i) $\Lambda$ is fair, (ii) $\check{F}$ satisfies stationarity, pairwise alignment, consistency, serializability, and naturality.

Lemma 13

$\Lambda$ is fair.

Proof. We show that every robot reaches state $R$ infinitely many times in $F$ . We first regard three states $Bk$ , $W$ , and $R$ as a virtual state $Y$ . Every robot starts with state $Y$ . When the state of a robot $r_{i}$ is $Y$ (i.e., $R$ ) and the sate of each robot $r_{i^{\prime}}\in S_{i}$ is either $Y$ (i.e., $R$ or $W$ ) or $B$ , then it can change its state to $B$ . When the state of $r_{i}$ is $G$ and the state of each robot $r_{i^{\prime}}\in S_{i}$ is either $G$ or $Y$ (i.e., $Bk$ ), then it can change its state to $Y$ (i.e., $Bk$ ). For the time being, we assume that if the state of $r_{i}$ is $Bk$ , then it will eventually change its state to $R$ . We show that every robot $r_{i}$ reaches state $Y$ infinitely many times in $F$ . This implies that it reaches state $R$ infinitely many times. Then, we can conclude that $\check{F}$ is fair, because $r_{i}$ changes its color to $R$ in $\omega_{i}(j)$ if and only if $\omega_{i}(j)$ is accepted by $\mathcal{S}_{VP}$ .

Consider any robot $r_{i}$ . Let $\Psi_{i}=(\psi_{i}(1),\psi_{i}(2),\ldots)\subseteq\Omega_{i}$ , where $\psi_{i}(j)$ is the cycle of $r_{i}$ in which it changes its state for the $j$ th time. The state of $r_{i}$ changes from state $Y$ to $B$ in $\psi_{i}(1)$ , from state $B$ to $G$ in $\psi_{i}(2)$ , from state $G$ to $Y$ in $\psi_{i}(3)$ , ans so on. For each $C\in\{Y,B,G\}$ , $C^{(k)}$ denotes the the state that $r_{i}$ takes $C$ for the $k$ th time. Thus, the state of $r_{i}$ changes from state $Y^{(1)}$ to $B^{(1)}$ in $\psi_{i}(1)$ , from state $B^{(1)}$ to $G^{(1)}$ in $\psi_{i}(2)$ , from state $G^{(1)}$ to $Y^{(2)}$ in $\psi_{i}(3)$ , and so on. Independently of $i$ , in $\psi_{i}(j)$ , $r_{i}$ changes its state from $c(j)$ to $c(j+1)$ , where $c(j)=Y^{(\lfloor j/3\rfloor+1)}$ if $j\pmod{3}=1$ , $c(j)=B^{(\lfloor j/3\rfloor+1)}$ if $j\pmod{3}=2$ , and $c(j)=G^{(\lfloor j/3\rfloor)}$ if $j\pmod{3}=0$ .

Let $\psi_{i}(j)=(o_{i}(j),s_{i}(j),f_{i}(j))$ . Then, $r_{i}$ takes a snapshot at $o_{i}(j)$ and changes the color of its light (i.e., its state) by $s_{i}(j)$ . The new color becomes visible from other robots at $s_{i}(j)$ . Thus, the state of $r_{i}$ at $o_{i}(j)$ is $c(j)$ and is $c(j+1)$ at $s_{i}(j)$ .

For any robot $r_{\ell}$ , let $\sigma_{\ell}(t)$ be the sate of $r_{\ell}$ at time $t\in{\mathbf{R}}^{+}$ . Thus, $\sigma_{i}(o_{i}(j))=c(j)$ and $\sigma_{i}(s_{i}(j))=c(j+1)$ . We first claim that for any $j\in{\mathbf{N}}$ , $\sigma_{i^{\prime}}(o_{i}(j))$ is either $c(j)$ or $c(j+1)$ for any robot $r_{i^{\prime}}\in S_{i}$ . The proof is by induction on $j$ .

When $j=1$ , $c_{i}(o_{i}(1))=c(1)=Y^{(1)}$ . Suppose that $\sigma_{i^{\prime}}(o_{i}(j))=c(j^{\prime})$ for some $j^{\prime}\geq 3$ . Then $r_{i^{\prime}}$ changes its state from $B^{(1)}$ to $G^{(1)}$ in $\psi_{i^{\prime}}(2)$ and $o_{i^{\prime}}(2)<o_{i}(1)$ . It is a contradiction, because $r_{i}\in S_{i^{\prime}}$ and $\sigma_{i}(o_{i^{\prime}}(2))=Y^{(1)}$ . Thus, $\sigma_{i^{\prime}}(o_{i}(1))$ is either $c(1)(=Y^{(1)})$ or $c(2)(=B^{(1)})$ .

Provided that $\sigma_{i^{\prime}}(o_{i}(j))$ is either $c(j)$ or $c(j+1)$ , we show that $\sigma_{i^{\prime}}(o_{i}(j+1))$ is either $c(j+1)$ or $c(j+2)$ . By definition, if $\sigma_{i^{\prime}}(o_{i}(j+1))=c(\ell)$ , then $\ell\geq j$ . If $\ell=j$ , then $r_{i}$ cannot change its state from $c(j+1)$ to $c(j+2)$ in $\psi_{i}(j+1)$ . Thus, $\ell\geq j+1$ . Suppose that $\ell\geq j+3$ . In time interval $[o_{i}(j),s_{i}(j))$ , the state of $r_{i}$ is still $c_{i}(j)$ . During this interval, the state of $r_{i}^{\prime}$ is either $c(j)$ or $c(j+1)$ . Thus, by the same argument as the base case for $\psi_{i^{\prime}}(j+2)$ , a contradiction is derived.

To show that $\Psi_{i}$ is an infinite sequence, we assume that it is a finite sequence and derive a contradiction. Let $h$ be the length of $\Psi_{i}$ , i.e., $\psi_{i}(h)$ is the last cycle of $\Psi_{i}$ . By the claim above, $\Psi_{k}$ is finite for any $k$ . Without loss of generality, we assume that $\Psi_{i}$ is the shortest one. By the claim, the length of $\Psi_{i^{\prime}}$ is either $h$ or $h+1$ , if $r_{i^{\prime}}\in S_{i}$ . Let $t^{*}$ be a time instant that $r_{i}$ and all $r_{i^{\prime}}\in S_{i}$ have finished their last cycles in $\Psi$ . Since $\Omega$ is fair, there is a cycle $\omega=(o,s,f)\in\Omega_{i}$ such that $t^{*}<o$ . The state of $r_{i}$ is $c(h+1)$ at $o$ , and the state of each $r_{i^{\prime}}\in S_{i}$ is either $c_{i}(h+1)$ or $c_{i}(h+2)$ at $o$ . Thus, the state of $r_{i}$ changes in $\omega$ , and hence $\omega\in\Psi_{i}$ . It is a contradiction.

We next show that, for all $k\in{\mathbf{N}}$ , if the state of a robot $r_{i}$ is $Bk$ , then it will eventually change its state to $R$ in $Y^{(k)}$ for any $k\in{\mathbf{N}}$ . The proof is by induction on $k$ .

Base Case (when $k=1$ ): Let $r_{i^{\prime}}\in S_{i}$ . The state of $r_{i^{\prime}}$ is either $Y^{(1)}$ or $B^{(1)}$ (and not $G^{(1)}$ ) as long as the state of $r_{i}$ is $Y^{(1)}$ (i.e., either $Bk$ , $R$ , or $W$ ). Recall the notation $\omega_{i}(j)=(o_{i}(j),s_{i}(j),f_{i}(j))$ for all $i$ and $j$ .

By $\mathcal{S}_{VP}$ , if $\sigma_{i}(o_{i}(j))=Bk$ , then it changes its state either $W$ or $R$ in $\omega_{i}(j)$ . It changes its state to $W$ if there is an $r_{i^{\prime}}\in S_{i}$ such that $\sigma_{i^{\prime}}(o_{i}(1))=R$ , otherwise it changes its state to $R$ .

Suppose that $\sigma_{i}(o_{i}(j))=R$ . If $\sigma_{i^{\prime}}(o_{i}(j))\in\{R,B,W\}$ for each $r_{i^{\prime}}\in S_{i}$ , since the state of $r_{i}$ is $Y^{(1)}$ then $r_{i}$ changes its state to $B$ in $\omega_{i}(j)$ . Otherwise, if there is an $r_{i^{\prime}}\in S_{i}$ such that $\sigma_{i^{\prime}}(o_{i}(j))=Bk$ , by the observation above, $r_{i^{\prime}}$ changes its state to $R$ or $W$ in $\omega_{i^{\prime}}(j^{\prime})$ , where $j^{\prime}$ satisfies $o_{i^{\prime}}(j^{\prime}-1)<o_{i}(j)\leq o_{i^{\prime}}(j^{\prime})$ . Furthermore, if $r_{i^{\prime}}$ changes its state state to $W$ , it maintains the state as long as the state of $r_{i}$ is $R$ . Thus, $r_{i}$ eventually changes its state to $B$ .

We show that $r_{i}$ whose state is $Bk$ will eventually change its state to $R$ after repeating the loop between $Bk$ and $W$ a finite number of times. Suppose that $\sigma_{i}(o_{i}(j))=Bk$ , and let $R_{i}(j)$ be the set of $r_{i^{\prime}}\in S_{i}$ such that $\sigma_{i^{\prime}}(o_{i}(j))=R$ . Robot $r_{i}$ changes its state to $W$ in $\omega_{i}(j)$ if and only if $R_{i}(j)=\emptyset$ . Since $|S_{i}|<n$ , $r_{i}$ will eventually change its state to $R$ after repeating the loop at most $n-1$ times, since any robot $r_{i^{\prime}}\in S_{i}$ with state $B$ will never return to $Bk$ as long as the state of $r_{i}$ is $X^{(1)}$ .

Finally, we show that $r_{i}$ whose state is $W$ will eventually change its state to $Bk$ . Suppose that $\sigma_{i}(o_{i}(j))=W$ . If $\sigma_{i^{\prime}}(o_{i}(j))\in\{B,W\}$ for each $r_{i^{\prime}}\in S_{i}$ , then $r_{i}$ changes its state to $Bk$ in $\omega_{i}(j)$ . Otherwise, if there is an $r_{i^{\prime}}\in S_{i}$ such that $\sigma_{i^{\prime}}(o_{i}(j))\in\{Bk,R\}$ , it does not change its state in $\omega_{i}(j)$ . If $\sigma_{i^{\prime}}(o_{i}(j))=R$ , then $r_{i^{\prime}}$ will eventually change its state to $B$ .

If $\sigma_{i^{\prime}}(o_{i}(j))=Bk$ , then $r_{i^{\prime}}$ changes its state to $W$ in $\omega_{i^{\prime}}(j^{\prime})$ , where $j^{\prime}$ satisfies $o_{i^{\prime}}(j^{\prime})<o_{i}(j)\leq o_{i^{\prime}}(j^{\prime}+1)$ . Thus, there is a $r_{k}\in S_{i}\cup\{r_{i}\}$ and $\ell\in{\mathbf{N}}$ such that $o_{i}(j)<o_{k}(\ell)$ such that $r_{k}$ changes its state from $W$ to $Bk$ in $\omega_{k}(\ell)$ . Since the total number of times that robots other than $r_{i}$ repeat the loops is bounded by $(n-1)^{2}$ , $r_{i}$ will eventually change its state from $W$ to $Bk$ . The proof of the base case completes.

Induction Step: Suppose that $\sigma_{i}(o_{i}(j))=G^{(k-1)}$ and $\sigma_{i^{\prime}}(o_{i}(j))\in\{Bk,G^{(k-1)}\}$ for all $r_{i^{\prime}}\in S_{i}$ . Then, $r_{i}$ changes its state from $G^{k-1}$ to $Bk$ in $\omega_{i}(j)$ . The state of $r_{i}$ is $Bk$ as long as there is an $r_{i^{\prime}}\in S_{i}$ such that $\sigma_{i^{\prime}}(o_{i}(j))=G^{(k-1)}$ . We show that $r_{i^{\prime}}$ will eventually change its state from $G^{(k-1)}$ to $Bk$ . If $r_{i^{\prime}}$ cannot change its state from $G^{(k-1)}$ , then there is an $r_{i^{\prime\prime}}\in S_{i^{\prime}}$ whose state is neither $Bk$ nor $G^{(k-1)}$ . If the state of $r_{i^{\prime\prime}}$ is $B^{(k-1)}$ , then it will eventually change its state to $G^{(k-1)}$ . If it is $W$ or $R$ , we can derive a contradiction, because $r_{i^{\prime\prime}}$ can change its state to $W$ or $R$ when the state of $r_{i}$ is $G^{(k-1)}$ . Thus, we can apply the proof for the base case to complete the induction step. $\Box$

Lemma 14

$\check{F}$ is stationary.

Proof. A robot $r_{i}$ can move in $\omega_{i}(j)$ if the cycle is accepted. If $\omega_{i}(j)$ is accepted, the state of $r_{i}$ is $R$ during the interval $[s_{i}(j),f_{i}(j)]$ . If a cycle $\omega_{i^{\prime}}(j^{\prime})$ of a robot $r_{i^{\prime}}\in S_{i}$ satisfies that $\sigma_{i}(o_{i^{\prime}}(j^{\prime}))=R$ , then $\omega_{i^{\prime}}(j^{\prime})$ is rejected. Thus, $\omega_{i^{\prime}}(j^{\prime})$ is accepted, only if $o_{i^{\prime}}(j^{\prime})\not\in[s_{i}(j),f_{i}(j)]$ . $\Box$

Lemma 15

$\check{F}$ is pairwise aligned.

Proof. Suppose that $\check{F}$ is not pairwise aligned. In $\Lambda$ , there are cycles $\omega_{i}(j)$ , $\omega_{i^{\prime}}(j^{\prime})$ , and $\omega_{i^{\prime}}(j^{\prime}+\ell)$ satisfying the following conditions:

•

$r_{i^{\prime}}\in S_{i}$ (thus, $r_{i}\in S_{i^{\prime}}$ ),
•

$\omega_{i}(j)$ and $\omega_{i^{\prime}}(j^{\prime})$ overlap each other,
•

$\omega_{i}(j)$ and $\omega_{i^{\prime}}(j^{\prime}+\ell)$ overlap each other, and
•

$\omega_{i^{\prime}}(j^{\prime}+1),\omega_{i^{\prime}}(j^{\prime}+2),\ldots,\omega_{i^{\prime}}(j^{\prime}+\ell-1)$ are not accepted (hence, they are not the elements of $\Lambda$ ).

Since $\check{F}$ is stationary, we have

o_{i^{\prime}}(j^{\prime})\leq o_{i}(j)<s_{i^{\prime}}(j^{\prime})<f_{i^{\prime}}(j^{\prime})<o_{i^{\prime}}(j^{\prime}+\ell)<s_{i}(j).

Then, for some $0<k<\ell$ , there is a cycle $\omega_{i^{\prime}}(j^{\prime}+k)$ where $r_{i^{\prime}}$ changes its state from $B$ to $G$ . It is a contradiction since $\sigma_{i}(o_{i^{\prime}}(j^{\prime})+k)=Bk$ . $\Box$

Recall that $\Psi_{i}=(\psi_{i}(1),\psi_{i}(2),\ldots)\subseteq\Omega_{i}$ , where $\psi_{i}(j)$ is the cycle of $r_{i}$ in which it changes its state for the $j$ th time. Scheduler $\mathcal{S}_{VP}$ accepts every cycle $\psi_{i}\in\Psi_{i}$ in which $r_{i}$ changes its state from $Bk$ to $R$ and accepts no other cycles.

Proposition 6

Suppose that $\mathcal{A}$ is vicinity preserving. Then if any pair of cycles $\psi_{i}(j)$ and $\psi_{i^{\prime}}(j^{\prime})$ in $\Lambda$ such that (in $\check{F}$ ) $r_{i^{\prime}}\in S_{i}$ and $\psi_{i}(j)\stackrel{{\scriptstyle*}}{{\parallel}}\psi_{i^{\prime}}(j^{\prime})$ satisfies that $\psi_{i}(j)\parallel\psi_{i^{\prime}}(j^{\prime})$ , then $\check{F}$ is consistent.

Proof. Since $\mathcal{A}$ is vicinity preserving, $r_{i^{\prime}}\in S_{i}$ if and only if $r_{i}\in S_{i^{\prime}}$ and $dist(\pi_{i}(j),\pi_{i^{\prime}}(j^{\prime}))>1$ if $r_{i^{\prime}}\not\in S_{i}$ . $\Box$

Lemma 16

$\check{F}$ is consistent.

Proof. Assume that there are two cycles $\psi_{i}(j)$ and $\psi_{i^{\prime}}(j)$ in $\Lambda$ such that (in $\check{F}$ ) $\psi_{i}(j)\stackrel{{\scriptstyle*}}{{\parallel}}\psi_{i^{\prime}}(j^{\prime})$ , $r_{i}\in S_{i^{\prime}}$ , and $\psi_{i}(j)\not\parallel\psi_{i^{\prime}}(j^{\prime})$ , to derive a contradiction. Let $\psi_{i}(j)=(o_{i}(j),s_{i}(j),f_{i}(j))$ .

Since $\psi_{i}(j)\stackrel{{\scriptstyle*}}{{\parallel}}\psi_{i^{\prime}}(j^{\prime})$ , there are cycles $\psi_{i_{h}}(j_{h})$ such that $\psi_{i_{h}}(j_{h})\parallel\psi_{j_{h+1}}(j_{h+1})$ for all $h=1,2,\ldots,\ell-1$ , where $(i_{1},j_{1})=(i,j)$ and $(i_{\ell},j_{\ell})=(i^{\prime},j^{\prime})$ . Note that in cycle $\psi_{i_{h}}(j_{h})$ , $r_{i_{h}}$ changes its state from $Bk$ to $R$ . Recall that in the proof of Lemma 13, we showed that $\sigma_{i^{\prime}}(o_{i}(j))$ is either $c(j)$ or $c(j+1)$ . Then in cycles $\psi_{i_{1}}(j_{1})$ and $\psi_{i_{2}}(j_{2})$ , $r_{i_{1}}$ and $r_{i_{2}}$ change their states to he same state $R$ for the $k$ th time for some $k$ , since $\psi_{i_{1}}(j_{1})\parallel\psi_{i_{2}}(j_{2})$ . Thus, in $\psi_{i_{1}}(j_{1})$ and $\psi_{i_{\ell}}(j_{\ell})$ , $r_{i}$ and $r_{i_{\ell}}$ change their states to $R$ for the $k$ th time.

Since $r_{i_{\ell}}\in S_{i_{1}}$ and $\psi_{i_{1}}(j_{1})\not\parallel\psi_{i_{\ell}}(j_{\ell})$ , we assume that $f_{i_{1}}(j_{1})<o_{i_{\ell}}(j_{\ell})$ by the stationarity. Since $\psi_{i_{\ell}}\in\Lambda$ , $\sigma_{i_{1}}(o_{i_{\ell}}(j_{\ell}))\neq R$ , which means that there is a cycle $\psi_{i_{1}}(h_{1})$ for some $h_{1}>j_{1}$ , in which $r_{i_{1}}$ changes its state from $R$ to $B$ . Obviously, $s_{i_{1}}(h_{1})<o_{i_{\ell}}(j_{\ell})$ .

Consider $c_{\ell}=\sigma_{i_{\ell}}(o_{i_{1}}(h_{1}))$ . By definition, $c_{\ell}\in\{W,R,B\}$ . Observe that $c_{\ell}=R$ means that $c_{\ell}=R^{(k)}$ and $c_{\ell}=B$ means that $c_{\ell}=B^{(k)}$ . Thus, $c_{\ell}=W$ , because $r_{i_{\ell}}$ changes its state to $R^{(k)}$ in $\phi_{i_{\ell}}(j_{\ell})$ . Then, there is a cycle $\psi_{i_{\ell}}(h_{\ell})$ such that $o_{i_{1}}(h_{1})<o_{i_{\ell}}(h_{\ell})$ and $h_{\ell}<j_{\ell}$ , and $r_{i_{\ell}}$ changes its state from $W$ to $Bk$ in $\psi_{i_{\ell}}(h_{\ell})$ .

Consider $c_{\ell-1}=\sigma_{i_{\ell-1}}(o_{i_{\ell}}(h_{\ell}))$ . By the same argument above, $c_{\ell-1}=W$ . Thus, $c_{h}=W$ or all $1\leq h\leq\ell$ . It is a contradiction, since $r_{i_{1}}$ changes its state to $W$ (in $Y^{(k)}$ ) from $R^{(k)}$ after $\psi_{i_{1}}(h_{1})$ . $\Box$

Lemma 17

$\check{F}$ is serializable.

Proof. Let $\mathcal{G}=(\{\Lambda_{0},\Lambda_{1},\ldots,\},\Rightarrow)$ , where $\Lambda_{0},\Lambda_{1},\ldots$ is the equivalence classes of $\Lambda$ with respect to $\stackrel{{\scriptstyle*}}{{\parallel}}$ .

If two cycles $\omega_{i}(j)$ and $\omega_{i^{\prime}}(j^{\prime})$ are in the same class $\Lambda_{m}$ , i.e., $\omega_{i}(j)\stackrel{{\scriptstyle*}}{{\parallel}}\omega_{i^{\prime}}(j^{\prime})$ , as we showed in the proof of Lemma 15, $r_{i}$ and $r_{i^{\prime}}$ change their states to the same state $R^{(k)}$ for some $k$ .

Suppose that $\omega_{i}(j)\rightarrow\omega_{i^{\prime}}(j^{\prime})$ . Then, in $\omega_{i}(j)$ , $r_{i}$ changes its state to $R^{(k)}$ for some $k$ , and in $\omega_{i^{\prime}}(j^{\prime})$ , $r_{i^{\prime}}$ changes its state to $R^{(k^{\prime})}$ for some $k^{\prime}$ . By definition, $\sigma_{i}(o_{i^{\prime}}(j^{\prime}))\neq R$ , which implies $k<k^{\prime}$ .

If $\check{F}$ is not serializable, there is a loop in $\mathcal{G}$ , which is a contradiction. $\Box$

Lemma 18

Suppose that $\mathcal{A}$ is vicinity preserving. $\check{F}$ is natural.

Proof. Let $T=(\Lambda_{0},\Lambda_{1},\Lambda_{2},\ldots)$ be any topological sort of $\mathcal{G}$ . Consider any pair of cycles $\psi_{i}(j)$ and $\psi_{i^{\prime}}(j^{\prime})$ in $\Lambda$ such that (in $\check{F}$ ) $k^{\prime}\leq k<k^{\prime\prime}$ , where $\psi_{i}(j)\in\Lambda_{k}$ , $\psi_{i^{\prime}}(j^{\prime}-1)\in\Lambda_{k^{\prime}}$ , and $\psi_{i^{\prime}}(j^{\prime})\in\Lambda_{k^{\prime\prime}}$ . (We assume that $k^{\prime}=-1$ when $j^{\prime}=1$ for the consistency.)

If $r_{i^{\prime}}\not\in S_{i}(j)$ , then $dist(\pi_{i}(j),\pi_{i^{\prime}}(j^{\prime}))>0$ since $\mathcal{A}$ is vicinity preserving.

Suppose that $r_{i^{\prime}}\in S_{i}(j)$ . If $o_{i}(j)\geq o_{i^{\prime}}(j^{\prime})$ , since $\omega_{i}(j)\not\parallel\omega_{i^{\prime}}(j^{\prime})$ , $\omega_{i^{\prime}}(j^{\prime})\rightarrow\omega_{i}(j)$ , which is a contradiction since $k<k^{\prime}$ . Thus, $o_{i}(j)<o_{i^{\prime}}(j^{\prime})$ . $\Box$

By Lemmas 13, 14, 15, 16, 17, and 18, we have the following theorem.

Theorem 19

For any vicinity preserving algorithm $\mathcal{A}$ for non-luminous SSYNC mobile robots, color-based synchronizer $\mathcal{S}_{VP}$ is correct.

5 Conclusion

In this paper, we investigated synchronization by ASYNC robots with limited visibility. We started with a sufficient condition for an ASYNC execution to have a similar SSYNC execution. Our condition consists of stationarity, pairwise alignment, consistency, serializability, and naturality on the timing of Look-Compute-Move cycles and visibility relation among the robots. We then showed the necessity of the five properties under a randomized adversary that selects non-rigid movement and asynchronous observations of the robots. Our randomized impossibility argument is a novel and stronger technique than a worst-case (deterministic) analysis. Finally, we presented a color-based synchronizer for luminous ASYNC robots together with the limit of color-based synchronizers. We showed that there exists an algorithm for which no color-based synchronizer can guarantee the five properties, if the algorithm is not visibility preserving. Then, we provided a color-based synchronizer that, for a given vicinity preserving algorithm $\mathcal{A}$ , produces an ASYNC execution that satisfies the five properties. Thus, luminous ASYNC robots can simulate vicinity preserving algorithms designed for (non-luminous) SSYNC robots. There are important open problems about a necessary and sufficient condition for an algorithm to have a luminous synchronizer. The requirement of our color-based synchronizer is that an algorithm $\mathcal{A}$ is vicinity preserving. It is open whether there exists a color-based synchronizer and a general luminous synchronizer that works for visibility preserving algorithms.

Acknowledgment

The authors would like to thank Prof. Toshio Nakata for his precious comments on the infinite product of a Borel probability measure space and Prof. Giovanni Viglietta for precious discussion in University of Ottawa.

References

[1] Dana Angluin, James Aspnes, Zoë Diamadi, Michael J. Fischer, and René Peralta. Computation in networks of passively mobile finite-state sensors. Distributed Computing, 18(4):235–253, 2006.
[2] Mark Cieliebak, Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro. Distributed computing by mobile robots: gathering. SIAM Journal on Computing, 41(4):829–879, 2012.
[3] Shantanu Das, Paola Flocchini, Giuseppe Prencipe, Nicola Santoro, and Masafumi Yamashita. Autonomous mobile robots with lights. Theoretical Computer Science, 609:171–184, 2016.
[4] Zahra Derakhshandeh, Shlomi Dolev, Robert Gmyr, Andréa W. Richa, Christian Scheideler, and Thim Strothmann. Brief announcement: Amoebot – a new model for programmable matter. In Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2014), pages 220–222, 2014.
[5] Zahra Derakhshandeh, Robert Gmyr, Thim Strothmann, Rida Bazzi, Andréa W. Richa, and Christian Scheideler. Leader election and shape formation with self-organizing programmable matter. In Proceedings of the 21st DNA Computing and Molecular Programming, pages 117–132, 2015.
[6] Giuseppe A. Di Luna, Paola Flocchini, Nicola Santoro, and Giovanni Viglietta. Turingmobile: A turing machine of oblivious mobile robots with limited visibility and its applications. In Proceedings of the 32nd International Symposium on Distributed Computing (DISC 2018), pages 19:1–19:18, 2018.
[7] Giuseppe A. Di Luna, Paola Flocchini, Nicola Santoro, Giovanni Viglietta, and Yukiko Yamauchi. Shape formation by programmable particles. Distributed Computing, 33:69––101, 2020.
[8] Yoann Dieudonné, Franck Petit, and Vincent Villain. Leader election problem versus pattern formation problem. In Proceedings of the 24th International Symposium on Distributed Computing (DISC2010), pages 267–281. Springer Berlin Heidelberg, 2010.
[9] Adrian Dumitrescu, Ichiro Suzuki, and Masafumi Yamashita. Formations for fast locomotion of metamorphic robotic systems. The International Journal of Robotics Research, 23(6):583–593, 2004.
[10] Adrian Dumitrescu, Ichiro Suzuki, and Masafumi Yamashita. Motion planning for metamorphic systems: feasibility, decidability, and distributed reconfiguration. IEEE Transactions on Robotics and Automation, 20:409–418, 2004.
[11] Paola Flocchini, Giuseppe Prencipe, Nicola Santoro, and Peter Widmayer. Gathering of asynchronous robots with limited visibility. Theoretical Computer Science, 337:147–168, 2005.
[12] Paola Flocchini, Giuseppe Prencipe, Nicola Santoro, and Peter Widmayer. Arbitrary pattern formation by asynchronous, anonymous, oblivious robots. Theoretical Computer Science, 407:412–447, 2008.
[13] Paola Flocchini, Nicola Santoro, Giovanni Viglietta, and Masafumi Yamashita. Rendezvous with constant memory. Theoretical Computer Science, 621:57––72, 2016.
[14] Paola Flocchini, Nicola Santoro, and Koichi Wada. On memory, communication, and synchronous schedulers when moving and computing. In Proceedings of the 23rd International Conference on Principles of Distributed Systems (OPODIS 2019), pages 25:1–25:17, 2020.
[15] Nao Fujinaga, Yukiko Yamauchi, Hirotaka Ono, Shuji Kijima, and Masafumi Yamashita. Pattern formation by oblivious asynchronous mobile robots. SIAM Journal on Computing, 44(3):740–785, 2015.
[16] Nao Fujinaga, Yukiko Yamauchi, Hirotaka Ono, Shuji Kijima, and Masafumi Yamashita. Erratum: Pattern formation by oblivious asynchronous mobile robots, 2017. http://tcs.inf.kyushu-u.ac.jp/ yamauchi/publications.html.
[17] Ichiro Suzuki and Masafumi Yamashita. Distributed anonymous mobile robots: Formation of geometric patterns. SIAM Journal on Computing, 28(4):1347–1363, 1999.
[18] Terence Tao. An Introduction to Measure Theory. American Mathematical Society, 2011.
[19] Masafumi Yamashita and Ichiro Suzuki. Characterizing geometric patterns formable by oblivious anonymous mobile robots. Theoretical Computer Science, 411:2433–2453, 2010.
[20] Yukiko Yamauchi and Masafumi Yamashita. Pattern formation by mobile robots with limited visibility. In Proceedings of the 20th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2013), pages 201–212. Springer International Publishing, 2013.