$\displaystyle\leq(1-\beta)\cdot\mathbb{E}\left(\pi(G-X,C^{-X})\right)$
$\displaystyle\leq(1-\beta)\cdot\mathbb{E}\left(\Pi^{u}_{P}\right)\,,$

where the last inequality holds due to Eq. 10. We can conclude that the total
potential, in expectation, that is removed during the time interval
$(t,t+\tau+\phi]$ is at least

$\mathbb{E}(\Pi^{d}_{P})+\beta\mathbb{E}\left(\Pi^{u}_{P}\right)\geq\beta\cdot\left(\mathbb{E}(\Pi^{d}_{P})+\mathbb{E}\left(\Pi^{u}_{P}\right)\right)\geq\beta\cdot\frac{1}{4\phi^{2}}\pi(G,C),$

by Eq. 8 and Eq. 9. ∎

In the round interval $[t^{*}_{a},t^{*}_{b}-1]$, the adversary may manipulate
nodes. In order to distinguish between the edge configuration that resulted
from the execution of $\mathcal{A}_{\mathit{ST}}$ and the graph and edge
configuration that the next round is executed on, we will formally define
both. We denote by $G_{t}\in\mathcal{G}$ the graph at time $t$, i.e., the
graph that resulted from the adversary manipulations in round $t-1$
(manipulations that occurred at time $t-\epsilon$), for every time
$t\in\mathbb{Z}_{\geq 0}$. Since the graph may only change by the adversary,
we denote by $G_{a}$ the graph $G_{t}$ for every time $t\leq t^{*}_{a}$.
Recall that we denote by $G$ the graph $G_{t^{*}_{b}}$. We denote by
$\widetilde{C}_{t}$ the edge configuration of $\mathcal{A}_{\mathit{ST}}$ that
corresponds to the edge configuration after all nodes finished their local
computation stage in round $t$. Notice that edge configuration
$\widetilde{C}_{t}$ is defined on the graph $G_{t}$ and that
$\widetilde{C}_{t}=C_{t+1}$ for every time $t\leq t^{*}_{a}-1$ and $t\geq
t^{*}_{b}$.

We now turn to redefine the set $\hat{D}_{t}$ and the edge configuration
$\hat{C}_{t}$. For every $t\geq t^{*}_{a}+1$ the set of edges that became
decided during round $t$ (by the simulation of the decision step of
$\mathtt{Phase}$) is denoted by $\hat{D}_{t}=U(C_{t})\cap
D(\widetilde{C}_{t})$. Let $\hat{f}_{t}:\hat{D}_{t}\rightarrow\mathcal{O}$ be
the function that corresponds to the decisions of the edges that were set in
for edges in $\hat{D}_{t}$ during round $t$, i.e.,
$\hat{f}(e)=\widetilde{C}_{t}(e)$ for every $e\in\hat{D}_{t}$. We denote by
$\hat{C}_{t}=[C_{t}\nwarrow\hat{f}]$ the edge configuration $C_{t}$ after
setting the decisions of round $t$ to the edges in $\hat{D}_{t}$.

We denote by $K\subseteq V(G)$ the set of nodes in $G$ that were manipulated
during the round interval $[t^{*}_{a},t^{*}_{b}-1]$. Notice that $|K|\leq k$.
Let $V_{0}=V(G)-K$ be the set of nodes in $G$ that were not manipulated and
let $E_{0}=E(G(V_{0}))$ be the set of edges in the subgraph of $G$ induced by
$V_{0}$. Let $V^{f}_{0}=\\{v\in V_{0}\mid\delta_{G}(v,K)\geq\phi+1\\}$ be the
set of nodes in $V_{0}$ that are at distance at least $\phi+1$ from any
manipulated node in $K$ in the graph $G$. Let $E^{f}_{0}=E(G(V_{0}^{f}))$ be
the set of edges in the subgraph of $G$ induced by $V^{f}_{0}$. Let
$K_{t}\subseteq V(G_{t})$ be the set of nodes that were manipulated in round
$t$. We denote by
$\delta^{m}_{t}(v)=\min\\{\delta_{G_{t^{\prime}}}(v,K_{t^{\prime}})\mid
t^{*}_{a}\leq t^{\prime}\leq t\\}$ for every $v\in V^{f}_{0}$ and $t\geq
t^{*}_{a}$.

######  Observation 11.7.

The following statements are true for every $t\geq t^{*}_{a}$:
(1) Every edge $e\in E^{f}_{0}$ is port-consistent at time $t$;
(2) $N_{G_{t}}(v)=N_{G_{a}}(v)=N_{G}(v)$, for every $v\in V_{0}$;
(3) $\delta^{m}_{t}(v)\geq\delta_{G}(v,K)\geq\phi+1$;
(4) $E^{f}_{0}\cap\Lambda(C_{t})=E^{f}_{0}\cap D(C_{t})\cap
U(\widetilde{C}_{t})=E^{f}_{0}\cap D(\hat{C}_{t})\cap U(\widetilde{C}_{t})$;
(5) $E^{f}_{0}\cap D(C_{t+1})=E^{f}_{0}\cap(D(\hat{C}_{t})-\Lambda(C_{t}))$;
(6) $E^{f}_{0}\cap D(C_{t})=E^{f}_{0}\cap D(\widetilde{C}_{t-1})$;
(7) $E^{f}_{0}\cap\Gamma(C_{t})=E^{f}_{0}\cap\Gamma(\widetilde{C}_{t-1})$; and
(8) if $e\in D(C_{t+1})$, then
$\widetilde{C}_{t}(e)=\hat{C}_{t}(e)=C_{t+1}(e)=\hat{C}_{t+1}(e)$, for every
$e\in E^{f}_{0}$.

Consider some time $t\geq t^{*}_{a}$ and an edge $e=\\{v,u\\}\in E(G_{t})$. We
denote by $V^{e}_{t}=\\{v,u\\}\cup\\{\\{w,x\\}\in E(G_{t})\mid\\{w,x\\}\in
N_{G_{t}}(e)\\}$.

######  Lemma 11.8.

For every $t\geq t^{*}_{a}$ it holds that $E^{f}_{0}\cap D(C_{t})\subseteq
E^{f}_{0}\cap\Gamma(\hat{C}_{t-1})$.

###### Proof.

Every node $v\in V^{f}_{0}$ simulating the decision step of $\mathtt{Phase}$
in round $t-1$ has $\mathit{step}_{v,t-1}=\phi-1$, which means that
$\mathit{step}_{v,t-\phi}=0$ by the design of the $\mathtt{PPS}$ module since
$v$ was not manipulated. Let $t^{\prime}=t-\phi$ and assume that
$t^{\prime}\geq t^{*}_{a}$. In round $t^{\prime}$ node $v$ simulated the $0$
step of $\mathtt{Phase}$, hence initialized all the registered maintained by
$\mathtt{Phase}$. Node $v$ and all the nodes $u\in V_{0}$ such that
$\delta^{m}_{t}(u)\geq\phi$ that are engaged in the phase that started at time
$t^{\prime}$ were not manipulated, hence simulated an execution of
$\mathtt{Phase}$ based on messages they received that corresponds to a full,
fault free, execution of $\mathtt{Phase}$ by Obs. 11.7.

Let $e\in E^{f}_{0}\cap D(C_{t})$. First we will prove that
$e\notin\Lambda(C_{t-1})$. Assume by contradiction that
$e=\\{v,u\\}\in\Lambda(C_{t-1})$. Since all the nodes in $V^{e}_{t}$ were not
manipulated in round $t-2$, it holds that
$\mathtt{Detect}_{v,t-1}(u)=\mathtt{Detect}_{v,t-1}(v)=\mathit{false}$ and
$\widetilde{C}_{t-1}(e)=C_{t}(e)=\bot$, by the design of
$\mathcal{A}_{\mathit{ST}}$ and the guarantee of $\mathtt{Detect}$. Hence,
$e\notin D(C_{t})$.

If $e\in U(C_{t-1})$, then $v$ and $u$ simulated the decision step of
$\mathtt{Phase}$ in round $t-1$ and by Prop. 6, it holds that $e\in
E^{f}_{0}\cap\Gamma(\hat{C}_{t-1})$. Otherwise ($e\in D(C_{t-1})$), the nodes
$w$ and $x$ such that $\\{w,x\\}\in U_{v}(C_{t-1})\cap D(\hat{C}_{t-1})$
simulated the decision step of $\mathtt{Phase}$ in round $t-1$. By Prop. 6, it
holds that $e\in\Gamma(\hat{C}_{t-1})$. ∎

We denote by $C_{a}$ the configuration $C_{t^{*}_{a}}$.

######  Lemma 11.9.

For every $e=\\{v,u\\}\in E_{0}$, it holds that if
$\delta_{G}(v,K)\geq\mathit{depth}_{D_{\mathcal{L}}}(C_{a}(e))+\phi+1$ and
$\delta_{G}(u,K)\geq\mathit{depth}_{D_{\mathcal{L}}}(C_{a}(e))+\phi+1$, then
$C_{t}(e)=C_{a}(e)$, for every $t\geq t^{*}_{a}$.

###### Proof.

The claim obviously holds for $t=t^{*}_{a},\cdots,t^{*}_{a}+\phi$, so we
assume hereafter that $t\geq t^{*}_{a}+\phi+1$. Recall that $\phi\geq 2$. Let
$e^{\prime}=\\{w,x\\}\in E^{f}_{0}$ be some edge and let
$C_{a}(e^{\prime})=o\in\mathcal{O}$. Assume that there exists a time $t\geq
t^{*}_{a}+\phi+1$ such that $C_{t}(e^{\prime})\neq o$ and let $t$ be the first
time it occurred. By Obs. 11.7, we know that
$\widetilde{C}_{t-1}(e^{\prime})=C_{t}(e^{\prime})\neq o$. Since
$C_{t-1}(e^{\prime})=o$ and the nodes $w$ and $x$ were not manipulated in
round $t-2$, it holds that $e^{\prime}$ changed decision since
$\mathtt{Detect}_{w,t-1}(x)=\mathtt{Detect}_{x,t-1}(w)=\mathit{false}$ by the
construction of $\mathcal{A}_{\mathit{ST}}$. Since the nodes in
$V^{e^{\prime}}_{t-2}$ were not manipulated in round $t-2$, by the guarantee
of $\mathtt{Detect}$, it holds that $e^{\prime}$ is uncontent under $C_{t-1}$.
Since $e^{\prime}\in D(C_{t-1})$ and $t\geq t^{*}_{a}$, by Lem. 11.8, it holds
that $e^{\prime}\in\Gamma(\hat{C}_{t-2})$. We denote by
$\hat{M}^{e^{\prime}}_{t-2}\in\mathcal{T}^{*}(o)$ some core for $o$ such that
$\hat{M}^{e^{\prime}}_{t-2}\subseteq\hat{C}_{t-2}[e^{\prime}]\in\mathcal{T}(o)$.

We will prove the claim by induction on
$\mathit{depth}_{D_{\mathcal{L}}}(\cdot)$. Let $e=\\{v,u\\}\in E_{0}$ be some
edge such that
$\delta_{G}(v,K)\geq\mathit{depth}_{D_{\mathcal{L}}}(C_{a}(e))+\phi+1$,
$\delta_{G}(u,K)\geq\mathit{depth}_{D_{\mathcal{L}}}(C_{a}(e))+\phi+1$ and
$\mathit{depth}_{D_{\mathcal{L}}}(C_{a}(e))=0$ and let
$C_{a}(e)=o\in\mathcal{O}$. Assume by contradiction that there exists a time
$t\geq t^{*}_{a}+\phi+1$ such that $C_{t}(e)\neq o$ and let $t$ be the first
time it occurred. Since $\mathit{depth}_{D_{\mathcal{L}}}(o)=0$, every core
for $o$ is the empty set, hence $\hat{M}^{e}_{t-2}=\emptyset$. The only
difference between configurations $\hat{C}_{t-2}$ and $\widetilde{C}_{t-2}$ is
that decided edges under $\hat{C}_{t-2}$ may become undecided under
$\widetilde{C}_{t-2}$. By the definition of a core
$e\in\Gamma(\widetilde{C}_{t-2})$ and by Obs. 11.7, $e\in\Gamma(C_{t-1})$
which is a contradiction.

