11institutetext:  Institut de Recherche en Informatique Fondamentale (IRIF),
CNRS and Université Paris Cité, Paris, France. 11email:
<EMAIL_ADDRESS>22institutetext: Facultad de Ingeniería y Ciencias,
Universidad Adolfo Ibáñez, Santiago, Chile 22email<EMAIL_ADDRESS>33institutetext: Departamento de Ingeniería Matemática - Centro de
Modelamiento Matemático (UMI 2807 CNRS), Universidad de Chile, Santiago, Chile
33email<EMAIL_ADDRESS>44institutetext: Laboratoire d’informatique
fondamentale d’Orléans (LIFO), Université d’Orléans, Orléans, France 44email:
<EMAIL_ADDRESS>
# Energy-Efficient Distributed Algorithms for Synchronous Networks††thanks:
This work was performed during the visit of the first and last authors to
Universidad de Chile, and to Universidad Adolfo Ibañez, Chile.

Pierre Fraigniaud Additional support from ANR project DUCAT (ref.
ANR-20-CE48-0006).11 Pedro Montealegre Additional support from ANID via
PIA/Apoyo a Centros Cientificos y Tecnológicos de Excelencia AFB 170001,
Fondecyt 1220142 and Fondecyt 1230599.22 Ivan Rapaport0 33
Ioan Todinca 44

###### Abstract

We study the design of energy-efficient algorithms for the LOCAL and CONGEST
models. Specifically, as a measure of complexity, we consider the maximum,
taken over all the edges, or over all the nodes, of the number of rounds at
which an edge, or a node, is active in the algorithm. We first show that every
Turing-computable problem has a CONGEST algorithm with constant node-
activation complexity, and therefore constant edge-activation complexity as
well. That is, every node (resp., edge) is active in sending (resp.,
transmitting) messages for only $O(1)$ rounds during the whole execution of
the algorithm. In other words, every Turing-computable problem can be solved
by an algorithm consuming the least possible energy. In the LOCAL model, the
same holds obviously, but with the additional feature that the algorithm runs
in $O(\mbox{poly}(n))$ rounds in $n$-node networks. However, we show that
insisting on algorithms running in $O(\mbox{poly}(n))$ rounds in the CONGEST
model comes with a severe cost in terms of energy. Namely, there are problems
requiring $\Omega(\mbox{poly}(n))$ edge-activations (and thus
$\Omega(\mbox{poly}(n))$ node-activations as well) in the CONGEST model
whenever solved by algorithms bounded to run in $O(\mbox{poly}(n))$ rounds.
Finally, we demonstrate the existence of a sharp separation between the edge-
activation complexity and the node-activation complexity in the CONGEST model,
for algorithms bounded to run in $O(\mbox{poly}(n))$ rounds. Specifically,
under this constraint, there is a problem with $O(1)$ edge-activation
complexity but $\tilde{\Omega}(n^{1/4})$ node-activation complexity.

###### Keywords:

Synchronous distributed algorithms LOCAL and CONGEST models Energy efficiency.

##  1 Introduction

###  1.1 Objective

Designing computing environments consuming a limited amount of energy while
achieving computationally complex tasks is an objective of utmost importance,
especially in distributed systems involving a large number of computing
entities. In this paper, we aim at designing energy-efficient algorithms for
the standard LOCAL and CONGEST models of distributed computing in networks
[11]. Both models assume a network modeled as an $n$-node graph $G=(V,E)$,
where each node is provided with an identifier, i.e., an integer that is
unique in the network, which can be stored on $O(\log n)$ bits. All nodes are
assumed to run the same algorithm, and computation proceeds as a series of
synchronous rounds (all nodes start simultaneously at round 1). During a
round, every node sends a message to each of its neighbors, receives the
messages sent by its neighbors, and performs some individual computation. The
two models LOCAL and CONGEST differ only in the amount of information that can
be exchanged between nodes at each round.

The LOCAL model does not bound the size of the messages, whereas the CONGEST
model allows only messages of size $O(\log n)$ bits. Initially, every node
$v\in V$ knows solely its identifier $\mathsf{id}(v)$, an upper bound of the
number $n$ of nodes, which is assumed to be polynomial in $n$ and to be the
same for all nodes, plus possibly some input bit-string $x(v)$ depending on
the task to be solved by the nodes. In this paper, we denote by $N$ the
maximum between the largest identifier and the upper bound on $n$ given to all
nodes. Hence $N=O(\mbox{poly}(n))$, and is supposed to be known by all nodes.
After a certain number of rounds, every node outputs a bit-string $y(v)$,
where the correctness of the collection of outputs $y=\\{y(v):v\in V\\}$ is
defined with respect to the specification of the task to be solved, and may
depend on the collection of inputs $x=\\{x(v):v\in V\\}$ given to the nodes,
as well as on the graph $G$ (but not on the identifiers assigned to the nodes,
nor on the upper bound $N$).

#### Activation complexity.

We measure the energy consumption of an algorithm $A$ by counting how many
times each node and each edge is activated during the execution of the
algorithm. More specifically, a node $v$ (resp., an edge $e$) is said to be
_active_ at a given round $r$ if $v$ is sending a message to at least one of
its neighbors at round $r$ (resp., if a message traverses $e$ at round $r$).
The _node-activation_ and the _edge-activation_ of an algorithm $A$ running in
a graph $G=(V,E)$ are respectively defined as

$\mathsf{nact}(A):=\max_{v\in
V}\\#\mbox{activation}(v),\;\;\mbox{and}\;\;\mathsf{eact}(A):=\max_{e\in
E}\\#\mbox{activation}(e),$

where $\\#\mbox{activation}(v)$ (resp., $\\#\mbox{activation}(e)$) denotes the
number of rounds during which node $v$ (resp., edge $e$) is active along the
execution of the algorithm $A$. By definition, we have that, in any graph of
maximum degree $\Delta$,

$\mathsf{eact}(A)\leq 2\cdot\mathsf{nact}(A),~{}\textrm{ and
}~{}\mathsf{nact}(A)\leq\Delta\cdot\mathsf{eact}(A).$ (1)

#### Objective.

Our goal is to design _frugal_ algorithms, that is, algorithms with _constant_
node-activation, or to the least _constant_ edge-activation, independent of
the number $n$ of nodes and of the number $m$ of edges. Indeed, such
algorithms can be viewed as consuming the least possible energy for solving a
given task. Moreover, even if the energy requirement for solving the task
naturally grows with the number of components (nodes or edges) of the network,
it grows _linearly_ with this number whenever using frugal algorithms. We
refer to _node-frugality_ or _edge-frugality_ depending on whether we focus on
node-activation or edge-activation, respectively.

###  1.2 Our Results

We first show that every Turing-computable problem111A problem is Turing-
computable if there exists a Turing machine that, given any graph with
identifiers and inputs assigned to the nodes, computes the output of each node
in the graph. can thus be solved by a node-frugal algorithm in the LOCAL model
as well as in the CONGEST model. It follows from Eq. 1 that every Turing-
computable problem can be solved by an edge-frugal algorithm in both models.
In other words, every problem can be solved by an energy-efficient distributed
algorithm. One important question remains: what is the round complexity of
frugal algorithms?

In the LOCAL model, our node-frugal algorithms run in $O(\mbox{poly}(n))$
rounds. However, they may run in exponentially many rounds in the CONGEST
model. We show that this cannot be avoided. Indeed, even if many symmetry-
breaking problems such as computing a maximal-independent set (mis) and
computing a $(\Delta+1)$-coloring can be solved by a node-frugal algorithm
performing in $O(\mbox{poly}(n))$ rounds, we show that there exist problems
(e.g., deciding $C_{4}$-freeness or deciding the presence of symmetries in the
graph) that cannot be solved in $O(\mbox{poly}(n))$ rounds in the CONGEST
model by any edge-frugal algorithm.

