Ben-Gurion University of The Negev<EMAIL_ADDRESS>T. Maimon
<ccs2012> <concept> <concept_id>10010147.10010919.10010172</concept_id>
<concept_desc>Computing methodologies Distributed algorithms</concept_desc>
<concept_significance>500</concept_significance> </concept> </ccs2012>
[500]Computing methodologies Distributed algorithms

###### Acknowledgements.

I want to thank Leonid Barenboim for the fruitful discussions. I want to thank
Nofit Fraizait for the great feedback. 2 Conference on Principles of
Distributed Systems OPODIS’21 OPODIS 2021 December 13–15, 2021 Strasbourg,
France

# Sleeping Model: Local and Dynamic Algorithms

Tzalik Maimon

###### Abstract

The distributed setting represents a communication network where each node is
a processor with its own memory, and each edge is a direct communication line
between two nodes. Algorithms are usually measured by the number of
synchronized communication rounds required until the algorithm terminates in
all the nodes of the input graph. In this work we refer to this as the clock
round complexity. The setting is studied under several models, more known
among them are the $\mathcal{LOCAL}$ model and the $\mathcal{CONGEST}$ model.
In recent years the sleeping model (or some variation thereof) came to the
focus of researchers [7, 8, 9, 11, 12, 13, 6]. In this model nodes can go into
a sleep state in which they spend no energy but at the same time cannot
receive or send messages, nor can they perform internal computations. This
model captures energy considerations of a problem. In [6] Barenboim and Maimon
defined the class of O-LOCAL111A problem $P$ is an O-LOCAL problem if, given
an acyclic orientation on the edges of the input graph, one can solve the
problem as follows. Each vertex awaits the decisions of its parents according
to the given orientation and can make its own decision in regard to $P$ using
only the information about its parents decisions. problems and showed that for
this class of problems there is a deterministic algorithm that runs in
$O(\log\Delta)$ awake time. The clock round complexity of that algorithm is
$O(\Delta^{2})$. Well-studied O-LOCAL problems include coloring and Maximal
Independence Set (MIS).

In this work we present several deterministic results in the sleeping model:

  1. 1.

We offer three algorithms for the O-LOCAL class of problems with a trade off
between awake complexity and clock round complexity. One of these algorithms
requires only $O(\Delta^{1+\epsilon})$ clock rounds for some constant
$\epsilon>0$ but still only $O(\log\Delta)$ awake time which improves on the
algorithm in [6]. We add to this two other algorithms that trade a higher
awake complexity for lower clock round complexity. We note that the awake time
incurred is not that significant.

  2. 2.

We offer dynamic algorithms in the sleeping model. We show three algorithms
for solving dynamic problems in the O-LOCAL class as well as an algorithm for
solving any dynamic decidable problem.

  3. 3.

We show that one can solve any O-LOCAL problem in constant awake time in
graphs with constant neighborhood independence. Specifically, our algorithm
requires $O(K)$ awake time where $K$ is the neighborhood independence of the
input graph. Graphs with bounded neighborhood independence are well studied
with several results in recent years for several core problem in the
distributed setting [1, 16, 3, 4, 5].

###### keywords:

Distributed Computing, Sleeping model, Bounded Neighborhood Independence

##  1 Introduction

In the distributed setting there are several problems which take a central
place in the attention of researchers. Among those are the Maximal Independent
Set (MIS), Maximal Matching and graph coloring. These problems have been
studied in various distributed models like the $\mathcal{CONGEST}$ model, the
congested clique and, recently, the sleeping model. The sleeping model is a
distributed model where network nodes can enter a sleeping state. As long as a
vertex is in the awake state, it can do whatever it can in the standard
message-passing setting. However, when a vertex is asleep it cannot receive or
send messages in the network nor can it perform internal computations. On the
other hand, sleeping rounds do not count towards the complexity in the model
which is aptly named awake complexity. This complexity is expressed by the
number of awake rounds a vertex spends during an execution. In this paper we
offer several results in the sleeping model. First, we offer three algorithms
with different awake time complexity and clock round complexity for solving
any O-LOCAL problem. This class of problems is consisted of problems that,
given an acyclic orientation, can be solved as follows. Each vertex awaits all
its parents (neighbors on outgoing edges) to calculate their solution for $P$
and then decides on its own solution for the problem. The three algorithms are
summarized in Table 1.

Method | Awake Time | Clock Rounds
---|---|---
Theorem 3.3 | $O(\log^{2}\Delta+\log^{*}\Delta\log^{*}n)$ | $O(\Delta+\log^{*}\Delta\log^{*}n)$
Theorem 3.1 | $O(\log^{2}\Delta+\log^{*}n)$ | $O(\Delta\log\Delta+\log^{*}n)$
Theorem 3.2 | $O(\log\Delta+\log^{*}n)$ | $O(\Delta^{1+\epsilon}+\log^{*}n)$
Table 1: : O-LOCAL Algorithms: the trade-off between awake complexity and
clock round complexity.