Let $e=\\{v,u\\}\in E_{0}$ be some node such that
$\delta_{G}(v,K)\geq\mathit{depth}_{D_{\mathcal{L}}}(C_{a}(e))+\phi+1$,
$\delta_{G}(u,K)\geq\mathit{depth}_{D_{\mathcal{L}}}(C_{a}(e))+\phi+1$ and
$\mathit{depth}_{D_{\mathcal{L}}}(C_{a}(e))=i>0$ and let
$C_{a}(v)=o\in\mathcal{O}$. Assume by contradiction that there exists a time
$t\geq t^{*}_{a}+\phi+1$ such that $C_{t}(e)\neq o$ and let $t$ be the first
time it occurred. It holds that $\emptyset\subset\hat{M}^{v}_{t-2}$, since
$i>0$ which means that the empty set it not a core for $o$. Let
$\hat{B}^{e}_{t-2}\subseteq N_{G}(e)$ be the set of $e$’s neighbors such that
their decisions are in $\hat{M}^{e}_{t-2}$. Since
$\mathit{depth}_{D_{\mathcal{L}}}(o)=i>0$, it holds that
$\mathit{depth}_{D_{\mathcal{L}}}(\hat{C}_{t-2}(e^{\prime}))\leq i-1$ and
$\delta_{G}(w,K)\geq\mathit{depth}_{D_{\mathcal{L}}}(\hat{C}_{t-2}(e^{\prime}))+\phi+1$,
$\delta_{G}(x,K)\geq\mathit{depth}_{D_{\mathcal{L}}}(\hat{C}_{t-2}(e^{\prime}))+\phi+1$
for every $e^{\prime}=\\{w,x\\}\in\hat{B}^{v}_{t-2}$. By induction hypothesis
$C_{t^{\prime}}(e^{\prime})=C_{a}(e^{\prime})$ and
$e^{\prime}\in\Gamma(C_{t^{\prime}})$ for every $t^{\prime}\geq t^{*}_{a}$.
and $e^{\prime}\in\hat{B}^{e}_{t-2}$. Let $e^{\prime}\in\hat{B}^{e}_{t-2}$. By
Obs. 11.7,
$\hat{C}_{t-2}(e^{\prime})=\widetilde{C}_{t-2}(e^{\prime})=C_{t-1}(e^{\prime})$.
The only difference between configurations $\hat{C}_{t-2}$ and
$\widetilde{C}_{t-1}$ is that decided edges under $\hat{C}_{t-2}$ may become
undecided under $\widetilde{C}_{t-2}$. By the definition of a core
$e\in\Gamma(\widetilde{C}_{t-2})$ and by Obs. 11.7, $e\in\Gamma(C_{t-1})$
which is a contradiction. ∎

###### proof of Lem. 11.6.

Every edge $e=\\{v,u\\}\in E_{0}$ such that $\delta_{G}(v,K)\geq\nu+\phi+1$
and $\delta_{G}(u,K)\geq\nu+\phi+1$ will not change its decision at any time
by Lem. 11.9. ∎

##  12 Concrete Problems and Algorithms

In this section, we develop the self-stabilizing algorithms listed in Table 1
and establish their fully adaptive run-time and message size bounds. Sec. 12.1
and 12.2 present the corresponding fault free algorithms (and detection
procedures) for node-LCLs and edge-LCLs, respectively, and derive their
eligibility parameters; the promised bounds are then obtained by plugging
these parameters into Thm. 4.1, 9.1, and 8.1. In Sec. 12.3, we provide an
alternative analysis for the self-stabilizing maximal matching algorithm
produced by the transformer, improving its fully adaptive run-time from
$O(\log(k+\Delta))$ to $O(\log k)$. Note that this alternative analysis relies
on specific features of the maximal matching problem and we do not know if it
can be incorporated into the line of arguments used by the transformer’s
generic analysis.

Consider a graph $G\in\mathcal{U}$ and a positive integer
$\alpha\in\mathbb{Z}_{>0}$. The _clone_ graph of $G_{\alpha}$ is the graph in
which $V(G_{\alpha})=\\{(v,i)\mid v\in V(G),i\in[\alpha]\\}$ and
$E(G_{\alpha})=\\{\\{(v,i),(v,i^{\prime})\\}\mid v\in V(G),1\leq
i<i^{\prime}\leq\alpha\\}\cup\\{\\{(v,i),(u,i)\\}\mid\\{v,u\\}\in
E(G),i\in[\alpha]\\}$. The clone graph was introduced in the seminal paper of
Luby [Lub86]. It is well known that the nodes of a communication network $G$,
can simulate an execution of a fault free distributed algorithm on
$G_{\alpha}$ for every $\alpha\in\mathbb{Z}_{>0}$. Moreover, if $\alpha$ is
“hard coded” into the nodes of $G$ (i.e., cannot be manipulated by the
adversary), then the nodes of $G$ can simulate an execution of a self-
stabilizing algorithm on $G_{\alpha}$.

###  12.1 Node-LCLs

For all problems discussed in this section, we take the straightforward
detection procedure $\mathtt{Detect}$ in which each node $v$ shares its output
register $\mathtt{out}_{v}$ with all its neighbors in every round.

####  12.1.1 Maximal Independent Set

We define the LCL $\mathcal{L}=\\{\ell_{d}\\}^{\infty}_{d=0}$ of maximal
independent set over the output values
$\mathcal{O}=\\{\mathit{IN},\mathit{OUT}\\}$ such that for every
$d\in\mathbb{Z}_{\geq 0}$ and $M\in M_{d}(\mathcal{O})$, it holds that (1)
$\ell_{d}(\mathit{IN},M)=true$ iff $\mathit{IN}\notin M$; and (2)
$\ell_{d}(\mathit{OUT},M)=true$ iff $\mathit{IN}\in M$. By construction,
$\mathcal{L}$ satisfies the $1$-bounded influence property (Prop. 3). Let
$\mathcal{P}=\langle\mathcal{O},\mathcal{U}_{\Delta},\mathcal{L}\rangle$ be
the resulting node-LCL.

##### Eligible distributed algorithm.

We use a modified version of the maximal independent set algorithm developed
in the seminal work of Alon et al. [ABI86]. The eligible distributed algorithm
$\mathcal{A}$ for $\mathcal{P}$ is presented through its phase procedure
$\mathtt{Phase}$ which has phase length of $3$. Let $G\in\mathcal{U}_{\Delta}$
be a graph and let $H$ be the subgraph induced by the undecided nodes at the
beginning of a phase of $\mathtt{Phase}$. Consider a node $v\in V(H)$. In step
$1$, node $v$ marks itself w.p. $1/\mathrm{d}_{H}(v)$ and sends a message to
its undecided neighbors indicating whether it is mark or not together with its
degree $\mathrm{d}_{H}(v)$. Step $2$ is the decision step: If node $v$ has a
decided neighbor with decision $\mathit{IN}$, then $v$ sets
$\mathtt{out}_{v}\leftarrow\mathit{OUT}$. Otherwise, node $v$ sets
$\mathtt{out}_{v}\leftarrow\mathit{IN}$ if and only if it is marked and
$\mathrm{d}_{H}(v)>\mathrm{d}_{H}(u)$ for every marked neighbor $u\in
N_{H}(v)$ of $v$.

##### Locally Separable Potential Function for $\mathcal{P}$.

Given $M,M^{\prime}\in\mathcal{M}(\mathcal{O})$, the potential coefficient
$\sigma(M,M^{\prime})$ is defined by setting $\sigma(M,M^{\prime})=1$ if
$\mathit{IN}\in M$ or $\mathit{IN}\in M^{\prime}$; and
$\sigma(M,M^{\prime})=2$ otherwise. This implies that
$\sigma_{0}=\sigma(\emptyset,\emptyset)=2$.

##### Proving the $(\beta,\sigma_{0})$-Progress Property for $\mathcal{A}$.

Consider a strongly configured graph $(G,C)\in\mathcal{SCG}(\mathcal{P})$ and
let $H=G(U(C))$ be the subgraph induced by the undecided nodes. We make an
extensive use of the operator $\psi_{C}:E(H)\rightarrow\mathbb{Z}_{\geq 0}$
defined by setting $\psi_{C}(e)=\sigma(C[u],C[v])$ for each edge
$e=\\{u,v\\}\in E(H)$. It is convenient to extend the domain of the operator
$\psi_{C}$ from $E(H)$ to $E(G)$, defining $\psi_{C}(e)=0$ for each edge $e\in
E(G)-E(H)$.

For a node $v\in V(H)$, let $N^{g}_{H}(v)=\\{u\in
N_{H}(v)\mid\mathrm{d}_{H}(u)\leq\mathrm{d}_{H}(v)\\}$ be the set of neighbors
$u$ of $v$ whose degree in $H$ is not larger than that of $v$. Node $v$ is
said to be _good_ in $H$ [ABI86] if $|N^{g}_{H}(v)|\geq\mathrm{d}_{H}(v)/3$.
It is a well known fact (see, e.g., [ABI86, Lem. 4.4]) that at least half of
edges in $E(H)$ are incident on a good node (at least one).

Consider the configuration $C^{\prime}=\mathtt{Phase}(G,C)$ obtained from
applying the phase procedure $\mathtt{Phase}$ to $G$ under configuration $C$;
observe that $C^{\prime}$ is a random variable. Let $v\in V(H)$ be a good node
and let $E_{v}=\\{e\in E(H)\mid v\in e\\}$. We will show that, in expectation,
at least a constant fraction of the edges $e\in E_{v}$ satisfy

$\psi_{C^{\prime}}(e)\,\leq\,\psi_{C}(e)-1\,.$ (11)

Since at least half of the edges in $H$ are incident on a good node and since
$\psi_{C}(e)\leq\sigma_{0}=2$ for every edge $e\in E(H)$, it follows that
$\mathbb{E}(\pi(G,C^{\prime}))\leq(1-\beta)\cdot\pi(G,C)$ for a constant
fraction $\beta>0$.

A node $u\in V(H)$ is said to be _doomed_ in $C$ if there exists a node $w\in
D_{u}(C)$ such that $C(w)=\mathit{IN}$. Notice that if $u$ is doomed in $C$,
then $u$ is guaranteed to be decided in $C^{\prime}$. In particular, if $v$ is
doomed in $C$, then $\psi_{C^{\prime}}(e)=0$ for every $e\in E_{v}$, thus
establishing (11). Assume in what follows that $v$ is not doomed in $C$.

Let $Z=\\{u\in N^{g}_{H}(v)\mid\text{$u$ is doomed in $C$}\\}$. If
$|Z|\geq|N^{g}_{H}(v)|/2$, then at least $(1/6)$-fraction of the edges in
$e\in E_{v}$ satisfy $\psi_{C^{\prime}}(e)=0$, thus establishing (11). Assume
that $|N^{g}_{H}(v)-Z|>|N^{g}_{H}(v)|/2$.

It is well known (see, e.g., [ABI86]) that each node $u\in V(H)$ that is not
doomed under $C$ satisfies $C^{\prime}(u)=\mathit{IN}$ with probability at
least $\Omega(1/\mathrm{d}_{H}(u))$. This applies, in particular, to the nodes
in $N^{g}_{H}(v)-Z$, concluding that each node $u\in N^{g}_{H}(v)-Z$ satisfies
$C^{\prime}(u)=\mathit{IN}$ with probability at least
$\Omega(1/\mathrm{d}_{H}(u))\geq\Omega(1/\mathrm{d}_{H}(v))$. Since

$|N^{g}_{H}(v)-Z|\,>\,|N^{g}_{H}(v)|/2\,\geq\,\mathrm{d}_{H}(v)/6\,,$

it follows by a standard probabilistic argument that with a positive constant
probability, at least one node $u\in N^{g}_{H}(v)-Z$ satisfies
$C^{\prime}(u)=\mathit{IN}$. This results in
$\psi_{C^{\prime}}(e)=1=\Psi_{C}(e)-1$ for each edge $e=\\{w,v\\}$ such that
$w\in N^{g}_{H}(v)-Z$, thus establishing (11).

####  12.1.2 Node $(1+\epsilon)\Delta$-coloring

Fix some $\Delta\in\mathbb{Z}_{>0}$ and a constant $\epsilon\geq 1/\Delta$ and
assume with out loss of generality that
$(1+\epsilon)\Delta\in\mathbb{Z}_{>0}$. Let
$\mathcal{L}{}=\\{\ell_{d}\\}^{\infty}_{d=0}$ be an LCL over the output values
$\mathcal{O}=\left[(1+\epsilon)\Delta\right]$ such that for every
$d\in\mathbb{Z}_{\geq 0}$, $i\in\mathcal{O}$, and
$M\in\mathcal{M}_{d}(\mathcal{O})$ it holds that $\ell_{d}(i,M)=\mathit{true}$
iff $M(i)=0$. By the definition of $\mathcal{L}$ it satisfies the $0$-bounded
influence property (Prop. 3.) Let
$\mathcal{P}=\langle\mathcal{O},\mathcal{U}_{\Delta},\mathcal{L}\rangle$ be a
node-LCL and notice that $\mathcal{P}$ is the node coloring problem with
$(1+\epsilon)\Delta$ colors.

