# DAG-Inducing Problems and Algorithms

Arya Tanmay Gupta Sandeep S Kulkarni<EMAIL_ADDRESS>Computer Science
and Engineering,
Michigan State University428 South Shaw LaneEast LansingMichiganUSA48823

(2018)

###### Abstract.

In this paper, we show that in a parallel processing system, if a directed
acyclic graph (DAG) can be induced in the state space and execution is
enforced along that DAG, then synchronization cost can be eliminated.
Specifically, we show that in such systems, correctness is preserved even if
the nodes execute asynchronously and rely on old/inconsistent information of
other nodes. We present two variations for inducing DAGs – DAG-inducing
problems, where the problem definition itself induces a DAG, and DAG-inducing
algorithms, where a DAG is induced by the algorithm.

We demonstrate that the dominant clique (DC) problem and shortest path (SP)
problem are DAG-inducing problems. Among these, DC allows self-stabilization,
whereas the algorithm that we present for SP does not. We demonstrate that
maximal matching (MM) and 2-approximation vertex cover (VC) are not DAG-
inducing problems. However, DAG-inducing algorithms can be developed for them.
Among these, the algorithm for MM allows self-stabilization and the 2-approx.
algorithm for VC does not. Our algorithm for MM converges in $2n$ moves and
does not require a synchronous environment, which is an improvement over the
existing algorithms in the literature. Algorithms for DC, SP and 2-approx. VC
converge in $2m$, $2m$ and $n$ moves respectively. We also note that DAG-
inducing problems are more general than, and encapsulate, lattice linear
problems (Garg, SPAA 2020). Similarly, DAG-inducing algorithms encapsulate
lattice linear algorithms (Gupta and Kulkarni, SSS 2022).

DAG-inducing problems, DAG-inducing algorithms, asynchrony, dominant clique,
shortest path, maximal matching, 2-approximation vertex cover

††copyright: acmcopyright††journalyear: 2018††doi:
XXXXXXX.XXXXXXX††conference: Make sure to enter the correct conference title
from your rights confirmation emai; June 03–05, 2018; Woodstock, NY††price:
15.00††isbn: 978-1-4503-XXXX-X/18/06

##  1\. Introduction

A parallel/distributed algorithm consists of multiple processes that solve a
problem. In these algorithms, processes need to coordinate with each other.
This could be achieved via shared memory (where the data is stored centrally
and processes have direct access to all data) or message passing (where
processes share their information via messages). In these programs, as the
level of parallelization increases, the need for synchronization increases as
well.

Consider the example of the minimal dominating set problem. An algorithm for
this problem is as follows: if node $i$ can leave the dominating set while
ensuring that $i$ and its neighbours stay dominated, then $i$ moves out.
Similarly, if $i$ or one of the neighbours of $i$ are not dominated, then $i$
turns itself in. If this algorithm is run in an interleaving fashion (where
one node executes at a time), it will result in a minimal dominating set.
However, consider the case where nodes are executing asynchronously. Consider
a complete graph of two nodes $i$ and $j$. Let that nodes $i$ and $j$ are out
of the dominating set and read the state of each other simultaneously.
Consider that $i$ executes first, node $i$ executes and changes its state to
$IN$. However, when $j$ executes, it has old/inconsistent information about
the state of $i$. Hence, $j$ also will change its state to $IN$, leading to a
non-optimal state. Effectively, without proper synchronization, $i$ and $j$
can repeat this execution forever without converging. Thus, we have that if
this algorithm is run in parallel where each node executes at its own pace
without synchronization with others then such a system may fail to find a
minimal dominating set.

If an algorithm can be run without synchronization and still lead to a correct
answer then it can highly benefit from available concurrency permitting each
node to execute at its own pace. While the embarrassingly parallel algorithms,
in which there is no data dependency among the nodes, do fit this requirement,
most problems require that the data of neighbouring nodes is correlated. We
study problems and algorithms where such asynchronous execution can be
permitted. Towards this end, in this paper, we introduce DAG-inducing problems
and DAG-inducing algorithms.

###  1.1. Permitting Asynchronous Execution

When an algorithm executes without synchronization, it is possible that some
nodes use an old value of other nodes. Thus, if we allow asynchrony, then we
have to ensure that the algorithm provides a correct answer even if a node
executes based on old values of variables. Next, we discuss some introductory
background on asynchronous systems that ensure correctness. This work includes
lattice linear problems (Garg2020, ), eventually lattice linear algorithms
(Gupta2021, ) and fully lattice linear algorithms (Gupta2022, ).

Garg (Garg2020, ) introduced modelling of problems such that the state space
forms a lattice. These problems are called lattice linear problems. The local
states in such problems form a total order, and as a result, the global states
form a partial order. A node moves ahead only if it determines that it is
violating the global state, i.e., the system will not converge if it retains
its state. The induction of a lattice ensures that if some node $i$ is reading
an old state of node $j$, $j$ would only have moved up in the lattice. As a
result, the nodes move only in one direction, allowing the system to execute
in asynchrony. In these problems, there is only one optimal state.

Gupta and Kulkarni (Gupta2021, ) studied problems that contain multiple
optimal states and require self-stabilization. The algorithms in (Gupta2021, )
induce single or multiple disjoint lattices in a subset of the state space.
The supremum of each lattice is an optimal state, and so self-stabilization is
allowed. These algorithms guarantee that the system traverses from an
arbitrary state to one of the states in the lattices and from there, traverses
that lattice to reach an optimal state. Because of the kind of partial order
induced among the states, these algorithms are called eventually lattice
linear algorithms. Furthermore, Gupta and Kulkarni (Gupta2022, ) provided with
a fully lattice linear algorithm for minimal dominating set. This algorithm is
capable of inducing multiple disjoint lattices in the entire state space while
guaranteeing that every supremum is an optimal state. Hence starting from an
arbitrary state, the algorithm traverses one of the lattices and reaches an
optimal state.

We note the class of DAG-inducing problems (respectively, DAG-inducing
algorithms) identified in this paper are a superset of lattice linear problems
(respectively, lattice linear algorithms).

###  1.2. Contributions of the paper

In this paper, we study the problems that can be represented by a predicate
which induces a DAG among the states, and the problems in which a DAG can be
induced algorithmically. Inducing a DAG is extremely valuable as it allows the
nodes to run asynchronously. In other words, each node can execute its actions
by reading the variables of other nodes at its own pace and take action based
on old values while still preserving correctness. Furthermore, inducing a DAG
is more general than inducing lattices (as considered in (Garg2020, ;
Gupta2021, )). Specifically, inducing a DAG permits more non-determinism (more
design choices) than the case where lattices are induced. Our specific
contributions are listed as follows.

  * •

We introduce the classes of DAG-inducing problems and DAG-inducing algorithms.

  * •

We show that the dominant clique problem and the shortest path problem are a
DAG-inducing problems. Among these the dominant clique problem allows self-
stabilization, whereas the algorithm that we develop for the shortest path
problem is not self-stabilizing.

  * •

We demonstrate that maximal matching problem and 2-approximation vertex cover
are not DAG-inducing problems. We present DAG-inducing algorithm for them. The
algorithm for maximal matching allows self-stabilization and the
2-approximation algorithm for vertex cover does not.

  * •

We study upper bound to the convergence time of an algorithm traversing a DAG
of states. We show how inducing a $<$-DAG in the state space is crucial to
allow asynchrony.

  * •

Algorithms for the dominant clique and shortest path, both, converge in $2m$
moves. The algorithm for the maximal matching converges in $2n$ moves and the
2-approximation algorithm for vertex cover converges in $n$ moves.

###  1.3. Organization of the paper

We discuss the notations and definitions used in this paper in Section 2. In
Section 3, we study the characteristics of DAG-inducing problems with
examples. In particular, we study the dominant clique problem (Section 3.3)
and the shortest path problem (Section 3.4) as DAG-inducing problems. In
Section 4, we study the characteristics of DAG-inducing algorithms for non-
DAG-inducing problems with examples. Specifically, we study the maximal
matching problem (Section 4.2) and 2-approximation vertex cover (Section 4.3).
In Section 5, we study the properties of an algorithm traversing a DAG of
global states. In particular, we study significance of inducing a DAG to allow
asynchrony (Section 5.1) and the time complexity of an algorithm traversing a
DAG of global states (Section 5.2). We study the related work in Section 6.
Finally, we conclude in Section 7.

##  2\. Preliminaries