Under this model one can also consider dynamic algorithms in which the task is
to update a given solution for a problem after an update phase in which
changes are made to the input graph. These changes can be expressed as updates
to the vertex set or the edge set of the graph. In this setting it is common
practice to analyze the performance of the update phases and the preparation
phase separately where usually the update time takes priority. This is since
the assumption is that the number of changes is much greater over time than
the complexity of solving the problem in an non-dynamic setting. In this paper
we will show that in the sleeping model, with the solution we show here, one
achieves dynamic algorithms for decidable problems as well as the O-LOCAL
class of problems. Our results appear in Table 2.

Method | Awake Time | Clock Rounds
---|---|---
Theorem 3.3 | $O(\log^{2}\alpha+\log^{*}\alpha\log^{*}\beta)$ | $O(\alpha+\log^{*}\alpha\log^{*}\beta)$
Theorem 3.1 | $O(\log^{2}\alpha+\log^{*}\beta)$ | $O(\alpha\log\alpha+\log^{*}\beta)$
Theorem 3.2 | $O(\log\alpha+\log^{*}\beta)$ | $O(\alpha^{1+\epsilon}+\log^{*}\beta)$
Table 2: : O-LOCAL Dynamic algorithms and the trade off between awake
complexity and clock round complexity.

Another result we offer in this work is a a constant awake time algorithm for
solving any O-LOCAL problem in graphs with bounded neighborhood independence.
The family of graphs with bounded neighborhood independence is a very wide
family of dense graphs. In particular, graphs with constant neighborhood
independence include line-graphs, claw-free graphs, unit disk graphs, and many
other graphs. Thus, these graphs represent very well various types of
networks. Our technique for this family of graphs is to build an acyclic
orientation of the input graph in constant awake time such that each vertex
has constant number of parents in the orientation. This allows us to solve
O-LOCAL problems in constant time according to the definition of this class.

###  1.1 Previous Work

Several variants of the sleeping setting were studied recently [7, 8, 9, 11,
12, 13]. The particular setting and complexity measurement we consider in this
paper were introduced by Chatterjee, Gmyr and Pandurangan [8] in PODC’20. In
this paper the authors presented a Maximal Independent Set randomized
algorithm with expected awake complexity of $O(1)$. Its high-probability awake
complexity is $O(\log n)$, and its worst-case awake complexity is
polylogarithmic. Recently Barenboim and Maimon [6] showed a completeness on
the class of decidable problems with a tight bound of $\Theta(\log n)$ awake
time complexity. That is, they offered an algorithm for solving any decidable
problem in the sleeping model in $O(\log n)$ awake time but also showed a
specific decidable problem which requires at least $\Omega(\log n)$ awake
time. Furthermore, for the O-LOCAL class of problems, among them the problem
of MIS, they showed an even better algorithm with $O(\log\Delta)$ awake time.
The importance of the sleeping model was shown empirically in experiments [10,
17]. The energy consumption in an idle state is only slightly smaller than
when a node is active. However, in the sleeping state the energy consumption
is decreased drastically. Thus, if a node may enter a sleeping mode to save
energy during the course of an algorithm, one can significantly improve the
energy consumption of the network during the execution of an algorithm.

###  1.2 Our Technique

In [6] the authors showed that given an acyclic orientation on the edge set of
the input graph $G$, one can use the given orientation to build a binary tree
internally in each vertex $v$ and have $v$ in the awake state exactly when one
of its parents in the orientation sends information to $v$. This is
facilitated to solve any O-LOCAL problem. In their paper, Barenboim and Maimon
used a $O(\Delta^{2})$-vertex-coloring to achieve this required acyclic
orientation but we here capitalize on this idea and offer different ways to
build an initial orientation such that, in terms of awake complexity, our
algorithms are more efficient.

For graphs with bounded neighborhood independence we do the same by showing
that building an initial orientation takes $O(1)$ time in this family of
graphs. Furthermore, we show that the length of the orientation, which
directly effects the efficiency of the algorithms in both awake time and
number of clock rounds required, is at most $K+1$ where $K$ is the
neighborhood independence of $G$. This gives us an efficient scheme for
solving any O-LOCAL problem in constant awake time which, up to a constant, is
most efficient.

##  2 Preliminaries

The O-LOCAL Class. This is a class of problems that can be solved in the
following way. Given an acyclic orientation of the edges and a problem $P$,
each vertex awaits the decisions of its parents in the orientation and is able
then to make a decision and find a solution for itself in regard to problem
$P$ using only internal computations. Core problems in the distributed setting
that belong to this class are the MIS and coloring problems.

Awake Worst-Case Complexity. This measurement is defined as the worst-case
number of rounds in which any single vertex is awake. That is, if $w(v)$ is
the number of awake rounds that a vertex $v\in G$ is awake, then the awake
worst case complexity is defined as $\max(w(v)|v\in G)$. In this work, we
loosely use the term awake complexity to mean awake worst-case complexity.

Neighborhood Independence. Given a vertex $v\in G$, the neighborhood
independence of $v$ is the maximum size set of independent neighbors one can
build from the 1-hop neighborhood of $v$. The neighborhood independence of $G$
is the maximum among all neighborhood independence values of the vertices in
$G$.