##### Eligible distributed algorithm.

We describe the eligible distributed algorithm $\mathcal{A}$ for $\mathcal{P}$
by its phase procedure $\mathtt{Phase}$ which has phase length of $3$. Let
$G\in\mathcal{U}_{\Delta}$ be some graph and let $v\in V(G)$ be some undecided
node at the beginning of $\mathtt{Phase}$. In the $1$ step, node $v$ chooses a
color $c_{v}$ u.a.r. (uniformly at random) from the pallet $\mathcal{O}$ and
sends it to all of its undecided neighbors. In the $2$ step (which is the
decision step), node $v$ sets $\mathtt{out}_{v}=c_{v}$ only if $c_{v}$ differ
from the color of all its decided neighbors and from $c_{u}$ for every
undecided neighbor $u$. If all of $v$’s neighbors are decided, then $v$ sets
$\mathtt{out}_{v}$ to some arbitrarily chosen non-conflicting color from the
set $\mathcal{O}$.

##### Locally Separable Potential Function for $\mathcal{P}$.

The potential coefficients for every $M,M^{\prime}\in\mathcal{M}(\mathcal{O})$
are defined such that $\sigma(M,M^{\prime})=1$. In this definition we get that
$\sigma_{0}=\sigma(\emptyset,\emptyset)=1$. Notice that the resulting
separable potential function for $\mathcal{P}$, denoted by $\pi$, simply
counts the number of edges that both endpoints are undecided.

##### Proving the $(\beta,\sigma_{0})$-progress Property for $\mathcal{A}$.

Consider some $G\in\mathcal{U}_{\Delta}$. Let
$C:V(G)\rightarrow\mathcal{O}\cup\\{\bot\\}$ be a configuration such that
$(G,C)\in\mathcal{SCG}(\mathcal{P})$ and let $v\in U(C)$. We denote by $A_{v}$
the event that node $v$ is decided under configuration $\mathtt{Phase}(G,C)$.
For a neighbor $u\in D_{v}(C)$, we denote by $A_{v,u}$, the event that node
$v$ choose the same color during the execution of $\mathtt{Phase}$ as the
color of neighbor $u$. For a neighbor $u\in U_{v}(C)$ we denote by $A_{v,u}$
the event that nodes $v$ and $u$ choose the same color during the execution of
$\mathtt{Phase}$.

It is easily verifiable that for every $u\in N_{G}(v)$, it holds that
$\mathbb{P}(A_{v,u})\leq\frac{1}{(1+\epsilon)\Delta}$. By the union bound we
get that $\mathbb{P}\left(\bigcup_{u\in
N_{G}(v)}A_{v,u}\right)\leq\frac{1}{1+\epsilon}$. We can conclude that
$\mathbb{P}(A_{v})\geq 1-\frac{1}{1+\epsilon}$, hence for every
$e=\\{u,v\\}\in E(G(U))$, the probability that at least one of $e$’s endpoints
is decided under configuration $\mathtt{Phase}(G,C)$ is at least
$1-\frac{1}{1+\epsilon}=\Omega(1)$. Once $u$ or $v$ becomes decided, the
potential coefficient of edge $e$ (which is $1$) is removed from $\pi$.

####  12.1.3 Maximal Node $c$-coloring

We define the LCL $\mathcal{L}=\\{\ell_{d}\\}^{\infty}_{d=0}$ of maximal node
$c$-coloring over the output values $\mathcal{O}_{c}=\\{1,\cdots,c\\}$ such
that for every $d\in\mathbb{Z}_{\geq 0}$ and $M\in M_{d}(\mathcal{O})$ it
holds that (1) $\ell_{d}(i,M)=true$ iff $i\notin M$ for every $1\leq i\leq
c-1$; and (2) $\ell_{d}(c,M)=true$ iff $M(j)\geq 1$ for every
$j\in\\{1,\cdots,c-1\\}$. By the definition of $\mathcal{L}$ it satisfies the
$1$-bounded influence property (Prop. 3). Let $2\leq c\leq\Delta+2$ be an
integer. Let
$\mathcal{P}=\langle\mathcal{O},\mathcal{U}_{\Delta},\mathcal{L}\rangle$ be
the resulting node-LCL.

Consider some $G\in\mathcal{G}$. The self-stabilizing algorithm for
$\mathcal{P}$, is a simulation of our self-stabilizing maximal independent set
algorithm on $G_{c-1}$. For every node $v\in V(G)$, if all of the nodes
$(v,i)\in V(G_{c-1})$ for $1\leq i\leq c-1$ are decided, then node $v$ takes
the color $i$ if there exists $(v,i)$ that is decided $\mathit{IN}$.
Otherwise, node $v$ takes the color $c$.

####  12.1.4 Node ($\Delta+1$)-coloring

We solve the node $(\Delta+1)$-coloring by solving the maximal node
$(\Delta+2)$-coloring.

####  12.1.5 Incremental Node $c$-coloring

We define the LCL $\mathcal{L}=\\{\ell_{d}\\}^{\infty}_{d=0}$ of incremental
node $c$-coloring over the output values $\mathcal{O}=\\{1,\dots,c\\}$ such
that for every $d\in\mathbb{Z}_{\geq 0}$, $1\leq i\leq c$, and $M\in
M_{d}(\mathcal{O})$, it holds that $\ell_{d}(i,M)=true$ iff (1) $i\notin M$;
and (2) $\sum_{j=1}^{i-1}M(j)\geq i-1$. By construction, $\mathcal{L}$
satisfies the $(c-1)$-bounded influence property (Prop. 3). Let
$\mathcal{P}=\langle\mathcal{O},\mathcal{U}_{\Delta},\mathcal{L}\rangle$ be
the resulting node-LCL.

##### Eligible distributed algorithm.

We use a variant of the maximal independent set algorithm presented in Sec.
12.1.1. The eligible distributed algorithm $\mathcal{A}$ for $\mathcal{P}$ is
presented through its phase procedure $\mathtt{Phase}$ which has phase length
of $3$. Let $G\in\mathcal{U}_{\Delta}$ be a graph and let $H$ be the subgraph
induced by the undecided nodes at the beginning of a phase of
$\mathtt{Phase}$. Consider a node $v\in V(H)$. In step $1$, node $v$ marks
itself w.p. $1/\mathrm{d}_{H}(v)$ and sends a message to its undecided
neighbors indicating whether it is mark or not together with its degree
$\mathrm{d}_{H}(v)$. Step $2$ is the decision step: If node $v$ has at least
$c-1$ decided neighbors with decisions $1\leq i\leq c-1$, then $v$ sets
$\mathtt{out}_{v}\leftarrow c$. Otherwise, if $v$ is marked and
$\mathrm{d}_{H}(v)>\mathrm{d}_{H}(u)$ for every marked neighbor $u\in
N_{H}(v)$ of $v$, then $v$ sets $\mathtt{out}_{v}\leftarrow i_{v}$, where
$i_{v}$ is the smallest $1\leq i\leq c-1$ such that (I) $v$ has no neighbor
with output $i$; and (II) $v$ has at least $i-1$ decided neighbors with
decisions $1\leq j\leq i-1$.

##### Locally Separable Potential Function for $\mathcal{P}$.

The potential coefficients for every $M,M^{\prime}\in\mathcal{M}(\mathcal{O})$
are defined such that
$\sigma(M,M^{\prime})=c+\max\\{0,c-1-\sum_{i=1}^{c-1}M(i)\\}+\max\\{0,c-1-\sum_{i=1}^{c-1}M^{\prime}(i)\\}$.
In this definition we get that $\sigma_{0}=\sigma(\emptyset,\emptyset)=3c-2$.

##### Proving the $(\beta,\sigma_{0})$-progress Property for $\mathcal{A}$.

Consider some strongly configured graph $(G,C)\in\mathcal{SCG}(\mathcal{P})$.
Let $H=G(U(C))$ and let $e=\\{v,u\\}\in E(H)$. We denote by
$\psi(e)=\sigma(C[v],C[u])$. By the definition of the potential coefficients,
it holds that $\psi(e)/\psi(e^{\prime})\leq O(1)$ for every $e,e^{\prime}\in
E(H)$. Let $v\in V(H)$ be a good node and let $E_{v}=\\{\\{v,u\\}\in E(H)\mid
u\in N_{H}(v)\\}$. We will show that, in expectation, at least a constant
fraction of the edges in $E_{v}$ “lose” at least $1$ unit of the potential
under configuration $\mathtt{Phase}{}(G,C)$. Since at least half of the edges
in $H$ are incident on a good node we can conclude that, in expectation, a
$\Omega(1/c)$ fraction of the potential is removed.

Let $v\in V(H)$ be a good node and let $\gamma=|N^{g}_{H}(v)|$, If there exist
$u_{1},\cdots,u_{c-1}\in D_{v}(C)$ such that $C(u_{i})=i$, then $v$ is decided
under $\mathtt{Phase}(G,C)$. Otherwise, if there exist
$u_{1},\cdots,u_{\lceil(1/2)\gamma\rceil}\in|N^{g}_{H}(v)|$ such that for
every $1\leq i\leq\lceil(1/2)\gamma\rceil$ there exist
$w^{i}_{1},\cdots,w^{i}_{c-1}\in D_{u_{i}}(C)$ with $C(w^{i}_{j})=j$, then at
least a constant fraction of the edges in $E_{v}$ “lose” $1$ unit of potential
under configuration $\mathtt{Phase}(G,C)$. Otherwise, using similar arguments
as in [ABI86], we can prove that at least one of $v$’s neighbors in
$N^{g}_{H}(v)$ is marked with at least a constant probability and that a
marked node will be decide with some color $1\leq i\leq c-1$ with at least a
constant probability. Hence, with at least a constant probability, node $v$
has an additional neighbor with some color $i$ for $1\leq i\leq c-1$ under
configuration $\mathtt{Phase}(G,C)$ which means that all the edges in $E_{v}$
“lose” $1$ unit of potential configuration $\mathtt{Phase}(G,C)$.

###  12.2 Edge-LCLs

####  12.2.1 Maximal Matching

We define the LCL $\mathcal{L}=\\{\ell_{d}\\}^{\infty}_{d=0}$ of maximal
maximal matching over the output values
$\mathcal{O}=\\{\mathit{IN},\mathit{OUT}\\}$ such that for every
$d\in\mathbb{Z}_{\geq 0}$ and $M\in\mathcal{M}_{d}(\mathcal{O})$ it holds that
(1) $\ell_{d}(\mathit{Mat},M)=\mathit{true}$ iff $M(\mathit{Mat})=0$; and (2)
$\ell_{d}(\mathit{UnM},M)=\mathit{true}$ iff $M(\mathit{Mat})\geq 1$. By
construction, $\mathcal{L}$ satisfies the $1$-bounded influence property
(Prop. 10). Let
$\mathcal{P}=\langle\mathcal{O},\mathcal{U}_{\Delta},\mathcal{L}\rangle$ be
the resulting edge-LCL.

##### Implementing the Detection Procedure for $\mathcal{L}$.

Consider some $G\in\mathcal{U}$. We will implement the detection procedure for
$\mathcal{L}$ with messages of size $O(1)$. Let $\mathtt{Detect}$ denote the
implementation of the aforementioned detection procedure. Every node $v$ will
send to every neighbor $u\in N_{G}(v)$, the content of $\mathtt{out}_{v}(u)$
and the value $\mathit{false}$ if $\mathtt{out}_{v}(w)\neq\mathit{Mat}$ for
every $w\in N_{G}(v)-\\{u\\}$ and $\mathit{true}$ otherwise. If node $v$
learns that an incident edge $\\{v,u\\}$ is port-inconsistent, then
$\mathtt{Detect}_{v}(u)$ returns $\mathit{false}$ for this edge. Otherwise
(edge $\\{v,u\\}$ is port-consistent), it follows the following (1) if
$\mathtt{out}_{v}(u)=\bot$, then $\mathtt{Detect}_{v}(u)=\mathit{true}$; (2)
if $\mathtt{out}_{v}(u)=\mathit{Mat}$, then $\mathtt{Detect}_{v}(u)=false$ if
and only if $v$ received $\mathit{true}$ from $u$ or
$\mathtt{out}_{v}(w)=\mathit{Mat}$ for some $w\in N_{G}(v)-\\{u\\}$; and (3)
if $\mathtt{out}_{v}(u)=\mathit{UnM}$, then
$\mathtt{Detect}_{v}(u)=\mathit{false}$ if and only if $v$ received
$\mathit{false}$ from $u$ and $\mathtt{out}_{v}(w)\neq\mathit{Mat}$ for every
$w\in N_{G}(v)-\\{u\\}$.