In this paper, we are mainly interested in graph algorithms where the input is
a graph $G$, $V(G)$ is the set of its nodes, $E(G)$ is the set of its edges,
$n=|V(G)|$, and $m=|E(G)|$. For a node $i\in V(G)$, $Adj_{i}$ is the set of
nodes connected to $i$ by an edge, and $Adj^{x}_{i}$ is the set of nodes
within $x$ hops from $i$, excluding $i$. $deg(i)=|Adj_{i}|$. $dis(i,j)$ is the
length of shortest path from $i$ to node $j$.

Each node $i$ is associated with a set of variables. The algorithms are
written in terms of rules, where each rule for every process $i$ is of the
form $g\longrightarrow a_{c}$ where the guard $g$ is a proposition consisting
of the variables of $i$ along with the variables of other nodes. If at least
one of the guards $g$ hold true for $i$, we say that $i$ is enabled. We say
that $i$ makes a move when $i$ is enabled and updates its variables by
executing the corresponding action $a_{c}$. A round is the minimum time-frame
where each node evaluates its guards at least once and takes corresponding
action (if it is enabled). An algorithm is silent if no node is enabled when
$G$ reaches an optimal state.

We notate $S$ as the set of all global states. A global state $s\in S$ is
represented as a vector where $s[i]$ denotes the variables of node $i$, $s[i]$
itself is a vector of the variables of $i$.

Scheduler/Daemon. A scheduler/daemon is a node whose function is to choose
one, some, or all nodes in a time step, throughout the execution, so that the
chosen nodes can evaluate their guards and take corresponding action. A
central scheduler chooses only one node per time-step. A distributed scheduler
chooses the nodes in an arbitrary subset of $V(G)$ per time-step. A
synchronous scheduler chooses all the nodes in $V(G)$ in each time-step.

Computation with Synchronization.  A computation of an algorithm $A$ (with
synchronization) is a sequence of the form $\langle s_{0}$, $s_{1}$,
$\cdots\rangle$ where each global state $s_{\ell}$ identifies the values of
variables of all nodes. Elaboratedly, a computation is of the form $\langle$
$\langle s_{0}[1]$, $s_{0}[2]$, $\cdots$, $s_{0}[n]\rangle$, $\langle
s_{1}[1]$, $s_{1}[2]$, $\cdots$, $s_{1}[n]\rangle$, $\cdots$ $\rangle$ where
$s_{\ell}[i]$ denotes the variables of node $i$ in global state $s_{\ell}$.
Here, $s_{\ell+1}$ ($\forall\ell\geq 0$) is obtained by executing an action of
some node $i$ in state $s_{\ell}$. Thus, a transition $(s_{\ell},s_{\ell+1})$
corresponds to $(\langle s_{\ell}[1]$, $s_{\ell}[2]$, $\cdots$,
$s_{\ell}[n]\rangle$, $\langle s_{\ell+1}[1]$, $s_{\ell+1}[2]$, $\cdots$,
$s_{\ell+1}[n]\rangle)$.

We assume that node $i$ executes its action in the current state $s_{\ell}$
(i.e., it executes based on fresh values of variables as in $s_{\ell}$) and
while node $i$ is executing no other node is updating its state. Clearly, this
definition is very restrictive, as it permits only a single node to execute at
a time. It can be easily extended to the case where two nodes can execute
simultaneously under proper synchronization.

However, in this paper, we are interested in asynchronous computations. This
means that while node $i$ is executing, other arbitrary nodes could be
updating their state as well. We study such computations without
synchronization, next.

Computation without Synchronization.  When node $i$ executes without
synchronization, it reads the states of other nodes at its own pace and the
updates its own variables. This means that by the time $i$ executes its
action, the states of other nodes may have changed. Effectively, node $i$ will
be reading old values of variables in $Adj_{i}^{x}$. In other words, the state
read by node $i$ may appear to $i$ as $\langle s_{\alpha_{0}}[1]$,
$s_{\alpha_{1}}[2]$, $\cdots$ $s_{\alpha_{n}}[n]\rangle$ where $\forall
t,\alpha_{t}\leq\ell$. Node $i$ can execute its action subsequently, based on
such inconsistent state, and update its state. Then, $s_{\ell+1}$ is obtained
from $s_{\ell}$ by changing the state of node $i$ where node $i$ views its
state as $\langle{s_{\alpha_{0}}[1],s_{\alpha_{1}}[2],\cdots
s_{\alpha_{n}}[n]}\rangle$ (where $\forall t,\alpha_{t}\leq\ell$) and executes
its action.

Self stabilization. An algorithm $A$ is self-stabilizing with respect to the
subset $S_{o}$ of the set $S$ of global states iff

  * •

Convergence: Starting from an arbitrary state, any sequence of computations of
$A$ reaches a state in $S_{o}$.

  * •

Closure: Any computation of $A$ starting from $S_{o}$ always stays in $S_{o}$.

##  3\. Natural DAG induction: DAG-inducing Problems

In this section, we discuss properties of problems where a DAG can be induced
naturally. Let P be a problem (e.g., shortest path problem) that is defined by
a predicate $\mathcal{P}$, i.e., $P$ requires that $\mathcal{P}$ is true. It
follows that if $\mathcal{P}$ is false in the current global state $s$, i.e.,
if $\mathcal{P}(s)$ is false, then there exists at least one node that must
change its state in order to solve $P$. The problems/algorithms considered in
this section rely on the requirement that execution of such node(s) is
critical for reaching an optimal state.

###  3.1. Embedding a $<$-DAG among global states

To explain the embedding of a $<$-DAG, recall that a global state $s$ is of
the form $\langle s[1],s[2],\cdots,s[n]\rangle$, where $s[i]$ denotes the
state of node $i$. Furthermore, in asynchrony, in a transition
$(s_{\ell},s_{\ell+1})$, when node $i$ reads the variables of another node
$j$, it may read it $s_{\alpha_{j}}[j]$, where $\alpha_{j}\leq\ell$ instead of
the latest state $s_{\ell}[j]$, i.e., it may read an older value of node $j$.
The $<$-DAG captures how the state of a node may change during its execution.

First, we define a partial order $<_{l}$ among the local states of a node.
(Intuitively, node $i$ can go from state $s[i]$ to $s^{\prime}[i]$ iff
$s[i]<_{l}s^{\prime}[i]$.) In a partial order, we allow the possibility that
$\lnot(s[i]<_{l}s^{\prime}[i])\land\lnot(s^{\prime}[i]<_{l}s[i])$. We
demonstrate this in a later part in this section.

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])$.
$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 use
the symbol ‘$>$’ which is the opposite of ‘$<$’, i.e. $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 DAG, formed from
such a partial order, a $<$-DAG.

###### Definition 3.1.

$<$-DAG. Given a partial order $<_{l}$ on local states of $s[i]$, the $<$-DAG
corresponding to $<_{l}$ is defined by the partial order: $s<s^{\prime}$ iff
$(\forall i\ \ s[i]\leq_{l}s^{\prime}[i])\wedge(\exists i\ \
s[i]<_{l}s^{\prime}[i])$.

Remark: A $<$-DAG can be induced in any problem/state space. It will permit
asynchronous execution only if it guarantees reachability to an optimal state.
We demonstrate this later in the section.

In (Garg2020, ; Gupta2021, ; Gupta2022, ), the discrete structure in the state
space $S$ is constrained to be a lattice. This is achieved by requiring a
total order among the local states of a node. If local states were totally
ordered, we would obtain a lattice instead, where join and meet could be
defined in the natural 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])$). If the
local states were totally ordered, then $\min(s_{1}[i],s_{2}[i])$ (and
$\max(s_{1}[i],s_{2}[i])$) is either $s_{1}[i]$ or $s_{2}[i]$. However, if
local states are partially ordered, $\min(s_{1}[i],s_{2}[i])$ (or,
$\max(s_{1}[i],s_{2}[i])$) may not be defined. Hence, the resultant structure
may not be a lattice.

###  3.2. General properties

Let that problem $P$ is defined by a predicate $\mathcal{P}$. For some
problems, when $\mathcal{P}(s)$ is false in a state $s$, we can identify at
least one node, say $i$, such that its execution is required in order to solve
$P$. In other words, if node $i$ does not execute (i.e., $s[i]$ remains
unchanged) then $\mathcal{P}$ remains false. Thus, we have the following
definition.

###### Definition 3.2.

(Garg2020, )
$\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}))$.

