11institutetext: Computer Science and Engineering, Michigan State University
11email<EMAIL_ADDRESS>
# Lattice Linearity in Assembling Myopic Robots on an Infinite Triangular Grid

Arya Tanmay Gupta  Sandeep S Kulkarni

###### Abstract

In this paper, we study the problem of gathering distance-1 myopic robots on
an infinite triangular grid. We show that the algorithm developed by Goswami
et al. (SSS, 2022) is lattice linear. This implies that a distributed
scheduler, assumed therein, is not required for this algorithm: it runs
correctly in asynchrony. It also implies that the algorithm works correctly
even if the robots are equipped with a unidirectional camera to see the
neighbouring robots (rather than an omnidirectional one, which would be
required under a distributed scheduler). Due to lattice linearity, we can
predetermine the point of gathering. We also show that this algorithm
converges in $2n$ rounds, which is lower than that ($2.5(n+1)$ rounds) shown
in Goswami et al.

###### Keywords:

robot gatheringinfinite triangular gridlattice linearbounding
polygonconvergence time

##  1 Introduction

A parallel processing system contains multiple processes running to solve one
problem. Each process may store some data. While the system executes, all
processes perform executions based on the information that they read from each
other. The goal of these processes is to reach a state where the problem is
deemed solved. To ensure correct execution, synchronization primitives are
deployed. Synchronization ensures that the processes read the latest copy of
data.

In some of the synchronization models, a selected process acts as a scheduler
for the rest of the processes. A scheduler/daemon is a process whose function
is to choose one, some, or all processes in a time step, throughout the
execution, so that the selected processes can evaluate their guards and take
the corresponding action. A central scheduler chooses only one process per
time step. A distributed scheduler one or more nodes, possibly arbitrarily,
per time step. A synchronous scheduler chooses all the processes in each time
step.

Enforcing synchronization adds cost to the system. For this reason, the
community is interested in developing algorithms that require minimal
synchronization. The recent introduction of lattice linearity has shown that
algorithms can be developed in such a way that the processes can execute
asynchronously. The key idea of lattice linearity is that a process/node
determines that its local state is not feasible in any reachable optimal
global state. In other words, it has to change its state to reach an optimal
state. Thus, if node $i$ changes its state from $st.i$ to $st^{\prime}.i$ it
never revisits state $st.i$ again. Hence, it can change its state even if it
is relying on the old values of its neighbours. Thus, the nodes can run
without synchronization and the system is guaranteed to reach an optimal
state.

Concepts of lattice linearity can be used to develop new lattice linear
algorithms or to study if existing algorithms exploit lattice linearity. If
existing algorithms can exploit lattice linearity, it would imply that we can
eliminate the synchronization assumptions – thereby saving the time and
resources involved in synchronization during their execution. For example,
lattice linearity was found to be exploited by Gale-Shapley’s algorithm for
stable marriage [8], Johnson’s algorithm for shortest paths in graphs [8] and
by Gale’s top trading cycle algorithm for housing market [9].

In this paper, we study the problem of gathering distance-1 myopic robots on
an infinite triangular grid. Authors of [10] showed this algorithm to work
correctly under a distributed scheduler. We demonstrate that this algorithm is
lattice linear. Hence, it will run correctly even if the robots run in
asynchrony.

###  1.1 Contributions of the paper

  * •

We show that the algorithm developed by Goswami et al. [10] is lattice linear.
Hence, this algorithm will run correctly even if the robots run in asynchrony.

  * •

Lattice linearity follows that the moves of the robots are predictable. This
allows us to show tighter bounds to the arena traversed by the robots under
the algorithm. Consequently, we obtain a better convergence time bound for
this algorithm, which is lower than that showed in [10].

  * •

We show that the gathering point of the robots can be uniquely determined from
the initial global state.

  * •

We also show that this algorithm converges in $2n$ rounds, which is lower as
compared to the time complexity bound ($2.5(n+1)$ rounds) shown in [10].

  * •

We present a revised version of this algorithm. The revised algorithm has
simpler guards and demonstrates lattice linearity more clearly. It converges
in the same number of rounds.

  * •

Because of lattice linearity, this algorithm the algorithm works correctly
even if the robots are equipped with a unidirectional camera to see
neighbouring robots. In other words, the robots can use old information about
the presence of robots at any number of locations in their neighbourhood.
Authors of [10] assumed a distributed scheduler, which would require an
omnidirectional camera, capable to get fresh values from all neighbouring
locations.

###  1.2 Organization of the paper

In Section 2, we describe the notations and definitions that we utilize in
this paper. In Section 3, we describe the problem of gathering distance-1
myopic robots on an infinite triangular grid. In Section 4, we describe the
lattice linearity of the algorithm in [10]; we also show some tighter bounds
on the properties of this algorithm. We provide a revised algorithm for this
problem in Section 5. We discuss the related work in Section 6 and conclude in
Section 7.

##  2 Preliminaries

A parallel/distributed algorithm consists of nodes where each node is
associated with a set of variables. A global state, say $s$, is obtained by
assigning each variable of each node a value from its respective domain. $s$
is represented as a vector, where $s[i]$ itself is a vector of the variables
of node $i$. $S$ denotes the state space, which is the set of all global
states that a given system can obtain.

Each node is associated with actions. Each action at node $i$ checks the
values of other nodes and updates its own variables. An action is of the form
$g\longrightarrow a_{c}$, where $g$ is the guard (a Boolean predicate
involving variables of $i$ and other nodes) and $a_{c}$ is an instruction that
updates the variables of $i$ atomically.

A move is an event where a node changes its state when one of its guards
evaluates to true. A round is a sequence of events in which every node
evaluates its guards at least once, and makes a move accordingly.

An algorithm $A$ is self-stabilizing with respect to the subset $S_{o}$ of $S$
iff (1) convergence: starting from an arbitrary state, any sequence of
computations of $A$ reaches a state in $S_{o}$, and (2) closure: any
computation of $A$ starting from $S_{o}$ always stays in $S_{o}$. We assume
$S_{o}$ to be the set of optimal states: the system is deemed converged once
it reaches a state in $S_{o}$. $A$ is a silent self-stabilizing algorithm if
no node makes a move once a state in $S_{o}$ is reached.