Finally, we discuss the relation between node-activation complexity and edge-
activation complexity. We show that the bounds given by Eq. 1 are essentially
the best that can be achieved in general. Precisely, we identify a problem,
namely Depth First Pointer Chasing (dfpc), which has edge-activation
complexity $O(1)$ for all graphs with an algorithm running in
$O(\mbox{poly}(n))$ rounds in the CONGEST model, but satisfying that, for
every $\Delta=O\left(\big{(}\frac{n}{\log n}\big{)}^{1/4}\right)$, its node-
activation complexity in graphs with maximum degree $\Delta$ is
$\Omega(\Delta)$ whenever solved by an algorithm bounded to run in
$O(\mbox{poly}(n))$ rounds in the CONGEST model. In particular, Depth First
Pointer Chasing has constant edge-activation complexity but node-activation
complexity $\tilde{\Omega}(n^{1/4})$ in the CONGEST model (for
$O(\mbox{poly}(n))$-round algorithms).

Our main results are summarized in Table 1.

|  Awakeness | Node-Activation |  Edge-Activation
---|---|---|---
LOCAL |  $\bullet\;\forall\Pi,\Pi\in O(\log n)$ with |  $\bullet\;\forall\Pi,\Pi\in O(1)$ with |  $\bullet\;\forall\Pi,\Pi\in O(1)$ with
|  $\;\;O(\mbox{poly}(n))$ rounds [2] |  $\;\;O(\mbox{poly}(n))$ rounds |  $\;\;O(\mbox{poly}(n))$ rounds
|  $\bullet\;\mbox{\sc st}\in\Omega(\log n)$ [2] |  |
CONGEST | $\bullet\;\mbox{\sc mis}\in O(\mbox{polyloglog}(n))$ | $\bullet\;\forall\Pi,\Pi\in O(1)$ | $\bullet\;\forall\Pi,\Pi\in O(1)$
| with $O(\mbox{polylog}(n))$ |  $\bullet\;\mbox{poly}(n)$ rounds |  $\bullet\;\mbox{poly}(n)$ rounds
| rounds [6] (randomized) | $\;\;\Rightarrow\exists\Pi\in\Omega(\mbox{poly}(n))$ | $\;\;\Rightarrow\exists\Pi\in\Omega(\mbox{poly}(n))$
| $\bullet\;\mbox{\sc mst}\in O(\log n)$ |  $\bullet\;\mbox{poly}(n)$ rounds |  $\bullet\;\mbox{\sc dfpc}\in O(1)$ with
| with $O(\mbox{poly}(n))$ | $\;\;\Rightarrow\mbox{\sc dfpc}\in\tilde{\Omega}(n^{1/4})$ |  $\;\;O(\mbox{poly}(n))$ rounds
| rounds [1] |  | $\bullet\;\Pi\in\mbox{FO and}\;\Delta=O(1)$
|  |  | $\;\;\Rightarrow\Pi\in O(1)\;\mbox{with}$
|  |  |  $\;\;O(\mbox{poly}(n))$ rounds [8]
Table 1: Summary of our results where, for a problem $\Pi$, $\Pi\in O(f(n))$
means that the corresponding complexity of $\Pi$ is $O(f(n))$ (same shortcut
for $\Omega$).

#### Our Techniques.

Our upper bounds are mostly based on similar types of upper bounds techniques
used in the sleeping model [2, 4] (cf. Section 1.3), based on constructing
spanning trees along with gathered and broadcasted information. However, the
models considered in this paper do not suffer from the same limitations as the
sleeping model (cf. Section 2), and thus one can achieve activation complexity
$O(1)$ in scenarios where the sleeping model limits the awake complexity to
$\Omega(\log n)$.

Our lower bounds for CONGEST are based on reductions from 2-party
communication complexity. However, as opposed to the standard CONGEST model in
which the simulation of a distributed algorithm by two players is
straightforward (each player performs the rounds sequentially, one by one, and
exchanges the messages sent across the cut between the two subsets of nodes
handled by the players at each round), the simulation of distributed
algorithms in which only subsets of nodes are active at various rounds
requires more care. This is especially the case when the simulation must not
only control the amount of information exchanged between these players, but
also the number of communication steps performed by the two players. Indeed,
there are 2-party communication complexity problems that are hard for $k$
steps, but trivial for $k+1$ steps [10], and some of our lower bounds rely on
this fact.

###  1.3 Related Work

The study of frugal algorithms has been initiated in [8], which focuses on the
edge-frugality in the CONGEST model. It is shown that for _bounded-degree
graphs_ , any problem expressible in first-order logic (e.g.,
$C_{4}$-freeness) can be solved by an edge-frugal algorithm running in
$O(\mbox{poly}(n))$ rounds in the CONGEST model. This also holds for planar
graphs with no bounds on the maximum degree, whenever the nodes are provided
with their local combinatorial embedding. Our results show that these
statements cannot be extended to arbitrary graphs as we prove that any
algorithm solving $C_{4}$-freeness in $O(\mbox{poly}(n))$ rounds in the
CONGEST model has edge-activation $\tilde{\Omega}(\sqrt{n})$.

More generally, the study of energy-efficient algorithms in the context of
distributed computing in networks has been previously considered in the
framework of the _sleeping_ model, introduced in [4]. This model assumes that
nodes can be in two states: _awake_ and _asleep_. A node in the awake state
performs as in the LOCAL and CONGEST models, but may also decide to fall
asleep, for a prescribed amount of rounds, controlled by each node, and
depending on the algorithm executed at the nodes. A sleeping node is totally
inactive in the sense that it does not send messages, it cannot receive
messages (i.e., if a message is sent to a sleeping node by an awake neighbor,
then the message is lost), and it is computationally idle (apart from counting
rounds). The main measure of interest in the sleeping model is the _awake
complexity_ , defined as the maximum, taken over all nodes, of the number of
rounds at which each node is awake during the execution of the algorithm.

In the LOCAL model, it is known [2] that all problems have awake complexity
$O(\log n)$, using algorithms running in $O(\mbox{poly}(n))$ rounds. This
bound is tight in the sense that there are problems (e.g., spanning tree
construction) with awake complexity $\Omega(\log n)$ [2, 3].

In the CONGEST model, It was first shown [4] that mis has constant _average_
awake complexity, thanks to a _randomized_ algorithm running in
$O(\mbox{polylog}(n))$ rounds. The round complexity was improved in [7] with a
_randomized_ algorithm running in $O(\log n)$ rounds. The (worst-case) awake
complexity of mis was proved to be $O(\log\log n)$ using a _randomized_ Monte-
Carlo algorithm running in $O(\mbox{poly}(n))$ rounds [6]. This (randomized)
round complexity can even be reduced to $O(\log^{3}n\cdot\log\log
n\cdot\log^{\star}n)$, at the cost of slightly increasing the awake complexity
to $O(\log\log n\cdot\log^{\star}n)$. mst has also been considered, and it was
proved [1] that its (worst-case) awake complexity is $O(\log n)$ thanks to a
(deterministic) algorithm running in $O(\mbox{poly}(n))$ rounds. The upper
bound on the awake complexity of mst is tight, thank to the lower bound for
spanning tree (st) in [2].

##  2 Preliminaries

In this section, we illustrate the difference between the standard LOCAL and
CONGEST models, their sleeping variants, and our node- and edge-activation
variants. Fig. 1(a) displays the automaton corresponding to the behavior of a
node in the standard models. A node is either _active_ (A) or _terminated_
(T). At each clock tick (i.e., round) a node is subject to message events
corresponding to sending and receiving messages to/from neighbors. A node
remains active until it terminates.

APTclockmsgmsgmsgclockclockclockAPTclockmsgclockclockclockATclockmsg(a)(b)(c)

Figure 1: (a) Classical model (b) Sleeping model, (c) Activation model.

Fig. 1(b) displays the automaton corresponding to the behavior of a node in
the sleeping variant. In this variant, a node can also be in a _passive_ (P)
state. In this state, the clock event can either leave the node passive, or
awake the node, which then moves back to the active state.