##### Eligible distributed algorithm.

We use a modified version the classic maximal matching algorithm of Israeli
and Itai [II86]. We describe the eligible distributed algorithm $\mathcal{A}$
for $\mathcal{P}$ by its phase procedure $\mathtt{Phase}$ which has phase
length of $4$. Let $G\in\mathcal{U}_{\Delta}$ be some graph, let $U\subseteq
E(G)$ be the set of undecided edges at the beginning of $\mathtt{Phase}$, let
$e=\\{v,u\\}\in U$, let $U_{v}=\\{u\in N_{G}(v)\mid\\{v,u\\}\in U\\}$, and let
$D_{v}=N_{G}(v)-U_{v}$.

In step $1$, node $v$ randomly marks itself as _active_ or _passive_ with
equal probability. If $v$ is active, then $v$ picks u.a.r. a neighbor $u\in
U_{v}$ and sends to it a ’matching request’ message and the value
$\mathit{true}$ if $v$ has an output register with the value $\mathit{Mat}$
and $\mathit{false}$ otherwise. In step $2$, a passive node $u$ that received
a ’matching request’ message from at least one (active) neighbor, chooses
(arbitrarily) one such neighbor $v$ and sends to it an ’accept’ message along
with the value $\mathit{true}$ if $u$ has an output register with the value
$\mathit{Mat}$ and $\mathit{false}$ otherwise. We denote such edge
$e=\\{u,v\\}$ as a _candidate_ edge. Step $3$ is the decision step: for a
candidate edge $e=\\{u,v\\}$, both $v$ and $u$ sets
$\mathtt{out}_{v}(u)=\mathtt{out}_{u}(v)=\mathit{Mat}$ if both $v$ and $u$
received the value $\mathit{false}$ regarding the matching status of $e$’s
neighbors and $\mathtt{out}_{v}(u)=\mathtt{out}_{u}(v)=\mathit{UnM}$
otherwise.

##### Locally Separable Potential Function for $\mathcal{P}$.

Given $M\in\mathcal{M}(\mathcal{O})$, the potential coefficient $\sigma(M)$ is
defined by setting $\sigma(M)=1$ if $M(\mathit{Mat})\geq 1$; and $\sigma(M)=2$
otherwise. This implies that $\sigma_{0}=\sigma(\emptyset,\emptyset)=2$.

##### Proving the $(\beta,\sigma_{0})$-progress Property for $\mathcal{A}$.

Consider some strongly configured graph $(G,C)\in\mathcal{SCG}(\mathcal{P})$.
Let $H=G(U(C))$ be the subgraph induced by the undecided edges. Consider the
configuration $C^{\prime}=\mathtt{Phase}(G,C)$ obtained from applying the
phase procedure $\mathtt{Phase}$ to $G$ under configuration $C$; observe that
$C^{\prime}$ is a random variable. Let $v\in V(H)$ be a good node (see Sec.
12.1.1) and let $E_{v}=\\{e\in E(H)\mid v\in e\\}$. We will show that, in
expectation, at least a constant fraction of the edges $e\in E_{v}$ satisfy
$\sigma(C[e])\leq\sigma(C^{\prime}([e]))-1$. Since at least half of the edges
in $H$ are incident on a good node and since $C(e)\leq\sigma_{0}=2$ for every
edge $e\in E(H)$, it follows that
$\mathbb{E}(\pi(G,C^{\prime}))\leq(1-\beta)\cdot\pi(G,C)$ for a constant
fraction $\beta>0$.

Let $e=\\{v,u\\}\in E(H)$ be an edge in $H$ such that $v$ is a good node in
$H$ and let $\gamma=|N^{g}_{H}(v)|$. If there exists $e^{\prime}=\\{v,w\\}\in
D_{e}(C)$ for some $w\in N_{G}(v)$ such that $C(e^{\prime})=Mat$, then all of
$v$’s incident edges in $H$ becomes decided under $C^{\prime}$. Otherwise, if
there exists $u_{1},\cdots,u_{\lceil(1/2)\gamma\rceil}\in N^{g}_{H}(v)$ such
that for every $1\leq i\leq\lceil(1/2)\gamma\rceil$ there exists a node
$w_{i}\in N_{G}(u_{i})$ and an edge $e_{i}=\\{u_{i},w_{i}\\}\in D_{e_{i}}(C)$
with $C(e_{i})=Mat$, then a constant fraction of $v$’s incident edges in $H$
become decided under configuration $C^{\prime}$. Otherwise, it is easily
verifiable that with at least a constant probability node $v$ is passive and
receives a ’matching request’ from at least one of its neighbors in the set
$\\{u\in N^{g}_{H}(v)\mid\forall w\in N_{H}(u),C(\\{w,u\\})\neq Mat\\}$.

####  12.2.2 Edge Coloring with $(2+\epsilon)\Delta$ Colors

Fix some $\Delta\in\mathbb{Z}_{>0}$ and a constant $\epsilon>0$ and assume
without loss of generality that $(2+\epsilon)\Delta\in\mathbb{Z}_{>0}$. We
define the LCL $\mathcal{L}=\\{\ell_{d}\\}^{\infty}_{d=0}$ of edge
$((2+\epsilon))\Delta$-coloring over the output values
$\mathcal{O}=\left[(2+\epsilon)\Delta\right]$ such that for every
$d\in\mathbb{Z}_{\geq 0}$, $i\in\mathcal{O}$, and
$M\in\mathcal{M}_{d}(\mathcal{O})$ it holds that $\ell_{d}(i,M)=\mathit{true}$
iff $M(i)=0$. By the definition of $\mathcal{L}$ it satisfies the $0$-bounded
influence property (Prop. 10.) Let
$\mathcal{P}=\langle\mathcal{O},\mathcal{U}_{\Delta},\mathcal{L}\rangle$ be an
edge-LCL and notice that $\mathcal{P}$ is the edge coloring problem with
$(2+\epsilon)\Delta$ colors.

##### Implementing the Detection Procedure for $\mathcal{L}$.

Consider some $G\in\mathcal{U}$. We will implement the detection procedure for
$\mathcal{L}$ with messages of size $O(\log(|\mathcal{O}|))$. Let
$\mathtt{Detect}$ denote the implementation of the aforementioned detection
procedure. Every node $v$ will send to every neighbor $u\in N_{G}(v)$, the
content of $\mathtt{out}_{v}(u)$ and the value $\mathit{false}$ if
$\mathtt{out}_{v}(u)$ is equal to some $\mathtt{out}_{v}(w)$ for $w\in
N_{G}(v)-\\{u\\}$ and $\mathit{true}$ otherwise. If node $v$ learns that an
incident edge $\\{v,u\\}$ is port-inconsistent, then $\mathtt{Detect}_{v}(u)$
returns $\mathit{false}$ for this edge. Otherwise (edge $\\{v,u\\}$ is port-
consistent), $\mathtt{Detect}_{v}(u)$ returns $\mathit{false}$ for edge
$\\{v,u\\}$ if and only if $\mathtt{out}_{v}(u)\neq\bot$ and $v$ received the
value $\mathit{false}$ from $u$ or there exists a neighbor $w\in
N_{G}(v)-\\{u\\}$ such that $\mathtt{out}_{v}(u)=\mathtt{out}_{v}(w)$.

##### Eligible distributed algorithm.

We describe the eligible distributed algorithm $\mathcal{A}$ for $\mathcal{P}$
by its phase procedure $\mathtt{Phase}$ which has phase length of $5$. Let
$G\in\mathcal{U}_{\Delta}$ be some graph, let $U\subseteq E(G)$ be the set of
undecided edges at the beginning of $\mathtt{Phase}$, let $e=\\{v,u\\}\in U$,
let $U_{v}=\\{u\in N_{G}(v)\mid\\{v,u\\}\in U\\}$, and let
$D_{v}=N_{G}(v)-U_{v}$.

In the $1$ step, node $v$ select a color $c_{v}(u)$ u.a.r. from the pallet
$\mathcal{O}$ for every edge $\\{v,u\\}\in U$ and sends it to neighbor $u\in
U_{v}$. In the $2$ step, both $v$ and $u$ determine the same candidate color
for edge $e$ defined to be $c_{e}=1+((c_{v}(u)+c_{u}(v))\mod|\mathcal{O}|)$.
Node $v$ sends $c_{e}$ to every neighbor $w\in U_{v}-\\{u\\}$. Let
$\gamma:U\rightarrow\mathcal{O}$ be the function of the candidate colors for
all undecided edges, i.e., $\gamma(e^{\prime})=c_{e^{\prime}}$ for every
$e^{\prime}\in U$. In the $3$ step, if $\gamma(e)\neq\gamma(e^{\prime})$ for
every $e^{\prime}\in\\{\\{v,w\\}\mid w\in U_{v}-\\{u\\}\\}$ and
$\gamma(e)\neq\mathtt{out}_{v}(w)$ for every $w\in D_{v}$, then $v$ sends an
accept message to $u$. Otherwise, $v$ sends a decline message to $u$. The $4$
step is the decision step. Node $v$ sets $\mathtt{out}_{v}(u)=\gamma(e)$ only
if $v$ sent an accept message to $u$ in the previous step and $v$ received an
accept message from $u$ (in that case $u$ will also set
$\mathtt{out}_{u}(v)=\gamma(e)$).

##### Locally Separable Potential Function for $\mathcal{P}$.

Given $M\in\mathcal{M}(\mathcal{O})$, the potential coefficient $\sigma(M)$ is
defined by setting $\sigma(M)=1$. This implies that
$\sigma_{0}=\sigma(\emptyset,\emptyset)=1$. Notice that the resulting
separable potential function for $\mathcal{P}$, denoted by $\pi$, simply
counts the number of undecided edges.

##### Proving the $(\beta,\sigma_{0})$-progress Property for $\mathcal{A}$.

Consider some $G\in\mathcal{U}_{\Delta}$. Let
$C:E(G)\rightarrow\mathcal{O}\cup\\{\bot\\}$ be an edge configuration such
that $(G,C)\in\mathcal{SCG}(\mathcal{P})$ and let $e=\\{u,v\\}\in U(C)$. We
denote by $A_{e}$ the event that edge $e$ is decided under edge configuration
$\mathtt{Phase}(G,C)$. For a neighboring edge $e^{\prime}\in U_{e}(C)$, we
denote by $A_{e,e^{\prime}}$, the event that the candidate color $c_{e}$
equals to the candidate color $e^{\prime}$ chosen during the execution of
$\mathtt{Phase}$. For a neighboring edge $e^{\prime}\in D_{e}(C)$ we denote by
$A_{e,e^{\prime}}$ the event that $C(e^{\prime})=c_{e}$, i.e., the candidate
color chosen from edge $e$ during the execution of $\mathtt{Phase}$ conflict
with an existing decided neighboring edge color.

It is easily verifiable that for every $e^{\prime}\in N_{G}(e)$, it holds that
$\mathbb{P}(A_{e,e^{\prime}})\leq\frac{1}{(2+\epsilon)\Delta}$. By the union
bound we get that $\mathbb{P}\left(\bigcup_{e^{\prime}\in
N_{G}(e)}A_{e,e^{\prime}}\right)\leq\frac{2}{2+\epsilon}$. We can conclude
that $\mathbb{P}(A_{e})\geq 1-\frac{2}{2+\epsilon}$. Hence, for every
$e=\\{u,v\\}\in U(C)$, the probability that $e$ is decided under configuration
$\mathtt{Phase}(G,C)$ is at least
$\left(1-\frac{2}{2+\epsilon}\right)=\Omega(1)$. Once $e$ becomes decided, the
potential coefficient of edge $e$ (which is $1$) is removed from $\pi$.

####  12.2.3 Maximal Edge $c$-coloring

Let $2\leq c\leq 2\Delta$ be an integer. The LCL is defined as in Sec. 12.1.3.
We solve the maximal edge $c$-coloring by solving maximal node $c$-coloring
using the simulation defined in Sec. 8.

####  12.2.4 Edge $(2\Delta-1)$-coloring

We solve the edge $(2\Delta-1)$-coloring by solving the maximal edge
$2\Delta$-coloring.

####  12.2.5 Incremental Edge $c$-coloring

Let $2\leq c\leq 2\Delta$ be an integer. The LCL is defined as in Sec. 12.1.5.
We solve the incremental edge $c$-coloring by solving incremental node
$c$-coloring on the line graph using the simulation defined in Sec. 8.

###  12.3 A Self Stabilizing Algorithm for Maximal Matching with Fully
Adaptive Run Time $O(\log(k))$