##  3 Trade-Offs for O-LOCAL Problems

Distributed algorithms in the $\mathcal{LOCAL}$ model have a certain running
time which depends on vertices which await their turn to make a decision. On
the contrary, in the sleeping model these vertices do not count towards the
worst-case awake time of the algorithm. But one might still wish to achieve
efficiency in both measurements, that is, both the energy required for the
algorithm to terminate as well as the number of total number of communication
clock rounds. And thus, algorithms that offer trade offs between these two
measurements are of interest. Here we bring three such algorithms and show
this trade off can be achieved. Furthermore, our result from Theorem 3.2
improves on the algorithm shown in [6] for the O-LOCAL class of problems
regardless of the trade off mentioned. Specifically, the number of clock
rounds is the same while we improve on the worst case awake time. The results
of this section are summarized in Table 1.

For the purpose of this section we will utilize the algorithm suggested in [6]
for solving any O-LOCAL problem in $O(\log\Delta+\log^{*}n)$ awake time. In
this algorithm, we start by coloring the vertices and using this coloring we
build binary trees in each vertex according which the vertex awakes and
sleeps. The depth of these trees is $O(\log\Delta)$ which sets the awake time
complexity of the algorithm. The number of colors used (originally
$O(\Delta^{2})$ in [6]) sets the number of clock rounds required for using
these binary trees to solve an O-LOCAL problem. Given an initial coloring of
the graph with $d$ colors, it is obvious one can orient the edges of the
graphs to achieve an acyclic orientation of length $d$. Using the algorithm
described above, from now denoted $A$, one can solve any O-LOCAL problem in
$O(\log d)$ awake time and $O(d)$ clock rounds. We will use this property of
the algorithm $A$ for iterative re-coloring of the input graph. This method
reduces the number of clock rounds required while maintaining low energy
consumption in the network. We state the performance property of the algorithm
$A$ as it plays an important role in the analysis of the algorithms described
in this section.

The Performance Property of Algorithm $A$. Given a graph $G$ with $d$-vertex-
coloring, the algorithm $A$ can be used for solving any O-LOCAL problem in
$O(\log d)$ awake time and $O(d)$ clock rounds.

###  3.1 Sleeping KW Reduction

We give our own version to The Kuhn-Wattenhofer Color Reduction (KW) [14]
algorithm. This version is more efficient in terms of the sleeping model. The
original algorithm starts with an initial coloring provided by the algorithm
of Linial [15] and proceeds to reduce the number of colors in phases. There
are $O(\log\Delta)$ phases, each takes $O(\Delta)$ time. In such a reduction,
each vertex $v$ with color $l$ awaits the $l$ clock round and inspects the
colors of its neighbors. Then $v$ chooses the smallest possible color
available as its final color. In such a reduction the running time depends on
the initial color palette size. In the KW algorithm these palettes are chosen
such that they are of size at most $O(\Delta)$.

In terms of awake time the core issue is that a vertex $v$ requires
information from all its neighbors potentially requiring its neighbors to be
awake to transmit their colors to $v$. This means that there could be vertices
that are kept awake only to report their colors to the vertices that color
themselves at round $l$. So, we use an alternative. Instead of using the
regular reduction we execute the algorithm $A$ to use the minimal colors
possible to achieve the same result as the reduction. The algorithm $A$
depends on the size of the palette as well as for palette of size $d$ the
performance of $A$ is $O(\log d)$ awake time and $O(d)$ clock rounds.
Asymptotically, we do not require additional clock rounds than the original
version of the KW algorithm but we do require less awake rounds in each phase
in the KW reduction. Therefore, the number of clocks required for our version
of KW reduction is still $O(\Delta\log\Delta)$. Since the KW algorithm has
$O(\log\Delta)$ phases and each requires at most $O(\log\Delta)$ awake rounds,
we achieve $O(\log^{2}\Delta)$ awake time. We must not forget that the
reduction starts with the coloring of Linial and therefore we have the
following result.

######  Theorem 3.1.

Any O-LOCAL problem can be solved in $O(\log^{2}\Delta+\log^{*}n)$ awake time
using at most $O(\Delta\log\Delta+\log^{*}n)$ clock rounds.

###  3.2 Preferring Low Awake Complexity

We give yet another version for solving problems in the O-LOCAL class. We use
the KW reduction again only this time we reduce the coloring of several sets
of colors at once instead of one color at a time. In the previous version, at
each phase of the KW reduction we achieved a palette of size $O(\Delta)$ for
the reduction by reducing the colors of a union on pairs of color sets. Let
$V_{1},\dots,V_{r}$ be the color sets and let $\epsilon>0$ be some constant.
Instead of reducing the colors on $V_{1}\cup V_{2},V_{3}\cup V_{4},\dots$,
which means pairs of color sets, we reduce the colors on the union of
$\Delta^{\epsilon}$ color sets. The reduction is done on the color sets of the
union $V_{1}\cup V_{2}\cup\dots
V_{\Delta^{\epsilon}},V_{\Delta^{\epsilon+1}}\cup
V_{\Delta^{\epsilon+2}}\dots$ and on each such union we execute the algorithm
$A$. According to the performance property of the algorithm $A$, this requires
$O((1+\epsilon)\log\Delta)$ awake rounds and $O(\Delta^{1+\epsilon})$ clock
rounds. The number of phases we now require is
$O(\frac{\log\Delta}{\log\Delta^{\epsilon}})=O(\frac{1}{\epsilon})$. We still
manage to achieve a $(\Delta+1)$-vertex-coloring. As mentioned before, this
result improves on the clock round complexity achieved in [6] without
incurring additional awake complexity.