Finally, Fig. 1(c) displays the automaton corresponding to the behavior of a
node in our activation variants. It differs from the sleeping variant in that
a passive node is also subject to message events, which can leave the node
passive, but may also move the node to the active state. In particular, a node
does not need to be active for receiving messages, and incoming messages may
not trigger an immediate response from the node (e.g., forwarding
information). Instead, a node can remain passive while collecting information
from each of its neighbors, and eventually react by becoming active.

#### Example 1: Broadcast.

Assume that one node of the $n$-node cycle $C_{n}$ has a token to be broadcast
to all the nodes. Initially, all nodes are active. However, all nodes but the
one with the token become immediately passive when the clock ticks for
entering the second round. The node with the token sends the token to one of
its neighbors, and becomes passive at the next clock tick. Upon reception of
the token, a passive node becomes active, forwards the token, and terminates.
When the source node receives the token back, it becomes active, and
terminates. The node-activation complexity of broadcast is therefore $O(1)$,
whereas it is known that broadcasting has awake complexity $\Omega(\log n)$ in
the sleeping model [2].

#### Example 2: At-least-one-leader.

Assume that each node of the cycle $C_{n}$ has an input-bit specifying whether
the node is leader or not, and the nodes must collectively check that there is
at least one leader. Every leader broadcasts a token, outputs accept, and
terminates. Non-leader nodes become passive immediately after the beginning of
the algorithm, and start waiting for $N$ rounds (recall that $N$ is an upper
bound on the number $n$ of nodes). Whenever the “sleep” of a (passive) non-
leader is interrupted by the reception of a token, it becomes active, forwards
the token, outputs accept, and terminates. After $N$ rounds, a passive node
that has not been “awaken” by a token becomes active, outputs reject, and
terminates. This guarantees that there is at least one leader if and only if
all nodes accept. The node-activation complexity of this algorithm is $O(1)$,
while the awake complexity of at-least-one-leader is $\Omega(\log n)$ in the
sleeping model, by reduction to broadcast.

The following observation holds for LOCAL and CONGEST, by noticing that every
algorithm for the sleeping model can be implemented with no overheads in terms
of node-activation.

###### Observation 1

In $n$-node graphs, every algorithm with awake complexity $a(n)$ and round
complexity $r(n)$ has node-activation complexity at most $a(n)$ and round
complexity at most $r(n)$.

It follows from Observation 1 that all upper bound results for the awake
complexity directly transfer to the node-activation complexity. However, as we
shall show in this paper, in contrast to the sleeping model in which some
problems (e.g., spanning tree) have awake complexity $\Omega(\log n)$, even in
the LOCAL model, all problems admit a frugal algorithm in the CONGEST model,
i.e., an algorithm with node-activation $O(1)$.

###### Definition 1

A LOCAL or CONGEST algorithm is _node-frugal_ (resp., _edge-frugal_) if the
activation of every node (resp., edge) is upper-bounded by a constant
independent of the graph, and of the identifiers and inputs given to the
nodes.

##  3 Universality of Frugal Algorithms

In this section we show that every Turing-computable problem can be solved by
frugal algorithms, both in the LOCAL and CONGEST models. Thanks to Eq. 1, it
is sufficient to prove that this holds for node-frugality.

###### Lemma 1

There exists a CONGEST algorithm electing a leader, and constructing a BFS
tree rooted at the leader, with node-activation complexity $O(1)$, and
performing in $O(N^{2})=O(\mbox{\rm poly}(n))$ rounds.

###### Proof

The algorithm elects as leader the node with smallest identifier, and
initiates a breadth-first search from that node. At every node $v$, the
protocol performs as follows.

  * •

If $v$ has received no messages until round $\mathsf{id}(v)\cdot N$, then $v$
elects itself as leader, and starts a BFS by sending message
$(\mathsf{id}(v),0)$ to all its neighbors. Locally, $v$ sets its parent in the
BFS tree to $\bot$, and the distance to the root to $0$.

  * •

Otherwise, let $r$ be the first round at which vertex $v$ receives a message.
Such a message is of type $(\mathsf{id}(u),d)$ where $u$ is the neighbor of
$v$ which sent the message to $v$, and $d$ is the distance from $u$ to the
leader in the graph. Node $v$ sets its parent in the BFS tree to
$\mathsf{id}(u)$, its distance to the root to $d+1$, and, at round $r+1$, it
sends the message $(\mathsf{id}(v),d+1)$ to all its neighbors. (If $v$
receives several messages at round $r$, from different neighbors, then $v$
selects the messages coming from the neighobors with smallest identifier).

The node $v$ with smallest identifier is indeed the node initiating the BFS,
as the whole BFS is constructed between rounds ${\mathsf{id}(v)\cdot N}$ and
${\mathsf{id}(v)\cdot N+N-1}$, and $N\geq n$. The algorithm terminates at
round at most $O(N^{2})$. ∎

An instance of a problem is a triple $(G,\mathsf{id},x)$ where $G=(V,E)$ is an
$n$-node graph, $\mathsf{id}:V\to[1,N]$ with $N=O(\mbox{poly}(n))$, and
$x:V\to[1,\nu]$ is the input assignment to the nodes. Note that the input
range $\nu$ may depend on $n$, and even be exponential in $n$, even for
classical problems, e.g., whenever weights assigned to the edges are part of
the input. A solution to a graph problem is an output assignment
$y:V\to[1,\mu]$, and the correctness of $y$ depends on $G$ and $x$ only, with
respect to the specification of the problem. We assume that $\mu$ and $\nu$
are initially known to the nodes, as it is the case for, e.g., mst, in which
the weights of the edges can be encoded on $O(\log n)$ bits.

###### Theorem 3.1

Every Turing-computable problem has a LOCAL algorithm with $O(1)$ node-
activation complexity, and running in $O(N^{2})=O(\mbox{\rm poly}(n))$ rounds.

###### Proof

Once the BFS tree $T$ of Lemma 1 is constructed, the root can (1) gather the
whole instance $(G,\mathsf{id},x)$, (2) compute a solution $y$, and (3)
broadcast $y$ to all nodes. Specifically, every leaf $v$ of $T$ sends the set

$E(v)=\big{\\{}\\{(\mathsf{id}(v),x(v)),(\mathsf{id}(w),x(w))\\}:w\in
N(v)\big{\\}}$

to its parent in $T$. An internal node $v$ waits for receiving a set of edges
$S(u)$ from each of its children $u$ in $T$, and then forwards the set

$S(v)=E(v)\cup(\cup_{u\in\mbox{\tiny child}(v)}S(u))$

to its parent. This set can be encoded in $O(N^{2})$ bits by the adjacency
matrix of the subgraph induced by the edges in $S(v)$. Each node of $T$ is
activated once during this phase, and thus the node-activation complexity of
gathering is 1. Broadcasting the solution $y$ from the leader to all the nodes
is achieved along the edges of $T$, again with node-activation 1. ∎

The algorithm used in the proof of Theorem 3.1 cannot be implemented in
CONGEST due to the size of the messages, which may require each node to be
activated more than a constant number of times. To keep the node-activation
constant, we increased the round complexity of the algorithm.

###### Lemma 2

Every node-frugal algorithm $\mathcal{A}$ performing in $R$ rounds in the
LOCAL model with messages of size at most $M$ bits222Without loss of
generality, in $\mathcal{A}$ each node sends the same message to all its
neighbors at each round when it is active. Otherwise, the different messages
can be merged into one, by adding the identifiers of the neighbors. can be
implemented by a node-frugal algorithm $\mathcal{B}$ performing in $R\,2^{M}$
rounds in the CONGEST model.

###### Proof

Let $v$ be a node sending a message $m$ through an incident edge $e$ at round
$r$ of $\mathcal{A}$. Then, in $\mathcal{B}$, $v$ sends one “beep” through
edge $e$ at round $r\,2^{M}+t$ where $t$ is lexicographic rank of $m$ among
the at most $2^{M}$ messages generated by $\mathcal{A}$. ∎