Let $\mathcal{A}_{\mathit{ST}}$ be the self stabilizing algorithm obtained
from the $(\nu,\mu(\Delta)),\phi,\beta,\sigma_{0})$-eligible algorithm defined
in Sec. 12.2.1 such that $\nu=1$, $\mu(\Delta)=O(1)$, $\phi=4$,
$\beta=\Omega(1)$, and $\sigma_{0}=2$. In order to derive the a fully adaptive
run-time of $O(\log k)$ we will use a similar analysis to the analysis of the
transformer when it is applied to an edge-LCL (see Sec. 11). Moreover, we will
use the same notations define in Sec. 11 Recall that adversary manipulate
$k>0$ nodes during the round interval $[t^{*}_{a},t^{*}_{b}-1]$. By the
properties of $\mathcal{A}_{\mathit{ST}}$, we know that for every time $t\geq
t_{s}$ the configuration is strong and at least a constant fraction of the
potential is removed after a constant number of rounds, in expectation (see
Lem. 11.2 and Lem. 11.5).

Let $T=\min\\{t\geq t_{s}\mid U(C_{t})=O(k^{2})\\}$ be the random variable
that marks the first time $t\geq t_{s}$ such that the number of undecided
edges at time $t$ is $O(k^{2})$. In order to prove that the fully adaptive
run-time of $\mathcal{A}_{\mathit{ST}}$ is $O(\log k)$ it suffice to prove
that $\mathbb{E}\left(T\right)\leq O(\log k)$, since the potential at time $T$
is at most $O(k^{2})$.

Consider some graph $G^{\prime}\in\mathcal{G}$ on which
$\mathcal{A}_{\mathit{ST}}$ runs and time $t\in\mathbb{Z}_{\geq 0}$. We say
that node $v\in V(G^{\prime})$ is _matched_ if there exists a neighbor $u\in
N_{G^{\prime}}(v)$ such that $\mathtt{out}_{v}(u)=\mathit{Mat}$ and
$\mathtt{out}_{u}(v)=\mathit{Mat}$. Node $v$ is said to be unmatched if
$\mathtt{out}_{v}(u)=\mathit{UnM}$ for every $u\in N_{G}(v)$.

Throughout, we denote by $G$ the graph at time $t^{*}_{b}+2$, i.e.,
$G_{t^{*}_{b}+2}$.

######  Lemma 12.1.

Let $S=\\{v\in V(G)\mid v\text{ is matched at time }t^{*}_{b}+2\\}$. There
exists a node set $\widetilde{K}\subseteq V-S$ of size $|\widetilde{K}|\leq
2k$ such that $I=V-(S\cup K)$ is an independent set in $G$.

###### Proof.

Let $A$ be the set of nodes in $V(G)-S$ that are manipulated (by the
adversary) during the round interval $[t^{*}_{a},t^{*}_{b}-1]$. Let $R$ be the
set of nodes in $V(G)-(S\cup A)$ that are matched at time $t^{*}_{a}$,
referred to hereafter as _orphans_. We define $\widetilde{K}=A\cup R$ and
establish the assertion by proving that (1) $|\widetilde{K}|\leq 2k$; and (2)
$I=V(G)-(S\cup\widetilde{K})$ is an independent set in $G$.

For every orphan $v\in R$, let $w(v)$ be the node with which $v$ is matched at
time $t^{*}_{a}$. Note that $w(v)$ does not necessarily exist in $G$ as it may
have been removed. Since $v$ and $w(v)$ are no longer matched at time
$t^{*}_{b}+2$ and since $v$ is not manipulated in the round interval
$[t^{*}_{a},t^{*}_{b}-1]$, $w(v)$ must be manipulated during that round
interval. We conclude that $|R|\leq k$ as the mapping defined by $w$ is
injective. The bound $|\widetilde{K}|\leq 2k$ follows since $|A|\leq k$.

It remains to show that $I$ is an independent set in $G$. This is done by
arguing that every node $v\in I$ is strongly unmatched at time $t^{*}_{a}$.
This establishes the assertion recalling that by definition, the nodes in $I$
are not manipulated during the time interval $[t_{a}^{*},t_{0}^{*})$, hence
the adversary does not introduce new edges in $I\times I$. To that end, assume
by contradiction that there exists some node $v\in I$ that is not unmatched at
time $t_{a}^{*}$. Since $\mathcal{A}_{\mathit{ST}}$ is in a legal
configuration at time $t^{*}_{a}$, it follows that $v$ must be matched at that
time. But by definition, the nodes in $V(G)-S$ that are matched at time
$t^{*}_{a}$ belong to either $R$ or $A$, in contradiction to $v\in
I=V(G)-(S\cup A\cup R)$. ∎

Let $V_{t}=\\{v\in V(G)\mid\forall u\in
N_{G}(v),\mathtt{out}_{v,t}(u)\neq\mathit{Mat}\\}$, let
$P_{t}=V_{t}\cap\\{v\in V(G)\mid\mathit{step}_{v,t}=0\\}$, and let
$D_{t}=\\{v\in K\cap V_{t}\mid\mathrm{d}_{G(V_{t})}(v)\geq\xi k\\}$ for some
constant $\xi>0$ that we determine later. .

######  Lemma 12.2.

Fix some time $t\geq t^{*}_{b}+\phi+2$. It holds that,
$\mathbb{P}\left(v\notin D_{t+2\phi}\right)\geq\Omega(1)$ for every node $v\in
D_{t}$.

###### Proof.

For every node $v\in V_{t}$, let $t\leq t(v)$ be the first time after time $t$
such that $\mathit{step}_{v,t(v)}=\mathit{\hbar}$. According to the definition
of the $\mathtt{PPS}$ module it must hold that $t\leq t(v)\leq t+\phi$ and
notice that $t(v)$ is fully determined by $\mathit{step}_{v,t}$. Denote by
$A_{v}$ the event that $\mathit{step}_{v,t^{\prime}}=\mathit{\hbar}$ for every
$t(v)\leq t^{\prime}\leq t+\phi$. By Obs. 5.1, it holds that the event $A_{v}$
is independent of any coin toss of $v$ prior to time $t(v)$ and of any coin
toss of all other nodes and that

$\mathbb{P}\left(A_{v}\right)\geq 2^{-\phi}.$ (12)

For every node $v\in V_{t}$, we augment the power of the adversary by allowing
it choose the outcome of any coin toss in during the round interval
$[t,t(v))$. Notice that this adversary can only choose the outcome of coin
tosses that are within a phase and cannot choose the outcome of coin tosses of
the $\mathtt{PPS}$ module. Let $S$ be the set of nodes $v\in V_{t}$ that are
not matched at time $t(v)$, i.e., $S=\\{v\in V_{t}\bigm{|}v\in V_{t(v)}\\}$.
Let $G^{S}=G(S)$.

Fix some node $v\in D_{t}$. If node $v$ is matched at time $t(v)$ or
$\mathrm{d}_{G^{S}}(v)<\xi k$, then $v\notin D_{t+2\phi-1}$ with probability
$1$. Otherwise ($v$ is not matched at time $t(v)$ and more than $\xi k$ of its
neighbors are in $S$), we will show that with probability $\Omega(2^{-\phi})$
node $v$ is matched at time $t+2\phi-1$ which implies that $v\notin
D_{t+2\phi-1}$.

Let $B$ be the event that $\mathrm{d}_{G(P_{t+\phi+1})}(v)\geq 3k$. We start
by showing that there exists $\alpha=\alpha(\phi)$ such that
$\mathbb{P}\left(B\right)\geq\alpha$. For every $u\in S$, let
$\widetilde{A}_{u}$ be the event that $A_{u}$ occurred and
$\mathit{step}_{v,t+\phi+1}=0$. By Eq. 12 and Obs. 5.1 we can conclude that
$\mathbb{P}\left(\widetilde{A}_{u}\right)=\mathbb{P}\left(A_{u}\right)\cdot(1/2)\geq
2^{-(\phi+1)}$. Moreover, the events in $\\{\widetilde{A}_{u}\bigm{|}u\in
S\\}$ are independent.

Denote $d=\mathrm{d}_{G^{S}}(v)$ and let $u_{1},\dots,u_{d}$ be the neighbors
of $v$ is $G^{S}$. Let $Y$ be the random variable that counts the number of
occurrences of events $\widetilde{A}_{u_{i}}$. Notice that if $Y\geq 3k$ and
$\widetilde{A}_{v}$ occurs, then event $B$ occur; moreover, events $Y\geq 3k$
and $\widetilde{A}_{v}$ are independent and $\mathbb{E}\left(Y\right)\geq\xi
k2^{-(\phi+1)}$ since $d\geq\xi k$.

By choosing $\xi=4/2^{-(\phi+1)}=2^{\phi+3}$ and applying Chernoff’s (lower
tail) bound we conclude that

$\begin{split}\mathbb{P}\left(Y<3k\right)=\mathbb{P}\left(Y<(1-1/4)\cdot\xi
k2^{-(\phi+1)}\right)\leq\mathbb{P}\left(Y<(1-1/4)\cdot\mathbb{E}\left(Y\right)\right)<e^{-k/8}\leq
e^{-1/8}\,.\end{split}$

Thus $\mathbb{P}\left(B\right)\geq(1-e^{-1/8})\cdot 2^{-(\phi+1)}$. Occurrence
of $B$ implies that $v$ is good in $G(P_{t+\phi+1})$ and a good node is
removed with at least a constant probability by the end of the phase, i.e., at
time $t+2\phi$. We conclude that

$\begin{split}\mathbb{P}\left(v\notin
D_{t+2\phi-1}\right)&=\mathbb{P}\left(B\land v\notin V_{t+2\phi}\right)\\\
&\geq\mathbb{P}\left(v\notin
V_{t+2\phi}\bigm{|}B\right)\cdot\mathbb{P}\left(B\right)=\Omega(1)\,,\end{split}$

thus establishing the assertion. ∎

##  13 Additional Related Work and Discussion

##### Transformers.

From the more theoretical point of view, a transformer is used to show the
reduction (or possibly the equivalence) of some source class of algorithms
(and/or problems) to some target class intended for problems that initially
seem “harder”. Some known such transformers in the context of distributed
computing are those that allow the application of synchronous algorithms on
asynchronous networks and those that allow the use of algorithms for static
networks to be performed on one that may undergo (detectable) topological
changes ([Awe85, AAG87] and many others). Transformers can also easy the
design of algorithms in the target class [Awe85, KP93]. When used in the
context of faults they may even reduce the amortized complexity per fault by
avoiding re-computation after fault [ACK90]. Below, we refer only to
transformers Some of the transformers mentioned below are more general than
the one presented in the current paper in either transforming algorithms where
nodes may also start with some input other than the graph, or algorithms for
non LCL problems or even algorithms that never terminate and interact with
users outside the network.

The first transformers, published as early as 1990 [KP93, AKY90], were rather
inefficient. In [KP93], copies of the states of all the nodes were collected
to some leader who detected illegal states and instructed the nodes to reset –
restart from some legal global state. Some limitations were (1) assuming some
incorruptible leader, (2) high overhead, including in time (that could be
reduced to the diameter if the LOCAL [Pel00] model was assumed), (3) assuming
a directed spanning tree, otherwise, the reset could be invoked many times
[APSVD94].

In [AKY97], points (1) and (3) were addressed by introducing (an inefficient,
improved later) self stabilizing algorithm to elect a leader and maintain a
spanning tree. leader election algorithm. Point (2) was addressed by
suggesting the paradigm of local detection, (also called local checking
[APSV91, AV91, NS95]) that allowed some nodes to detect incorrectness just by
communicating with their neighbors,rather than with the the remote leader. It
was shown that any problem could be revised to be locally checkable [AD02,
KKP10].

Transformers using these global reset protocols, e.g. [AKM+93, APSVD94],
including on spanning tree, consume time that is at least a diameter, since
they reset the whole network to some correct configuration. The
“resynchronizer” of [AV91], and the “superstabilizer” [DH95, DH97] are global
in their stabilization time for a similar reason. (The “superstabilizer”
transformer may treat some faults faster in the specific case that these
faults are topological changes such that the endpoint node of an inserted (or
deleted) edge is notified by the environment about the change.)

In [APSV91], a class of distributed languages that are both locally
correctable and locally checkable is defined. Their local correction algorithm
nevertheless could suffer from at least a diameter time even for a few faults.

The “rollback compiler” in [AV91] logs in each node, all the local history of
the algorithm it transforms. Moreover, each node exchanges its log with its
neighbors in every round. That way, the nodes can simulate the history
repeatedly and verify that all the actions were taken correctly, or correct
them if they were not. If the time complexity of non-self-stabilizing
algorithm to be transformed is $t$, then the stabilization time of the
transformed algorithm is $t$ too. Indeed they mention as applications local
algorithms such as MIS and $\Delta^{2}$ coloring. However, this held only
under the LOCAL model, since their messages were very large. Moreover, this
may not work well for randomized algorithms. A more detailed description of
how this transformer applies to local algorithms appears in [LSW09].