###  2.1 Execution without Synchronization

Typically, we view the computation of an algorithm as a sequence of global
states $\langle s_{0},s_{1},\cdots\rangle$, where $s_{t+1},t\geq 0,$ is
obtained by executing some action by one or more nodes in $s_{t}$. For the
sake of discussion, assume that only node $i$ executes in state $s_{t}$. The
computation prefix uptil $s_{t}$ is $\langle s_{0},s_{1},\cdots,s_{t}\rangle$.
The state that the system traverses to after $s_{t}$ is $s_{t+1}$. Under
proper synchronization, $i$ would evaluate its guards on the current local
states of its neighbours in $s_{t}$.

To understand the execution in asynchrony, let $x(s)$ be the value of some
variable $x$ in state $s$. If $i$ executes in asynchrony, then it views the
global state that it is in to be $s^{\prime}$, where
$x(s^{\prime})\in\\{x(s_{0}),x(s_{1}),\cdots,x(s_{t})\\}.$ In this case,
$s_{t+1}$ is evaluated as follows. If all guards in $i$ evaluate to false,
then the system will continue to remain in state $s_{t}$, i.e.,
$s_{t+1}=s_{t}$. If a guard $g$ evaluates to true then $i$ will execute its
corresponding action $a_{c}$. Here, we have the following observations: (1)
$s_{t+1}[i]$ is the state that $i$ obtains after executing an action in
$s^{\prime}$, and (2) $\forall j\neq i$, $s_{t+1}[j]=s_{t}[j]$.

The model described above allows nodes to read old values of other nodes
arbitrarily. In this paper, however, we require that the nodes (robots) take a
snapshot of their surroundings after every move. However, doing so does not
require synchronization.

###  2.2 Embedding a $<$-lattice among Global States

Let $s$ denote a global state, and let $s[i]$ denote the state of node $i$ in
$s$. First, we define a total order $<_{l}$; all local states of a node $i$
are totally ordered under $<_{l}$. Using $<_{l}$, we define a partial order
$<_{g}$ among global states as follows.

We say that $s<_{g}s^{\prime}$ iff $(\forall i:s[i]=s^{\prime}[i]\lor
s[i]<_{l}s^{\prime}[i])\land(\exists i:s[i]<_{l}s^{\prime}[i])$. Also,
$s=s^{\prime}$ iff $\forall i~{}s[i]=s^{\prime}[i]$. For brevity, we use $<$
to denote $<_{l}$ and $<_{g}$: $<$ corresponds to $<_{l}$ while comparing
local states, and $<$ corresponds to $<_{g}$ while comparing global states. We
also use the symbol ‘$>$’ which is such that $s>s^{\prime}$ iff
$s^{\prime}<s$. Similarly, we use symbols ‘$\leq$’ and ‘$\geq$’; e.g., $s\leq
s^{\prime}$ iff $s=s^{\prime}\vee s<s^{\prime}$. We call the lattice, formed
from such partial order, a $<$-lattice.

###### Definition 1

$<$-lattice. Given a total relation $<_{l}$ that orders the states visited by
a node $i$ (for each $i$) the $<$-lattice corresponding to $<_{l}$ is defined
by the following partial order: $s<_{g}s^{\prime}$ iff $(\forall i\ \
s[i]\leq_{l}s^{\prime}[i])\wedge(\exists i\ \ s[i]<_{l}s^{\prime}[i])$.

In the $<$-lattice discussed above, we can define the meet and join of two
states in the standard way: the meet (respectively, join), of two states
$s_{1}$ and $s_{2}$ is a state $s_{3}$ where $\forall i,s_{3}[i]$ is equal to
$min(s_{1}[i],s_{2}[i])$ (respectively, $max(s_{1}[i],s_{2}[i])$), where
$\min(x,y)=\min(y,x)=x$ iff $(x<_{l}y\lor x=y)$, and $\max(x,y)=\max(y,x)=y$
iff $(y>_{l}x\lor y=x)$. For $s_{1}$ and $s_{2}$, their meet (respectively,
join) has paths to (respectively, is reachable from) both $s_{1}$ and $s_{2}$.

A $<$-lattice, embedded in the state space, is useful for permitting the
algorithm to execute asynchronously. Under proper constraints on the structure
of $<$-lattice, convergence can be ensured.

###  2.3 Lattice Linear Problems

A lattice linear problem $P$ can be represented by a predicate $\mathcal{P}$
such that if any node $i$ is violating $\mathcal{P}$ in a state $s$, then it
must change its state. Otherwise, the system will not satisfy $\mathcal{P}$.
Let $\mathcal{P}(s)$ be true iff state $s$ satisfies $\mathcal{P}$. A node
violating $\mathcal{P}$ in $s$ is called an impedensable node (an impediment
to progress if does not execute, indispensable to execute for progress).
Formally,

###### Definition 2

[8] Impedensable node.
$\textsc{Impedensable}(i,s,\mathcal{P})\equiv\lnot\mathcal{P}(s)$ $\land$
$(\forall
s^{\prime}>s:s^{\prime}[i]=s[i]\implies\lnot\mathcal{P}(s^{\prime}))$.

If a node $i$ is impedensable in state $s$, then in any state $s^{\prime}$
such that $s^{\prime}>s$, if the state of $i$ remains the same, then the
algorithm will not converge. Thus, predicate $\mathcal{P}$ induces a total
order among the local states visited by a node, for all nodes. Consequently,
the discrete structure that gets induced among the global states is a
$<$-lattice, as described in Definition 1. We say that $\mathcal{P}$,
satisfying Definition 2, is lattice linear with respect to that $<$-lattice.

There can be multiple arbitrary lattices that can be induced among the global
states. A system cannot guarantee convergence while traversing an arbitrary
lattice. To guarantee convergence, we design the predicate $\mathcal{P}$ such
that it fulfils some properties, and guarantees reachability to an optimal
state. $\mathcal{P}$ is used by the nodes to determine if they are
impedensable, using Definition 2. Thus, in any suboptimal global state, there
will be at least one impedensable node. Formally,

###### Definition 3