###### Theorem 3.2

Every Turing-computable problem has a CONGEST algorithm with $O(1)$ node-
activation complexity, and running in $2^{\mbox{\rm\scriptsize
poly}(n)(1+\log(\nu\mu))}$ rounds for inputs in the range $[1,\nu]$ and
outputs in the range $[1,\mu]$.

###### Proof

The algorithm used in the proof of Theorem 3.1 used messages of size at most
$N^{2}+N\log\nu$ bits during the gathering phase, and of size at most
$N\log\mu$ bits during the broadcast phase. The result follows from Lemma 2.∎

Of course, there are many problems that can be solved in the CONGEST model by
a frugal algorithm much faster than the bound from Theorem 3.2. This is
typically the case of all problems that can be solved by a sequential greedy
algorithm visiting the nodes in arbitrary order, and producing a solution at
the currently visited node based only on the partial solution in the
neighborhood of the node. Examples of such problems are mis,
$\Delta+1$-coloring, etc. We call such problem _sequential-greedy_.

###### Theorem 3.3

Every sequential-greedy problem whose solution at every node can be encoded on
$O(\log n)$ bits has a node-frugal CONGEST algorithm running in
$O(N)=O({\mbox{\rm poly}(n)})$ rounds.

###### Proof

Every node $v\in V$ generates its output at round $\mathsf{id}(v)$ according
to its current knowledge about its neighborhood, and sends this output to all
its neighbors. ∎

##  4 Limits of CONGEST Algorithms with Polynomially Many Rounds

Given a graph $G=(V,E)$ such that $V$ is partitioned in two sets
$V_{A},V_{B}$, the set of edges with one endpoint in $V_{A}$ and the other in
$V_{B}$ is called the _cut_. We denote by $e(V_{A},V_{B})$ the number of edges
in the cut, and by $n(V_{A},V_{B})$ the number of nodes incident to an edge of
the cut. Consider the situation where there are two players, namely Alice and
Bob. We say that a player controls a node $v$ if it knows all its incident
edges and its input. For a CONGEST algorithm $\mathcal{A}$, we denote
$\mathcal{A}(\mathcal{I})$ the output of $\mathcal{A}$ on input
$\mathcal{I}=(G,\mathsf{id},x)$. We denote $R_{\mathcal{A}}(n)$ the round
complexity of $\mathcal{A}$ on inputs of size $n$.

######  Lemma 3 (Simulation lemma)

Let $\mathcal{A}$ be an algorithm in the CONGEST model, let
$\mathcal{I}=(G,\mathsf{id},x)$ be an input for $\mathcal{A}$, and let
$V_{A},V_{B}$ be a partition of $V(G)$. Suppose that Alice controls all the
nodes in $V_{A}$, and Bob controls all the nodes in $V_{B}$. Then, there
exists a communication protocol $\mathcal{P}$ between Alice and Bob with at
most
$2\cdot\min(n(V_{A},V_{B})\cdot\mathsf{nact}(\mathcal{A}),e(V_{A},V_{B})\cdot\mathsf{eact}(\mathcal{A}))$
rounds and using total communication
$\mathcal{O}(\min(n(V_{A},V_{B})\cdot\mathsf{nact}(\mathcal{A}),e(V_{A},V_{B})\cdot\mathsf{eact}(\mathcal{A}))\cdot(\log
n+\log R_{\mathcal{A}}(n))$, such that each player computes the value of
$\mathcal{A}(\mathcal{I})$ at all nodes he or she controls.

###### Proof

In protocol $\mathcal{P}$, Alice and Bob simulate the rounds of algorithm
$\mathcal{A}$ in all the nodes they control. The simulation run in phases.
Each phase is used to simulate up to a certain number of rounds $t$ of
algorithm $\mathcal{A}$, and takes two rounds of protocol $\mathcal{P}$ (one
round for Alice, and one round for Bob). By simulating $\mathcal{A}$ up to $t$
rounds, we mean that Alice and Bob know all the states of all the nodes they
control, on every round up to round $t$.

In the first phase, players start simulating $\mathcal{A}$ from the initial
state. Let us suppose that both Alice and Bob have already executed $p\geq 0$
phases, meaning that they had correctly simulated $\mathcal{A}$ up to round
$t=t(p)\geq 0$. Let us explain phase $p+1$ (see also Figure 2).

rounds $V_{A}$$V_{B}$$r_{a}$$r_{b}$$V_{A}$$V_{B}$$V_{A}$$V_{B}$ Oblivious
simulation of Alice $t$ Oblivious simulation of Bob Transcript of algorithm
$\displaystyle\mathcal{A}$ Figure 2: Illustration of one phase of the
simulation protocol. Assuming that the players agree on the simulation of
algorithm $\mathcal{A}$ up to round $t$, each player runs an oblivious
simulation at the nodes they control. In the example of the figure, the next
message corresponds to a node controlled by Bob, who sends a message to a node
in $V_{A}$ at round $r_{b}$. The oblivious simulation of Alice is not aware of
this message, and incorrectly considers that a message is sent from $V_{A}$ to
$V_{B}$ at round $r_{a}>r_{b}$. Using the communication rounds in this phase,
the players agree that the message of Bob was correct. Thus the simulation is
correct up to round $r_{b}$, for both players.

Starting from round $t$, Alice runs an _oblivious simulation_ of algorithm
$\mathcal{A}$ over all nodes that she controls. By oblivious, we mean that
Alice assumes that no node of $V_{B}$ communicates a message to a node in
$V_{A}$ in any round at least $t$. The oblivious simulation of Alice stops in
one of the following two possible scenarios:

  * (1)

All nodes that she controls either terminate or enter into a passive state
that quits only on an incoming message from $V_{B}$.

  * (2)

The simulation reaches a round $r_{a}$ where a message is sent from a node in
$V_{A}$ to a node in $V_{B}$.

At the same time, Bob runs and oblivious simulation of $\mathcal{A}$ starting
from round $t$ (i.e. assuming that no node of $V_{A}$ sends a message to a
node in $V_{B}$ in any round at least $t$). The oblivious simulation of Bob
stops in one of the same two scenarios analogous to the ones above. In this
case, we call $r_{b}$ the round reached by Bob in his version of scenario (2).

At the beginning of a phase, it is the turn of Alice to speak. Once the
oblivious simulation of Alice stops, she is ready to send a message to Bob. If
the simulation stops in the scenario (1), Alice sends a message "_scenario 1_
" to Bob. Otherwise, Alice sends $r_{a}$ together with all the messages sent
from nodes in $V_{A}$ to nodes in $V_{B}$ at round $r_{a}$, to Bob. When Bob
receives the message from Alice, one of the following situations holds:

Case 1: the oblivious simulation of both Alice and Bob stopped in the first
scenario. In this case, since $\mathcal{A}$ is correct, there are no
deadlocks. Therefore, all vertices of $G$ reached a terminal state, meaning
that the oblivious simulation of both players was in fact a real simulation of
$\mathcal{A}$, and the obtained states are the output states. Therefore, Bob
sends a message to Alice indicating that the simulation is finished, and
indeed Alice and Bob have correctly computed the output of $\mathcal{A}$ for
all the nodes they control.

Case 2: the oblivious simulation of Alice stopped in scenario (1), and the one
of Bob stopped in the scenario (2). In this case, Bob infers that his
oblivious simulation was correct. He sends $r_{b}$ and all the messages
communicated in round $r_{b}$ through the cut to Alice. When Alice receives
the message of Bob, she updates the state of the nodes she controls up to
round $r_{b}$. It follows that both players have correctly simulated algorithm
$\mathcal{A}$ up to round $r_{b}>t$.

Case 3: the oblivious simulation of Alice stopped in scenario (2), and the one
of Bob stopped in scenario (1). In this case, Bob infres that the simulation
of Alice was correct up to round $r_{a}$. He sends a message to Alice
indicating that she has correctly simulated $\mathcal{A}$ up to round $r_{a}$,
and he updates the states of all the nodes he controls up to round $r_{a}$. It
follows that both players have correctly simulated $\mathcal{A}$ up to round
$r_{a}>t$.

Case 4: the oblivious simulation of both players stopped in scenario (2), and
$r_{a}>r_{b}$. Bob infers that his oblivious simulation was correct up to
$r_{b}$, and that the one of Alice was not correct after round $r_{b}$. Then,
the players act in the same way as described in Case 2. Thus, both players
have correctly simulated $\mathcal{A}$ up to round $r_{b}$.

Case 5: the oblivious simulation of both players stopped in scenario (2), and
$r_{b}>r_{a}$. Bob infers that his oblivious simulation was incorrect after
round $r_{a}$, and that the one of Alice was correct up to round $r_{a}$.
Then, the players act in the same way as described in Case 3. Thus, both
players have correctly simulated $\mathcal{A}$ up to round $r_{a}$.

Case 6: the oblivious simulation of both players stopped in scenario (2), and
$r_{b}=r_{a}$. Bob assumes that both oblivious simulations were correct. He
sends $r_{b}$ together with all the messages communicated from his nodes at
round $r_{b}$ through the cut. Then, he updates the states of all the nodes he
controls up to round $r_{b}$. When Alice receives the message from Bob, she
updates the states of the nodes she controls up to round $r_{b}$. It follows
that both players have correctly simulated $\mathcal{A}$ up to round
$r_{b}>t$.

Observe that, except when the algorithm terminates, on each phase of the
protocol, at least one node controlled by Alice or Bob is activated. Since the
number of rounds of $\mathcal{P}$ is twice the number of phases, we deduce
that the total number of rounds is at most

$2\cdot\min(n(V_{A},V_{B})\cdot\mathsf{nact}(\mathcal{A}),e(V_{A},V_{B})\cdot\mathsf{eact}(\mathcal{A})).$

Moreover, on each round of $\mathcal{P}$, the players communicate
$O((\log(R_{\mathcal{A}}(n))+\log n)\cdot e(V_{A},V_{B}))$ bits. As a
consequence, the total communication cost of $\mathcal{P}$ is

$O((\log(R_{\mathcal{A}}(n))+\log n)\cdot
e(V_{A},V_{B}))\cdot\min(n(V_{A},V_{B})\cdot\mathsf{nact}(\mathcal{A}),e(V_{A},V_{B})\cdot\mathsf{eact}(\mathcal{A}))),$