Remark: We use the term impedensable as a combination of the words impediment
(obstacle) and indispensable (essential), as the nodes that are impedensable
are essential to make progress but they also prevent the system from making
progress if they do not execute. This term is similar to the notion of a node
being forbidden described in (Garg2020, ), which comes from predicate
detection background (Chase1995, ). We changed the notation to avoid
misinterpretation due to the English meaning of the word forbidden while
reading the paper.

The above definition states that in a state where $\mathcal{P}(s)$ is false,
we can identify a specific node $i$ that must change its state to reach an
optimal state. If $\mathcal{P}$ is false in state $s$ then it will remain
false if node $i$ does not execute, even if other nodes execute. The problems
where this constraint cannot be applied are studied in Section 4.

If no node is impedensable in $s$, then $\mathcal{P}(s)$ is true, i.e., $s$ is
an optimal state. Based on the above definition and given that $S$ forms a
$<$-DAG, we define DAG-inducing problems as follows.

###### Definition 3.3.

DAG-inducing problem (DIP). A problem $P$ is DAG-inducing iff there exists a
predicate $\mathcal{P}$ and a $<$-DAG such that

  * •

$P$ requires that we reach a state where $\mathcal{P}$ is true, and

  * •

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

For a DAG-inducing problem $P$, we can design an algorithm $A$ by following
the following guidelines (Garg2020, ).

  * •

Each node $i$ checks if it is impedensable.

    * –

If $\mathcal{P}(s)$ is false then there is at least one node that is
impedensable.

    * –

If $\mathcal{P}(s)$ is true then no node is impedensable.

  * •

If $i$ is impedensable, then $i$ increments its value with respect to $<_{l}$,
otherwise, no action is taken.

If the above rules are followed, then $A$ will reach a state where
$\mathcal{P}$ is true if there exists a state $o$ which satisfies
$\mathcal{P}$ and $o$ is reachable from the initial state. Definition 3.1
ensures that this property is satisfied even if the nodes read old values: if
$\mathcal{P}$ is false in the state observed by the given node, it will also
be false in the current state. Thus such an algorithm finds the lowest state
in the DAG where $\mathcal{P}$ is true.

###### Definition 3.4.

Successors of a global state. A state $s^{\prime}$ is a successor of a state
$s$ iff $s^{\prime}$ is reachable from $s$ in the induced DAG. Formally,
$\textsc{Successors}(s)\equiv\\{s^{\prime}:s^{\prime}>s\\}$.

###### Definition 3.5.

$\textsc{Successor}(s,s^{\prime})\equiv s^{\prime}\in\textsc{Successors}(s)$.

###### Definition 3.6.

Terminal Successors of a global state. A state $s^{\prime}$ is a terminal
successor of a state $s$ iff $s^{\prime}$ is the successor of $s$ and
$s^{\prime}$ has no successor. Formally, $\textsc{Terminal-Successors}(s)$
$\equiv$ $\\{s^{\prime}|$ $\textsc{Successor}(s$, $s^{\prime})\land$
$\textsc{Successors}(s^{\prime})$ $=$ $\phi\\}$.

###### Definition 3.7.

$\textsc{Terminal-Successor}(s,s^{\prime})\equiv$ $s^{\prime}$ $\in$
$\textsc{Terminal-Successors}(s)$.

Continuing from Definition 3.3, we have

###### Definition 3.8.

Self-stabilizing DIP. $P$ is a self-stabilizing DIP if and only if all
terminal successors of every node are optimal states, i.e. $\forall
s,s^{\prime}\in S:\textsc{Terminal-
Successor}(s,s^{\prime})\Rightarrow\mathcal{P}(s^{\prime})=true$.

In the next two subsections, we show that the dominant clique problem and the
shortest path problem are DAG-inducing problems. We also note that these are
not lattice linear problems, as the discrete structure that is induced among
the global states is not a lattice.

###  3.3. Dominant Clique (DC) problem

###### Definition 3.9.

Dominant clique. In the dominant clique problem, the input is an arbitrary
graph $G$ suvh that for the variable $clique.i$ of each node $i$,
$clique.i\subseteq Adj_{i}\cup\\{i\\}$ and $\\{i\\}\subseteq clique.i$. The
task is to compute maximal cliques such that for any node $i$, (1) all the
nodes in $clique.i$ form a clique, i.e. $\forall j,k\in clique.i,j\neq k:k\in
Adj_{j}$, and (2) there exists no clique $c$ in $G$ such that $clique.i$ is a
proper subset of $c$, i.e. $\not\exists j\in Adj_{i}:j\not\in
clique.i\land(\forall k\in clique.i:k\in Adj_{j})$.

Thus, the DC problem can be defined by the following predicate.

$\mathcal{P}_{dc}\equiv(\forall j,k\in clique.i,j\neq k:k\in Adj_{j})\land$

$(\not\exists j\in Adj_{i}:j\not\in clique.i\land(\forall k\in clique.i,:k\in
Adj_{j}))$

An impedensable node $i$ in a state $s$ is a node for which (1) all the nodes
in $clique.i$ do not form a clique, or otherwise (2) there exists some node
$k$ in $Adj_{i}$ such that $clique.i\cup\\{k\\}$ is a valid clique, but $k$ is
not in $clique.i$. Formally,

$\textsc{Impedensable-DC}(i,s,\mathcal{P}_{dc})\equiv(\exists j\in
clique.i:(j\not\in Adj_{i}\lor(\exists k\in clique.i,k\neq j:j\not\in
Adj_{k})))\lor$

$(\exists j\in Adj_{i}:j\not\in clique.i\land(\forall k\in clique.i:k\in
Adj_{j}))$.

The algorithm is defined as follows. If there exists some node $k$ in
$Adj_{i}$ which forms a clique with every node in $clique.i$, but is not in
$clique.i$, then $k$ is added to $clique.i$. If otherwise all the nodes in
$clique.i$ do not form a clique, then $clique.i$ is reset to be $\\{i\\}$.

###### Algorithm 1.

Rules for node $i$ in state $s$.

$\begin{array}[]{|l|}\hline\cr\textsc{Impedensable-
DC}(i,s,\mathcal{P}_{dc})\longrightarrow\\\
\begin{cases}clique.i=clique.i~{}\cup\\{j\\}&\text{if $\exists j\in
Adj_{i}:j\not\in clique.i\land$}\\\ &\text{$(\forall k\in clique.i:k\in
Adj_{j})$}\\\ clique.i=\\{i\\}&\text{otherwise}\end{cases}{}\\\
\hline\cr\end{array}$

The DC problem induces a partial order among the local states. As an instance,
the partial order induced among the local states of node $v_{1}$ (of the graph
in Figure 1 (a)) is shown in Figure 1 (b).

$v_{1}$$v_{3}$$v_{2}$

{$v_{1}$}
---
{$v_{1}$,$v_{2}$}
---
{$v_{1}$,$v_{3}$}
---
{$v_{1}$,$v_{2}$,$v_{3}$}
---
{$v_{2}$,$v_{3}$}
---
{}
---
{$v_{2}$}
---
{$v_{3}$}
---

Figure 1. (a) Input graph. (b) Partial order induced among the local states of
node 1.

Remark: Notice from Figure 1 that the states $\\{v_{1},v_{2}\\}$ and
$\\{v_{1},v_{3}\\}$ are not related under the $<_{l}$ relation. If we
restricted $<_{l}$ to be a total order, then all possible local states would
be related under $<_{l}$.

As a result, the global states in the graph presented in Figure 1 (a) form a
DAG that we show in Figure 2. Note that the state space for this instance has
a total 512 states. In the figure, we only show the states where the second
guard is false in all the nodes. Observe that all the global states where the
second guard is true in some nodes will converge to one of the states present
in this figure, and then it will converge to one of the terminal successors of
this graph.

{1},{2},{3}
---
{1,2},{2},{3}
---
{1},{1,2},{3}
---
{1},{2},{1,3}
---
{1,3},{2},{3}
---
{1,2},{1,2},{3}
---
{1,2},{2},{1,3}
---
{1},{1,2},{1,3}
---
{1},{1,2},{1,3}
---
{1,3},{1,2},{3}
---
{1,3},{2},{1,3}
---
{1,2},{1,2},{1,3}
---
{1,3},{1,2},{1,3}
---
Figure 2. DAG, assuming that initial state is
$\langle\\{1\\},\\{2\\},\\{3\\}\rangle$. In all these states, the second guard
of Algorithm 1 is false. Observe that any other state will converge to one of
these states and then converge to one of the optimal states in this DAG.
Transitive edges are not shown in this DAG.

###### Lemma 3.10.

The d ominant Clique problem is a DAG-inducing problem.