######  Theorem 3.2.

Any O-LOCAL problem can be solved in $O(\log\Delta+\log^{*}n)$ awake time
using at most $O(\Delta^{1+\epsilon}+\log^{*}n)$ clock rounds where
$\epsilon>0$ is a constant.

###  3.3 Preferring Clock Rounds

In this section we offer another sleeping algorithm in which the number of
clock rounds is lower if one is willing to pay in awake complexity. We note,
though, that this payment is not significant compared to the complexity
achieved in Section 3.1. In their monograph [2] Barenboim and Elkin showed
that the KW color reduction can be used in combination with defective coloring
to create a series of $\log^{*}\Delta$ algorithms such that the overall
running time of computing a $(\Delta+1)$-vertex-coloring is
$O(\Delta+\log^{*}\Delta\log^{*}n)$ clock rounds. In that series of algorithms
they used KW reduction and the KW iterative reduction in each algorithm for
reducing the number of colors of the defective subsets of colors. In [2]
Barenboim and Elkin named KW iterative reduction the algorithm of which the
reduction starts with a given coloring $\phi$. Given a coloring using $a$
colors, it is known that the KW reduction in this case requires
$O(\log\frac{a}{\Delta+1})$ phases each in which a reduction is done on
palette of size $O(\Delta)$. We can replace both these algorithms with our own
versions of KW reduction for the sleeping model (as we only changed the
technique of reduction in each phase, the number of phases remain the same in
the KW iterative reduction. We call this the Sleeping KW Iterative Reduction).
We do this by defining the algorithm $H_{1}$ to be the algorithm from Theorem
3.1. For integer values of $k\geq 2$ we define the algorithm $H_{k}$ in
Algorithm 1. Ours is a revision of the algorithm in [2]. This variation brings
us closer to the lower bound of the O-LOCAL class of problems while incurring
a very small additive factor in the awake complexity in comparison to the
algorithms in Section 3.1.

Algorithm 1 $\mathcal{H}_{k}(G)$

1: $p=\log^{(k-1)}\Delta$.

2: Compute an $O(\frac{\Delta}{p})$-defective coloring using $p^{2}$ colors.
Denote $G_{1},\dots,G_{p^{2}}$ the subgraphs induced by the color sets.

3: for each $G_{i}$ in parallel do

4: Compute a proper coloring for $G_{i}$ using the algorithm
$\mathcal{H}_{k-1}$. Denote the coloring as $\mu_{i}$.

5: end for

6: Denote as $\mu$ the $O(p\Delta)$-coloring created from
$\mu_{1},\dots,\mu_{p^{2}}$. Invoke the sleeping KW iterative reduction on
$\mu$ to gain a $(\Delta+1)$-coloring on $G$. Denote final coloring as $\phi$.

7: return $\phi$

######  Theorem 3.3.

Any O-LOCAL problem can be solved in
$O(\log^{2}\Delta+\log^{*}\Delta\log^{*}n)$ awake time using at most
$O(\Delta+\log^{*}\Delta\log^{*}n)$ clock rounds.

###### Proof.

In [2] it is shown that the number of clock rounds required for the algorithm
$H_{\log^{*}\Delta}$ is $O(\Delta+\log^{*}\Delta\log^{*}n)$. Our version of KW
require $O(\Delta\log\Delta+\log^{*}\Delta)$ clock rounds which is the same as
the standard KW reduction which is used in [2]. Therefore the number of clock
rounds is the same as in [2]. Thus, we focus this proof on the awake
complexity. The proof is by reduction on $2\leq i\leq k$. Denote $T(H_{i})$
the awake time of the algorithm $H_{i}$. We inspect the lines in Algorithm 1.
Line 2 requires $O(\log^{*}n)$ awake rounds [15]. Line 4 requires $T(H_{i-1})$
awake rounds. Line 6 invokes the sleeping KW iterative reduction. Each phase
in this variant takes $O(\log\Delta)$ time. There are
$O(\log\frac{p\Delta}{\Delta})=O(\log p)=O(\log^{(i)}\Delta)$ phases and
overall line 6 requires $O(\log\Delta\log^{(i)}\Delta)$ awake rounds.
Specifically, for every value of $2\leq i\leq k$, line 6 requires at most
$O(\log\Delta\log\log\Delta)$. We denote $c$ as a super-constant to represent
the maximum between constants hidden in the awake times for all algorithms.
Then,