[8]Lattice linear predicate. $\mathcal{P}$ is a lattice linear predicate with
respect to a $<$-lattice induced among the global states iff $\forall s\in
S:\lnot\mathcal{P}(s)\Rightarrow\exists
i:\textsc{Impedensable}(i,s,\mathcal{P})$.

Now we complete the definition of lattice linear problems. In a lattice linear
problem $P$, given any suboptimal global state $s$, we can identify all and
the only nodes which cannot retain their local states. $\mathcal{P}$ is thus
designed conserving this nature of the subject problem $P$.

###### Definition 4

Lattice linear problems. A problem $P$ is lattice linear iff there exists a
predicate $\mathcal{P}$ and a $<$-lattice such that

  * •

$P$ is deemed solved iff the system reaches a state where $\mathcal{P}$ is
true,

  * •

$\mathcal{P}$ is lattice linear with respect to the $<$-lattice induced among
the states in $S$, i.e., $\forall s:\neg\mathcal{P}(s)\Rightarrow\exists
i:\textsc{Impedensable}(i,s,\mathcal{P})$, and

  * •

$\forall s:(\forall
i:\textsc{Impedensable}(i,s,\mathcal{P})\Rightarrow(\forall
s^{\prime}:\mathcal{P}(s^{\prime})\Rightarrow s^{\prime}[i]\neq s[i]))$.

Remark: A $<$-lattice, induced under $\mathcal{P}$, allows asynchrony because
if a node, reading old values, reads the current state $s$ as $s^{\prime}$,
then $s^{\prime}<s$. So
$\lnot\mathcal{P}(s^{\prime})\Rightarrow\lnot\mathcal{P}(s)$ because
$\textsc{Impedensable}(i,s^{\prime},\mathcal{P})$ and $s^{\prime}[i]=s[i]$.

###### Definition 5

Self-stabilizing lattice linear predicate. Continuing from Definition 4,
$\mathcal{P}$ is a self-stabilizing lattice linear predicate if and only if
the supremum of the lattice, that $\mathcal{P}$ induces, is an optimal state,
i.e., $\mathcal{P}(supremum(S))=true$.

Note that a self-stabilizing lattice linear predicate $\mathcal{P}$ can also
be true in states other than the supremum of the $<$-lattice.

###  2.4 Lattice Linear Algorithms

Certain problems are non-lattice linear problems. In such problems, there are
instances in which the impedensable nodes cannot be determined naturally,
i.e., in those instances $\exists s:\lnot\mathcal{P}(s)\wedge(\forall
i:\exists s^{\prime}:\mathcal{P}(s^{\prime})\land s[i]=s^{\prime}[i]$). For
such problems, $<$-lattices may be induced algorithmically, through lattice
linear algorithms.

###### Definition 6

Lattice linear algorithms (LLA). Algorithm $A$ is an LLA for a problem $P$,
iff there exists a predicate $\mathcal{P}$ and $A$ induces a $<$-lattice among
the states of $S_{1},...,S_{w}\subseteq S(w\geq 1)$, such that

  * •

State space $S$ of $P$ contains mutually disjoint lattices, i.e.

    * –

$S_{1},S_{2},\cdots,S_{w}\subseteq S$ are pairwise disjoint.

    * –

$S_{1}\cup S_{2}\cup\cdots\cup S_{w}$ contains all the reachable states
(starting from a set of initial states, if specified; if an arbitrary state
can be an initial state, then $S_{1}\cup S_{2}\cup\cdots\cup S_{w}=S$).

  * •

Lattice linearity is satisfied in each subset under $\mathcal{P}$, i.e.,

    * –

$P$ is deemed solved iff the system reaches a state where $\mathcal{P}$ is
true

    * –

$\forall k$, $1\leq k\leq w$, $\mathcal{P}$ is lattice linear with respect to
the partial order induced in $S_{k}$ by $A$, i.e., $\forall s\in
S_{k}:\lnot\mathcal{P}(s)\Rightarrow\exists i\ \
\textsc{Impedensable}(i,s,\mathcal{P})$.

In the next section, we discuss how the gathering problem of distance-1 myopic
robots is not a lattice linear problem is a non-lattice linear problem. The
lattice linear algorithm developed for this problem imposes the lattice
structure among the global states reachable by the system of robots.

###### Definition 7

Self-stabilizing LLA. From Definition 6, $A$ is self-stabilizing only if
$S_{1}\cup S_{2}\cup\cdots\cup S_{w}=S$ and $\forall k:1\leq k\leq w$,
$\mathcal{P}(supremum(S_{k}))=true$.

##  3 Gathering of Distance-1 Myopic Robots on Infinite Triangular Grid
(GMRIT)

This paper focuses on the problem where the input is a swarm of robots with
minimal capabilities. Each robot is present at a vertex on an infinite
triangular grid. In the initial global state, the robots form a connected
graph on the underlying grid. The robots agree on an axis (i.e. a direction
and its orientation). The robots can move only across one edge at a time. Each
robot is myopic, i.e., it can only sense if another robot is present at an
adjacent vertex. Robots do not have an abiliy to communicate with each other.
Under these constraints, it is required that all robots gather at one point.

###  3.1 Problem Statement

The input is a global state $s$ that describes the location of $n$ robots
placed on the grid points of an infinite triangular grid $G$ such that the
robots form a connected graph. The GMRIT problem requires that all robots
gather at one vertex of $G$ and stay forever at that vertex subject to the
following constraints:

  * •

Visibility: A robot can only determine if another robot is present in a
neighbouring location. It cannot exchange data with another robot.

  * •

One Axis Agreement: All robots agree on one axis and the orientation of that
axis. (cf. $y$-axis as shown in Figure 1).

$A$$B$$C$$D$$P$$B^{\prime}$$C^{\prime}$$Q$$E$$J$ $+y$

Figure 1: Robots on an infinite triangular grid: one on every round
highlighted vertex.

All robots are independent and identical from a physical and computational
perspective and do not have an ID. They are oblivious to the coordinates of
their location on the infinite triangular grid $G$. Observe that we can allow
a global state $s$ to be a multiset of vertices, each of which is the location
of a robot. For $s$, its visibility graph is the subgraph of $G$ induced by
the set of vertices in $s$.