###### Proof.

For a node $i$, $clique.i$ contains the nodes that $i$ is connected with and
the nodes in $clique.i$ should form a clique. A global state does not manifest
a dominant clique if at least one node $i$ in $s$ does not store a set of
nodes forming a maximal clique with itself, i.e. (1) $clique.i$ is not a
maximal clique, that is, $\exists j\in Adj_{i}\setminus
clique.i:clique.i\cup\\{j\\}$ forms a valid clique, or (2) the nodes in
$clique.i$ do not form a clique.

Next, we need to show that if some node $i$ in state $s$ is violated, then
$\forall s^{\prime}>s$, if $s^{\prime}[i]=s[i]$, then $s^{\prime}$ will not
manifest a dominant clique. This is straightforward from the definition
itself, that if a node $i$ is impedensable, then $i$ does not store a set of
nodes forming a maximal clique with itself. If $i$ is impedensable in $s$, and
$i$ has the same state in some $s^{\prime}>s$ then $i$ stays impedensable in
$s^{\prime}$ as well as it does not store a set of nodes forming a maximal
clique. ∎

We define the state value and rank as follows.

$\begin{array}[]{l}\textsc{State-Value-DS}(i,s)=\\\
\begin{cases}|C|-|clique.i|:C=\text{the largest clique}\\\ \text{which
$clique.i$ is a subset of}&\text{if $clique.i$ is a clique}.\\\
|Adj.i+1|&\text{otherwise}.\end{cases}\end{array}$

$\textsc{Rank-DC}(s)=\sum\limits_{i\in V(G)}\textsc{State-Value-DC}(i,s).$

###### Theorem 3.11.

Algorithm 1 is an converging algorithm for the dominant clique problem.

###### Proof.

We need to show that (1) Algorithm 1 traverses a DAG of global states, (2) for
all suboptimal states, $\exists$ a terminal successor, and (3) all terminal
global states are optimal states.

Let the current state be $s$. If $s$ is suboptimal, then for at least for one
of the nodes $i$: (1) $clique.i$ is not a maximal clique, that is, $\exists
j\in Adj_{i}\setminus clique.i:clique.i\cup\\{j\\}$ forms a valid clique, or
(2) the nodes in $clique.i$ do not form a clique.

In the case that $s$ is suboptimal and the first case holds true for some node
$i$, then under Algorithm 1, $i$ will include a node $j$ in $clique.i$ which
forms a clique with the nodes already present in $clique.i$, which reduces the
state value of $i$ by at least 1.

In the case that $s$ is suboptimal and the second case holds true for some
node $i$, then under Algorithm 1, $i$ will change $clique.i$ to be $\\{i\\}$,
which reduces the state value of $i$ from $|Adj+1|$ to some value less than or
equal to $|Adj_{i}|$.

Thus under Algorithm 1, an arbitrary graph will follow a DAG of states and if
it transitions from a state $s$ to another state $s^{\prime}$, then we have
that $s^{\prime}>s$ such that rank of $s^{\prime}$ is less than the rank of
$s$.

The state value of any node is impedensable. Thus the rank of any global state
is also impedensable. When a impedensable node $i$ makes an execution, then
its state value reduces, until it becomes 0. Thus if there is a global state
$s$ with rank greater than 0, then there exists at least one impedensable node
in it. When any node performs execution in $s$ then $s$ transitions to some
state with rank less than $s$. This shows that for every suboptimal global
state, there exists at least one terminal successor.

Let that $s$ is a terminal successor. This implies that $\mathcal{P}(s)$ is
true. There does no exist an impedensable node in $s$, so any node will not
change its state and $s$ manifests a dominant clique. Thus we have that all
terminal states are optimal states. ∎

###  3.4. Shortest Path (SP) Problem

###### Definition 3.12.

Shortest path. In the shortest path problem, the input is a weighted arbitrary
connected graph $G$ (all edge weights are positive) and a destination node
$d_{es}$. Every node $i$ stores $p.i$ (initialized with $\top$) and $d.i$
(initialized with $\infty$). The task is to compute, $\forall i\in V(G)$, the
length $d.i$ of a shortest path from $i$ to $d_{es}$, and the parent $p.i$
through which an entity would reach $d_{es}$ starting from $i$.

The positive weights assigned for every edge denote the cost that it would
take to move from node $i$ to node $j$, given that $\\{i,j\\}\in E(G)$. In
this problem, if we consider the local state of a node $i$ to be represented
only by the variable $d.i$ then the local states of the nodes will form a
total order. Consequently, the resultant discrete structure formed among the
global states will be a lattice. This was shown in (Garg2020, ). On the other
hand, in applications such as source routing (Medhi2017, ) where the source
node specifies the path that should be taken, the local states form a partial
order. Hence, the global states form a DAG as opposed to a lattice. For
brevity, we only represent the next hop in $p.i$. The SP problem can be
represented by the following predicate, where, $w(i,j)$ is the weight of edge
$\\{i,j\\}$.

$\mathcal{P}_{sp}\equiv\forall
i:(d.i=dis(i,d_{es})=\min\\{dis(j,d_{es})+w(i,j):j\in
Adj_{i}\\})\land(p.i=\text{arg }\min\\{dis(j,d_{es})+w(i,j):j\in Adj_{i}\\})$.

An impedensable node $i$ in a state $s$ is a node for which its current parent
is not a direct connection to the shortest path from $i$ to $d_{es}$.
Formally,

$\textsc{Impedensable}(i,s,\mathcal{P}_{sp})\equiv(d.i\neq 0\land
i=d_{es})\lor(\exists j:d.i>d.j+w(i,j))$.

The algorithm is defined as follows. If an impedensable node $i$ is $d_{es}$,
then $d.i$ is updated to 0 and $p.i$ is updated to $d_{es}$. Otherwise, $p.i$
is updated to the $j$ in $Adj_{i}$ for which $d.j+w(i,j)$ is minimum.

###### Algorithm 2.

Rules for node $i$.

$\begin{array}[]{|l|}\hline\cr\textsc{Impedensable}(i,s,\mathcal{P}_{sp})\longrightarrow\\\
\begin{cases}d.i=0,p.i=i&\text{if $i=d_{es}$}\\\ \langle
d.i,p.i\rangle=\langle d.j+w(i,j),j\rangle:j\\\
\quad\quad=\text{arg}\min\\{d.k+w(i,k):k\in
Adj_{i}\\}&\text{otherwise}\end{cases}{}\\\ \hline\cr\end{array}$

As a result, the global states form a DAG. We show an example in Figure 3:
Figure 3 (a) is the input graph and Figure 3 (b) is the induced DAG. In this
figure, a global state is represented as $\langle\langle p.v_{1}$,
$d.v_{1}\rangle$, $...$, $\langle p.v_{4}$, $d.v_{4}\rangle\rangle$.

$v_{1}$$v_{2}$$v_{3}$$v_{4}=d_{es}$2123

$\langle\top,\infty\rangle$,$\langle\top,\infty\rangle$,
---
$\langle\top,\infty\rangle$,$\langle\top,\infty\rangle$
$\langle\top,\infty\rangle$,$\langle\top,\infty\rangle$,
---
$\langle\top,\infty\rangle$,$\langle v_{4},0\rangle$
$\langle\top,\infty\rangle$,$\langle v_{4},2\rangle$,
---
$\langle\top,\infty\rangle$,$\langle v_{4},0\rangle$
$\langle\top,\infty\rangle$,$\langle\top,\infty\rangle$,
---
$\langle v_{4},1\rangle$,$\langle v_{4},0\rangle$
$\langle\top,\infty\rangle$,$\langle v_{4},2\rangle$,
---
$\langle v_{4},1\rangle$,$\langle v_{4},0\rangle$
$\langle v_{2},4\rangle$,$\langle v_{4},2\rangle$,
---
$\langle v_{4},1\rangle$,$\langle v_{4},0\rangle$
$\langle v_{3},4\rangle$,$\langle v_{4},2\rangle$,
---
$\langle v_{4},1\rangle$,$\langle v_{4},0\rangle$

Figure 3. (a) Input graph. (b) DAG induced among the global states in
evaluating for the shortest path parblem in the graph shown in (a); a global
state is represented as $\langle\langle p.v_{1},d.v_{1}\rangle,...,\langle
p.v_{4},d.v_{4}\rangle\rangle$. Transitive edges are not shown.