$T(H_{\log^{*}\Delta})\leq
c(\log\Delta\log\log\Delta+\log^{*}n)+T(H_{\log^{*}\Delta-1})\leq$
$2c(\log\Delta\log\log\Delta+\log^{*}n)+T(H_{\log^{*}\Delta-2})\leq$
$3c(\log\Delta\log\log\Delta+\log^{*}n)+T(H_{\log^{*}\Delta-3})\leq\dots$
$i\cdot
c(\log\Delta\log\log\Delta+\log^{*}n)+T(H_{\log^{*}\Delta-i})\leq\dots$
$c(\log^{*}\Delta-1)(\log\Delta\log\log\Delta+\log^{*}n)+T(H_{1})$

From Theorem 3.1 executing $H_{1}$ on a graph of degree
$\frac{\Delta}{\log\Delta}$ gives us $T(H_{1})=O(\log^{2}\Delta+\log^{*}n)$.
Thus, $T(H_{\log^{*}\Delta})=$
$O(\log^{2}\Delta+\log^{*}n)+O(\log\Delta\log\log\Delta\log^{*}\Delta+\log^{*}\Delta\log^{*}n)=$
$O(\log^{2}\Delta+\log^{*}\Delta\log^{*}n)$.
Using this $(\Delta+1)$ coloring with the algorithm $A$ provides a solution to
any O-LOCAL problem in the same awake and running times as the algorithm
$H_{\log^{*}\Delta}$. ∎

##  4 Sleeping in Bounded Neighborhood Independence

Given some acyclic orientation $\mu$ on an input graph $G$ with bounded
neighborhood independence $K$, we give an algorithm that solves any O-LOCAL
problem in $O(K)$ awake deterministic time. The general scheme of the
algorithm is quite simple. Using the orientation $\mu$, we build a new partial
orientation $\phi$ on the edge set in the sense that some edges are not being
orientated. We show that solving an O-LOCAL problem $P$ using this new
orientation is the same as solving $P$ on the original orientation. The
difference is that the new orientation requires less awake rounds from
vertices in $G$ which is our goal.

The new orientation is built as follows. At first all vertices of the graph
are awake and each vertex is collecting the information from its 1-hop-
neighborhood. Then all vertices enter a sleep state. Each vertex $v$ chooses
parents from its 1-hop-neighborhood as follows. Internally, $v$ calculates an
independent ruling set of the subgraph induced by its neighbors which have
labels smaller than the label of $v$ and notes them as its parents. Moreover,
these vertices are chosen such that their labels are the greatest among the
potential parents of $v$. This can be done greedily by choosing the neighbor
$u$ such that $ID(u)=\min(ID(w)\ |\ w\in N^{*}(v))$ and $ID(u)<ID(v)$ (where
$N^{*}(v)$ is the 1-hop-neighborhood of $v$ without including $v$ itself).
Then $v$ sets $u$ as a parent. $v$ then repeats this process until it can no
longer choose new parents that holds the above requirements. For solving a
given problem $P\in$ O-LOCAL each vertex is awakened in the clock round equal
to each of its parents labels as well as the clock round that equals its own
label. We now show that solving $P$ on $G$ using the orientation $\phi$ indeed
gives us the solution of $P$ on $G$ according to $\mu$.

######  Lemma 4.1.

Let $v$ be a vertex in $G$ and $u$ be a neighbor of $v$ such that
$\mu(u)<\mu(v)$. Then, in clock rounds $L(v)$, $v$ has the knowledge of the
solution of $u$, denote $s(u)$, made. Thus, $v$ can resolve $P$ internally.

###### Proof.

We will show that there must be an oriented path in $\phi$ on which the value
of $s(u)$ is propagated such that in round $L(v)$ the information of $s(v)$ is
in $v$ and $v$ can use the information to calculate $s(v)$. In the case $u$ is
a parent of $v$ in $\phi$ then $v$ is awake in clock round $L(u)$ and receives
the value $s(u)$ for $P$ in that round and we are done. Otherwise, $u$ is not
a parent of $v$ in $\phi$. Denote the subset of vertices $v$ chose as a ruling
set from its neighbors as $M(v)$. When $v$ chose the set $M(v)$ then there
must be a vertex $w_{1}\in M(v)$ which $v$ chose over $u$. Thus, $w_{1}$ and
$u$ are neighbors in $G$, and $L(w_{1})>L(u)$.
If $u$ is a parent of $w_{1}$ in $\phi$ then $w_{1}$ is awake in clock round
$L(u)$ and receives the knowledge of $s(u)$ in that round. Then $w_{1}$ passes
this knowledge to $v$ in clock round $L(w_{1})$ as $v$ is awake in that clock
round. Otherwise, If $u$ is not a parent of $w_{1}$ in $\phi$ then there must
be a vertex $w_{2}\in M(w_{1})$ which $w_{1}$ chose over $u$. Therefore,
$L(w_{1})>L(w_{2})>L(u)$ and $w_{2}$ is also a neighbor of $u$ in $G$. The
same as before, if $u$ is a parent of $w_{2}$ in $\phi$ then $w_{2}$ passes
$s(u)$ to $w_{1}$ in clock round $L(w_{2})$ and $w_{1}$ passes $s(u)$ to $v$
in clock round $L(w_{1})$.
Since we assume the graph is finite and therefore any acyclic orientation on
its edges is finite, an oriented path can only be of length of the
orientation, denote $\ell$. Note that for each $i$ we have the following:
First, $w_{i}$ is a neighbor of $u$ in $G$. Secondly, for each $1\leq j\leq
i$, any $w_{j}$ is a neighbor of $u$ and did not choose $u$ to be in
$M(w_{j})$. Thirdly, for each $i$ we have $L(w_{i})<L(w_{i-1})$. We can have
only so many repetitions of reducing the labels for the value of $i$ until we
reach the label of $u$ itself. Thus, for some value of $i\leq\ell$, $w_{i}$
must choose $u$ to be in $M(w_{i})$ and our oriented path is complete. it
contains the vertices, in order, $u,w_{i},w_{i-1},\dots,v$. Each vertex in
this path is awake in the clock round equals to the label of its parent
allowing $s(u)$ to propagate to $v$ until clock round $L(v)$ arrives in which
$v$ can use $s(v)$ to compute $s(v)$. ∎