which completes the proof. ∎

We use the simulation lemma to show that there are problems that cannot be
solved by a frugal algorithm in a polynomial number of rounds. In problem
C4-freeness, all nodes of the input graph $G$ must accept if $G$ has no cycle
of 4 vertices, and at least one node must reject if such a cycle exists.
Observe that this problem is expressible in first-order logic, in particular
it has en edge-frugal algorithm with a polynomial number of rounds in graphs
of bounded degree [8]. We show that, in graphs of unbounded degree, this does
not hold anymore. We shall also consider problem Symmetry, where the input is
a graph $G$ with $2n$ nodes indexed from $1$ to $2n$, and with a unique edge
$\\{1,n+1\\}$ between $G_{A}=G[\\{1,\dots,n\\}]$ and
$G_{B}=G[\\{n+1,\dots,2n\\}]$. Our lower bounds holds even if every node is
identified by its index. All nodes must output _accept_ if the function
$f:\\{1,\dots,n\\}\to\\{n+1,\dots,2n\\}$ defined by $f(x)=x+n$ is an
isomorphism from $G_{A}$ to $G_{B}$, otherwise at least one node must output
_reject_.

The proof of the following theorem is based on classic reductions from
communication complexity problems Equality and Set Disjointness (see, e.g.,
[9]), combined with Lemma 3.

###### Theorem 4.1

Any CONGEST algorithm solving Symmetry (resp., C4-freeness) in polynomially
many rounds has node-activation and edge-activation at least
$\Omega\left(\frac{n^{2}}{\log n}\right)$ (resp.,
$\Omega\left(\frac{\sqrt{n}}{\log n}\right)$).

###### Proof

In problem Equality, two players Alice and Bob have a boolean vector of size
$k$, $x_{A}$ for Alice and $x_{B}$ for Bob. Their goal is to answer _true_ if
$x_{A}=x_{B}$, and _false_ otherwise. The communication complexity of this
problem is known to be $\Theta(k)$ [9]. Let $k=n^{2}$. We can interpret
$x_{A}$ and $x_{B}$ as the adjacency matrix of two graphs $G_{A}$ and $G_{B}$
in an instance of Symmetry. It is a mere technicality to "shift" $G_{B}$ as if
its vertices were indexed from $1$ to $n$, such that Symmetry is true for $G$
iff $x_{A}=x_{B}$. Moreover, Alice can construct $G_{A}$ from its input
$x_{A}$, and Bob can construct $G_{B}$ from $x_{B}$. Both can simulate the
unique edge joining the two graphs in $G$. Therefore, by Lemma 3 applied to
$G$, if Alice controls the vertices of $G_{A}$, and Bob controls the vertices
of $G_{B}$, then any CONGEST algorithm $\mathcal{A}$ solving Symmetry in
polynomially many rounds yields a two-party protocol for Equality on $n^{2}$
bits. Since graphs $G_{A}$ and $G_{B}$ are linked by a unique edge, the total
communication of the protocol is $O(\mathsf{eact}(\mathcal{A})\cdot\log n)$
and $O(\mathsf{nact}(\mathcal{A})\cdot\log n)$. The result follows.

In Set Disjointness, each of the two players Alice and Bob has a Boolean
vector of size $k$, $x_{A}$ for Alice, and $x_{B}$ for Bob. Their goal is to
answer _true_ if there is no index $i\in[k]$ such that both $x_{A}[i]$ and
$x_{B}[i]$ are true (in which case, $x_{A}$ and $x_{B}$ are disjoint), and
_false_ otherwise. The communication complexity of this problem is known to be
$\Theta(k)$ [9]. We use the technique in [5] to construct an instance $G$ for
$C_{4}$ freeness, with a small cut, from two Boolean vectors $x_{A},x_{B}$ of
size $k=\Theta(n^{3/2})$. Consider a $C_{4}$-free $n$-vertex graph $H$ with a
maximum number of edges. Such a graph has $k=\Theta(n^{3/2})$ edges, as
recalled in [5]. We can consider the edges $E(H)$ as indexed from $1$ to $k$,
and $V(H)$ as $[n]$. Let now $x_{A}$ and $x_{B}$ be two Boolean vectors of
size $k$. These vectors can be interpreted as edge subsets $E(x_{A})$ and
$E(x_{B})$ of $H$, in the sense that the edge indexed $i$ in $E(H)$ appears in
$E(x_{A})$ (resp. $E(x_{B})$) iff $x_{A}[i]$ (resp. $x_{B}[i]$) is true. Graph
$G$ is constructed to have $2n$ vertices, formed by two sub-graphs
$G_{A}=G[\\{1,\dots,n\\}]$ and $G_{B}=G[\\{n+1,\dots,2n\\}]$. The edges of
$E(G_{A})$ are exactly the ones of $E(x_{A})$. Similarly, the edges of
$E(G_{B})$ correspond to $E(x_{A})$, modulo the fact that the vertex indexes
are shifted by $n$, i.e., for each edge $\\{u,v\\}\in E(x_{B})$, we add edge
$\\{u+n,v+n\\}$ to $G_{B}$. Moreover we add a perfect matching to $G$, between
$V(G_{A})$ and $V(G_{B})$, by adding all edges $\\{i,i+n\\}$, for all
$i\in[n]$. Note that $G$ is $C_{4}$-free if and only if vectors $x_{A}$ and
$x_{B}$ are disjoint. Indeed, since $G_{A},G_{B}$ are isomorphic to sub-graphs
of $H$, they are $C_{4}$-free. Thus any $C_{4}$ of $G$ must contain two
vertices in $G_{A}$ and two in $G_{B}$, in which case the corresponding edges
in $G_{A}$ and $G_{B}$ designate the same bit of $x_{A}$ and $x_{B}$
respectively. Moreover Alice and Bob can construct $G_{A}$ and $G_{B}$, as
well as the edges in the matching, from their respective inputs $x_{A}$ and
$x_{B}$. Therefore, thanks to Lemma 3, a CONGEST algorithm $\mathcal{A}$ for
C4-freeness running in a polynomial number of rounds can be used to design a
protocol $\mathcal{P}$ solving Set Disjointness on $k=\Theta(n^{3/2})$ bits,
where Alice controls $V(G_{A})$ and Bob controls $V(G_{B})$. The communication
complexity of the protocol is $O(\mathsf{eact}(\mathcal{A})\cdot n\cdot\log
n)$, and $O(\mathsf{nact}(\mathcal{A})\cdot n\cdot\log n)$, since the cut
between $G_{A}$ and $G_{B}$ is a matching. The result follows. ∎