Remark: Notice that in this case (Figure 3), the DAG among the global states
is induced because $v_{1}$ has a choice which node to choose as its parent. If
we remove the parent information from representing the local state, this
discrete structure will get reduced to a lattice. Also, if we restrict the
choice of $v_{1}$ (and all nodes) to, e.g., choose only the node with higher
ID as a parent in the case of conflict, then this discrete structure will get
reduced to a lattice.

###### Lemma 3.13.

The shortest path problem is a DAG-inducing problem.

###### Proof.

For a node $i$, $d.i$ contains the distance of $d_{es}$ from node $i$. A
global state $s$ does not manifest all correct distances if for at least one
node $i$ in $s$, (1) $dis(i,d_{es})\neq d.i$, that is, $i$ does not store a
shortest path from $i$ to $d_{es}$, or (2) the parent of $i$ is not a valid
direct connection in a shortest path from $i$ to $d_{es}$.

Next, we need to show that if some node $i$ in state $s$ is violated, then
$\forall s^{\prime}>s$, if $s^{\prime}[i]=s[i]$, then $s^{\prime}$ will not
manifest all shortest paths. This is straightforward from the definition
itself, that if a node $i$ is impedensable, then either $i=d_{es}$ and it is
not pointing to itself through $p.i$, or there is at least one other node $j$
such that $d.i>d.j+w(i,j)$. If $i$ is impedensable in $s$, and $i$ has the
same state in some $s^{\prime}>s$ then $i$ stays impedensable in $s^{\prime}$
as well as it does not store the length of a shortest path in $d.i$. ∎

Since the local states of all nodes have to be initialized as
$d.i=\infty,p.i=\top$, this solution is not self-stabilizing.

We define the state value and rank as follows.

$\begin{array}[]{l}\textsc{State-Value-SP}(i,s)=d.i-dis(i,d_{es}).\end{array}$

$\textsc{Rank-SP}(s)=\sum\limits_{i\in V(G)}\textsc{State-Value-SP}(i,s).$

###### Theorem 3.14.

Algorithm 2 solves the shortest path problem on a connected positive weighted
graph.

###### Proof.

We need to show that (1) Algorithm 2 traverses a DAG of global states, (2) for
all suboptimal states, $\exists$ a terminal successor, and (3) all terminal
global states are optimal states.

Let the current state be $s$. If $s$ is suboptimal, then for at least for one
of the nodes $i$: (1) $p.i\neq i\land i=d_{es}$, that is, $i$ is the
destination node and is not pointing to itself, or (2) $dis(i,d_{es})\neq
d.i$, that is, $i$ does not store a shortest path from $i$ to $d_{es}$.

In the case that $s$ is suboptimal and the first case holds true for some node
$i$, then under Algorithm 1, $i$ updates $d.i$ to 0 and $p.i$ to $i$, which
reduces the state value of $i$ to 0.

In the case that $s$ is suboptimal and the second case holds true for some
node $i$, then under Algorithm 2, $i$ will reduce its $d.i$ value and update
$p.i$, which reduces the state value of $i$ at least by 1.

Thus under Algorithm 1, an arbitrary graph will follow a DAG of states and if
it transitions from a state $s$ to another state $s^{\prime}$, then we have
that $s^{\prime}>s$ such that rank of $s^{\prime}$ is less than the rank of
$s$.

If no node is impedensable, then this implies that all nodes have computed the
shortest distance in their $d.i$ variable, and thus the rank is 0. Thus if
there is a global state $s$ with rank greater than 0, then there exists at
least one impedensable node in it. When any node performs execution in $s$
then $s$ transitions to some state with rank less than $s$. This shows that
for every suboptimal global state, there exists at least one terminal
successor.

Let that $s$ is a terminal successor. This implies that $\mathcal{P}(s)$ is
true. There does no exist an impedensable node in $s$, so any node will not
execute and $s$ manifests correct shortest path evaluation for all nodes. Thus
we have that all terminal states are optimal states. ∎

###  3.5. Limitations of modelling problems as DAG-inducing problems

Unlike the DAG-inducing problems where the problem description creates a DAG
among the states in $S$, there are problems where the states do not form a DAG
naturally. E.g., the maximal matching (MM) problem is not a lattice linear
problem. This can be illustrated through a simple instance of a 3 nodes
network forming a simple path $\langle A,B,C\rangle$. Initially no node is
paired with any other node. Here, MM can be obtained by matching $A$ and $B$.
Thus, $C$ is not impedensable. Another maximal matching can be obtained by
matching $B$ and $C$, in which case $A$ is not impedensable. Thus the problem
itself does not define which node is impedensable. Similarly, it can be shown
that, e.g., vertex cover (both minimal vertex cover and 2-approximation vertex
cover) is not a DAG-inducing problem.

We observe that it is possible to induce a DAG in non-DAG-inducing problems
algorithmically. In the next section (Section 4), we study the properties of a
DAG-inducing algorithm, which is capable of inducing a DAG in a non-DAG-
inducing problem, along with examples for demonstration.

##  4\. Imposed DAG Induction: DAG-inducing Algorithms

In this section, we discuss problems where the problems cannot be represented
by a predicate under which the global states form a DAG. It means that the
problem does not naturally define which node is impedensable. Effectively,
there may be multiple optimal states. We start by describing the general
properties of such problems.

###  4.1. General Properties

In DAG-inducing problems, we observe that $\mathcal{P}$(s) is of the form
$\forall i\ \mathcal{P}_{i}(s)$ a node $i$ is impedensable in state $s$ if and
only if $\mathcal{P}_{i}(s)$ is false. But if $P$ is not a DAG-inducing
problem, then a node violating $\mathcal{P}_{i}(s)$ may not always be
impedensable. (cf. the example of maximal matching as demonstrated in Section
3.5). In these cases, to utilize the definition of impedensable, a DAG is
induced algorithmically. In other words, the algorithm creates rules to
determine which nodes are impedensable, and creates a partial order among the
local states, and thereby induces a DAG among the global states. The algorithm
must also ensure that an optimal state is reached while traversing the induced
DAG.

Next, we consider how we can define the DAG induced by an algorithm $A$. $A$
creates rules to identify $<_{l}$. Specifically, $A$ changes the state of node
$i$ from $s_{0}[i]$ to $s_{1}[i]$ only if $s_{0}[i]<_{l}s_{1}[i]$.
Consequently, the definition of $<_{g}$ is identical to that in Section 2. If
$<_{g}$ identified in this fashion is a DAG then we call it the DAG induced by
$A$. Using the DAG induced by $A$ in this manner, we define DAG-inducing
algorithms, next.

###### Definition 4.1.

DAG-inducing algorithms (DIA). Algorithm $A$ is a DIA for a problem $P$,
represented by a predicate $\mathcal{P}$, iff

  * •

$P$ requires that we reach a state where $\mathcal{P}$ is true.

  * •

$\mathcal{P}$ is DAG-inducing with respect to the partial order induced in $S$
by $A$, i.e. $\forall s\in S:\lnot\mathcal{P}(s)\Rightarrow\exists i\ \
\textsc{Impedensable}(i,s,\mathcal{P})$.

  * •

The guard of any action of $A$ checks that $\mathcal{P}(s)$ is false (i.e., if
$g$ is a guard of an action in $A$ then $g\Rightarrow\neg\mathcal{P}(s))$.

Continuing from Definition 4.1, we have

###### Definition 4.2.

Self-stabilizing DIA. $A$ is self-stabilizing only if $\forall s,s^{\prime}\in
S:\textsc{Terminal-
Successor}(s,s^{\prime})\Rightarrow\mathcal{P}(s^{\prime})=true$.

Remark: Note that this definition appears identical to Definition 3.8. The
only difference is that the partial order to define terminal successors is
based on the DAG induced by $A$.

###  4.2. Maximal Matching (MM) problem

As discussed above, MM is one of the problems which is not a DAG-inducing
problem. However, we find that a DAG-inducing algorithm can be developed for
this problem, which we discuss in the following. We start by defining the MM
problem as follows.

###### Definition 4.3.

Maximal matching. In the maximal matching problem, the input is an arbitrary
graph $G$. The state $match.i$ of each node $i$ has the domain
$Adj_{i}\cup\\{\top\\}$. The task is to compute the matchings such that for
any node $i$, (1) $\forall i:match.i\neq top\Rightarrow match.(match.i)=i$,
and (2) if $match.i=\top$, then there must not exist a $j$ in $Adj_{i}$ such
that $match.j=\top$.