From the above lemma we have that $v$ has all resolutions of its parents
according to the orientation $\mu$ at clock round $L(v)$ in which $s(v)$ is
calculated. Note that $v$ has at most $K$ parents in the orientation $\phi$ as
its parents has to be independent of each other. According to the definition
of the problem $P$ as a O-LOCAL problem, we achieve the following result.

######  Theorem 4.2.

Given a graph with an acyclic orientation, any O-LOCAL problem can be solved
deterministically within $K+1$ awake rounds where $K$ is the maximal
neighborhood independence of the input graph $G$.

One now might wonder where this initial orientation comes from. One can use
the algorithm and feed it with an orientation as an input as long as that
orientation is acyclic. We use any of the algorithms given in Section 3 to
achieve this initial orientation with different awake complexities as well as
different clock round complexities. In this section, though, we focus on the
awake time complexity and prefer to neglect the number of clock rounds. And so
we only need an acyclic orientation which one can achieve in a single awake
round for all vertices by orienting the edges towards the vertex with the
greater ID. This immediately gives us the following result and the corollary
which follows.

######  Theorem 4.3.

Any O-LOCAL problem can be solved deterministically within $K+1$ awake rounds
where $K$ is the maximal neighborhood independence of the input graph $G$.

######  Corollary 4.4.

Any O-LOCAL problem can be solved within constant deterministic awake time in
graphs with bounded neighborhood independence.

A Remark on the Trade-Off Between Awake Time Complexity and Number of Clock
Rounds Complexity:
Our algorithm is not dependent on the length of the given orientation in terms
of the awake time complexity. But it is clear that the length of the
orientation effects the communication clock rounds complexity. For an
orientation of length $\ell$ we need $O(\ell)$ clock rounds. The orientation
we use above can be of length $O(n)$. But if one is willing to trade off
$O(\log^{*}n)$ awake time there are coloring algorithms that will guarantee a
shorter orientation such as the algorithm of Linial [15] for
$O(\Delta^{2})$-vertex-coloring. This shows another strength of our algorithm
as it can work with any algorithm for orienting the edges of the input graph.

######  Corollary 4.5.

Any O-LOCAL problem can be solved within $O(\log^{*}n)$ awake time and
$O(\log^{*}n)$ clock rounds in graphs with bounded neighborhood independence.

##  5 Dynamic Distributed O-LOCAL Problems

We devise a deterministic dynamic algorithm in the sleeping setting for
maintaining a solution for a given O-LOCAL problem $P$. This scheme is later
improved significantly but lays the basis for understanding how to use
coloring algorithms as dynamic sleeping algorithms for O-LOCAL problems. The
preparation stage is the algorithm in [6] for solving O-LOCAL problems,
denoted $A$. We do this only at the preparation stage. Given a problem $P$ as
defined above one can solve $P$ in $O(\log\Delta)$ awake time with $O(\Delta)$
number of clock rounds.
Let $t$ be an integer representing the number of changes between executions of
the update algorithm. That is, we advance in phases. In each phase the
vertices of the graph are asleep for $t$ clock rounds and wake up after to
check if changes were made to their adjacent edges. Without loss of
generality, we allow for a single change in each of the $t$ clock rounds in
the change state. This includes both changes to edges and vertices. We start
with the assumption the problem $P$ was solved on $G$ prior to the current
changes. Then we run an update algorithm during which there can be no changes
to the graph. Our algorithm recolors the sub-graph which was changed properly
and uses $A$ to maintain the solution for the problem $P$ on the new version
of $G$ thus keeping the assumption we started from for the next batch of
changes.
Let $S$ be the subset of vertices whose adjacent edges changed and also
including new vertices. Let $k=\min(t,\Delta)$. Notice that $|S|=O(t)$. We set
the color of the vertices in $S$ to 0 (no color). We color $S$ using
$O(k^{2})$ colors in $O(\log^{*}t)$ time. We then awake the entire graph for 1
round so that vertices in $S$ can collect the colors of vertices in $N(S)$,
that is the information from the vertices in $G$ of distance at most 1 from
vertices in $S$, as well as their yet legal choices in regard to problem $P$.
We then use the algorithm $A$ to reduce the number of colors in $S$ to $k+1$.
We now again use the algorithm $A$ to Solve $P$ within $S$ when the
orientation we use is one where vertices outside of $S$ are directed into $S$
and inside $S$ the orientation continues according to the coloring.