The above idea of exchanging logs was pushed further in [AD02] to not only
exchange logs with neighbors, but also to flood the network with the log of
every node in every round of computation. That allowed them to address
algorithms that never terminate and interact repeatedly with users outside the
system. Such interactive algorithms are adaptive in a different sense than the
one addressed in the current paper. That is, the stabilization may take time
that is proportional to the diameter. However, the length of the duration of
the interruption at each node is just the diameter of the subgraph induced by
the faulty node. It is plausible that the kind of adaptivity addressed here
can also be obtained. However, recall that all this would hold only under the
LOCAL model (because of the huge messages) and possibly only for deterministic
algorithms. Another transformer for deterministic algorithms that yielded time
adaptive self stabilizing ones used a “brute force” method (and huge messages)
too and was thus time efficient only under the LOCAL model [KPS97].

Bounding the amount of memory used by transformers have been addressed
indirectly by addressing the memory requirements of the reset and the fault
detection module. A bounded memory reset protocol was proposed in [KA98], but
only assuming a bounded number of faults. Minimizing the memory used for fault
detection has been the subject of numerous studies, both in the general case
and for specific tasks, see e.g. [BDDT98, KKP10, GS16, CHPP20].

##### Locally Checkable Labelings.

The term LCL was coined in [NS95]. One of its motivations was the above
mentioned self stabilization transformers. Specifically, the checking of local
conditions and the detection of faults so that transformers could reactivate
the correction algorithm. Another motivations was to identify algorithms where
a fault at a processor $p$ could only affect processors in some bounded region
around $p$. (The second motivation seems related to adaptivity, please see
below).

Research on non-self-stabilizing algorithms for LCL problems has been far too
extensive to survey here. Some very partial (and somewhat arbitrary) list
includes [KW85, II86, HKP01, BEPS16, Gha19, BBH+19, Suo20, GHK+20, CLP20,
CP19]. In that non-self-stabilizing context there has also been interest in
automatic conversion and generation of algorithms [Bra19].

The transformer presented here addresses phase based algorithms. We use the
fact that such algorithms are very common for LCLs, so the transformer
presented here is rather general. Moreover, even though every previous
algorithm was designed for some specific problem, many addressed issues of
phase synchronization under various environments that can be useful in
designing other phase based algorithms (e.g. [ACS94, WW04, Tur19]). The
latter, [Tur19], even designs two self stabilizing in $O(\log n)$ time
algorithms for the specific LCL problems of Maximal Matching and of MIS by
revising (manually) two non-stabilizing phase base algorithms. The algorithms
presented in [Tur19] were not adaptive. The design of a transformer for a wide
class of phase based algorithms is stated in to be the ultimate goal of the
ideas discussed in there.

The only other sublinear self stabilizing algorithms we are aware of for LCL
problems are the $O(\Delta+\log^{*}n)$ stabilization time $(\Delta+1)$-node
coloring, $(2\Delta-1)$-edge-coloring, Maximal Independent set and Maximal
Matching of [BEG18].131313Many of the previous self-stabilizing algorithms
were deterministic and asynchronous. Some also addressed related tasks that
are not LCL. A unique identity is assumed and the algorithms are not shown to
be adaptive.

Self-stabilizing LCL problems were extensively studied even before that. in
particular, there is a long line of works on distributed self-stabilizing MM,
MIS, and/or coloring algorithms, see table $1$ in [ID19] and [HH92, Tel94,
CLM+16, CMPS18, HJS01, GJ01, GHJS03b, GHJS03a, MMPT09, MMPT11, SGH04, AOI16,
KTK10, GK10, DLM16, AD19, Tur19, Tur07, XHGS03, CC13, HHJS03, HJS03]. However,
the stabilization time of all of them was $O(n)$ (or more).

##### Adaptive Run-Time.

Adaptivity has gained a lot of interest outside of distributed computing. See,
e.g., [Fre85, BGS15, BGS15, NS16]. In the non-self-stabilizing computing
context, Lamport suggested that an algorithm should benefit from the common
case where the number of contending processes is small [Lam87].