Notice that by definition of the problem statement, a solution to GMRIT will
provide silent self-stabilization. An instance of GMRIT is shown in Figure 1.
Here, each round highlighted vertex represents a robot. Observe that the
visibility graph of this global state is a connected graph.

Next, we discuss how GMRIT problem is not a lattice linear problem. This can
be illustrated by a system containing two robots $x_{1}$ and $x_{2}$ present
at locations $l_{1}$ and $l_{2}$ ($l_{1}$ and $l_{2}$ are different vertices
on the same edge) on $G$. In such a system $x_{1}$ can move to $l_{2}$, in
which case, $x_{2}$ is not impedensable, or otherwise, $x_{2}$ can move to
$l_{1}$, in which case, $x_{1}$ is not impedensable. Hence it cannot be
determined which robot is impedensable.

###  3.2 Problem Specific Definitions

Some of the definitions that we discuss in this subsection are from [10]. A
horizontal layer is a line perpendicular to the $y$-axis that passes through
at least one robot. The top layer of a global state $s$ is a horizontal layer
such that there is no horizontal layer above it (cf. $AD$ in Figure 1). Bottom
layer of $s$ is a horizontal layer such that there is no horizontal layer
below it (cf. $BC$ in Figure 1).

A vertical layer is parallel to the $y$-axis such that it passes through at
least one robot. The left layer of $s$ is the vertical layer such that there
is no vertical layer on its left (cf. $AB$ in Figure 1). The right layer of
$s$ is the vertical layer such that there is no vertical layer on its right
(cf. $CD$ in Figure 1).

As seen in Figure 1, vertices in $G$ are intersections of three groups of
parallel lines; one of these groups are lines parallel to the $y$-axis. We use
$p$-axis (positive slope) and $n$ axis (negative slope) to denote the other
group of parallel lines. The positive slant is a line parallel to $p$-axis
(cf. $BP$ in Figure 1) and negative slant is a line parallel to $n$-axis (cf.
$CP$ in Figure 1). The bottom $l2r$ slant of $s$ is a negative slant that
passes through a robot such that there is no negative slant on its left
passing through a robot (cf. $B^{\prime}Q$ in Figure 1). The bottom $r2l$
slant of $s$ is a positive slant that passes through a robot such that there
is no positive slant on its right passing through a robot (cf. $C^{\prime}Q$
in Figure 1). Note that a negative slant and a positive slant can be
imaginary, or a line in $G$.

The depth of $s$ is the distance between its top layer and its bottom layer.
The width of $s$ is defined as the distance between its left layer and right
layer.

As shown in Figure 1, a polygon $ABPCD$ is a bounding polygon of a global
state $s$ if (1) $AB$ and $CD$ are line segments of the left layer and the
right layer of $s$ respectively, (2) $AD$ and $BC$ are line segments of the
top layer and the bottom layer of $s$ respectively, and (3) $P$ is the point
of intersection between the negative slant passing through $B$ and the
positive slant passing through $C$.

Note that these definitions (top/bottom layer, etc.) are only used for
discussion of the protocol and proofs. The robots are not aware of them.
Similarly, the robots can distinguish between $up$ and $down$, but not $left$
and $right$.

###  3.3 General Idea of the Algorithm

A robot has six possible neighbours. The naming convention for these locations
is as shown in Figure 2 (a) [10]. Since each robot has 6 neighbouring
locations, it can be in one of $2^{6}$ possible local states. Of these, the
robot can move in only 11 states. Of these 7 states are shown in Figure 2 (b)
[10]. The other 4 states are mirror images of those shown in cases 2, 5, 6 and
7 in Figure 2 (b).

$i$$v_{1}$$v_{2}^{\ell}$$v_{2}^{r}$$v_{3}^{\ell}$$v_{3}^{r}$$v_{4}$

$\ast$

$\ast$

$\ast$

$\ast$

case 1case 2case 3case 4

$\ast$

$\ast$

$\ast$

case 5case 6case 7

$+y$

Figure 2: (a) Naming conventions for neighbourhood of a robot. (b) Cases where
a node is impedensable. Note that the mirror images of these local states are
also impedensable.

As an illustration, in Case 3, the center robot (marked with dark circle) sees
that there are two robots in its vicinity in locations marked with hollow
circle. Then, the center robot moves to location marked with an asterisk.

Authors of [10] show that the robots do not move out of the bounding polygon.
They also show that the visibility graph induced among the robots stay
connected, and the dimensions of the bounding polygon reduce with every round.

##  4 GSGS Algorithm [10] for GMRIT problem

In this section, we reword the algorithm in [10] to demonstrate its lattice
linearity. We define the following macros. For a set $L$ of locations around a
node $i$, $\textsc{At}(i,L)$ is true iff if there is at least one robot at
each location in $L$. $\textsc{Only-At}(i,L)$ is true iff $\textsc{At}(i,L)$
and there is no other robot at locations other than locations in $L$. A robot
$i$ is extreme if (1) there is no robot on top ($v_{4}.i$) of $i$ and (2) if
there is a robot on the left ($v_{2}^{l}$ or $v_{3}^{l}$) of $i$, then there
is no robot on the right ($v_{2}^{r}$ or $v_{3}^{r}$) of $i$. If a robot $i$
is extreme, and there is no robot around it, then $i$ is a terminating robot.
If $i$ is extreme, and there is a robot only on $v_{3}(i)$ or there are robots
only on both $v_{1}(i)$ and $v_{3}(i)$, then $i$ is a staying robot.

If $i$ is extreme, and there is a robot on $v_{1}(i)$ and no robot on
$v_{3}(i)$, then $i$ is a downward impedensable robot. If $i$ is not a
downward impedensable robot, not a staying robot, and not a terminating robot,
then it is a downslant impedensable robot. If $i$ is not an extreme robot, and
there is a robot on both $v_{2}(i)$ and no robot at its y-coordinate $>$ 0,
then $i$ is a non-extreme impedensable robot.