We use the following macros. A node $i$ is wrongly matched if $i$ is pointing
to some node $j$, but $j$ is pointing to some node $k\neq i$. A node $i$ is
matchable if $i$ is not pointing to any node, i.e. $match.i=\top$, and there
exists a node $j$ adjacent to $i$ which is also not pointing to any node. A
node $i$ is being pointed to, or $i$ is $i$-pointed, if $i$ is not pointing to
any node, and there exists a node $j$ adjacent to $i$ which is pointing to
$i$. A node sees that another node is being pointed, or $i$ “sees” else-
pointed, if some node $j$ around (in 2-hop neighbourhood of) $i$ is pointing
to another node $k$ and $k$ is not pointing to anyone. A node is unsatisfied
if it is wrongly matched or matchable. A node $i$ is impedensable if $i$ is
i-pointed, or otherwise, given that $i$ does not see else-pointed, $i$ is the
highest ID node which is unsatisfied in its 2-hop neighbourhood.

$\textsc{Wrongly-Matched}(i)\equiv
match.i\neq\top\land(match.i\neq\top\Rightarrow$
---
$(match.(match.i)\neq i\land match.(match.i)\neq\top))$.
$\textsc{Matchable}(i)\equiv match.i=\top\land(\exists j\in
Adj_{i}:match.j=\top)$.
$\textsc{I-Pointed}(i)\equiv match.i=\top\land(\exists j\in
Adj_{i}:match.j=i)$.
$\textsc{Else-Pointed}(i)\equiv\exists j\in Adj^{2}_{i},\exists k\in Adj_{j}:$
$match.j=k\land match.k=\top$.
$\textsc{Unsatisfied}(i)\equiv\textsc{Wrongly-
Matched}(i)\lor\textsc{Matchable}(i)$.
$\textsc{Impedensable-MM}(i)\equiv\textsc{I-Pointed}(i)\lor$
$(\lnot\textsc{Else-Pointed}(i)\land(\textsc{Unsatisfied}(i)\land(\forall j\in
Adj^{2}_{i}:$
$id.j>id.i\lor\lnot\textsc{Unsatisfied}(i)))$.

The algorithm for an arbitrary node $i$ can be defined as follows. If $i$ is
impedensable and i-pointed, then $i$ starts to point to the node which is
pointing at $i$. If $i$ is wrongly matched and impedensable, then $i$ takes
back its pointer, i.e. $i$ starts pointing to $\top$. Otherwise (if $i$ is
matchable and impedensable) $i$ chooses a node $j$ which is not pointing to
anyone, i.e. $match.j=\top$, and $i$ starts pointing to $j$.

###### Algorithm 3.

Rules for node $i$.

$\begin{array}[]{|l|}\hline\cr\textsc{Impedensable-MM}(i)\longrightarrow\\\
\begin{cases}match.i=j:j\in Adj_{i}:match.j=i&\text{if
$\textsc{I-Pointed}(i)$}.\\\ match.i=\top&\text{if $\textsc{Wrongly-
Matched}(i)$}.\\\ match.i=j:j\in
Adj_{i}:match.j=\top&\text{otherwise}.\end{cases}{}\\\ \hline\cr\end{array}$

$v_{4}$$v_{2}$$v_{3}$$v_{1}$

$\top,\top,\top,\top$
---
$\langle 2,2,2,2\rangle=8$
$\top,\top,\top,v_{1}$
---
$\langle 1,0,0,0\rangle=1$
$\top,\top,\top,v_{2}$
---
$\langle 0,1,0,0\rangle=1$
$\top,\top,\top,v_{3}$
---
$\langle 0,0,1,0\rangle=1$
$v_{4},\top,\top,v_{1}$
---
$\langle 0,0,0,0\rangle=0$
$\top,v_{4},\top,v_{2}$
---
$\langle 0,0,0,0\rangle=0$
$\top,\top,v_{4},v_{3}$
---
$\langle 0,0,0,0\rangle=0$

Figure 4. (a) Input graph. (b) The state transition diagram, a DAG, assuming
that initial global state is $\langle\top,\top,\top,\top\rangle$. In every
state, the first row shows the global state, the second row shows the
respective local state values of nodes and the rank of the global state.
Observe that any other state will converge to one of these states and then
converge to one of the optimal states in this DAG. Transitive edges are not
shown for brevoty.

###### Lemma 4.4.

Algorithm 3 induces a DAG in the global state space.

###### Proof.

The DAG is induced in the global state space with respect to the state values.
Let $s$ be a suboptimal state that the input graph is in. A node $i$ is
impedensable in $s$ (1) if $i$ is wrongly matched, (2) if $i$ is matchable, or
(3) if $i$ is being pointed at by another node $j$, but $i$ does not point
back to $j$ or any other node.

Next we show that if some node $i$ is impedensable in some state $s$, then for
any state $s^{\prime}:s^{\prime}>s$, if $s^{\prime}[i]=s[i]$, then
$s^{\prime}$ will not form a maximal matching under Algorithm 3.

In the case if $i$ is wrongly matched in $s$ and is impedensable, and it is
pointing to the same node in $s^{\prime}$ as well, then $i$ stays to be
impedensable in $s^{\prime}$ because any other node will not take back its
pointer before $i$ does under Algorithm 3. Thus $s^{\prime}$ does not have a
correct matching.

In the case if in $s$, $i$ is being pointed to by some node but $j$ does not
point to any node, and $i$ stays in the same state in $s^{\prime}$, then
$s^{\prime}$ is stays to be impedensable as $s^{\prime}$ because once a node
points towards an unmatched node, it does not retreat its pointer under
Algorithm 3. Also, any node in $Adj^{2}_{j}$ will not execute until $i$ does
under. Thus $s^{\prime}$ does not form a correct matching.

Finally, in the case if $i$ is matchable and impedensable in $s^{\prime}$, and
it stays the same in $s^{\prime}$, then it is still impedensable as any other
node in $Adj_{i}$ will not initiate matching with it under Algorithm 3. Also,
any node in $Adj^{2}_{i}$ will not execute until $i$ does. Thus $s^{\prime}$
stays to be impedensable. ∎

We define the state value and rank as follows.

$\textsc{State-Value-MM}(i,s)=\begin{cases}3&\text{if $\textsc{Wrongly-
Matched}(i)$}.\\\ 2&\text{if
$\textsc{Matchable}(i)\land\lnot\textsc{I-Pointed(i)}$}.\\\ 1&\text{if
$\textsc{I-Pointed(i)}$}.\\\ 0&otherwise.\end{cases}$

$\textsc{Rank-MM}(s)=\sum\limits_{i\in V(G)}\textsc{State-Value-MM}(i,s).$

###### Theorem 4.5.

Algorithm 3 is a DAG-inducing algorithm for the maximal matching problem.

###### Proof.

We show that (1) Algorithm 3 traverses a DAG that has the properties as
mentioned in Lemma 4.4, (2) for all subpotimal states $\exists$ a terminal
successor, and (3) all terminal global states are optimal states.

If $s$ is suboptimal, then for at least one of the nodes $i$: (1) $i$ is
wrongly matched, (2) $i$ is matchable, or (3) $i$ is being pointed at by
another node $j$, but $i$ does not point back to $j$ or any other node.

In the case that $s$ is suboptimal and some node $i$ is being pointed to by
some node $j$ and $i$ does not point to any node, then under Algorithm 3, $i$
will point back to $j$, and thus the state value of $i$ will get reduced from
$1$ to $0$.

In the case that $s$ is suboptimal and some node $j$ is wrongly matched or
matchable with $\lnot\textsc{Else-Pointed}(j)$, then at least one node (e.g.,
a node with highest ID which is wrongly matched or matchable) will be
unsatisfied and impedensable. Let that $i$ is unsatisfied and impedensable.
Here $i$ is either wrongly matched or matchable. If $i$ is wrongly matched,
then $i$ will change its pointer and start pointing to $\top$, in which case
its state value will change from 3 to 2, 1, or 0. If $i$ is matchable then,
$i$ will start pointing to some node $i^{\prime}$ in $Adj_{i}$, in which case,
the state value of $i$ will change from 2 to 0 and the state value of
$i^{\prime}$ will change from 2 to 1.

In all the above cases, we have that under Algorithm 3, if $s$ is a suboptimal
state, then its rank will be of some value greater than zero because at least
one of the nodes will be impedensable. $s$ will transition to some state
$s^{\prime}$ whose rank is less than that of $s$. Thus, we have that Algorithm
3 transitions $s$ to $s^{\prime}$ and thus decreases the rank of the system.
This shows that (1) Algorithm 3 traverses a DAG that has the properties as
mentioned in Lemma 4.4, (2) for all subpotimal states $\exists$ a terminal
successor.

In the case that $s$ is an optimal state, then none of the nodes will be
optimal. So no node will change its state. This state will manifest a maximal
matching. This shows that all terminal successors are optimal states. ∎

###  4.3. 2- approximation vertex cover (VC)

In this section, we consider the problem of 2-approximation vertex cover to
demonstrate that DAG-inducing algorithms can be applied for approximation
algorithms for NP-Hard problems as well.

###### Definition 4.6.

Vertex cover. In the vertex cover problem, the input is an arbitrary graph $G$
with every node having a domain $\\{IN,OUT\\}$. The output is a minimal set
$\mathcal{V}$ such that for every edge $\\{i,j\\}\in E(G)$, either
$i\in\mathcal{V}$ or $j\in\mathcal{V}$ or both.

The standard two approximation algorithm for the VC problem can be stated as
follows.  Choose an uncovered edge $\\{A,B\\}$, select both $A$ and $B$,
repeat until all edges are covered.  Since the minimum VC must contain either
$A$ or $B$, the selected VC is at most twice the size of the minimum VC.

While the above algorithm is sequential in nature, (Gupta2022a, ) presented
its distributed version under the paradigm of lattice linearity. For the sake
of completeness, we describe a key idea and the correctness of this algorithm.
Then, we show how it can be transformed into a DAG-inducing algorithm.

In the lattice linear algorithm (Gupta2022a, ), all nodes are initially out of
the VC. A node is called done if it has already evaluated if all the edges
incident on it are covered, and executed the respective action. But only
impedensable nodes perform an execution. A node is impedensable if it is not
done yet and it is the highest ID node in its distance-3 neighbourhood which
is not done. If node $i$ is impedensable and it has uncovered edges then $i$
and one neighbour $j$ of $i$ is added to vertex cover. The algorithm presented
in (Gupta2022a, ) is shown in Figure 5. While the transformed DAG-inducing
algorithm is similar to Figure 5, we use this to distinguish between lattice
linear and DAG-inducing algorithms.

1 | Init: $\forall i\in V(G),st.i=OUT,done.i=false$.
---|---
2 |  Impedensable-VC$(i)$ $\equiv done.i=false\land(\forall j\in Adj^{3}_{i}:$
3 |  $id.j<id.i\lor done.j=true)$.
4 |
5 | Rules for node $i$.
6 |  Impedensable-VC$(i)$ $\longrightarrow$
7 |  if $(\forall k\in Adj_{i},st.k=IN)$, then $done.i=true$.
8 |  else, then
9 |  $j=\text{arg}\max\\{id.x:x\in Adj_{i}\land done.x=false\\}$.
10 |  $st.i=IN$.
11 |  if $j\neq\top$, then $st.j=IN$, $done.j=true$.
12 |  $done.i=true$.
Figure 5. A 2-approx. lattice linear algorithm for VC (Gupta2022a, ).

The algorithm in Figure 5 is lattice linear, as shown in (Gupta2022a, ). It
means that the global states form a lattice.

In Figure 6, we show a graph (containing eight nodes $v_{1},...,v_{8}$) and
the lattice induced by the algorithm, in Figure 5, in the state space of that
graph. We are omitting how the value of $done.i$ gets modified; we only show
how the vertex cover is formed. Only the reachable states are shown. The
global states in the lattice are written as
$(st.v_{1},st.v_{2},\cdots,st.v_{8})$.

$v_{2}$$v_{1}$$v_{3}$$v_{6}$$v_{4}$$v_{5}$

$(OUT,OUT,OUT$
---
$OUT,OUT,OUT)$
$(OUT,IN,IN$
---
$OUT,OUT,OUT)$
$(OUT,OUT,OUT$
---
$OUT,IN,IN)$
$(OUT,IN,IN$
---
$OUT,IN,IN)$

Figure 6. Execution of the algorithm in Figure 5: (a) input graph, and (b)
lattice induced in the input graph. Transitive edges are not shown for
brevity.

####  4.3.1. Correctness of the algorithm in Figure 5

If an impedensable node has an uncovered edge, and assume that $\\{i,j\\}$ is
an uncovered edge with $j$ being the highest ID node which is out (note that
$i$ is out), then $i$ turns both $i$ and $j$ into the VC. If otherwise $i$
evaluates that all its edges are covered, then it declares that it is done
($i$ sets $done.i$ to true), while staying out of the VC.

This is straightforward from the 2-approximation algorithm for VC.
3-neighbourhood to evaluate impedensable ensures that race conditions do not
arise while execution from the perspective of the 2-approximation algorithm
for VC.

####  4.3.2. Why the algorithm in Figure 5 is lattice linear

Under this algorithm, when any impedensable node evaluates that one of its
edges is uncovered, it selects itself and a node with highest ID to move into
the VC. As a result, the local states form a total order. And therefore, the
partial order that results among the global states because of this total order
among the local states is a lattice.

####  4.3.3. Transforming into a DAG-inducing algorithm

If the chosen node $j$ such that $j$ is the highest ID node in $Adj_{i}$ that
is not in the VC and is not done, then the resultant discrete structure will
be a lattice (Gupta2022a, ). However, ideally, a chosen node $j$ can be any
node in $Adj_{i}$ which is not in the VC and is not done. If we let $i$ choose
an arbitrary neighbour, in this way, to add to the VC, the resulting structure
will be a DAG but not a lattice. And thus, the resulting algorithm will be a
DAG-inducing algorithm. We write this as Algorithm 4 for the sake of
completeness.

###### Algorithm 4.

Follow the algorithm in Figure 5. Change line 9 to
$j=x:x\in Adj_{i}\land done.x=false$
to enable node $i$ to choose an arbitrary vertex $j$.

Thus, it follows that there are cases where lattice linear algorithms force
certain determinism to induce a lattice structure. By contrast, DAG-inducing
algorithms permit more non-determinism.

###### Example 4.7.

In Figure 7, we show the DAG induced by Algorithm 4 (where a node can choose
any of its neighbours to turn into the VC) in the state space of the graph
presented in Figure 6 (a). ∎

$(OUT,OUT,OUT$
---
$OUT,OUT,OUT)$
$(OUT,OUT,OUT$
---
$OUT,IN,IN)$
$(OUT,OUT,OUT$
---
$IN,OUT,IN)$
$(OUT,IN,IN$
---
$OUT,OUT,OUT)$
$(OUT,IN,IN$
---
$OUT,IN,IN)$
$(OUT,IN,IN$
---
$IN,OUT,IN)$
Figure 7. Execution of Algorithm 4: DAG induced in the graph as shown in
Figure 6 (a). Transitive edges are not shown for brevity.

##  5\. Properties of DAG-Induction

###  5.1. DAG-induction to obtain asynchrony

###### Theorem 5.1.

An algorithm converges in asynchronous systems iff it traverses a DAG of
global states (given that an optimal state is reachable, starting from the set
of provided initial states).

###### Proof.

If: This follows from the definition of DAG-inducing problems and DAG-inducing
algorithms.

Only If: An algorithm $A$ must guarantee two things in any scheduler: (1)
upper bound on convergence time, (2) correctness in all executions.

For any scheduler, to guarantee convergence with correctness, for any pair of
global states $s,s^{\prime}\in S$ if there is a path from $s$ to $s^{\prime}$,
then there must not be a path from $s^{\prime}$ to $s$. Otherwise, there will
always a possibility that $A$ can traverse $s^{\prime}$ to $s$ and then from
$s$ to $s^{\prime}$; this can continue for an arbitrary number of times, and
that is why, an upper bound to the convergence time cannot be guaranteed.

To guarantee convergence within an upper time bound, we must guarantee for a
finite value $k$ that the rank of the system will decrease in every $k$ steps.
That is, within $k$ time steps, if the system is in state $s$, then it moves
to some state $s^{\prime}$ such that the rank of $s^{\prime}$ is less than the
rank of $s$. If the states do not form a DAG, then again there is a
possibility for the system to transition from $s^{\prime}$ to $s$ or
otherwise, never reach $s^{\prime}$.

Thus, we have that if the algorithm is running under an asynchronous scheduler
and the states do not form a DAG, then one of the above properties cannot be
guaranteed. ∎

###  5.2. Time Complexity Properties of an algorithm traversing a $<$-DAG

###### Theorem 5.2.

The convergence time is the longest path in the DAG induced among the global
states.

###### Proof.

We have that any impedensable state $s$ will transition to a state
$s^{\prime}$ where $s^{\prime}>s$. Thus every transition takes the system
higher in the induced DAG. Therefore, the convergence time is the longest path
in the $<$-DAG induced among the global states. ∎

Since the local states form a partial order, the the upper bound to the
convergence time can also be evaluated in terms of the size of a local state
as follows.

###### Corollary 5.3.

Let that in each node, atmost $r$ of these variables,
$var_{1}.i,...,var_{r}.i$ (with domain sizes
$m_{1}^{\prime},...m_{r}^{\prime}$ respectively) contribute independently to
the formation of the lattice. Then an algorithm traversing a $<$-DAG will
converge in $n\times\Big{(}\prod\limits_{j=1}^{r}(m_{j}^{\prime}-1)\Big{)}$
moves.

###### Corollary 5.4.

(From Theorem 3.11 and Corollary 5.3) Algorithm 1 converges in
$\sum\limits_{i\in V(G)}deg(i)=2m$ moves. In terms of rounds, it converges in
$\Delta$ rounds, where $\Delta$ is the maximum degree of the input graph.

###### Corollary 5.5.

(From Theorem 3.14 and Corollary 5.3) Algorithm 2 converges in $2n$ moves.

###### Corollary 5.6.

(From Theorem 4.5 and Corollary 5.3) Algorithm 3 converges in $2n$ moves.

###### Corollary 5.7.

(Gupta2022a, ) Algorithm 4 converges in $n$ moves.

##  6\. Related Work

Lattices and DAGs among states in distributed systems: In (Garg2020, ), the
authors have described problems which possess a predicate under which the
states naturally form a lattice. Problems like the stable marriage problem,
job scheduling, market clearing price and others are studied in (Garg2020, ).
In (Garg2021, ) and (Garg2022, ), the authors have studied lattice linearity
in, respectively, housing market problem and several dynamic programming
problems.

In (Gupta2021, ), the authors have extended the theory in (Garg2020, ) to
develop eventually lattice linear self-stabilizing algorithms for some non-
lattice linear problems. Such algorithms induce single or multiple disjoint
lattices in a subset of the state space of the transition system. In
(Gupta2022, ), the authors presented a fully lattice linear algorithm for the
minimal dominating set problem, where the algorithm induces single or multiple
disjoint lattices among the global states.

In this paper, we introduce DAG-inducing problems and DAG-inducing algorithms.
We observed that induction of a DAG provides greater choices to individual
nodes as compared to their lattice linear counterparts, and thus provides more
nondeterminism.

We demonstrate that the dominant clique problem and the shortest path problem
are DAG-inducing problems. Among these the dominant clique problem allows
self-stabilization whereas the (algorithm for) shortest path problem does not.
We demonstrate that the maximal matching problem and 2-approximation vertex
cover are not DAG-inducing problems. We present DAG-inducing algorithm for
them. Among these, the algorithm for maximal matching allows self-
stabilization and the 2-approximation algorithm for vertex cover does not. We
study upper bound to the convergence time of an algorithm traversing a DAG of
states. We show why inducing a $<$-DAG in the state space allows nodes to
perform execution in asynchrony based on old values of other nodes. The
algorithms for the dominant clique problem and shortest path problem both
converge in $2m$ moves. The algorithm for the maximal matching problem
converges in $2n$ moves and the 2-approximation algorithm for vertex cover
converges in $n$ moves.

Maximal Matching: A distributed self-stabilizing algorithm for the maximal
matching problem is presented in (Hsu1992, ); this algorithm converges in
$O(n^{3})$ moves. The algorithm in (Hanckowiak2001, ) converges in
$O(\log^{4}n)$ moves under a synchronous scheduler. The algoritrithm for
maximal matching presented in (Goddard2003, ) converges in $n+1$ rounds.
Hedetniemi et al. (2001) (Hedetniemi2001, ) showed that the algorithm
presented in (Hsu1992, ) converges in $2m+n$ moves.

In this paper, the DAG-inducing algorithm for maximal matching that we present
converges in $2n$ moves and does not require a synchronous environment. This
is an improvement as compared to the results presented in the literature.

##  7\. Conclusion

In this paper, we introduce the class of problems called DAG-inducing problems
and the class of algorithms called DAG-inducing algorithms.

The key idea in these problems and algorithms is that when the algorithm is in
a suboptimal state, there is at least one process that is impedensable; those
are the processes whose execution is essential to reach the optimal state.

DAG-inducing problems exhibit a DAG among their states based on the problem
definition. In the case that a problem is not DAG-inducing, a DAG-inducing
algorithm may be designed for it. In both cases, since the execution of the
impedensable nodes causes the program to move up in the DAG, correctness is
guaranteed in asynchronous execution (where nodes may have to rely on old
information).

As an example, we study the dominant clique (DC) problem and the shortest path
(SP) problem and show that they are DAG-inducing problems. We demonstrated an
algorithm which traverses a DAG of states and reaches an optimal state,
starting from an arbitrary state. Thus, we have that the DC problem is a self-
stabilizing DAG-inducing problem. In contrast, the algorithm that we present
for SP problem is not self-stabilizing.

We also study the maximal matching (MM) problem and 2-approximation vertex
cover. These problems are non-DAG-inducing problems. We present a DAG-inducing
algorithm for the MM problem, which induces a $<$-DAG of states and reaches an
optimal state, starting from an arbitrary state. Thus, the algorithm that we
presented for the MM problem is a self-stabilizing DAG-inducing algorithm. On
the other hand, the algorithm presented for 2-approximation vertex cover is
not self-stabilizing. It remains to be an open problem whether a distributed
DAG-inducing self-stabilizing algorithm can be developed for 2-approximation
vertex cover.

In the literature, there are works on lattice linear problems and lattice
linear algorithms, where a ($<$-)lattice is induced under a predicate or an
algorithm respectively. Since a lattice is a subclass of a DAG, from the
observations that we make in this paper, we have that the lattice linear
problems are a proper subset of the class of DAG-inducing problems, and
lattice linear algorithms are a proper subset of the class of DAG-inducing
algorithms. This can be observed from the fact that the discrete structure
that is induced among the states of an instance of the DC problem is a DAG but
not a lattice (cf. Figure 1), and similarly, the states of an instance of the
MM problem, as induced under Algorithm 3, is also a DAG but not a lattice (cf.
Figure 4). The same can be observed in Figures 3 and 7.

We analyzed the time complexity bounds of an algorithm traversing a DAG of
states (whether present naturally in the problem or imposed by the algorithm).
As corollaries of this analysis, we obtain the time complexity bounds for all
the algorithms present in this paper. We also observed that asynchrony can be
allowed if and only if a DAG is induced among the global states.

## References

  * (1) Chase, C. M., and Garg, V. K. Efficient detection of restricted classes of global predicates.  In Distributed Algorithms (Berlin, Heidelberg, 1995), J.-M. Hélary and M. Raynal, Eds., Springer Berlin Heidelberg, pp. 303–317.
  * (2) 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.
  * (3) Garg, V. K. Predicate Detection to Solve Combinatorial Optimization Problems.  Association for Computing Machinery, New York, NY, USA, 2020, p. 235–245.
  * (4) 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.
  * (5) Goddard, W., Hedetniemi, S., Jacobs, D., and Srimani, P. Self-stabilizing protocols for maximal matching and maximal independent sets for ad hoc networks.  In Proceedings International Parallel and Distributed Processing Symposium (2003), pp. 14 pp.–.
  * (6) 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.
  * (7) Gupta, A. T., and Kulkarni, S. S. Brief announcement: Fully lattice linear algorithms.  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. 341–345.
  * (8) Gupta, A. T., and Kulkarni, S. S. Lattice linear problems vs algorithms, 2022.
  * (9) Hanckowiak, M., Karonski, M., and Panconesi, A. On the distributed complexity of computing maximal matchings.  SIAM Journal on Discrete Mathematics 15, 1 (2001), 41–57.
  * (10) Hedetniemi, S. T., Jacobs, D. P., and Srimani, P. K. Maximal matching stabilizes in time o(m).  Information Processing Letters 80, 5 (2001), 221–223.
  * (11) Hsu, S.-C., and Huang, S.-T. A self-stabilizing algorithm for maximal matching.  Information Processing Letters 43, 2 (1992), 77–81.
  * (12) Medhi, D., and Ramasamy, K. Network Routing: Algorithms, Protocols, and Architectures, 2 ed.  The Morgan Kaufmann Series in Networking. Morgan Kaufman, 2017.