######  Lemma 5.1.

The new orientation allows us to solve $P$ legally on $G$.

###### Proof.

In the subgraph induced on the vertex subset $V/S$ the problem $P$ is already
solved and legal. One can now regard the process of solving $P$ on $S$ as if
we activated $A$ on $G$ where vertices in $V/S$ take priority in the
orientation. But these vertices do not awake in our scheme besides for a
single round to have their neighbors in $S$ know of their choices. From now
solving $P$, since it is an ${O-LOCAL}$ problem, is a manner of progressing on
the orientation inside $S$ which we are given by the coloring of $S$. ∎

Note that although overall in $G$ there might now be more colors than
$(\Delta+1)$ we do not use all these colors in our scheme as only vertices in
$S$ need recalculation for $P$. We do though preserve the property that $P$ is
solved on $G$ and that is all we require for Lemma 5.1.

######  Theorem 5.2.

Let $t$ be the number of edge additions that occur between executions of an
update algorithm. Let $\alpha=\min(\Delta,t)$ and let $\beta=\min(n,t)$ where
$\Delta$ is the current maximum degree of the graph. Then there is a
deterministic dynamic sleeping algorithm for solving any problem in the class
of O-LOCAL problems with awake update-time $O(\log\alpha+\log^{*}\beta)$. The
update requires $O(\alpha^{2}+\log^{*}\beta)$ clock rounds.

Using the results from Table 1, each as a dynamic algorithm in the same manner
presented in this section, we can achieve three results each expressed in
terms of the changes made to a graph and using the algorithms in question as
the coloring algorithm for the subset $S$. The running times can be concluded
easily in terms of $\alpha,\beta$. One simply sets $\Delta=\alpha$ and
$n=\beta$ in Table 1 to achieve the complexities of the dynamic variations.

##  6 Dynamic Algorithm for Decidable Problems

In [6] Barenboim and Maimon offered an algorithm for building a Distributed
Layered Tree (DLT) in $O(\log n\log^{*}n)$ awake time that requires $O(n\log
n\log^{*}n)$ clock rounds. Loosely described, a DLT is an oriented tree in $G$
with a labeling to the vertices of the graph. The labeling is such that the
label of each vertex is greater than that of its parent in the tree. A close
inspection of this algorithm shows that these complexities derive from the
initial $n$ vertices that are connected to a single DLT. We show here that the
algorithm can be adapted to the dynamic setting. Assume that in the
preparation stage we built a DLT for $G$. The following lemma shows the number
of sub-DLTs created by the changes to the graph.

######  Lemma 6.1.

After $t$ changes to $G$, a DLT of $G$ is partitioned to at most $O(t\Delta)$
distinct sub DLTs.

###### Proof.

We prove this by types of changes. Adding an edge or a vertex does not shatter
the existing DLT of a connected component. Adding an edge, though, does have
the potential to unite two connected components into one, thus requires us to
unite 2 DLTs into one. Thus, addition creates at most 1 connection requirement
between the existing DLTs. Removing an edge, if it one that is in the DLT,
shatters the DLT into two, again requires us for at most 1 connection between
two DLTs, amending the disconnection (if such amend is possible). Removing a
vertex removes all $\Delta$ adjacent edges thus requiring at most $\Delta$
connections between $\Delta+1$ sub DLTs to re-unite into a single DLT (where
possible). Therefore, the worse case is that we will have $t$ vertex removal
and from this we conclude that we have at most $O(t\Delta)$ sub DLTs to
connect into a single DLT that spans the input graph. ∎

Thus, we are required for $O(\log t+\log\Delta)$ connection phases using the
same DLT algorithm from [6]. Each phase requires coloring in
$O(\log^{*}t+\log^{*}\Delta)$ awake time. The number of clock rounds is still
$O(n)$ in each connection phase.

######  Theorem 6.2.

Let $t$ be the number of changes between executions of an update algorithm.
Let $b=\min(\max(t,\Delta),n)$. In the dynamic sleeping model there is a
deterministic algorithm for any decidable problem with awake update-time of
$O(\log b\log^{*}b)$. The update requires $O(n\log b\log^{*}b)$ clock rounds.

Remark: In the worst case where the number of changes is very large, i.e.
$\Omega(n)$, our algorithm aligns with the algorithm at [6].