$\begin{array}[]{|l|}\hline\cr\textsc{Extreme}(i)\equiv\lnot\textsc{At}(i,\\{v_{4}\\})\land\\\
\quad\quad((\textsc{At}(i,\\{v_{2}^{r}\\})\lor\textsc{At}(i,\\{v_{3}^{r}\\}))\Rightarrow(\lnot\textsc{At}(i,\\{v_{2}^{\ell}\\})\land\lnot\textsc{At}(i,\\{v_{3}^{\ell}\\})))\\\
\textsc{Terminating}(r)\equiv\textsc{Extreme}(i)\land(\forall
q\in\\{v_{1},v_{2}^{r},v_{3}^{r},v_{4},v_{3}^{\ell},v_{2}^{\ell}\\}:\lnot\textsc{At}(i,\\{q\\})).\\\
\textsc{Staying}(i)\equiv\textsc{Extreme}(i)\land(\textsc{Only-
At}(i,\\{v_{3}^{r}\\})\lor\textsc{Only-At}(i,\\{v_{3}^{l}\\})\lor\\\
\quad\quad\textsc{Only-At}(i,\\{v_{1},v_{3}^{r}\\})\lor\textsc{Only-
At}(i,\\{v_{1},v_{3}^{\ell}\\})).\\\
\textsc{Downward}(i)\equiv\textsc{Extreme}(i)\land\textsc{At}(i,\\{v_{1}\\})\land\lnot(\textsc{At}(i,\\{v_{3}^{r}\\})\lor\textsc{At}(i,\\{v_{3}^{\ell}\\})).\\\
\textsc{Downslant-
Right}(i)\equiv\textsc{Extreme}(i)\land\lnot\textsc{Downward}(i)\land\lnot\textsc{Staying}(i)\land\\\
\quad\quad\lnot\textsc{Terminating}(r)\land\textsc{At}(i,\\{v_{2}^{r}\\}).\\\
\textsc{Downslant-
Left}(i)\equiv\textsc{Extreme}(i)\land\lnot\textsc{Downward}(i)\land\lnot\textsc{Staying}(i)\land\\\
\quad\quad\lnot\textsc{Terminating}(r)\land\textsc{At}(i,\\{v_{2}^{\ell}\\}).\\\
\textsc{Non-
Extreme}(i)\equiv\lnot\textsc{Extreme}(i)\land\textsc{At}(i,\\{v_{2}^{r},v_{2}^{\ell}\\})\land\\\
\quad\quad\lnot(\textsc{At}(i,\\{v_{3}^{r}\\})\lor\textsc{At}(i,\\{v_{3}^{\ell}\\})\lor\textsc{At}(i,\\{v_{4}\\})).\\\
\textsc{Impedensable-GSGS}(i)\equiv\textsc{Downward}(i)\lor\textsc{Downslant-
Right}(i)\lor\\\ \quad\quad\textsc{Downslant-Left}(i)\lor\textsc{Non-
Extreme}(i).\\\ \hline\cr\end{array}$

The algorithm is described as follows. If a robot $i$ is downward
impedensable, then $i$ moves downwards to $v_{1}(i)$. If $i$ is downslant
impedensable, then $i$ moves to $v_{2}(i)$. If $i$ is a non-extreme
impedensable robot, then $i$ moves to $v_{1}(i)$.

###### Algorithm 1

Rules for robot $i$.

$\begin{array}[]{|l|}\hline\cr\textsc{Impedensable-
GSGS}(i)\longrightarrow\begin{cases}move(i,v_{1}(i))&\text{if
$\textsc{Downward}(i)$}\\\ move(i,v_{2}^{r}(i))&\text{if $\textsc{Downslant-
Right}(i)$}\\\ move(i,v_{2}^{\ell}(i))&\text{if $\textsc{Downslant-
Left}(i)$}\\\ move(i,v_{1}(i))&\text{if $\textsc{Non-
Extreme}(i)$}\end{cases}{}\\\ \hline\cr\end{array}$

In [10], authors assume a distributed scheduler. Next, we show that Algorithm
1 is lattice linear, Thus, it will be correct even in asynchrony.

###  4.1 Lattice Linearity

In this subsection, we show lattice linearity of Algorithm 1. Among the lemmas
and theorems presented here, Lemma 3 and Lemma 4 are adopted from [10]. We use
them to help prove some properties of Algorithm 1. All other results show or
arise from the lattice linearity of Algorithm 1.

###### Lemma 1

The predicate $\forall i:\lnot\textsc{Impedensable-GSGS}(i)$ is a lattice
linear predicate on $n$ robots, and the visibility graph does not get
disconnected by the actions under Algorithm 1.

###### Proof

In this proof, we consider the 7 cases as shown in Figure 2 (b) and show that
if robot $i$ is impedensable, it must execute to reach the goal state. We show
that if a robot $i$ is impedensable, then there exists at least one robot
around $i$ which does not move until $i$ moves. It means that the gathering
point is not at the location of $i$. Furthermore, since it is essential for
convergence that the visibility graph stays connected, this proof also shows
that it stays connected throughout the execution of Algorithm 1.

Case 1: This robot $i$ is a downward impedensable robot. The other robot that
is present below it is not extreme and is also not a non-extreme impedensable
robot because $i$ is present above it, so it will not move until $i$ changes
its location.

Case 2: This robot $i$ is a downward impedensable robot. There are two robots,
$x_{1}$ and $x_{2}$, present at locations $v_{1}(i)$ and $v_{2}(i)$
respectively. $x_{1}$ is not extreme and is also not non-extreme impedensable
because $i$ is present above it. So $x_{1}$ will not move until $i$ changes
its location. $x_{2}$ may be impedensable. $x_{2}$ can only move to the
location of $x_{1}$ thereby resulting in case 1. In this possibility, the
robot $i$ remains impedensable and its required action does not change.

Case 3: This robot $i$ is a non-extreme impedensable robot. There are two
robots, $x_{1}$ and $x_{2}$, present at locations $v_{2}(i)$-left and
$v_{2}(i)$-right respectively. For $x_{1}$ or $x_{2}$ to be impedensable,
there must be some robot at the $v_{1}(i)$ location, which is not the case,
thus, they are not impedensable. Hence, $x_{1}$ and $x_{2}$ will not move
until $i$ changes its location.