In the context of fault tolerance, adaptivity in sublinear time was suggested
in [KP95b] for mending a Maximal Independent set that was corrupted at some
$k$ locations. The mending took $O(\log(k)$ time instead of $O(\log n)$ for
computing in scratch. That algorithm was not fully self-stabilizing. Several
other mending (or fixing) algorithms, again, not fully self stabilizing, were
suggested in [KW13]. A graph theoretical definition of mendability was
discussed in [BHM+21] and it was suggested that it can be helpful for self
stabilization in the LOCAL model.

A self stabilizing paradigm to handle a single fault, or multiple isolated
faults (“sufficiently far” from each other) was suggested in [GGHP96, GGHP07].

Self stabilizing algorithms whose time adaptivity was at least linear in the
number of faults for various tasks were suggested in [KP95a, KPS97, AKPS03,
DANL04, BHKPS05, AZ06, KM07]. We note that, while the above algorithms are
adaptive since the time was expressed as a function of the number $k$ of
faults, they are not always _fully_ adaptive since all the faults are assumed
to occur in a single batch before the mending starts and no additional faults
occur at least until they are mended. In contrast, the run-time analysis in
the current paper is fully adaptive in the sense that it allows the adversary
to divide the $k$ faults (and/or topology changes) over multiple batches.

Adapting efficiently to detectable topological changes (that is, not self
stabilizing) was addressed e.g. in [LPSR09, BKM18, CHDK+19]. Those are not not
self-stabilizing. The algorithm is [BKM18] is adaptive (the time is not
expressed as a function of $k$) while in [CHDK+19], the _amortized_ (not the
worst case) time complexity is optimized, assuming that the graph is initially
empty. Both papers rely on messages of super-constant size.

## References

  * [AAG87] Yehuda Afek, Baruch Awerbuch, and Eli Gafni.  Applying static network protocols to dynamic networks.  In 28th Annual Symposium on Foundations of Computer Science (sfcs 1987), pages 358–370. IEEE, 1987.
  * [ABI86] Noga Alon, László Babai, and Alon Itai.  A fast and simple randomized parallel algorithm for the maximal independent set problem.  Journal of algorithms, 7(4):567–583, 1986.
  * [ACK90] Baruch Awerbuch, Israel Cidon, and Shay Kutten.  Communication-optimal maintenance of replicated information.  In Proceedings [1990] 31st Annual Symposium on Foundations of Computer Science, pages 492–502. IEEE, 1990.
  * [ACS94] Baruch Awerbuch, Lenore J Cowen, and Mark A Smith.  Efficient asynchronous distributed symmetry breaking.  In Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, pages 214–223, 1994.
  * [AD02] Yehuda Afek and Shlomi Dolev.  Local stabilizer.  Journal of Parallel and Distributed Computing, 62(5):745–765, 2002\.
  * [AD19] Ozkan Arapoglu and Orhan Dagdeviren.  An asynchronous self-stabilizing maximal independent set algorithm in wireless sensor networks using two-hop information.  In 2019 International Symposium on Networks, Computers and Communications (ISNCC), pages 1–5. IEEE, 2019.
  * [ADDP19] Karine Altisen, Stéphane Devismes, Swan Dubois, and Franck Petit.  Introduction to distributed self-stabilizing algorithms.  Synthesis Lectures on Distributed Computing Theory, 8(1):1–165, 2019.
  * [AKM+93] Baruch Awerbuch, Shay Kutten, Yishay Mansour, Boaz Patt-Shamir, and George Varghese.  Time optimal self-stabilizing synchronization.  In Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, pages 652–661, 1993.
  * [AKPS03] Yossi Azar, Shay Kutten, and Boaz Patt-Shamir.  Distributed error confinement.  In Proceedings of the twenty-second annual symposium on Principles of distributed computing, pages 33–42, 2003.
  * [AKY90] Yehuda Afek, Shay Kutten, and Moti Yung.  Memory-efficient self stabilizing protocols for general networks.  In International Workshop on Distributed Algorithms, pages 15–28. Springer, 1990.
  * [AKY97] Yehuda Afek, Shay Kutten, and Moti Yung.  The local detection paradigm and its applications to self-stabilization.  Theoretical Computer Science, 186(1-2):199–229, 1997.
  * [AOI16] Yuma Asada, Fukuhito Ooshita, and Michiko Inoue.  An efficient silent self-stabilizing 1-maximal matching algorithm in anonymous networks.  Journal of Graph Algorithms and Applications, 2016.
  * [APSV91] Baruch Awerbuch, Boaz Patt-Shamir, and George Varghese.  Self-stabilization by local checking and correction.  In Foundations of Computer Science, 1991. Proceedings., 32nd Annual Symposium on, pages 268–277. IEEE, 1991.
  * [APSVD94] Baruch Awerbuch, Boaz Patt-Shamir, George Varghese, and Shlomi Dolev.  Self-stabilization by local checking and global reset.  In International Workshop on Distributed Algorithms, pages 326–339. Springer, 1994.
  * [AV91] Baruch Awerbuch and George Varghese.  Distributed program checking: a paradigm for building self-stabilizing distributed protocols.  In Foundations of Computer Science, 1991. Proceedings., 32nd Annual Symposium on, pages 258–267. IEEE, 1991.
  * [Awe85] Baruch Awerbuch.  Complexity of network synchronization.  Journal of the ACM (JACM), 32(4):804–823, 1985.
  * [AZ06] Anish Arora and Hongwei Zhang.  Lsrp: Local stabilization in shortest path routing.  IEEE/ACM Transactions on Networking, 14(3):520–531, 2006.
  * [BBH+19] Alkida Balliu, Sebastian Brandt, Juho Hirvonen, Dennis Olivetti, Mikaël Rabie, and Jukka Suomela.  Lower bounds for maximal matchings and maximal independent sets.  In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 481–497. IEEE, 2019.
  * [BDDT98] Joffroy Beauquier, Sylvie Delaët, Shlomi Dolev, and Sébastien Tixeuil.  Transient fault detectors.  In International Symposium on Distributed Computing, pages 62–74. Springer, 1998.
  * [BEG18] Leonid Barenboim, Michael Elkin, and Uri Goldenberg.  Locally-iterative distributed ($\delta$\+ 1) -coloring below szegedy-vishwanathan barrier, and applications to self-stabilization and to restricted-bandwidth models.  In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, pages 437–446, 2018.
  * [BEPS16] Leonid Barenboim, Michael Elkin, Seth Pettie, and Johannes Schneider.  The locality of distributed symmetry breaking.  Journal of the ACM (JACM), 63(3):20, 2016.
  * [BGS15] Surender Baswana, Manoj Gupta, and Sandeep Sen.  Fully dynamic maximal matching in o($\backslash$logn) update time.  SIAM Journal on Computing, 44(1):88–113, 2015.
  * [BHKPS05] Janna Burman, Ted Herman, Shay Kutten, and Boaz Patt-Shamir.  Asynchronous and fully self-stabilizing time-adaptive majority consensus.  In International Conference On Principles Of Distributed Systems, pages 146–160. Springer, 2005.
  * [BHM+21] Alkida Balliu, Juho Hirvonen, Darya Melnyk, Dennis Olivetti, Joel Rybicki, and Jukka Suomela.  Local mending.  CoRR, abs/2102.08703, 2021.
  * [BKM18] Philipp Bamberger, Fabian Kuhn, and Yannic Maus.  Local distributed algorithms in highly dynamic networks.  arXiv preprint arXiv:1802.10199, 2018.  To appear in IPDPSw2019.
  * [Bra19] Sebastian Brandt.  An automatic speedup theorem for distributed problems.  In Peter Robinson and Faith Ellen, editors, Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Canada, July 29 - August 2, 2019, pages 379–388. ACM, 2019.
  * [CC13] Well Y. Chiu and Chiuyuan Chen.  Linear-time self-stabilizing algorithms for minimal domination in graphs.  In Combinatorial Algorithms, pages 115–126, 2013.
  * [CHDK+19] Keren Censor-Hillel, Neta Dafni, Victor I Kolobov, Ami Paz, and Gregory Schwartzman.  Fast and simple deterministic algorithms for highly-dynamic networks.  arXiv preprint arXiv:1901.04008, 2019.
  * [CHPP20] Keren Censor-Hillel, Ami Paz, and Mor Perry.  Approximate proof-labeling schemes.  Theoretical Computer Science, 811:112–124, 2020.
  * [CLM+16] Johanne Cohen, Jonas Lefevre, Khaled Maâmra, Laurence Pilard, and Devan Sohier.  A self-stabilizing algorithm for maximal matching in anonymous networks.  Parallel Processing Letters, 26(04):1650016, 2016.
  * [CLP20] Yi-Jun Chang, Wenzheng Li, and Seth Pettie.  Distributed ($\Delta$+1)-coloring via ultrafast graph shattering.  SIAM J. Comput., 49(3):497–539, 2020.
  * [CMPS18] Johanne Cohen, George Manoussakis, Laurence Pilard, and Devan Sohier.  A self-stabilizing algorithm for maximal matching in link-register model.  In International Colloquium on Structural Information and Communication Complexity, pages 14–19. Springer, 2018.
  * [CP19] Yi-Jun Chang and Seth Pettie.  A time hierarchy theorem for the LOCAL model.  SIAM J. Comput., 48(1):33–69, 2019.
  * [CV86] Richard Cole and Uzi Vishkin.  Deterministic coin tossing with applications to optimal parallel list ranking.  Information and Control, 70(1):32 – 53, 1986.
  * [DANL04] Murat Demirbas, Anish Arora, Tina Nolte, and Nancy Lynch.  A hierarchy-based fault-local stabilizing algorithm for tracking in sensor networks.  In International Conference on Principles of Distributed Systems, pages 299–315. Springer, 2004.
  * [DH95] S. Dolev and T. Herman.  SuperStabilizing Protocols for Dynamic Distributed Systems.  Technical report, University of Iowa Department of Computer Science Technical Report 95-02, 01 1995.  presented at the Second Workshop on Self-Stabilizing Systems (WSS95), May 1995.
  * [DH97] Shlomi Dolev and Ted Herman.  Superstabilizing protocols for dynamic distributed systems.  Chic. J. Theor. Comput. Sci., 1997, 1997.
  * [Dij82] Edsger W Dijkstra.  Self-stabilization in spite of distributed control.  In Selected writings on computing: a personal perspective, pages 41–46. Springer, 1982.
  * [DLM16] Ajoy K Datta, Lawrence L Larmore, and Toshimitsu Masuzawa.  Maximum matching for anonymous trees with constant space per process.  In LIPIcs-Leibniz International Proceedings in Informatics, volume 46. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016.
  * [Dol00] Shlomi Dolev.  Self-stabilization.  MIT press, 2000.
  * [Fre85] G.N. Frederickson.  Data structures for on-line updating of minimum spanning trees, with applications.  SIAM J. on Computing (SICOMP), 14(4):781–798, 1985.
  * [GGHP96] Sukumar Ghosh, Arobinda Gupta, Ted Herman, and Sriram V Pemmaraju.  Fault-containing self-stabilizing algorithms.  In Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, pages 45–54. ACM, 1996.
  * [GGHP07] Sukumar Ghosh, Arobinda Gupta, Ted Herman, and Sriram V. Pemmaraju.  Fault-containing self-stabilizing distributed protocols.  Distributed Comput., 20(1):53–73, 2007.
  * [Gha19] Mohsen Ghaffari.  Distributed maximal independent set using small messages.  In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 805–820. SIAM, 2019.
  * [GHJS03a] Wayne Goddard, Stephen T Hedetniemi, David P Jacobs, and Pradip K Srimani.  Self-stabilizing protocols for maximal matching and maximal independent sets for ad hoc networks.  In null, page 162b. IEEE, 2003.
  * [GHJS03b] Wayne Goddard, Stephen T Hedetniemi, DR Jacobs, and Pradip K Srimani.  A robust distributed generalized matching protocol that stabilizes in linear time.  In Distributed Computing Systems Workshops, 2003. Proceedings. 23rd International Conference on, pages 461–465. IEEE, 2003.
  * [GHK+20] Mohsen Ghaffari, Juho Hirvonen, Fabian Kuhn, Yannic Maus, Jukka Suomela, and Jara Uitto.  Improved distributed degree splitting and edge coloring.  Distributed Comput., 33(3-4):293–310, 2020.
  * [GJ01] Maria Gradinariu and Colette Johnen.  Self-stabilizing neighborhood unique naming under unfair scheduler.  In European Conference on Parallel Processing, pages 458–465. Springer, 2001.
  * [GK10] Nabil Guellati and Hamamache Kheddouci.  A survey on self-stabilizing algorithms for independence, domination, coloring, and matching in graphs.  Journal of Parallel and Distributed Computing, 70(4):406–415, 2010\.
  * [GS16] Mika Göös and Jukka Suomela.  Locally checkable proofs in distributed computing.  Theory of Computing, 12(1):1–33, 2016.
  * [HH92] Su-Chu Hsu and Shing-Tsaan Huang.  A self-stabilizing algorithm for maximal matching.  Information processing letters, 43(2):77–81, 1992.
  * [HHJS03] S. M. Hedetniemi, S. T. Hedetniemi, D. P. Jacobs, and P. K. Srimani.  Self-stabilizing algorithms for minimal dominating sets and maximal independent sets.  Computers & Mathematics with Applications, 46(5):805–811, 2003\.
  * [HJS01] Stephen T Hedetniemi, David P Jacobs, and Pradip K Srimani.  Maximal matching stabilizes in time o (m).  Information Processing Letters, 80(5):221–223, 2001.
  * [HJS03] Stephen T. Hedetniemi, David Pokrass Jacobs, and Pradip K. Srimani.  Linear time self-stabilizing colorings.  Information Processing Letters, 87(5):251–255, 2003.
  * [HKP01] Michal Hanckowiak, Michal Karonski, and Alessandro Panconesi.  On the distributed complexity of computing maximal matchings.  SIAM Journal on Discrete Mathematics, 15(1):41–57, 2001.
  * [ID19] Can Umut Ileri and Orhan Dagdeviren.  A self-stabilizing algorithm for b-matching.  Theoretical Computer Science, 753:64–75, 2019.
  * [II86] Amos Israeli and Alon Itai.  A fast and simple randomized parallel algorithm for maximal matching.  Information Processing Letters, 22(2):77–80, 1986.
  * [KA98] Sandeep S Kulkarni and Anish Arora.  Multitolerance in distributed reset.  Chicago Journal of Theoretical Computer Science, 4:1998, 1998.
  * [KKP10] Amos Korman, Shay Kutten, and David Peleg.  Proof labeling schemes.  Distributed Computing, 22(4):215–233, 2010.
  * [KM07] Shay Kutten and Toshimitsu Masuzawa.  Output stability versus time till output.  In Andrzej Pelc, editor, Distributed Computing, 21st International Symposium, DISC 2007, Lemesos, Cyprus, September 24-26, 2007, Proceedings, volume 4731 of Lecture Notes in Computer Science, pages 343–357. Springer, 2007.
  * [KP93] Shmuel Katz and Kenneth J Perry.  Self-stabilizing extensions for meassage-passing systems.  Distributed Computing, 7(1):17–26, 1993.
  * [KP95a] Shay Kutten and David Peleg.  Fault-local distributed mending.  In Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, pages 20–27. ACM, 1995.
  * [KP95b] Shay Kutten and David Peleg.  Tight fault locality (extended abstract).  In 36th Annual Symposium on Foundations of Computer Science, Milwaukee, Wisconsin, USA, 23-25 October 1995, pages 704–713. IEEE Computer Society, 1995.
  * [KPS97] Shay Kutten and Boaz Patt-Shamir.  Time-adaptive self stabilization.  In Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, pages 149–158. ACM, 1997.
  * [KSOS06] Kishore Kothapalli, Christian Scheideler, Melih Onus, and Christian Schindelhauer.  Distributed coloring in o/spl tilde/(/spl radic/(log n)) bit rounds.  In 20th International Parallel and Distributed Processing Symposium (IPDPS), 2006.
  * [KTK10] Masahiro Kimoto, Tatsuhiro Tsuchiya, and Tohru Kikuno.  The time complexity of hsu and huang’s self-stabilizing maximal matching algorithm.  IEICE transactions on information and systems, 93(10):2850–2853, 2010.
  * [KW85] Richard M Karp and Avi Wigderson.  A fast parallel algorithm for the maximal independent set problem.  Journal of the ACM (JACM), 32(4):762–773, 1985.
  * [KW13] Michael König and Roger Wattenhofer.  On local fixing.  In International Conference On Principles Of Distributed Systems, pages 191–205. Springer, 2013.
  * [Lam87] Leslie Lamport.  A fast mutual exclusion algorithm.  ACM Transactions on Computer Systems (TOCS), 5(1):1–11, 1987.
  * [LPSR09] Zvi Lotker, Boaz Patt-Shamir, and Adi Rosén.  Distributed approximate matching.  SIAM Journal on Computing, 39(2):445–460, 2009.
  * [LSW09] Christoph Lenzen, Jukka Suomela, and Roger Wattenhofer.  Local algorithms: Self-stabilization on speed.  In Symposium on Self-Stabilizing Systems, pages 17–34. Springer, 2009.
  * [Lub86] Michael Luby.  A simple parallel algorithm for the maximal independent set problem.  SIAM journal on computing, 15(4):1036–1053, 1986.
  * [MMPT09] Fredrik Manne, Morten Mjelde, Laurence Pilard, and Sébastien Tixeuil.  A new self-stabilizing maximal matching algorithm.  Theoretical Computer Science, 410(14):1336–1345, 2009.
  * [MMPT11] Fredrik Manne, Morten Mjelde, Laurence Pilard, and Sébastien Tixeuil.  A self-stabilizing 23-approximation algorithm for the maximum matching problem.  Theoretical Computer Science, 412(40):5515–5526, 2011.
  * [NS95] Moni Naor and Larry Stockmeyer.  What can be computed locally?  SIAM Journal on Computing, 24(6):1259–1277, 1995.
  * [NS16] Ofer Neiman and Shay Solomon.  Simple deterministic algorithms for fully dynamic maximal matching.  ACM Transactions on Algorithms (TALG), 12(1):7, 2016.
  * [Pel00] David Peleg.  Distributed Computing: A Locality-sensitive Approach.  Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2000.
  * [SGH04] Zhengnan Shi, Wayne Goddard, and Stephen T Hedetniemi.  An anonymous self-stabilizing algorithm for 1-maximal independent set in trees.  Information Processing Letters, 91(2):77–83, 2004.
  * [Suo20] Jukka Suomela.  Landscape of locality (invited talk).  In Susanne Albers, editor, 17th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2020, June 22-24, 2020, Tórshavn, Faroe Islands, volume 162 of LIPIcs, pages 2:1–2:1. Schloss Dagstuhl \- Leibniz-Zentrum für Informatik, 2020.
  * [Tel94] Gerard Tel.  Maximal matching stabilizes in quadratic time.  Information Processing Letters, 49(6):271–272, 1994.
  * [Tur07] Volker Turau.  Linear self-stabilizing algorithms for the independent and dominating set problems using an unfair distributed scheduler.  Information Processing Letters, 103(3):88–93, 2007.
  * [Tur19] Volker Turau.  Making randomized algorithms self-stabilizing.  In International Colloquium on Structural Information and Communication Complexity, pages 309–324. Springer, 2019.
  * [Val82] Leslie G. Valiant.  Parallel computation.  In Prooceedings of the 7th IBM Symp. on Math. Foundations of Computer Science, pages 171–189, 1982.
  * [Wil99] Elizabeth Lee Wilmer.  Exact rates of convergence for some simple non-reversible Markov chains.  PhD thesis, Department of Mathematics, Harvard University, 1999.
  * [WW04] Mirjam Wattenhofer and Roger Wattenhofer.  Distributed weighted matching.  In International Symposium on Distributed Computing, pages 335–348. Springer, 2004.
  * [XHGS03] Z. Xu, S. T. Hedetniemi, W. Goddard, and P. K. Srimani.  A synchronous self-stabilizing minimal domination protocol in an arbitrary network graph.  In Samir R. Das and Sajal K. Das, editors, Distributed Computing \- IWDC 2003, pages 26–32, 2003.

APPENDIX

##  Appendix A Proving Lem. 5.2

###### Proof of Lem. 5.2.

To avoid cumbersome notation, we assume throughout this proof that $t_{0}=0$.
Let $\\{X_{t}\\}_{t=0}^{\infty}$ be a stochastic process such that
$X_{t}=\mathit{step}_{v,t}$. The stochastic process
$\\{X_{t}\\}_{t=0}^{\infty}$ can be defined by the discrete time Markov chain
$M_{\phi}$ with state space $S_{\phi}$ as in Fig. 1.

Let $P_{\phi}\in\mathbb{R}^{S_{\phi}\times S_{\phi}}_{\geq 0}$ be the time-
homogeneous transition matrix of the Markov chain $M_{\phi}$ and
$P_{\phi}^{t}$ the matrix $P_{\phi}$ to the power of $t$. Denote entry
$(i,j)\in S_{\phi}\times S_{\phi}$ of $P_{\phi}$ by $P_{\phi}(i,j)$ and recall
that for every $t,s\in\mathbb{Z}_{\geq 0}$ such that $t\geq 1$, it holds that
$P_{\phi}^{t}(i,j)=\mathbb{P}\left(X_{t+s}=j\mid X_{s}=i\right)$. For
convenience sake, let $n=|S_{\phi}|=\phi+1$.

The chain $M_{\phi}$ is ergodic, thus there exists a unique stationary
distribution on the state space $S_{\phi}$, which we denote by the size $n$
vector $\boldsymbol{\pi}\in\mathbb{R}_{>0}^{S_{\phi}}$. It is easily
verifiable that $\boldsymbol{\pi}(\mathit{\hbar})=\frac{2}{n+1}$ and
$\boldsymbol{\pi}(j)=\frac{1}{n+1}$ for every $j\in
S_{\phi}-\\{\mathit{\hbar}\\}$. We will prove that there exists
$\hat{t}=O(\log(1/\epsilon)\cdot n^{3})$ such that for every $t\geq\hat{t}$,
it holds that

$P_{\phi}^{t}(j_{0},\mathit{\hbar})\geq\frac{2}{n+1}(1-\epsilon)$ (13)

and

$P_{\phi}^{t}(j_{0},j)\geq\frac{1}{n+1}(1-\epsilon),\forall j\in
S_{\phi}-\\{\mathit{\hbar}\\}.$ (14)

The chain $M_{\phi}$ is a special case of the _coin-flip_ chain as defined in
[Wil99] with $p=q=1/2$. By Proposition $5.8$, Theorem $3.6$ and Lemma $2.4$ in
[Wil99], for every positive $\epsilon<1$ there exists a time $t(n)=O(n^{3})$
such that for every $t\geq O(\log(1/\epsilon)\cdot t(n))$, and $i\in S_{\phi}$

$\max\limits_{j\in
S_{\phi}}\left|\frac{P_{\phi}^{t}(i,j)}{\boldsymbol{\pi}(j)}-1\right|\leq\epsilon.$

Thus, for every $t\geq O(\log(1/\epsilon)\cdot n^{3})$ we can low-bound Eq.
13–14 by,

$P^{t}_{\phi}(j_{0},j)\geq\boldsymbol{\pi}(j)\cdot(1-\epsilon).$

The proof is completed by the value of $\boldsymbol{\pi}$. ∎

##  Appendix B Pseudocodes

###  B.1 The Transformers

In this section we present the pseudocode of the transformer. Consider a node-
LCL (resp., edge-LCL)
$\mathcal{P}=\langle\mathcal{O},\mathcal{G},\mathcal{L}\rangle$, where
$\mathcal{G}\subseteq\mathcal{U}_{\Delta}$ for a degree bound $\Delta$. Let
$\mathcal{A}$ be an eligible fault free algorithm for $\mathcal{P}$, let
$\phi$ be it phase length, let $\mathtt{Phase}$ be the phase procedure of
$\mathcal{A}$, and let $\mathtt{Detect}$ be a detection procedure for
$\mathcal{L}$. The pseudocode for the self-stabilizing algorithm for the node-
LCL (resp., edge-LCL) $\mathcal{P}$ obtained by applying our transformer to
$\langle\mathtt{Phase},\mathtt{Detect}\rangle$ as defined in Sec. 6 (resp.,
Sec. 10) is Algorithm 1 (resp., Algorithm 2).

Consider some $G\in\mathcal{G}$ on which $\mathcal{A}_{\mathit{ST}}$ runs and
let $v\in V(G)$ be some node. We denote the message that node $v$ reads at the
beginning of the local computation of a round from a neighbor $u\in N_{G}(v)$
by $\mathit{InM}_{v}(u)$ and the message it sends to $u$ in a round by
$\mathit{OutM}_{v}(u)$. Recall that $\mathcal{A}_{\mathit{ST}}$ have $3$
components. These components are $\mathtt{Detect}$, $\mathtt{Phase}$, and
$\mathtt{PPS}$. The messages sent (and received) under
$\mathcal{A}_{\mathit{ST}}$ have a designated field for each of these
components. The fields in every message are denoted by $\mathtt{detect}$,
$\mathtt{phase}$, and $\mathtt{pps}$, respectively.

Consider some $G\in\mathcal{G}$ on which $\mathcal{A}_{\mathit{ST}}$ runs. Let
$v\in V(G)$ be some node and $N\subseteq N_{G}(v)$ a subset of $v$’s
neighbors. We denote by $\mathtt{Phase}^{v}_{j}[N]$ the code for the $j$-th
step of $\mathtt{Phase}$ for every $j\in\\{0,\cdots,\phi-1\\}$ executing on
$v$ with the set of undecided neighbors $N$ with respect to the
$\mathtt{phase}$ field in the messages. We denote by $\mathtt{Detect}_{\ell}$
the part in the local computation of $\mathtt{Detect}$ in which
$\mathtt{Detect}$ decides to return $\mathit{true}$ or $\mathit{false}$ and by
$\mathtt{Detect}_{m}$ the part in which $\mathtt{Detect}$ construct the
messages to be sent. Recall that $\mathtt{Detect}$ is also implemented over
the $\mathtt{detect}$ filed of the messages.

Algorithm 1 Self-stabilizing algorithm for node-LCL obtained by applying the
transformer on $\langle\mathtt{Phase},\mathtt{Detect}\rangle$, code for node
$v$.

1:for all $u\in N_{G}(v)$ do

2: $\mathit{OutM}_{v}(u).\mathtt{phase}\leftarrow\mathit{NIL}$

3:if $\mathtt{Get\\_Step\\_PPS}()=\mathit{\hbar}$ then

4: $wait_{v}\leftarrow\mathit{false}$

5:if $\mathtt{out}_{v}\neq\bot$ then $\triangleright$ node $v$ is decided

6: if $\mathtt{Detect}_{\ell}=\mathit{false}$ then

7: $\mathtt{out}_{v}\leftarrow\bot$

8: $wait_{v}\leftarrow\mathit{true}$

9: else

10: for all $u\in N_{G}(v)$ do

11: $\mathit{OutM}_{v}(u).\mathtt{phase}\leftarrow\mathtt{out}_{v}$

12:else if $\mathtt{out}_{v}=\bot$ and $wait_{v}=\mathit{false}$ then
$\triangleright$ node $v$ is undecided

13: if $\mathtt{Get\\_Step\\_PPS}()=0$ then

14: $\mathit{OutM}_{v}(u).\mathtt{phase}\leftarrow\mathtt{out}_{v}$

15: if $\mathtt{Get\\_Step\\_PPS}()=1$ then

16: $S_{v}\leftarrow\\{u\in
N_{G}(v)\mid\mathit{InM}_{v}.\mathtt{pps}(u)=0,\mathit{InM}_{v}.\mathtt{phase}=\bot\\}$

17: $\mathtt{Phase}^{v}_{1}[S_{v}]$

18: if $\mathtt{Get\\_Step\\_PPS}()=j\in\\{2,\cdots,\phi-1\\}$ then

19: $\mathtt{Phase}^{v}_{j}[S_{v}]$

20:for all $u\in N_{G}(v)$ do

21: $\mathit{OutM}_{v}(u).\mathtt{pps}\leftarrow\mathtt{Get\\_Step\\_PPS}()$

22: $\mathit{OutM}_{v}(u).\mathtt{detect}\leftarrow\mathtt{Detect}_{m}(u)$

23:Send messages

24:Receive messages

Algorithm 2 Self-stabilizing algorithm for edge-LCL obtained by applying the
transformer on $\langle\mathtt{Phase},\mathtt{Detect}\rangle$, code for node
$v$.

1:for all $u\in N_{G}(v)$ do

2: $\mathit{OutM}_{v}(u).\mathtt{phase}\leftarrow\mathit{NIL}$

3: if $\mathtt{Get\\_Step\\_PPS}()=\mathit{\hbar}$ then

4: $wait_{v}(u)\leftarrow\mathit{false}$

5:for all $u\in N_{G}(v)$ do

6: if $\mathtt{Detect}_{\ell}(u)=\mathit{false}$ then

7: $\mathtt{out}_{v}(u)\leftarrow\bot$

8: $wait_{v}(u)\leftarrow\mathit{true}$

9:if $\mathtt{Get\\_Step\\_PPS}()=0$ then

10: $W_{v}=\\{u\in N_{G}(v)\mid
wait_{v}(u)=\mathit{false},\mathtt{out}_{v}(u)=\bot\\}$

11: for all $u\in W_{v}$ do

12: $\mathit{OutM}_{v}(u).\mathtt{phase}\leftarrow\mathtt{out}_{v}(u)$

13:if $\mathtt{Get\\_Step\\_PPS}()=1$ then

14: $S_{v}\leftarrow W_{v}\cap\\{u\in
N_{G}(v)\mid\mathit{InM}_{v}(u).\mathtt{pps}=0,\mathit{InM}_{v}(u).\mathtt{phase}=\bot\\}$

15: $\mathtt{Phase}^{v}_{1}[S_{v}]$

16:if $\mathtt{Get\\_Step\\_PPS}()=j\in\\{2,\cdots,\phi-1\\}$ then

17: $\mathtt{Phase}^{v}_{j}[S_{v}]$

18:for all $u\in N_{G}(v)$ do

19: $\mathit{OutM}_{v}(u).\mathtt{pps}\leftarrow\mathtt{Get\\_Step\\_PPS}()$

20: $\mathit{OutM}_{v}(u).\mathtt{detect}\leftarrow\mathtt{Detect}_{m}(u)$

21:Send messages

22:Receive messages

###  B.2 Module $\mathtt{PPS}$

Algorithm 3 $\mathtt{Step\\_Counter\\_\phi}{}()$, code for node $v$. Executed
in every round towards the end of the local computation stage.

1:if $\mathit{step}_{v}=\mathit{\hbar}$ then

2: $\mathit{phase\\_start}_{v}\leftarrow\mathit{true}\,\,w.p.\
1/2;\,\mathit{false}\,\,w.p.\ 1/2$

3: if $\mathit{phase\\_start}_{v}$ then $\mathit{step}_{v}\leftarrow 0$

4:else if $\mathit{step}_{v}=\phi-1$ then
$\mathit{step}_{v}\leftarrow\mathit{\hbar}$

5:else $\mathit{step}_{v}\leftarrow\mathit{step}_{v}+1$

FIGURES AND TABLES

Problem | Fully adap. run-time | Message size | Comments
---|---|---|---
max. ind. set | $O(\log(k+\Delta))$ | $O(\log\Delta)$ |
node $((1+\epsilon)\Delta)$-coloring | $O(\log(k+\Delta))$ | $O(\log\Delta)$ | constant $\epsilon>0$
node $(\Delta+1)$-coloring | $O(\log(k+\Delta))$ | $O(\Delta\log\Delta)$ | max. node $(\Delta+2)$-coloring
max. node $c$-coloring | $O(\log(k+\Delta))$ | $O(c\log\Delta)$ | $2\leq c\leq\Delta+2$
|  |  | reduction from max. ind. set
inc. node $c$-coloring | $O(c\log(k)+c^{2}\log(\Delta))$ | $O(\log\Delta)$ | $2\leq c\leq\Delta+2$
max. matching | $O(\log(k+\Delta))$ | $O(1)$ |
| $O(\log k)$ | $O(1)$ | with dedicated analysis
edge $((2+\epsilon)\Delta)$-coloring | $O(\log(k+\Delta))$ | $O(\log\Delta)$ | constant $\epsilon>0$
edge $(2\Delta-1)$-coloring | $O(\log(k+\Delta))$ | $O(\Delta^{2}\log\Delta)$ | max. edge $(2\Delta)$-coloring
max. edge $c$-coloring | $O(\log(k+\Delta))$ | $O(c\Delta\log\Delta)$ | $2\leq c\leq 2\Delta$
|  |  | line graph simulation
inc. edge $c$-coloring | $O(c\log(k)+c^{2}\log(\Delta))$ | $O(\Delta\log\Delta)$ | $2\leq c\leq 2\Delta$
|  |  | line graph simulation
Table 1:  The fully adaptive run-time and message size of the self-stabilizing
algorithms obtained through our transformer (all algorithms are applicable to
general graphs).
$0$$1$$\vdots$$\boldsymbol{\phi-1}$$\mathit{\hbar}$$1/2$$1/2$$1$$1$$1$$1$
Figure 1: The underlying Markov chain of $\mathtt{PPS}$ with state space
$S_{\phi}=\\{\mathit{\hbar},0,\dots,\phi-1\\}$.