## References

  * [1] Leonid Barenboim and Michael Elkin.  Distributed deterministic edge coloring using bounded neighborhood independence.  Distributed Comput., 26(5-6):273–287, 2013.  doi:10.1007/s00446-012-0167-7.
  * [2] Leonid Barenboim and Michael Elkin.  Distributed Graph Coloring: Fundamentals and Recent Developments.  Synthesis Lectures on Distributed Computing Theory. Morgan & Claypool Publishers, 2013.  doi:10.2200/S00520ED1V01Y201307DCT011.
  * [3] Leonid Barenboim and Tzalik Maimon.  Distributed symmetry breaking in graphs with bounded diversity.  In 2018 IEEE International Parallel and Distributed Processing Symposium, IPDPS 2018, Vancouver, BC, Canada, May 21-25, 2018, pages 723–732. IEEE Computer Society, 2018.  doi:10.1109/IPDPS.2018.00082.
  * [4] Leonid Barenboim and Tzalik Maimon.  Fully dynamic graph algorithms inspired by distributed computing: Deterministic maximal matching and edge coloring in sublinear update-time.  ACM J. Exp. Algorithmics, 24(1):1.14:1–1.14:24, 2019.  doi:10.1145/3338529.
  * [5] Leonid Barenboim and Tzalik Maimon.  Simple distributed spanners in dense congest networks.  In Alexander Chatzigeorgiou, Riccardo Dondi, Herodotos Herodotou, Christos A. Kapoutsis, Yannis Manolopoulos, George A. Papadopoulos, and Florian Sikora, editors, SOFSEM 2020: Theory and Practice of Computer Science - 46th International Conference on Current Trends in Theory and Practice of Informatics, SOFSEM 2020, Limassol, Cyprus, January 20-24, 2020, Proceedings, volume 12011 of Lecture Notes in Computer Science, pages 260–272. Springer, 2020.  doi:10.1007/978-3-030-38919-2\\_22.
  * [6] Leonid Barenboim and Tzalik Maimon.  Deterministic logarithmic completeness in the distributed sleeping model (to be published in DISC’21).  CoRR, abs/2108.01963, 2021.  arXiv:2108.01963.
  * [7] Leonid Barenboim and Yaniv Tzur.  Distributed symmetry-breaking with improved vertex-averaged complexity.  In Proceedings of the 20th International Conference on Distributed Computing and Networking, ICDCN 2019, Bangalore, India, January 04-07, 2019, pages 31–40. ACM, 2019.  doi:10.1145/3288599.3288601.
  * [8] Soumyottam Chatterjee, Robert Gmyr, and Gopal Pandurangan.  Sleeping is efficient: MIS in _O_(1)-rounds node-averaged awake complexity.  In PODC ’20: ACM Symposium on Principles of Distributed Computing, Virtual Event, Italy, August 3-7, 2020, pages 99–108. ACM, 2020\.  doi:10.1145/3382734.3405718.
  * [9] Cynthia Dwork, Joseph Y. Halpern, and Orli Waarts.  Performing work efficiently in the presence of faults.  SIAM J. Comput., 27(5):1457–1491, 1998.  doi:10.1137/S0097539793255527.
  * [10] Laura Marie Feeney and Martin Nilsson.  Investigating the energy consumption of a wireless network interface in an ad hoc networking environment.  In Proceedings IEEE INFOCOM 2001, The Conference on Computer Communications, Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies, Twenty years into the communications odyssey, Anchorage, Alaska, USA, April 22-26, 2001, pages 1548–1557. IEEE Comptuer Society, 2001.  doi:10.1109/INFCOM.2001.916651.
  * [11] Laurent Feuilloley.  How long it takes for an ordinary node with an ordinary id to output?  Theor. Comput. Sci., 811:42–55, 2020.  doi:10.1016/j.tcs.2019.01.023.
  * [12] Leszek Gasieniec, Erez Kantor, Dariusz R. Kowalski, David Peleg, and Chang Su.  Time efficient k-shot broadcasting in known topology radio networks.  Distributed Comput., 21(2):117–127, 2008.  doi:10.1007/s00446-008-0058-0.
  * [13] Valerie King, Cynthia A. Phillips, Jared Saia, and Maxwell Young.  Sleeping on the job: Energy-efficient and robust broadcast for radio networks.  Algorithmica, 61(3):518–554, 2011.  doi:10.1007/s00453-010-9422-0.
  * [14] Fabian Kuhn and Roger Wattenhofer.  On the complexity of distributed graph coloring.  In Eric Ruppert and Dahlia Malkhi, editors, Proceedings of the Twenty-Fifth Annual ACM Symposium on Principles of Distributed Computing, PODC 2006, Denver, CO, USA, July 23-26, 2006, pages 7–15. ACM, 2006.  doi:10.1145/1146381.1146387.
  * [15] Nathan Linial.  Legal coloring of graphs.  Comb., 6(1):49–54, 1986.  doi:10.1007/BF02579408.
  * [16] Lazar Milenkovic and Shay Solomon.  A unified sparsification approach for matching problems in graphs of bounded neighborhood independence.  In Christian Scheideler and Michael Spear, editors, SPAA ’20: 32nd ACM Symposium on Parallelism in Algorithms and Architectures, Virtual Event, USA, July 15-17, 2020, pages 395–406. ACM, 2020.  doi:10.1145/3350755.3400248.
  * [17] Rong Zheng and Robin Kravets.  On-demand power management for ad hoc networks.  Ad Hoc Networks, 3(1):51–68, 2005.  doi:10.1016/j.adhoc.2003.09.008.