Case 4: This robot $i$ is a non-extreme impedensable robot. There are three
robots, $x_{1}$, $x_{2}$ and $x_{3}$, present at locations $v_{2}(i)$-left,
$v_{1}(i)$ and $v_{2}(i)$-right respectively. $x_{2}$ is not impedensable.
$x_{1}$ and $x_{3}$ may be impedensable, based on their local states. If one
or both of them move, they will move to the location of $x_{2}$, resulting in
case 2 or case 1. In these possibilities, the robot $i$ remains impedensable
and its required action does not change.

Case 5: This robot $i$ is a downslant impedensable robot. There are two
robots, $x_{1}$ and $x_{2}$, present at locations $v_{2}(i)$ and $v_{3}(i)$
respectively. $x_{1}$ is not extreme and is also not non-extreme impedensable.
So $x_{1}$ will not move until $i$ changes its location. $x_{2}$ may be
impedensable, based on its local state. $x_{2}$ can move to the location of
$x_{1}$ or $i$ thereby resulting in case 7. In this possibility, the robot $i$
remains impedensable and its required action does not change.

Case 6: This robot $i$ is a downslant impedensable robot. There are three
robots, $x_{1}$, $x_{2}$ and $x_{3}$, present at locations $v_{1}(i)$,
$v_{2}(i)$ and $v_{3}(i)$ respectively. $x_{1}$ and $x_{2}$ are not extreme
and are also not non-extreme impedensable. Initially, $x_{1}$ and $x_{2}$
cannot move. $x_{3}$ may be downward impedensable, based on its local state.
$x_{3}$ can only move to the location of $x_{2}$ thereby resulting in case 2.
After this, one or both of $x_{1}$ and $x_{2}$ can move to the location of
$x_{1}$, resulting in case 1. In these possibilities, $i$ remains
impedensable, its required may change, but the graph does not get disconnected
if it executes under case 6.

Case 7: This robot $i$ is a downslant impedensable robot. The other robot
$x_{1}$ that is present at $v_{2}(i)$ is not extreme and is also not a non-
extreme impedensable robot, so $x_{1}$ will not move until $i$ changes its
location. ∎

The robots executing Algorithm 1, as shown in [10], stay in the bounding
polygon $ABPCD$. Next, we show, using the above proof, a tighter polygon
bounding the robots. To define this polygon, we let $Q$ to be the point such
that it is an intersection between the bottom $l2r$ slant of $s$ and the
bottom $r2l$ slant of $s$ (cf. Figure 1). Let $B^{\prime}$ be the point of
intersection between left layer ($AB$) and the bottom $l2r$ slant of $s$ and
let $C^{\prime}$ be the point of intersection between the right layer ($CD$)
and the bottom $r2l$ slant of $s$. We show that the robots never step out of
the polygon $AB^{\prime}QC^{\prime}D$, which is tighter than $ABPCD$.

###### Observation 1

If the neighbouring robot, say $j$ of an impedensable robot $i$ moves then $i$
or $j$ fall under case 5 or case 6.

###### Lemma 2

Throughout the execution of Algorithm 1, the bottom $r2l$ slant and the bottom
$l2r$ slant will not change.

###### Proof

In a global state $s$, a robot present at the bottom $l2r$ slant of $s$ or a
bottom $r2l$ slant of $s$ is represented in cases 5 and 7. From Algorithm 1
and the proof of Lemma 1, if a robot is present at bottom $l2r$ slant
(respectively, bottom $r2l$ slant), it will never move below ($v_{1}(i)$) or
left ($v_{2}^{\ell}(i)$) of its location (respectively, below ($v_{1}(i)$) or
right ($v_{2}^{r}(i)$) of its location). ∎

###### Lemma 3

[10] Throughout the execution of Algorithm 1, left layer does not move
leftwards and right layer does not move rightwards.

###### Lemma 4

[10] In every round of Algorithm 1, the top layer moves at least 1/2 unit in
the negative direction of the $y$-axis.

###### Corollary 1

(From Lemma 2 and Lemma 3) The robots will never step out of the polygon
$AB^{\prime}C^{\prime}DQ$.

###### Theorem 4.1

Algorithm 1 is a lattice linear self-stabilizing algorithm for the GMRIT
problem on $n$ robots executing asynchronously.

###### Proof

From Lemma 2, we have that bottom $l2r$ slant and bottom $r2l$ slant do not
change. From Corollary 1, we have that the robots will never step out of the
polygon $AB^{\prime}C^{\prime}DQ$. From Lemma 4, we have that the top layer
moves down by at least half a unit in the negative direction of $y$-axis. Thus
we have that the robots converge at the point of intersection of the bottom
$l2r$ slant and the bottom $r2l$ slant, and the robots will eventually gather
at that point. ∎

###### Corollary 2

(From Lemma 4, Corollary 1 and Theorem 4.1) The point, $Q$, where the robots
gather, can be uniquely determined from the initial global state.

###  4.2 Time Complexity Properties

In [10], authors showed that Algorithm 1 converges in $2.5(n+1)$ rounds. Based
on Corollary 2 which identifies a predictable gathering point, we show that a
maximum of $2n$ rounds is sufficient, which is a tighter bound.

###### Theorem 4.2

Algorithm 1 converges in $2n$ rounds.

###### Proof

We use Figure 1 to discuss convergence of robots in Algorithm 1. As discussed
in Section 3.2 and Section 4.1, let $A$, $B^{\prime}$, $Q$, $C^{\prime}$ and
$D$ be the points obtained by pairwise intersection of the top layer, left
layer, bottom $l2r$ slant, bottom $r2l$ slant and right layer. Let $h_{\ell}$
be the depth of the line segment $AB^{\prime}$, $h_{r}$ be the depth of the
line segment $C^{\prime}D$, and $w$ be the width of the line segment $AD$.
Note that a unit of length of the depth of $AB^{\prime}$ or $C^{\prime}D$ is
$\sqrt{3}$ times a unit of length of the width of $AD$ due to the geometry of
$G$. Since the robots form a connected graph, $w\leq n$. And, if $w>0$ then
$h_{\ell}+h_{r}\leq n$. If $w=0$, we define $h_{\ell}=0$ and $h_{r}=n$.

In the case where $w=0$, it can be clearly observed that Algorithm 1 converges
in $n$ moves. Next, we consider if $w>0$. Without the loss of generality, let
$h_{r}\geq h_{\ell}$. Thus, $h_{\ell}\leq n/2$.