##  5 Node versus Edge Activation

In this section we exhibit a problem that admits an edge-frugal CONGEST
algorithm running in a polynomial number of rounds, for which any algorithm
running in a polynomial number of rounds has large node-activation complexity.

We proceed by reduction from a two-party communication complexity problem.
However, unlike the previous section, we are now also interested in the number
of rounds of the two-party protocols. We consider protocols in which the two
players Alice and Bob do not communicate simultaneously. For such a protocol
$\mathcal{P}$, a _round_ is defined as a maximal contiguous sequence of
messages emitted by a same player. We denote by $R(\mathcal{P})$ the number of
rounds of $\mathcal{P}$.

Let $G$ be a graph, and $S$ be a subset of nodes of $G$. We denote by
$\partial S$ the number of vertices in $S$ with a neighbor in $V\setminus S$.

######  Lemma 4 (Round-Efficient Simulation lemma)

Let $\mathcal{A}$ be an algorithm in the CONGEST model, let
$\mathcal{I}=(G,\mathsf{id},x)$ be an input for $\mathcal{A}$, and let
$V_{A},V_{B}$ be a partition of $V(G)$. Let us assume that Alice controls all
the nodes in $V_{A}$, and Bob controls all the nodes in $V_{B}$, and both
players know the value of $\mathsf{nact}(\mathcal{A})$. Then, there exists a
communication protocol $\mathcal{P}$ between Alice and Bob such that, in at
most $\min(\partial V_{A},\partial V_{B})\cdot\mathsf{nact}(\mathcal{A})$
rounds, and using total communication
$O\Big{(}\big{(}(\partial(V_{A})+\partial(V_{B}))\cdot\mathsf{nact}(\mathcal{A})\big{)}^{2}\cdot(\log
n+\log R_{\mathcal{A}}(n))\Big{)}$ bits, each player computes the value of
$\mathcal{A}(\mathcal{I})$ at all the nodes he or she controls.

###### Proof

In protocol $\mathcal{P}$, Alice and Bob simulate the rounds of algorithm
$\mathcal{A}$ at all the nodes each player controls. Without loss of
generality, we assume that algorithm $\mathcal{A}$ satisfies that the nodes
send messages at different rounds, by merely multiplying by $N$ the number of
rounds.

Initially, Alice runs an oblivious simulation of $\mathcal{A}$ that stops in
one of the following three cases:

  1. 1.

Every node in $V_{A}$ has terminated;

  2. 2.

Every node in $V_{A}$ entered into the passive state that it may leave only
after having received a message from a node in $V_{B}$ (this corresponds to
what we called the “first scenario” in the proof of Lemma 3);

  3. 3.

The number of rounds $R_{\mathcal{A}}(n)$ is reached.

Then, Alice sends to Bob the integer $t_{1}=0$, and the set $M^{1}_{A}$ of all
messages sent from nodes in $V_{A}$ to nodes in $V_{B}$ in the communication
rounds that she simulated, together with their corresponding timestamps. If
the number of messages communicated by Alice exceeds
$\mathsf{nact}(\mathcal{A})\cdot\partial A$, we trim the list up to this
threshold.

Let us suppose that the protocol $\mathcal{P}$ has run for $p$ rounds, and let
us assume that it is the turn of Bob to speak at round $p+1$ — the case where
Alice speaks at round $p+1$ can be treated in the same way. Moreover, we
assume that $\mathcal{P}$ satisfies the following two conditions:

  1. 1.

At round $p$, Alice sents an integer $t_{p}\geq 0$, and a list of timestamped
messages $M^{p}_{A}$ corresponding to messages sent from nodes in $V_{A}$ to
nodes in $V_{B}$ in an oblivious simulation of $\mathcal{A}$ starting from a
round $t_{p}$.

  2. 2.

Bob had correctly simulated $\mathcal{A}$ at all the nodes he controls, up to
round $t_{p}$.

rounds $V_{A}$$V_{B}$$V_{A}$$V_{B}$$V_{A}$$V_{B}$ Transcript of the algorithm
$\displaystyle\mathcal{A}$ Simulation of Alice $t_{p}$ Simulation of Bob
$t_{p+1}$ Figure 3: Illustration of the round-efficient simulation protocol
for algorithm $\mathcal{A}$. After round $p$, Alice has correctly simulated
the algorithm up to round $t_{p}$. It is the turn of Bob to speak in round
$p+1$. In round $p$, Alice sent to Bob the set of messages $M^{p}_{A}$,
obtained from an oblivious simulation of $\mathcal{A}$ starting from $t_{p}$.
Only the first three messages are correct, since at round $t_{p+1}$ Bob
communicates a message to Alice. Then, Bob runs an oblivious simulation of
$\mathcal{A}$ starting from $t_{p+1}$, and communicates all the messages sent
from nodes $V_{B}$ to nodes in $V_{A}$. In this case the two first messages
are correct.

We now describe round $p+1$ (see also Figure 3). Bob initiates a simulation of
$\mathcal{A}$ at all the nodes he controls. However, this simulation is _not_
oblivious. Specifically, Bob simulates $\mathcal{A}$ from round $t_{p}$ taking
into account all the messages sent from nodes in $V_{A}$ to nodes in $V_{B}$,
as listed in the messages $M^{p}_{A}$. The simulation stops when Bob reaches a
round $t_{p+1}>t_{p}$ at which a node in $V_{B}$ sends a message to a node in
$V_{A}$. Observe that, up to round $t_{p+1}$, the oblivious simulation of
Alice was correct. At this point, Bob initiates an oblivious simulation of
$\mathcal{A}$ at all the nodes he controls, starting from $t_{p+1}$. Finally,
Bob sends to Alice $t_{p+1}$, and the list $M^{p+1}_{B}$ of all timestamped
messages sent from nodes in $V_{B}$ to nodes in $V_{A}$ resulting from the
oblivious simulation of the nodes he controls during rounds at least
$t_{p+1}$. Using this information, Alice infers that her simulation was
correct up to round $t_{p+1}$, and she starts the next round for protocol
$\mathcal{P}$.

The simulation carries on until one of the two players runs an oblivious
simulation in which all the nodes he or she controls terminate, and no
messages were sent through the cut in at any intermediate round. In this case,
this player sends a message "_finish_ " to the other player, and both infer
that their current simulations are correct. As a consequence, each player has
correctly computed the output of $\mathcal{A}$ at all the nodes he or she
controls.

At every communication round during which Alice speaks, at least one vertex of
$V_{A}$ which has a neighbor in $V_{B}$ is activated. Therefore, the number of
rounds of Alice is at most $\partial V_{A}\cdot\mathsf{nact}(\mathcal{A})$. By
the same argument, we have that the number of rounds of Bob is at most
$\partial V_{B}\cdot\mathsf{nact}(\mathcal{A})$. It follows that

$R(\mathcal{P})=\min(\partial V_{A},\partial
V_{B})\cdot\mathsf{nact}(\mathcal{A}).$