Let $E$ be the point of intersection between the bottom $l2r$ slant and the
right layer (cf. Figure 1). We draw a horizontal line (perpendicular to the
$y$-axis) through $B^{\prime}$ and use $J$ to denote its intersection with
$DC^{\prime}$. Thus, the depth of $AB^{\prime}JD$ is $h_{\ell}$. Additionally,
observe that the length of $B^{\prime}E$ on the $n$-axis is $w$. Thus the
height of $JE$ is $w/2$ units on the $y$-axis. This means that the depth of
$B^{\prime}EJ$ is $w/2$. By construction of $E$, the depth of
$B^{\prime}QC^{\prime}J$ is upper bounded by the depth of $B^{\prime}EJ$.
Thus, the depth of $B^{\prime}QC^{\prime}J$ cannot exceed $w/2\leq n/2$ units.

Thus, the total depth of $AB^{\prime}QC^{\prime}D$ is equal to the sum of the
depth of $AB^{\prime}JD$ and the depth of $B^{\prime}QC^{\prime}J$, which is
upper bounded by $n/2+n/2=n$ units. From Lemma 4, the total number of rounds
required for the robots to gather is upper bounded by $2n$ moves. ∎

##  5 Revised Algorithm for GMRIT

In this section, we present a revised algorithm that simplifies the proof of
lattice linearity. This algorithm is based on the difficulties involved in the
proof of Lemma 1 where we needed to consider the possible actions taken by the
neighbours of the impedensable robot. Our proof would have been simpler if all
the neighbours of an impedensable robot $i$ could not move until $i$ moves.
Additionally, from 1, we have that if a robot $j$, neighbouring to an
impedensable node $i$, is impedensable, then $i$ or $j$ fall in case $5$ or
case $6$.

These issues can be alleviated by removing cases 5 and 6 from the algorithm.
The macros that we utilize are as follows. A robot is downward impedensable if
its local state is one of those represented in cases 1, 2, 3 or 4 (and their
mirror images; cf Figure 2 (b)). A robot is is downslant impedensable if its
local state is that represented in case 7.

$\begin{array}[]{|l|}\hline\cr\textsc{Downward-
II}(i)\equiv(\textsc{At}(i,\\{v_{1}\\})\land\lnot\textsc{At}(i,\\{v_{3}^{\ell},v_{4},v_{3}^{r}\\}))\lor\textsc{Only-
At}(i,\\{v_{2}^{\ell},v_{2}^{r}\\}).\\\ \textsc{Downslant-Left-
II}(i)\equiv\textsc{Only-At}(i,\\{v_{2}^{\ell}\\}).\\\ \textsc{Downslant-
Right-II}(i)\equiv\textsc{Only-At}(i,\\{v_{2}^{r}\\}).\\\
\hline\cr\end{array}$

The revised algorithm is as follows. A downward impedensable robot moves to
$v_{1}(i)$ location, and a downslant impedensable robot moves to $v_{2}(i)$
location.

###### Algorithm 2

Rules for robot $i$.

$\begin{array}[]{|l|}\hline\cr\textsc{Downward-II}(i)\longrightarrow
move(i,v_{1}(i)).\\\ \textsc{Downslant-Right-II}(i)\longrightarrow
move(i,v_{2}^{r}(i)).\\\ \textsc{Downslant-Left-II}(i)\longrightarrow
move(i,v_{2}^{\ell}(i)).\\\ \hline\cr\end{array}$

In Algorithm 2, because of the removal of cases 5 and 6, any robot around an
impedensable robot does not move. Thus lattice linearity of this algorithm can
be visualized more intuitively. Consequently, we have the following lemma.

###### Lemma 5

The predicate $\forall i:\lnot(\textsc{Downward-II}(i)$ $\lor$
$\textsc{Downslant-Right-II}(i)$ $\lor$ $\textsc{Downslant-Left-II}(i))$, is a
lattice linear predicate on $n$ robots, and the visibility graph does not get
disconnected by the actions under Algorithm 2.

Lemma 4 shows the top-layer moves down in each round. This proof is not
affected by cases 5 and 6, as the robot executing in cases 5 or 6 is not a
top-layer robot. Consequently, Algorithm 2 follows the properties as described
in Lemma 4, Theorem 4.1 and hence Theorem 4.2. Thus, we have the following
theorem.

###### Theorem 5.1

Algorithm 2 is a lattice linear self-stabilizing algorithm for GMRIT problem
on $n$ robots executing asynchronously. It converges in $2n$ rounds, and the
robots gather at $Q$.

##  6 Related Work

Lattice Linearity: The notion of representing problems through a predicate
under which the states form a lattice was introduced in [8]. We call the
problems for which such a representation is possible lattice linear problems.
Lattice linear problems are also studied in [9, 7], where the authors have
studied lattice linearity in, respectively, housing market problem and several
dynamic programming problems. Gupta and Kulkarni introduced eventually lattice
linear algorithms [11] and fully lattice linear algorithms [12] for non-
lattice linear problems.

Robot gathering problem on discrete grids: In a general case, it is impossible
to gather a system of robots if their visibility graph is not a connected
graph. One-axis agreement and distance-1 myopia are the minimal capabilities
that robots need to converge on a triangular grid [10].

A system of robots with minimal capabilities has been studied with several
output requirements, including gathering [10, 5, 6], dispersion [1], arbitrary
pattern formation [3]. Gathering of robots has been studied more recently in
[2, 13]. We focus on systems of robots on grids, mainly the papers that study
gathering.

Robots placed on an infinite rectangular grid were studied in [14], where the
authors presented two algorithms for gathering. A synchronous scheduler is
assumed and the robots require, respectively, distance-2 and distance-3
visibility. Moreover, under the latter algorithm, robots may not gather at one
point but will gather a horizontal line segment of unit length.