At each communication round, Alice sends at most
$\partial(V_{A})\cdot\mathsf{nact}(\mathcal{A})$ timestamped messages, which
can be encoded using
$O\big{(}\partial(V_{A})\cdot\mathsf{nact}(\mathcal{A})\cdot(\log n+\log
R_{\mathcal{A}}(n))\big{)}$ bits. Similarly, Bob sends
$O\big{(}\partial(V_{B})\cdot\mathsf{nact}(\mathcal{A})\cdot(\log n+\log
R_{\mathcal{A}}(n))\big{)}$ bits. It follows that

$C(\mathcal{P})=O\Big{(}\big{(}(\partial(V_{A})+\partial(V_{B}))\cdot\mathsf{nact}(\mathcal{A})\big{)}^{2}\cdot(\log
n+\log R_{\mathcal{A}}(n))\Big{)},$

which completes the proof. ∎

In order to separate the node-activation complexity from the edge-activation
complexity, we consider a problem called Depth First Pointer Chasing, and we
show that this problem can be solved by an edge-frugal CONGEST algorithm
running in $O(\mbox{poly}(n))$ rounds, whereas the node-activation complexity
of any algorithm running in $O(\mbox{poly}(n))$ rounds for this problem is
$\Omega(\Delta)$, for any $\Delta\in O(\big{(}\frac{n}{\log n}\big{)}^{1/4})$.
The lower bound is proved thanks to the Round-Efficient Simulation Lemma
(Lemma 3), by reduction from the two-party communication complexity problem
Pointer Chasing, for which too few rounds imply large communication complexity
[10].

In the Depth First Pointer Chasing, each node $v$ of the graph is given as
input its index $\mbox{DFS}(v)\in[n]$ in a depth-first search ordering (as
usual we denote $[n]=\\{1,\dots,n\\}$). Moreover the vertex indexed $i$ is
given a function $f_{i}:[n]\to[n]$, and the root (i.e., the node indexed 1) is
given a value $x\in[n]$ as part of its input. The goal is to compute the value
of $f_{n}\circ f_{n-1}\circ\dots\circ f_{1}(x)$ at the root.

###### Lemma 5

There exists an edge-frugal CONGEST algorithm for problem Depth First Pointer
Chasing, with polynomial number of rounds.

###### Proof

The lemma is established using an algorithm that essentially traverses the DFS
tree encoded by the indices of the nodes, and performs the due partial
computation of the function at every node, that is, the node with index $i$
computes $f_{i}\circ f_{i-1}\dots f_{1}(x)$, and forwards the result to the
node with index $i+1$.

At round 1, each node $v$ transmits its depth-first search index
$\mbox{DFS}(v)$ to its neighbors. Therefore, after this round, every node
knows its parent, and its children in the DFS tree. Then the algorithm merely
forwards messages of type $m(i)=f_{i}\circ f_{i-1}\dots f_{1}(x)$,
corresponding to iterated computations for increasing values $i$, along the
DFS tree, using the DFS ordering. That is, for any node $v$, let
$\mbox{MaxDFS}(v)$ denote the maximum DFS index appearing in the subtree of
the DFS tree rooted at $v$. We will not explicitly compute this quantity but
it will ease the notations. At some round, vertex $v$ of DFS index $i$ will
receive a message $m(i-1)$ from its parent (of index $i-1$). Then node $v$
will be in charge of computing message $m(\mbox{MaxDFS}(v))$, by “calling” its
children in the tree, and sending this message back to its parent. In this
process, each edge in the subtree rooted at $v$ is activated twice.

The vertex of DFS index 1 initiates the process at round 2, sending $f_{1}(x)$
to its child of DFS index $2$. Any other node $v$ waits until it receives a
message from its parent, at a round that we denote $r(v)$. This message is
precisely $m(i-1)=f_{i-1}\circ f_{i-2}\dots f_{1}(x)$, for $i=\mbox{DFS}(v)$.
Then $v$ computes message $m(i)=f_{i}\circ f_{i-1}\dots f_{1}(x)$ using its
local function $f_{i}$. If it has no children, then it sends this message
$m(i)$ to its parent at round $r(v)+1$. Assume now that $v$ has $j$ children
in the DFS tree, denoted $u_{1},u_{2},\dots,u_{j}$, sorted by increasing DFS
index. Observe that, by definition of DFS trees,
$\mbox{DFS}(u_{k})=\mbox{MaxDFS}(u_{k-1})+1$ for each $k\in\\{2,\dots,j\\}$.
Node $v$ will be activated $j$ times, once for each edge $\\{v,u_{k}\\}$,
$1\leq k\leq j$, as follows. At round $r(v)+1$ (right after receiving the
message from its parent), $v$ sends message $m(i)$ to its child $u_{1}$, then
it awaits until round $r^{1}(v)$ when it gets back a message from $u_{1}$.

The process is repeated for $k=2,\dots,j$: at round $r^{k-1}(v)+1$, node $v$
sends the message $m(\mbox{DFS}(u_{k})-1)$ received from $u_{k-1}$ to $u_{k}$,
and waits until it gets back a message from $u_{k}$, at round $r^{k}(v)$. Note
that if $k<j$ then this message is $m(\mbox{DFS}(u_{k+1})-1)$, and if $k=j$
then this message is $m(\mbox{MaxDFS}(v))$. At round $r^{j}(v)+1$, after
having received messages from all its children, $v$ backtracks message
$m(\mbox{MaxDFS}(v))$ to its parent. If $v$ is the root, then the process
stops.

The process terminates in $O(n)$ rounds, and, except for the first round,
every edge of the DFS tree is activated twice: first, going downwards, from
the root towards the leaves, and, second, going upwards. At the end, the root
obtains the requested message $m(n)=f_{n}\circ f_{n-1}\dots f_{1}(x)$. ∎

Let us recall the Pointer Chasing problem as defined in [10]. Alice is given a
function $f_{A}:[n]\to[n]$, and a number $x_{0}\in[n]$. Bob is given function
$f_{B}:[n]\to[n]$. Both players have a parameter $k\in[n]$. Note that the size
of the input given to each player is $\Theta(n\log n)$ bits. The goal is to
compute $(f_{A}\circ f_{B})^{k}(x_{0})$, i.e., $k$ successive iterations of
$f_{A}\circ f_{B}$ applied to $x_{0}$. We give a slightly simplified version
of the result in [10].

######  Lemma 6 (Nissan and Wigderson [10])

Any two-party protocol for Pointer Chasing using less than $2k$ rounds has
communication complexity $\Omega(n-k\log n)$.

We have now all ingredients for proving the main result of this section.

###### Theorem 5.1

For every $\Delta\in O\left(\big{(}\frac{n}{\log n}\big{)}^{1/4}\right)$,
every CONGEST algorithm solving Depth First Pointer Chasing in graphs of
maximum degree $\Delta$ with polynomialy many rounds has node-activation
complexity $\Omega(\Delta)$.

###### Proof

Let $k$ be the parameter of Pointer Chasing that will be fixed later. The
lower bound is established for this specific parameter $k$. Let us consider an
arbitrary instance of Pointer Chasing $f_{A},f_{B}:[n]\to[n]$, and
$x_{0}\in[n]$, with parameter $k$. We reduce that instance to a particular
instance of Depth First Pointer Chasing (see Fig. 4).

$a_{1}$$a_{2}$$a_{k}$$b_{1}$$b_{2}$$b_{k}$$v_{1}$$v_{n}{}_{-2k}$$v_{2}$AliceBob
Figure 4: Reduction from Pointer Chasing to Depth First Pointer Chasing.