Robots placed on an infinite triangular grid were studied in [4], where the
authors provided an algorithm to form any arbitrary pattern. They require full
visibility. Their algorithm works only when the the initial global state is
asymmetric. Authors of [15] have studied gathering problem of 7 robots –
initially, 6 of them form a hexagon and one robot is present at the centre of
that hexagon. They require the initial state to form a connected visibility
graph; the system finally reaches a global state where the maximum distance
between two robots is minimized. A synchronous scheduler is assumed. In [5],
authors characterized the problem of gathering on a tree and finite grid.

This paper studies the algorithm developed by Goswami et al. [10]. As
discussed above, this algorithm requires only minimal capabilities in robots.

##  7 Conclusion

In this paper, we show lattice linearity of the algorithm developed by Goswami
et al [10] for gathering robots on an infinite triangular grid. This removes
the assumptions of synchronization from the algorithm and thus makes a system
running this algorithm fully tolerant to asynchrony. We also present a revised
algorithm that simplifies the proof of lattice linearity without losing any of
the desired properties (e.g., convergence time, stabilization).

Lattice linearity implies that the locations, possibly visited by a robot,
form a total order. The total order is a result of the fact that we are able
to determine all and the only robots in any global state that are
impedensable, and an impedensable robot has only one choice of action. By
making this observation, it can also be noticed that we can closely predict
the executions that the robots would perform. As a result, we are able to (1)
compute the exact arena traversed by the robots throughout the execution of
the algorithm (Lemma 2 and Lemma 3), and (2) deterministically predict the
point of gathering of the robots (Corollary 2).

We also provided a better upper bound on the time complexity of this
algorithm. Specifically, we show that it converges in $2n$ rounds, whereas
[10] showed that a maximum of $2.5(n+1)$ rounds are required. This was
possible due to the observations that followed from the proof of lattice
linearity of this algorithm.

Being able to design systems that fully tolerate asynchrony has been a
desired, albeit unattainable, objective. Lattice linear systems provide with a
deterministic, discrete, guarantee to attain such fault tolerance. Studying
whether existing algorithms exploit lattice linearity is extremely interesting
and beneficial. Specifically, it allows us to eliminate costly, sophisticated,
assumptions of synchronization from existing systems, instead of redesigning
them from scratch.

## References

  * [1] Augustine, J., and Moses, W. K. Dispersion of mobile robots: A study of memory-time trade-offs.  In Proceedings of the 19th International Conference on Distributed Computing and Networking (New York, NY, USA, 2018), ICDCN ’18, Association for Computing Machinery.
  * [2] Bhagat, S., Gan Chaudhuri, S., and Mukhopadhyaya, K. Fault-tolerant gathering of asynchronous oblivious mobile robots under one-axis agreement.  In WALCOM: Algorithms and Computation (Cham, 2015), M. S. Rahman and E. Tomita, Eds., Springer International Publishing, pp. 149–160.
  * [3] Bose, K., Adhikary, R., Kundu, M. K., and Sau, B. Arbitrary pattern formation on infinite grid by asynchronous oblivious robots.  Theoretical Computer Science 815 (2020), 213–227.
  * [4] Cicerone, S., Di Fonso, A., Di Stefano, G., and Navarra, A. Arbitrary pattern formation on infinite regular tessellation graphs.  In Proceedings of the 22nd International Conference on Distributed Computing and Networking (New York, NY, USA, 2021), ICDCN ’21, Association for Computing Machinery, p. 56–65.
  * [5] D’Angelo, G., Di Stefano, G., Klasing, R., and Navarra, A. Gathering of robots on anonymous grids and trees without multiplicity detection.  Theoretical Computer Science 610 (2016), 158–168.  Structural Information and Communication Complexity.
  * [6] Flocchini, P., Prencipe, G., Santoro, N., and Widmayer, P. Gathering of asynchronous robots with limited visibility.  Theoretical Computer Science 337, 1 (2005), 147–168.
  * [7] Garg, V. A lattice linear predicate parallel algorithm for the dynamic programming problems.  In 23rd International Conference on Distributed Computing and Networking (New York, NY, USA, 2022), ICDCN 2022, Association for Computing Machinery, p. 72–76.
  * [8] Garg, V. K. Predicate detection to solve combinatorial optimization problems.  In SPAA ’20: 32nd ACM Symposium on Parallelism in Algorithms and Architectures, Virtual Event, USA, July 15-17, 2020 (2020), C. Scheideler and M. Spear, Eds., ACM, pp. 235–245.
  * [9] Garg, V. K. A lattice linear predicate parallel algorithm for the housing market problem.  In Stabilization, Safety, and Security of Distributed Systems (Cham, 2021), C. Johnen, E. M. Schiller, and S. Schmid, Eds., Springer International Publishing, pp. 108–122.
  * [10] Goswami, P., Sharma, A., Ghosh, S., and Sau, B. Time optimal gathering of myopic robots on an infinite triangular grid.  In Stabilization, Safety, and Security of Distributed Systems (Cham, 2022), S. Devismes, F. Petit, K. Altisen, G. A. Di Luna, and A. Fernandez Anta, Eds., Springer International Publishing, pp. 270–284.
  * [11] Gupta, A. T., and Kulkarni, S. S. Extending lattice linearity for self-stabilizing algorithms.  In Stabilization, Safety, and Security of Distributed Systems (Cham, 2021), C. Johnen, E. M. Schiller, and S. Schmid, Eds., Springer International Publishing, pp. 365–379.
  * [12] Gupta, A. T., and Kulkarni, S. S. Brief announcement: Fully lattice linear algorithms.  In Stabilization, Safety, and Security of Distributed Systems: 24th International Symposium, SSS 2022, Clermont-Ferrand, France, November 15–17, 2022, Proceedings (Berlin, Heidelberg, 2022), Springer-Verlag, p. 341–345.
  * [13] Klasing, R., Kosowski, A., and Navarra, A. Taking advantage of symmetries: Gathering of many asynchronous oblivious robots on a ring.  Theoretical Computer Science 411, 34 (2010), 3235–3246.
  * [14] Poudel, P., and Sharma, G. Time-optimal gathering under limited visibility with one-axis agreement.  Information 12, 11 (2021).
  * [15] Shibata, M., Ohyabu, M., Sudo, Y., Nakamura, J., Kim, Y., and Katayama, Y. Gathering of seven autonomous mobile robots on triangular grids.  In 2021 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW) (2021), pp. 566–575.