The graph is a tree $T$ on $n$ vertices, composed of a path
$(v_{1},\dots,v_{n-2k})$, and $2k$ leaves $v_{n-2k+1},\dots,v_{n}$, all
adjacent to $v_{n-2k}$. Node $v_{1}$ is called the root, and node $v_{n-2k}$
is said central. Note that the ordering obtained by taking
$\mbox{DFS}(v_{i})=i$ is a depth-first search of $T$, rooted at $v_{1}$. The
root $v_{1}$ is given value $x_{0}$ as input. If $i\leq n-2k$, then function
$f_{i}$ is merely the identity function $f$ (i.e., $f(x)=x$ for all $x$). For
every $j\in[k]$, let $a_{j}=v_{n-k+2j-1}$, and $b_{j}=v_{n-k+2j}$. All nodes
$b_{j}$ get as input the function $f_{B}$, and all nodes $a_{j}$ get the
function $f_{A}$. Observe that the output of Depth First Pointer Chasing on
this instance is precisely the same as the output of the initial instance of
Pointer Chasing. Indeed, $f_{n-2k}\circ f_{n-2k-1}\circ\cdots\circ f_{1}$ is
the identity function, and the sequence $f_{n}\circ f_{n-1}\circ\cdots\circ
f_{n-2k+2}\circ f_{n-2k+1}$ alternates nodes of “type” $a_{j}$ with nodes of
“type” $b_{j}$, for decreasing values of $j\in[k]$, and thus corresponds to
$f_{A}\circ f_{B}\circ\cdots\circ f_{A}\circ f_{B}$, where the pair
$f_{A}\circ f_{B}$ is repeated $k$ times, exactly as in problem Pointer
Chasing.

We can now apply Round-Efficient Simulation Lemma. Let Alice control all
vertices $a_{j}$, for all $j\in[k]$, and vertices $v_{1},\dots,v_{n-2k}$. Let
Bob control vertices $b_{j}$, for all $j\in[k]$. See Fig. 4. Note that Alice
and Bob can construct the subgraph that they control, based only on their
input in the considered Pointer Chasing instance, and they both now value $k$.

###### Claim

If there exists a CONGEST algorithm $\mathcal{A}$ for Depth First Pointer
Chasing on $n$-node graphs performing in $R_{\mathcal{A}}$ rounds with node-
activation smaller than $2k$, then Pointer Chasing can be solved by a two-
party protocol $\mathcal{P}$ in less than $2k$ rounds, with communication
complexity $O(k^{4}\log n\log R_{\mathcal{A}})$ bits.

The claim directly follows from Lemma 4. Indeed, by construction, $\partial
V_{A}=1$ and $\partial V_{B}=k$. Since we assumed
$\mathsf{nact}(\mathcal{A})<2k$, the two-way protocol $\mathcal{P}$ provided
by Lemma 4 solves the Pointer Chasing instance in less than $2k$ rounds, and
uses $O(k^{4}\log n\log R_{\mathcal{A}})$ bits.

By Lemma 6, we must have $k^{4}(\log n+\log R_{\mathcal{A}})\in\Omega(n-k\log
n)$. Therefore, if our CONGEST algorithm $\mathcal{A}$ has polynomially many
rounds, we must have $k\in\Omega\left(\big{(}\frac{n}{\log
n}\big{)}^{1/4}\right)$. Since our graph has maximum degree $\Delta=2k+1$, the
conclusion follows. ∎

##  6 Conclusion

In this paper, we have mostly focused on the round complexity of
(deterministic) _frugal_ algorithms solving general graph problems in the
LOCAL or CONGEST model. It might be interesting to consider specific classical
problems. As far as “local problems” are concerned, i.e., for locally
checkable labeling (LCL) problems, we have shown that MIS and
$(\Delta+1)$-coloring admit frugal algorithms with polynomial round
complexities. It is easy to see, using the same arguments, that problems such
as maximal matching share the same properties. It is however not clear that
the same holds for $(2\Delta-1)$-edge coloring.

###### Open Problem 1

Is there a (node or edge) frugal algorithm solving $(2\Delta-1)$-edge-coloring
with round complexity $O(\mbox{\rm poly}(n))$ in the CONGEST model?

In fact, it would be desirable to design frugal algorithms with sub-polynomial
round complexities for LCL problems in general. In particular:

###### Open Problem 2

Is there a (node or edge) frugal algorithm solving mis or
$(\Delta+1)$-coloring with round complexity $O(\mbox{\rm polylog}(n))$ in the
LOCAL model?

The same type of questions can be asked for global problems. In particular, it
is known that MST has no “awake frugal” algorithms, as MST has awake
complexity $\Omega(\log n)$, even in the LOCAL model. In contrast, frugal
algorithms for MST do exist as far as node-activation complexity is concerned.
The issue is about the round complexities of such algorithms.

###### Open Problem 3

Is there a (node or edge) frugal algorithm solving mst with round complexity
$O(\mbox{\rm poly}(n))$ in the CONGEST model?

Another intriguing global problem is depth-first search (dfs), say starting
from an identified node. This can be performed by an edge-frugal algorithm
performing in a linear number of rounds in CONGEST. However, it is not clear
whether the same can be achieved by a node-frugal algorithm.

###### Open Problem 4

Is there a node-frugal algorithm solving dfs with round complexity
$O(\mbox{\rm poly}(n))$ in the CONGEST model?

Finally, we have restricted our analysis to _deterministic_ algorithms, and it
might obviously be worth considering _randomized_ frugal algorithms as well.

## References

  * [1] Augustine, J., Moses, W.K., Pandurangan, G.: Brief announcement: Distributed MST computation in the sleeping model: Awake-optimal algorithms and lower bounds. In: 41st ACM Symposium on Principles of Distributed Computing (PODC). pp. 51–53 (2022). https://doi.org/10.1145/3519270.3538459
  * [2] Barenboim, L., Maimon, T.: Deterministic logarithmic completeness in the distributed sleeping model. In: 35th International Symposium on Distributed Computing (DISC). LIPIcs, vol. 209, pp. 10:1–10:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021). https://doi.org/10.4230/LIPIcs.DISC.2021.10
  * [3] Chang, Y., Dani, V., Hayes, T.P., He, Q., Li, W., Pettie, S.: The energy complexity of broadcast. In: 37th ACM Symposium on Principles of Distributed Computing (PODC). pp. 95–104 (2018). https://doi.org/10.1145/3212734.3212774
  * [4] Chatterjee, S., Gmyr, R., Pandurangan, G.: Sleeping is efficient: MIS in _O_(1)-rounds node-averaged awake complexity. In: 39th ACM Symposium on Principles of Distributed Computing (PODC). pp. 99–108 (2020). https://doi.org/10.1145/3382734.3405718
  * [5] Drucker, A., Kuhn, F., Oshman, R.: On the power of the congested clique model. In: Proceedings of the 2014 ACM Symposium on Principles of Distributed Computing. p. 367–376. PODC ’14, Association for Computing Machinery, New York, NY, USA (2014). https://doi.org/10.1145/2611462.2611493, https://doi.org/10.1145/2611462.2611493
  * [6] Dufoulon, F., Moses, W.K., Pandurangan, G.: Sleeping is superefficient: MIS in exponentially better awake complexity (2022). https://doi.org/10.48550/ARXIV.2204.08359
  * [7] Ghaffari, M., Portmann, J.: Average awake complexity of MIS and matching. In: 34th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). pp. 45–55 (2022). https://doi.org/10.1145/3490148.3538566
  * [8] Grumbach, S., Wu, Z.: Logical locality entails frugal distributed computation over graphs. In: 35th International Workshop on Graph-Theoretic Concepts in Computer Science (WG). LNCS, vol. 5911, pp. 154–165. Springer (2009). https://doi.org/10.1007/978-3-642-11409-0
  * [9] Kushilevitz, E., Nisan, N.: Communication complexity. Cambridge University Press (1997)
  * [10] Nisan, N., Wigderson, A.: Rounds in communication complexity revisited. SIAM Journal on Computing 22(1), 211–219 (1993). https://doi.org/10.1137/0222016
  * [11] Peleg, D.: Distributed computing: a locality-sensitive approach. SIAM (2000)

#### Acknowledgements.

The authors are thankful to Benjamin Jauregui for helpful discussions about
the sleeping model.