Tight Energy Lower Bounds for Distributed Graph Algorithms

Tight Energy Lower Bounds for Distributed Graph Algorithms Fabien Dufoulon # Lancaster University, UK

Gopal Pandurangan # University of Houston, Texas, USA

Peter Robinson # Augusta University, Augusta, Georgia, USA

arXiv:2608.18992v1 [cs.DC] 19 Aug 2026

Abstract There has been a significant recent interest in designing distributed algorithms in the SLEEPING model that minimize the energy (a.k.a awake) complexity, which measures the number of rounds a node is awake during the algorithm. A node spends non-trivial resources (messages, energy, etc.) only when it is awake and not while sleeping. Energy complexity has been studied for various fundamental problems with respect to minimizing the maximum (worst-case) or the average number of rounds a node is awake. It has been shown that the energy complexities of several fundamental problems such as leader election (LE), broadcast, Minimum Spanning Tree (MST), Maximal Independent Set (MIS) is exponentially smaller compared to their respective best-possible round complexities in the standard CONGEST model (where nodes can only send messages of small size). This raises a fundamental question of whether such significant energy gains are possible for many other fundamental problems. Our main contribution is a general and powerful technique for showing energy lower bounds using information theory. It gives almost a “plug-in" way to show energy lower bounds for various problems in the standard CONGEST model. Our information-theoretic technique allows us to leverage known lower bounds on communication complexity to obtain new, almost optimal (up to logarithmic factors) polynomial (in n) lower bounds on energy complexity — for both worst-case and average-case — for fundamental graph problems such as triangle enumeration, All-Pairs Shortest Paths (APSP), diameter computation, minimum weight cycle, Maximum Independent Set (MaxIS), Minimum Dominating Set (MinDS), Minimum Vertex Cover (MinVC). The energy lower bounds of these problems match their respective round lower bounds, implying that one cannot obtain any significant gains in energy complexity. 2012 ACM Subject Classification Theory of computation → Distributed algorithms Keywords and phrases distributed graph algorithm, energy complexity, information-theoretic lower bound Digital Object Identifier 10.4230/LIPIcs.DISC.2026.13 Funding Gopal Pandurangan was supported in part by Army Research Office (ARO) grant W911NF231-0191 and National Science Foundation (NSF) grant CCF-2402837. Peter Robinson was supported in part by National Science Foundation (NSF) Grant No. CCF-2402836.

F. Dufoulon, G. Pandurangan, and P. Robinson

1

13:1

Introduction

Motivated by resource-constrained networks such as sensor networks, where nodes spend a lot of energy or other resources, in recent years, there has been significant research in designing energy-efficient distributed algorithms for various fundamental problems (see e.g., [15, 13, 14, 17, 9, 28, 29, 35, 24, 3, 30, 20, 6, 21, 23]). Such algorithms assume the sleeping model [17], where nodes can operate in two modes: awake and sleeping. Each node can choose to enter the awake or sleep state at the start of any specified round. In sleeping mode, a node cannot send or receive, nor perform any non-trivial local computation, and it consumes very little energy or resources. On the other hand, significant resources are utilized only in the awake mode, and hence the goal is to design distributed algorithms that minimize the number of awake rounds, i.e., the energy (a.k.a awake) complexity. It is challenging to design such algorithms, partly because one must judiciously balance keeping nodes asleep as much as possible with coordinating communication between nodes (we note that messages sent to a sleeping node are lost). Energy complexity has been studied for various fundamental problems with respect to minimizing the maximum (worst-case) or the average number of rounds a node is awake. While energy complexity is typically used to refer to worst-case scenarios, for averagecase scenarios we use node-averaged energy complexity. Both measures have been studied extensively for various problems (see e.g., [17, 28, 24] and the references therein). Note that, traditionally, in distributed algorithms, all nodes are considered awake in all rounds (i.e., there is no sleeping mode) and the goal is to minimize the round complexity of the algorithm, which counts the (worst-case) total number of rounds taken by any node. After decades of intensive research, distributed algorithms with optimal (or near-optimal) round complexity for various fundamental problems are now well-established. In the standard CONGEST model of distributed computing, which captures bandwidth limitations of realworld networks, only messages of size O(log n) can be sent over an edge per round. Unfortunately, the round complexity of distributed algorithms can be quite large for various fundamental problems due to well-established lower bounds. Hence, several works have addressed designing algorithms that have significantly less energy (awake) complexity, even at the cost of increased round complexity, since only awake rounds contribute to energy. To illustrate, for fundamental problems such as leader election, broadcast, and spanning tree, it is well known that Ω(D) (where D is the network diameter) is a universal lower bound on the round complexity [37], but one can design algorithms with O(log n) energy complexity p [9, 3]. Similarly, for the fundamental Maximal Independent Set (MIS) problem, while Ω( log n/ log log n) is a lower bound on the round complexity [36], there are algorithms with O(log log n) energy complexity [24, 29]. Moreover, one can show that the node-averaged energy complexity of MIS is O(1), which is optimal [17, 28]. Thus, the energy complexities of the above fundamental problems are exponentially smaller compared to their respective best-possible round complexities. This raises a fundamental question of whether such large energy gains are possible for many other fundamental problems. The focus of this paper is to show lower bounds on the energy complexity of various fundamental graph problems. Generally, establishing lower bounds on energy complexity appears more difficult than establishing lower bounds on round complexity. For one, a locality-based approach (see e.g., [37, 36]) e.g., that captures many round complexity lower bounds does not apply (at least directly) for energy complexity. Indeed, a basic property that underlies many round complexity lower bounds is that in r rounds a node cannot get any information from beyond its r-hop neighborhood. However, this property does not apply

DISC 2026

13:2

Tight Energy Lower Bounds for Distributed Graph Algorithms

to energy complexity, since in r awake rounds, a node can get information much farther than its r-hop neighborhood. Communication complexity-based techniques give a uniform way to show round complexity lower bounds in the CONGEST model (see e.g., [22, 27, 25, 2, 1, 11, 5]). At a high level, these techniques show that a lot of information — usually established by communication complexity — has to be exchanged across an appropriate cut in a graph, and if the cut size is small, this implies congestion across the cut edges, which leads to round lower bounds. This high-level idea does not directly apply to energy complexity, as it may be possible to transfer information simply by waking up at the appropriate rounds. Indeed, this is the reason √ why the communication complexity-based lower bound of Ω̃(D + n) for the fundamental Minimum Spanning Tree (MST) problem [22] does not apply for energy complexity, and one can design an O(log n) energy algorithm [3].

1.1

Our Contributions

We present a general and powerful technique for establishing energy lower bounds that applies not only to the worst-case setting but also to the node-averaged setting. As an application of our technique, we show new and (almost) tight energy complexity lower bounds for various fundamental problems. Using information-theoretic techniques, we present a technique to show energy lower bounds for various problems in the CONGEST model. Our technique allows us to leverage known lower bounds on communication complexity to obtain new, optimal polynomial (in n) lower bounds on energy complexity — for both worst-case and average-case — for fundamental problems such as triangle enumeration, All-Pairs Shortest Paths (APSP), diameter computation, Maximum Independent Set (MaxIS), Minimum Dominating Set (MinDS), and Minimum Vertex Cover (MVC) (cf. Table 1). The energy lower bounds of these problems match their respective round lower bounds, implying that one cannot obtain any significant gains in energy complexity. More precisely, we show a lower bound of Ω(n1/3 / log n) for triangle enumeration, Ω(n/ log n) for both worst-case and node-averaged energy complexity for diameter computation, APSP, and minimum weight cycle finding. We also show a worst-case energy lower bound of Ω(n2 / log2 n) and a node-averaged lower bound of Ω(n2 / log3 n) for MaxIS, MinDS, and MinVC. Our main technical result is summarized in the Cut-based Energy Lower Bound Lemma, which relates a lower bound on the amount of information that has to be transmitted across a cut to a lower bound on the energy complexity: Lemma 1 (informal and simplified; see Sec. 3.1, p. 7): Cut-based Energy Lower Bound. Suppose there exist two subsets of vertices U and ∂U , such that each node in U has at most dU neighbors in ∂U , and we are interested in some bit string Z that is a function of the graph. More concretely, the nodes in U need to learn L bits about Z, and this information is only  known to the nodes in ∂U initially. Then, each node in U must wake up at least Ω dU |UL| log n times. In fact, when L roughly corresponds to the number of possibilities of Z, then we also obtain the same bound for the node-averaged energy complexity (over the nodes in U ). These bounds hold independently of the number of rounds allowed before termination. The lemma shows a precise relationship between the two lower bounds that depends on the amount of information, cut size, and the degree of nodes across the cut. The high-level

F. Dufoulon, G. Pandurangan, and P. Robinson

13:3

idea is to lower-bound the total number of messages that a node has to send across the cut and show that the node has a small number of neighbors across the cut, which would imply a lower bound on the energy complexity. We use information theory to argue that the asymptotically same round lower bounds also apply to energy. However, there are two main technical challenges that we need to overcome: First, we note that, unlike round complexity, for which it is easy to obtain a lower bound by dividing the information lower bound by the cut size, the situation is more subtle for energy complexity. For instance, an algorithm could require an exponential number of rounds, 2 T ≈ 2n , to compute the solution, whereby nodes wake up in only a small number of rounds to keep the energy complexity low. In particular, the algorithm could use the interval [T ] to encode the possible choices of the information that needs to be transmitted.1 If nodes on both sides of the cut could manage to wake up in the same particular round i ∈ [T ], then it may look plausible that the nodes on the receiving side of the cut have learned log T ≈ n2 bits of information by being awake in just a single round. The reader may rightfully object that achieving this coordination between the two sides of the cut may itself incur a high energy cost. To show formally that this (and related) strategies are futile, we make use of a result of Massey [40] that, intuitively speaking, allows us to lower bound the energy cost of “guessing” the right time to wake up for nodes on both sides. The second challenge is combinatorial, where one has to appropriately set up a lower bound graph to ensure that nodes have a small degree across the cut. We accomplish this by using ℓ-separated graph families, which might be of independent interest (cf. Section 3.2). Our approach is general enough to apply to a broad range of graph problems, even though their existing lower-bound proofs for round complexity may rely on very different techniques. For instance, the hardness results of minimum vertex cover, maximum independent set, and minimum dominating set are all based on reductions from the set disjointness problem in 2-party communication complexity (see [5]). In contrast, problems such as triangle listing or sclique enumeration seem to require information-theoretic arguments from first principles [34]. We show that our Cut-based Energy Lower Bound Lemma applies to any problem for which there is an ℓ-separated graph family on which any algorithm exhibits high information cost. This information cost is a notion from 2-party communication complexity introduced in [8], which, intuitively, quantifies how much information a protocol must leak about one party’s input to the other. This enables us to address all problems whose hardness is based on set disjointness, which is known to have high information cost. As a result, we directly obtain energy complexity lower bounds for numerous fundamental graph problems: Theorem 4 (informal and simplified; see Sec. 3.2 on page 9.) Suppose that there exists an ℓ-separated graph family with a cut set size s and a maximum cut degree dcut , such that solving a graph  predicate  P exhibits information cost I. Then, the worst case I energy complexity is Ω dcut ·s·log n . Moreover, assuming a natural bound on the inputs (satisfied by all problems whose round complexity hardness is based   on set disjointness), the expected node-averaged energy complexity is Ω

ℓ I n · dcut log n

.

Finally, we point out that ℓ-separated graph families with large ℓ (say, ℓ = Θ(n/ log n))

1

This approach is similar to time encoding to transmit information [44], which can be used to reduce the message complexity at the cost of increasing the round complexity. In fact, one has to be careful in using communication complexity-based techniques for showing lower bounds in distributed computing with synchronous clocks [33, 41].

DISC 2026

13:4

Tight Energy Lower Bounds for Distributed Graph Algorithms

Problem Triangle Listing s-Clique Listing Local Triangle Listing

Lower Bound

Upper Bound

Our Result

 1/3 ∗

1/3 ∗

Corollary 7

Ω Ω

n

n ∗  log1−2/s

Ω

Computing Diameter / APSP

Ω

Minimum Weight Cycle

Ω

Minimum Vertex Cover

Ω

Maximum Independent Set Minimum Dominating Set

Ω Ω

n log n † n log n † n log n † n log n

  

n2 log2 n n2 log2 n n2 log2 n

† † †

Õ n

[16]

1−2/s ∗

Õ n

[10]

O( logn n )‡ [32] ∗ O logn n [31] ∗

Corollary 8 Corollary 7

Corollary 10

Õ(n) [39]

Corollary 10

O(n2 )∗,#

Corollary 9

O(n2 )∗,#

Corollary 9

O(n2 )∗,#

Corollary 9

∗) Worst-case energy complexity. †) Expected node-averaged (which also implies worst-case) energy complexity. #) The trivial algorithm of learning the entire topology. ‡) When parametrized also by the maximum degree ∆, the upper bound of [32] is O(∆/ log n + log log ∆) Table 1 Energy Complexity Bounds for Graph Problems in the CONGEST model. All energy complexity lower bounds match the best-known round complexity lower bounds.

are crucial for some of our results, specifically, for our quadratic node-averaged energy complexity lower bounds. Indeed, these quadratic lower bound instances exhibit small cut set size s (say, s = O(log n)). However, only cut nodes need to spend significant energy. To amplify the fraction of cut nodes (to ℓs/n), we “stretch” these small cuts by a large ℓ factor. This approach is inspired by that of [25], in which stretching such cuts allows to obtain (time-conditional) cubic message complexity lower bounds.

2

Preliminaries

2.1

Distributed Computing Model

The (synchronous) CONGEST model [43] considers some n-node input graph G = (V, E), whose nodes represent the machines in a distributed network, and edges represent the communication links between any two machines. Each node has a unique integer ID of O(log n) bits, and we assume the clean network model [43], where nodes are unaware of their neighbors’ IDs initially. Note that, in the context of energy complexity, there is no substantial difference between the clean network model and the stronger KT1 assumption [4], where each node knows the IDs of its neighbors from the start: In the clean network model, each node can learn its neighbors’ IDs by being awake in round 1. In addition, we encode problem-specific inputs via some function in defined on the vertices, where for any v ∈ V , in(v) encodes the portion of the problem-specific inputs that pertain to v and its incident edges. Finally, each node also has some common knowledge regarding G, such as a polynomial upper bound N on the number of nodes, and has access to some private randomness (which is also independent of the nodes’ inputs). Computation proceeds in synchronous rounds. In each round, each node can send (possibly different) messages of O(log n) size to each of its neighbors, receives the messages sent by its neighbors, and performs some local computations. The round complexity of some algorithm

F. Dufoulon, G. Pandurangan, and P. Robinson

13:5

is defined as the worst-case, over all nodes, number of rounds a node requires to produce an output and terminate.

2.2

Sleeping Model

We assume the sleeping model [17], where a node can be in either of the two states — sleeping or awake. (At the beginning, we assume that all nodes are awake.) This is a simple generalization of the standard distributed computing model, where nodes are always assumed to be awake. In the sleeping model, each node decides to be either awake or asleep in each round (till it terminates), corresponding to whether the node can receive/send messages and perform computations in that round or not, respectively. That is, any node v can decide to sleep starting at any (specified) round of its choice. We assume that all nodes know the correct round number whenever they are awake. A node can wake up again later at any specified round and enter the awake state. We note that the model allows a node to cycle through the process of sleeping in some round and waking up in a later round as many times as it wishes. To summarize, distributed computation in the sleeping model proceeds in synchronous rounds, and each round consists of the following steps: (1) Each awake node can perform local computation. (2) Each awake node can send a message to its adjacent nodes. (3) Each awake node can receive messages sent to it in this round (in the previous step) by other awake nodes. Thus, the paper assumes the sleeping model in the CONGEST setting, called the SLEEPING-CONGEST model [24]. Energy Complexity. In the sleeping model, let Av denote the number of awake rounds for a node v before it terminates (i.e., finishes the execution of the algorithm, locally). A node utilizes significant energy only when it is awake. Hence we define the (worst-case) energy (a.k.a) awake complexity as Amax = maxv∈V Av . Note that, for a randomized algorithm, Av P will be a random variable. We also define Aavg = n1 v∈V Av , i.e., the average of the Av random variables. Then the expected node-averaged energy complexity of the randomized P P algorithm is E[Aavg ] = E[ n1 v∈V Av ] = n1 v∈V E[Av ], where the expectation is taken over the random coin choices of the algorithm. In this paper, we study lower bounds on both the worst-case and the node-averaged energy complexity. For worst-case energy complexity, we study worst-case (per node) energy lower bounds for (Monte-Carlo) algorithms that succeed with constant probability. For node-averaged energy complexity, we study lower bounds on the expected node-averaged energy complexity. We note that lower bounds for node-averaged energy complexity also imply the same for worst-case energy complexity.

2.3

Basic Facts from Information Theory

We recall some facts from information theory that we rely on in the proofs of Sections 3 and 4. Additional details and proofs can be found in standard textbooks such as [18]. Here, we consider jointly distributed random variables W , X, Y , and Z, and we follow the convention of using capitals for random variables and lowercase letters for values of random variables. We denote the Shannon entropy of X by H[X], which is defined as H[X] =

X

Pr[X = x] log2 (1/ Pr[X = x]).

(1)

x

DISC 2026

13:6

Tight Energy Lower Bounds for Distributed Graph Algorithms

The conditional entropy of X conditioned on Y is defined as H[X | Y ] = E[H[X | Y = y]]. Y

(2)

The conditional mutual information of X and Y is defined as I[X : Y | Z] = E[I[X : Y | Z = z]] = H[X | Z] − H[X | Y, Z]. Z

(3)

▶ Fact 2.1. It holds that: 1. I[X : Y | Z] ≤ H[X | Z] ≤ H[X], 2. I[X : Y | Z] ≤ I[X, W : Y | Z]. ▶ Fact 2.2 (Chain Rule of Mutual Information). I[X : Y, Z | W ] = I[X : Y | W ]+I[X : Z | W, Y ]. ▶ Fact 2.3 (Chain Rule of Conditional Entropy). H[X, Y | W ] = H[X | W ] + H[Y | X, W ]. ▶ Fact 2.4. H[X] ≤ log2 (|supp(X)|), where supp(X) denotes the support of X. Equality holds if X is uniformly distributed. ▶ Fact 2.5. I[X : Y, Z | W ] ≤ |X|. ▶ Fact 2.6 (Data Processing Inequality, see Theorem 2.8.1 in [18]). If random variables X, Y , and Z form the Markov chain X → Y → Z, i.e., the conditional distribution of Z depends only on Y and is conditionally independent of X, then I[X : Y ] ≥ I[X : Z].

2.4

Additional Related Work

We mainly focus on related works on lower bounds on energy complexity, though as mentioned in Section 1, several recent works have designed energy-efficient distributed algorithms in the sleeping model for various fundamental problems including MIS, approximate matching, maximal matching, coloring, and vertex cover, broadcast, spanning tree, breadth-first spanning tree, minimum spanning tree (MST), and single-source shortest paths [15, 13, 14, 17, 9, 28, 29, 35, 24, 3, 30, 20, 6, 21, 23]). While some of these works assume the SLEEPING-CONGEST model, some assume the SLEEPING-RADIO model (see e.g., [24] for works in this model), where the radio network model is assumed. In this model, nodes can only broadcast to their neighbors, and there are interference constraints. It is important to note that lower bounds for the SLEEPING-CONGEST also apply to SLEEPING-RADIO, and hence all the lower bounds in this paper also apply. Few works have shown lower bounds on energy complexity. As mentioned earlier, there is a lack of general techniques for showing energy lower bounds, partly due to the reasons mentioned in Section 1. Still, a notable lower bound on energy complexity is the Ω(log n) lower bound for broadcast, which also applies for leader election and minimum spanning tree [13, 3]. This bound applies even to randomized algorithms and to the LOCAL model (where there are no restrictions on message sizes, unlike in CONGEST). The work of [9] showed a deterministic lower bound of Ω(log n) node-averaged energy complexity for leader election on rings. This lower bound exploits the fact that Ω(n log n) is a deterministic lower bound on the message complexity of leader election in rings, and as a result, on average, a node has to transmit Ω(log n) messages and hence be awake for so many rounds. This basic idea of exploiting per-node congestion is also used to demonstrate an energy-round trade-off in [3]. We note that the approach of [3] for showing energy-round trade-off (which uses the lower approach of [22] in conjunction with per-node congestion) is different from the information-theoretic approach (cf. Lemma 1) used in the current paper.

F. Dufoulon, G. Pandurangan, and P. Robinson

13:7

Additionally, some energy complexity lower bounds were shown in the SLEEPING-RADIO model (see e.g., [13, 7]), but these lower bounds leverage the radio nature (in particular, collision constraints of the radio model) and do not apply to CONGEST. For example, the work of [13] provides two polynomial in n lower bounds for computing the graph diameter in the SLEEPING-RADIO model — Ω(n) energy is required to (2 − ϵ)-approximate diameter on dense graphs, and Ω(n/ log2 n) is required to (3/2 − ϵ)-approximate diameter on sparse graphs. While the above results hold for arbitrary graphs, subsequently it was shown that √ the energy bound can be improved to O( n) in bounded genus graphs for computing the exact diameter and global minimum cut size in bounded genus graphs [12]. This paper also shows Ω(n) energy lower bound on computing the minimum cut size in unit-disc graphs and s − t minimum cut size in planar bipartite graphs. It should be noted, as mentioned earlier, that all the above-mentioned (polynomial in n) lower bound results are due to the radio nature (in fact, they do not depend on the bandwidth constraint) and do not apply to SLEEPING-CONGEST. We note that, for SLEEPING-CONGEST, the above (unconditional2 ) energy lower bounds are logarithmic in n. No significantly higher energy lower bounds—such as a polynomial in n—were known for well-studied graph problems prior to our work. We present the first such lower bounds for various fundamental problems.

3

An Information-Theoretic Framework for Energy Complexity Lower Bounds

In this section, we present a framework for deriving lower bounds on the energy complexity of distributed graph problems via information-theoretic techniques. In Section 3.1, we give the fairly generic Lemma 1 that captures the impact of the amount of information that an algorithm needs to send across a cut on the (expected) total number of awake rounds of the nodes that lie at the boundary of the cut. Then, in Section 3.2, we turn our attention to so-called ℓ-separated lower bound graph families, which were originally introduced for proving round and message complexity lower bounds via problems in communication complexity, such as set disjointness. By leveraging Lemma 1, we give Theorem 4 and quantify the relationship between the information cost of a communication complexity problem — the amount of information that any protocol must leak about the players’ inputs — and the energy complexity of a distributed algorithm that can be simulated in the two-party communication complexity model.

3.1

A Cut-based Approach to Energy Complexity Lower Bounds

Throughout this section, we use basic facts from information theory that we summarize in Section 2 for completeness. In particular, for random variables X, Y , and Z, we use I[X : Y | Z] to denote the conditional mutual information, i.e., how much information X reveals about Y (and vice versa) given Z. Before stating our main technical lemma, we first introduce some notation. For a node u and a set W , we use e(u, W ) to denote the number of neighbors of u in W . When considering a probability distribution G on a family of graphs, we slightly abuse notation and write G ∈ G if G has nonzero probability of being sampled from G. We define the support of a random variable X as supp(X) = {x | Pr[X = x] > 0}.

2

That is, it does not depend on round complexity, unlike the trade-off result in [3].

DISC 2026

13:8

Tight Energy Lower Bounds for Distributed Graph Algorithms

Round 2 5

Awake Nodes u1 , u2 , v1 , v2 u1 , u3 , v1 , v3

Communication (∂U → U ) m m v1 →1 u1 , v2 →2 {u2 , u3 } m3 m v1 → u1 , v3 →4 u3

m

Π̂ = { (2, v1 →1 u1 ) m

(2, v2 →2 u2 ), m

(5, v1 →3 u1 ), m

(5, v3 →4 u3 ) }

(a) The cut-based lower bound approach.

Lemma 1 gives a bound on the total number of awake rounds of the nodes in U .

(b) The table shows a possible execution on the network in Figure 1a and the resulting extended transcript Π̂ (see Def. 12). For simplicity, we do not distinguish between a node and its ID in this example.

Figure 1

▶ Lemma 1 (Cut-based Energy Lower Bound). Consider a randomized ϵ-error algorithm A in the sleeping CONGEST model, and let G be a probability distribution of n-node graphs such that every G ∈ G has the same set of nodes. Let Z be a random variable that is a function of G. Suppose that there exist sets VA and VB such that (VA , VB ) is a cut of every G. Let U ⊆ VA and ∂U ⊆ VB be any sets such that the edges in (U, ∂U ) form an edge cut, and every node in U has a neighbor in ∂U . Let dU = maxG∈G maxu∈U e(u, ∂U ) be the maximum number of such neighbors. Moreover, the choice of VA and VB must be independent of the algorithm’s execution. Finally, let ΠU be the transcript of the messages sent to the nodes in U across (U, ∂U ). If, for some L = O(poly(n)), we have I[ΠU : Z | SVA ] ≥ L, where SVA is the initial state of the nodes in VA , then the following hold: (i) Let αU be the number of total awake rounds summed over the nodes  in U .

If |supp(Z)| ≤ 2c·L , for some positive constant c, then E[αU ] = Ω   (ii) The worst-case energy complexity bound of A is Ω dU |UL| log n .

L dU log n

.

Figure 1a shows how the different node sets and the cut relate to each other. Overview of the Proof of Lemma 1. We first outline the high-level ideas and provide the full details in Section A. There are several technical challenges that we need to overcome. First, we do not impose any restriction on the algorithm’s round complexity. This, combined with the fact that nodes have access to a global clock and know the current round number, may lead us to believe that the algorithm could employ a time-encoding trick, where information of L bits is conveyed across the cut by sending just a single bit in a specific round of an interval of length 2L , thus drastically reducing the number of required awake rounds.3 If successful, then the algorithm would be able to convey L bits of information across an edge in just a single awake round of the sender and receiver.

3

In fact, it is
known [44] that time-encoding can reduce the message complexity for many graph problems from Θ n2 to near-optimal O(n poly log n) messages at the cost of increasing the number of rounds.

F. Dufoulon, G. Pandurangan, and P. Robinson

13:9

We now provide some intuition on how we rule out such strategies in our proof. For simplicity, we limit our discussion to cuts involving a single sender and a single receiver. Suppose that a node on the receiving side of the cut is indeed able to learn a large amount of information from the sender while waking up only a few times (and hence receiving only a few O(log n)-size messages). By carefully analyzing the extended transcript of the communication across the cut, which augments each message with its round number and also includes the wake-up steps in which no message was received, we show that the receiver must have been able to correctly “guess” the round number of the sender’s next wake-up. Furthermore, the sender must have used a sufficiently large range when selecting the time of their next awake round to ensure that the round number has the necessary amount of entropy. As sender and receiver have to both be awake in the same round for a successful transmission to occur, we conclude that this is unlikely to happen unless the receiver wakes up a large number of times, by leveraging the relationship between the entropy of a random variable and the expected number of guesses for finding its value due to Massey [40]. Intuitively, Massey’s result rules out a time-encoding approach in which sending only a single message in a specific round, chosen from an exponentially large interval, can convey a large amount of information (and thus save on messages). We obtain a contradiction on the assumed upper bound on the worst-case number of awake rounds, which shows Property (ii) of the lemma. To extend the proof to Property (i), i.e., the case where the algorithm only satisfies the energy complexity bound in expectation, we first observe that a given node-averaged algorithm will satisfy (a constant factor of) the expected bound on the total awake complexity with constant probability, and apply the above argument directly to that case. However, when the algorithm exceeds the expected number of awake steps, it becomes more challenging to directly bound the amount of information that the receiver may learn. This is because conditioning on the event that the algorithm significantly exceeds the expected total number of awake rounds may actually increase how much useful information the algorithm’s transcript carries about the random variable Z, which is a function of the subgraph on the sender’s side that the receiver wants to learn. We overcome this issue by introducing a restriction on the number of possible choices for Z (i.e., its support). This essentially guarantees that the amount of information learned about Z cannot be off by more than a constant factor compared to the case when the algorithm is close to the expected number of wake-up steps, which suffices to prove (i).

3.2

Lower Bounds for ℓ-Separated Graph Families

Many existing lower bounds for fundamental graph problems are based on the hardness of solving certain functions in the two-party model of communication complexity, where Alice and Bob have inputs X and Y respectively, and need to communicate in order to compute f (X, Y ) with error at most ϵ. To make it easier to apply Lemma 1 to such problems, we first introduce the notion of ℓ-separated families of lower bound graphs that were defined in [25], which are a generalization of the lower bound graph families of [11] and [5]. Intuitively speaking, a graph G of an ℓ-separated family consists of ℓ vertex sets V1 , . . . , Vℓ with the property that we can simulate a given distributed algorithm in the two-party model of communication complexity for any possible cut (V≤i , V>i ) (i ∈ [1, ℓ − 1]). Moreover, G[V1 ] depends on Alice’s input, and Bob uses his input to create G[Vℓ ], with the goal of simulating a distributed algorithm on G to compute a given two-party function f . We use the internal information cost (IC) introduced in [8] to quantify the amount of information that the cross-cut transcript of such a simulation must leak to Alice about Bob’s input and vice versa. In Definition 3 below, we extend the notion of information cost to graph

DISC 2026

13:10

Tight Energy Lower Bounds for Distributed Graph Algorithms

predicates P , such that IC(P ) corresponds to IC(f ) of the function f that exhibits the highest information cost of all functions that can be computed by simulating an algorithm for P on some ℓ-separated graph family. We obtain Theorem 4, which, intuitively speaking, states that a graph predicate with a high information cost entails a corresponding lower bound on its energy complexity. To see why Theorem 4 holds, we observe that, when simulating an algorithm for P for a given cut (V≤i , V>i ), the nodes on one side of the cut must learn at least IC(P ) ) bits. Consequently, we can instantiate Lemma 1 for obtaining a lower bound ≥ IC(f 2 2 on the expected total number of awake rounds of the corresponding nodes. By summing over the ℓ − 1 possible cuts, the lower bound on the expected total energy complexity follows. Figure 2 shows the general setup used in Theorem 4 for the special case ℓ = 3. ▶ Definition 2 (ℓ-Separated Family of Lower Bound Graphs; see Def 2.1 in [25]). Let f : X × Y → {true, false} be a function and P be a graph predicate. For an integer ℓ > 1, a family of graphs {Gx,y = (V, Ex,y ) | x ∈ X, y ∈ Y } is said to be an ℓ-separated family of lower bound graphs w.r.t. f and P if V can be partitioned into ℓ disjoint subsets V1 , V2 , . . . , Vℓ−1 , Vℓ such that the following properties hold: (a) Only the existence or the weight of edges in V1 × V1 depend on x; (b) Only the existence or the weight of edges in Vℓ × Vℓ depend on y; (c) For all 1 ≤ i ≤ ℓ, the vertices in Vi are only connected to vertices in Vi−1 ∪ Vi ∪ Vi+1 (where V0 = Vℓ+1 = ∅). (d) Gx,y satisfies the predicate P iff f (x, y) = true. The equivalence captured by (d) motivates simulating a distributed algorithm for the predicate P in the two-party model of communication complexity, where Alice and Bob want to compute the value of f (X, Y ). As the simulation follows the standard approach used in previous work, we provide only a high-level overview; additional details can be found in [25, 11]. Simulation Protocol. For an index i ∈ [ℓ − 1], we obtain the simulation protocol for cut (V≤i , V≥i+1 ), by instructing Alice to construct the edges of G[V1 ], according to her input X, whereas Bob is responsible for constructing G[Vℓ ] according to Y . The rest of G does not depend on their inputs and hence can be (locally) constructed by both. Then, they jointly simulate algorithm A round by round, whereby Alice simulates all nodes in V≤i , and Bob simulates the remaining nodes given by V≥i+1 . Alice and Bob only need to communicate for the messages that cross the cut (V≤i , V≥i+1 ). It is straightforward to verify that the simulation protocol has the same error probability as A. Maximum Cut Degree and Cut Size. For each i ∈ [ℓ], we define subsets Vi− , Vi+ ⊆ Vi as follows: Vi− contains all nodes in Vi that have a neighbor in Vi−1 and Vi+ consists of all nodes having a neighbor in Vi+1 . We call s the cut set size of the graph family and define
s = max |Vi− |, |Vi+ | . We also define the maximum cut degree 1≤i≤ℓ

dcut = max

  max e(u, Vi+1 ), max e(v, Vi ) .

1≤i≤ℓ−1

u∈Vi

v∈Vi+1

(4)

Information Cost. A common way to quantify how much information the transcript Π of all messages leaks to the players in the two-party model about each other’s input is the (internal) information cost [8] of the protocol π on distribution µ, defined as ICµ (π) = I[X : Π | Y ] + I[Y : Π | X].

F. Dufoulon, G. Pandurangan, and P. Robinson

13:11

Figure 2 An example of the graph construction in the proof of Theorem 4 for a 3-separated graph family. For the node-averaged lower bound, we apply Lemma 1 to both cuts, (V1 , V2 ∪ V3 ) and (V1 ∪ V2 , V3 ). The figure depicts this application for the cut (V1 ∪ V2 , V3 ). Here we assume that the nodes on V3 ’s side learn more than I/2 bits about G[V1 ], and hence we choose the set U to lie on this side and swap VA and VB accordingly when instantiating Lemma 1.

Moreover, the information cost of f with error ϵ is defined as IC(f, ϵ) = inf max ICµ (π), π

µ

where the infimum is taken over all ϵ-error protocols π that compute f , and the maximum identifies the worst case input distribution µ with respect to the best protocol π. ▶ Definition 3 (Information Cost of Graph Predicate). Consider a graph predicate P and a function f : X × Y → {true, false}. We say that P has an information cost of IC(f, ϵ) with error ϵ for f , formally IC(P, f, ϵ) = IC(f, ϵ), if there exists an ℓ-separated graph family with respect to f and P . The information cost of predicate P with error ϵ is defined as IC(P, ϵ) = supf IC(P, f, ϵ), where the supremum is taken over all functions f , for which there exists an ℓ-separated family w.r.t. P . ▶ Theorem 4 (Information Cost −→ Energy Complexity). Consider a graph predicate P and some ϵ > 0. Suppose that IC(P, ϵ) ≥ I, where I = O(poly(n)), i.e., there exists a suitable function f : X × Y → {true, false} and an ℓ-separated family such that IC(P, f, ϵ) = IC(f, ϵ) ≥ I. Let s be the cut set size (see Def. 2), and let dcut denote the maximum cut degree; see (4). The following hold for any ϵ-error algorithm for P : c·I (a) If |supp(X)| ≤ 2c·I and |supp(Y )| ≤ 2 , for some positive constant c, then the expected  node-averaged energy complexity is Ω

ℓ−1 I n · dcut ·log n

.



 I (b) The worst case energy complexity (per node) is Ω dcut ·s·log n . Moreover, the energy complexity bounds hold independently of the round complexity of the algorithm. Proof. We first show the bound on the worst-case energy complexity of a given algorithm A. Consider the ℓ-separated graph family G w.r.t. f and P , and fix some arbitrary i ∈ [ℓ − 1]. Suppose that we use A to run the simulation protocol πi for the cut (V≤i , V≥i+1 ), for

DISC 2026

13:12

Tight Energy Lower Bounds for Distributed Graph Algorithms

some i ∈ [ℓ − 1], with the goal of computing f (X, Y ), and recall that Alice uses her input to construct the edges of G[V1 ], whereas Bob will construct G[Vℓ ] according to Y . Since IC(f, ϵ) ≥ I, we know that there exists a distribution µ on X × Y such that the information cost of protocol πi is ICµ (πi ) = I[X : Π | Y ] + I[Y : Π | X] ≥ I. Without loss of generality, we assume that I[X : Π | Y ] ≥

I . 2

(5)

Let ΠVi denote the transcript of messages that the nodes in Vi receive from their neighbors in Vi+1 and define ΠVi+1 analogously; note that Π = (ΠVi , ΠVi+1 ) contains the entire transcript of the communication between Alice and Bob, i.e., which corresponds to all messages crossing the cut. Our goal is to apply Lemma 1, and hence we need to first argue that (5) holds when only considering the transcript ΠVi+1 .   ▷ Claim 5. I X : ΠVi+1 | Y ≥ I2 . Proof. Let RB be the private randomness of Bob. Consider the mutual information I[X : RB | Π, Y ]. Conditioned on the transcript Π and Bob’s input Y , we know that Alice’s input X is independent of Bob’s randomness RB . In other words, X → (Π, Y ) → RB forms a Markov chain, and hence I[X : RB | Π, Y ] = 0. By a similar argument, it follows that I[X : RB | Y ] = 0. Combining these observations and applying the chain rule multiple times yields I[X : Π | Y ] = I[X : Π | Y ] + I[X : RB | Π, Y ] − I[X : RB | Y ]

(6)

= I[X : Π, RB | Y ] − I[X : RB | Y ]

(7)

= I[X : Π | RB , Y ]   = I X : ΠVi , ΠVi+1 | RB , Y     = I X : ΠVi+1 | RB , Y + I X : ΠVi | ΠVi+1 , RB , Y   = I X : ΠVi+1 | RB , Y ,

(8)

(9)

where the final step follows because the conditioning on ΠVi+1 , RB , Y ensures that the messages sent to the nodes   in Vi , i.e., ΠVi , do not reveal any information about X, and hence I X : ΠVi | ΠVi+1 , RB , Y = 0. Finally, we can again remove the conditioning on the private randomness in (9) by simply executing the chain rule applications order  in (6)-(8) in reverse I (after replacing Π with Πi+1 ). It follows that I X : ΠVi+1 | Y = I[X : Π | Y ] ≥ 2 , which completes the proof of the claim. ◀ We are now ready to instantiate Lemma 1(ii) for algorithm A with Z = G[V1 ], L = − + I 2 , VA = V≥i+1 , VB  = V≤i , U = Vi+1 , ∂U I= Vi , and dU = dcut , which means that I[Z : ΠU | SVA ] = I G[V1 ] : ΠVi+1 | SV≥i+1 ≥ 2 , as required by the premise of the lemma. This yields the sought worst case bound per node. To extend the result to the node-averaged case, we proceed similarly as for the worst case above, with the main difference being that we apply Lemma 1(i) for every cut (Vi , Vi+1 ) (1 ≤ i ≤ ℓ − 1). Let αi be the total number of awake rounds of the nodes in Vi ∪ Vi+1 . It follows that, for all i ∈ [ℓ − 1],   I E[αi ] = Ω , dcut log n

F. Dufoulon, G. Pandurangan, and P. Robinson

13:13

and thus E[α] ≥

  ℓ−1 1X (ℓ − 1) · I E[αi ] = Ω , 2 i=1 dcut log n

and the claimed bound on the expected node-averaged complexity follows.

◀

The most prominent instance of a function f in communication complexity is the set disjointness function (DISJm ): Alice and Bob each get a subset of some universe of size m, represented as the corresponding m-length characteristic vectors, and they must communicate to decide whether these sets are disjoint. Numerous lower bound reductions employ the hardness result of set disjointness (e.g., [11, 5]), which says that the players need to communicate Ω(m) bits. For the subsequent applications, we require a stronger property, namely that any set disjointness protocol must leak a linear amount of information: ▶ Fact 3.1 (Information cost of set disjointness [19]). The set disjointness function on input vectors of length m has IC(DISJm , ϵ) = Ω(m), for a suitable small constant ϵ > 0. Next, we state a corollary that allows a streamlined application of Theorem 4 for several important graph problems. That is, it enables us to directly obtain energy complexity bounds by reusing existing lower bound constructions in the CONGEST model. ▶ Corollary 6. Consider a graph predicate P , and suppose that
there exists an ℓ-separated graph family G with respect to DISJm and P , where m = Θ n2 , and where dcut denotes the maximum cut degree and s denotes the cut set size ofG. Then, the worst case energy n2 complexity of any distributed algorithm that decides P is Ω dcut ·s·log n , whereas its expected   ℓ−1 n2 node-averaged energy complexity is Ω n · dcut log n . These bounds hold independently of the time complexity of the algorithm. Proof. The claim on the worst-case energy complexity is immediate from Fact 3.1 and Theorem 4(b). For applying Theorem 4(a), we need to argue that the support of Alice’s
input 2 X and Bob’s input Y are bounded from above by 2c·n , which holds since m = Θ n2 . ◀

4

Applications

We now demonstrate how to obtain lower bounds for a diverse range of graph problems via the framework from Section 3. For showing a lower bound on the energy complexity of listing all triangles in the graph, we directly apply Lemma 1, whereas, subsequently, we use Corollary 6 for graph problems, whose hardness is based on a reduction from set disjointness. ▶ Corollary 7 (Triangle Listing). For triangle listing, where every triangle in the
graph is output by at least one of its nodes, the worst case energy complexity is Ω n1/3 / log n rounds for algorithms that fail with some small constant probability ϵ > 0. For local triangle listing, which requires every node to output all triangles that it is part of, we obtain a lower bound of Ω(n/ log n) that holds even for the expected node-averaged energy complexity. Proof. We make use of the existing lower bounds for the CONGEST model of [34, 42]. In more detail, we adapt the proof of Theorem 4.1 in [34], where they
show that the node who outputs the maximum number of triangles needs to learn Ω n4/3 bits (on average) about the edges E of an Erdös-Renyi random graph Gn,1/2 .

DISC 2026

13:14

Tight Energy Lower Bounds for Distributed Graph Algorithms

We use N = n(n−1)(n−2) to denote the maximum possible number of triangles in any 6 n-node graph. Define w to be a node chosen uniformly at random (note that w itself is a random variable), and let Tw denote the set of triangles output by w. In the proof of Theorem 4.1 in [34], they show that, if w is not a randomly chosen node, but instead the node that outputs the maximum number of triangles, then √  2/3   2 N N I[E : Tw ] ≥ · Pr |Tw | ≥ . (10) 3 16n 16n We now argue that an asymptotically-equivalent bound also holds for a randomly chosen w, under the assumption that each triangle needs to be output by at least one of its constituting N nodes. Since there are N8 triangles in expectation, [34] show that there are at least 16 1 triangles with probability at least 15 by the (reverse) Markov’s inequality. Condition on this event. Observing that each node is in at most O(n2 ) = O(N/n) triangles, implies that a constant fraction of the nodes must output
at least Ω(N/n) each. Since w is chosen uniformly at random, it follows that |Tw | ≥ Ω N n happens with constant probability, and thus (10) tells us that  2/3 ! N I[E : Tw ] = Ω . (11) n Let Sw denote the initial state of w, which includes the knowledge of its incident edges and let Πw be the transcript of the messages received by w. We aim to apply Lemma 1 with U = {w}, and thus we need to derive a suitable lower bound on I[E : Πw | Sw ]. Observe that Tw is a function of Πw , Sw , and the private randomness of w. By the data-processing inequality (see Fact 2.6) we obtain that I[E : Πw | Sw ] ≥ I[E : Tw | Sw ] (by (3)) (since w has ≤ n − 1 incident edges) (by Fact 2.1) (by (3)) (by (11))

= H[E | Sw ] − H[E | Sw , Tw ] ≥ H[E] − (n − 1) − H[E | Sw , Tw ] ≥ H[E] − (n − 1) − H[E | Tw ] = I[E : Tw ] − (n − 1)   = Ω n4/3

(12)

To complete the proof of the worst-case energy complexity bound, we instantiate Lemma 1(ii)
with VA = U = {w}, VB = ∂U = V (G) \ {w}, dU = n − 1, Z = E, and L = Θ n4/3 . Note that there is no dependency between the algorithm’s output and the choice of the cut (VA , VB ), as the latter only depends on the randomly chosen node w. This shows that node
1/3 w has a worst-case energy complexity of Ω n / log n . Next, we prove the node-averaged bound of Ω(n/ log n) for local triangle listing. Let P(Tv ) denote the set of edges that are part of the triangles output by node v. From Lemma 4.3 of [34], it follows that I[E : Tv ] = E[|P(Tv )|], for any
v. Since v needs to output all its triangles, (11) can be strengthened to yield I[E : Tv ] = Ω n2 (as argued in Proposition 4.4
of [34]), and this holds for any node v. Analogously to (12), we obtain I[E : Πv | Sv ] = Ω n2 . Before we can instantiate Lemma 1(i) with VA = U = {v}, Z = E, VB = ∂U = V (G) \ {v}, dU = n − 1,
2 and L = Θ n2 , we need to verify that |supp(Z)| ≤ 2c·L = 2c·Θ(n ) , which indeed holds for a suitable constant c. This shows that v requires Ω(n/ log n) awake rounds in expectation. Since the above holds for any v, the claimed bound on the node-averaged energy complexity follows. ◀

F. Dufoulon, G. Pandurangan, and P. Robinson

13:15

▶ Corollary 8. For s-clique listing, where every s-clique in the graph
is output by at least one of its nodes, the worst case energy complexity is Ω n1−2/s / log n rounds for algorithms that fail with some small constant probability ϵ > 0. Proof. As explained in [26], the proof is analogous to the lower bound for triangle enumeration by [34], with the crucial difference being the use of Lemma 1.3 of [26] to bound the number of s-cliques in any graph with a given number of edges. ◀ We now turn our attention to graph problems for which the existing lower bound constructions are based on reductions from the set disjointness function. By virtue of Corollary 6, we immediately obtain lower bounds on the energy complexity of several important graph problems: set, or ▶ Corollary 9. Computing an exact minimum vertex cover, maximum   independent 2 minimum dominating set has a node-averaged energy complexity of Ω logn2 n in expectation. Proof. In [25], it is shown that these problems admit an ℓ-separated lower bound family with respect to the set disjointness function DISJΘ(n2 ) , for ℓ = Θ(n/ log n). The result follows from Corollary 6. ◀ ▶ Corollary 10. Computing the exact network diameter with ϵ error, for some small constant ϵ > 0, has a node-averaged energy complexity of Ω(n/ log n) in expectation. The same bound holds for computing exact all-pair-shortest-paths (APSP) routing tables. Proof. It is straightforward to verify that the lower bound construction of [27] has all the important properties of a 2-separated graph family with respect to DISJΘ(n2 ) and the graph predicate P for deciding whether the diameter is at most 4. Since there are Θ(n)-nodes in |V1+ | and |V2− | that form a perfect matching, we know that dcut = 1, and the maximum cut size is s = Θ(n). Applying Corollary 6 completes the proof. ◀ ▶ Corollary 11. In any undirected, weighted graph G, or directed, unweighted graph G, computing the exact Minimum Weight Cycle with ϵ error, for some small constant ϵ > 0, has a node-averaged energy complexity of Ω(n/ log n) in expectation. Proof. It is straightforward to verify that the lower bound constructions of [38] both have all the important properties of a 2-separated graph family with respect to DISJΘ(n2 ) and the graph predicate P for deciding, respectively, whether there exists a directed cycle of length at most 4 and a cycle of weight at most 6, whereby the cut set size (for both constructions) is s = Θ(n). Moreover, the edges in the (only) cut form a perfect matching and hence dcut = 1, and we can apply Corollary 6 to complete the proof. ◀

5

Conclusion

In this paper, we presented an information-theoretic framework for showing polynomial (in n) lower bounds for various fundamental graph problems. These energy lower bounds almost match (up to logarithmic factors) their respective round lower bounds. Hence, it is not fruitful to design distributed algorithms for these problems that achieve significantly lower energy complexity than their round complexity. The good news is that our technique can be used to establish energy lower bounds, provided we have suitable communication-complexity lower bounds that are sufficiently large (e.g., polynomial in n). There are still several problems, such as minimum cut and maximum matching, where we do not have (almost) matching energy bounds, which are worth studying.

DISC 2026

13:16

Tight Energy Lower Bounds for Distributed Graph Algorithms

References 1

2 3

4 5

6

7

8

9

10

11 12 13

14

15

16

Amir Abboud, Keren Censor-Hillel, and Seri Khoury. Near-linear lower bounds for distributed distance computations, even in sparse networks. In Cyril Gavoille and David Ilcinkas, editors, Distributed Computing - 30th International Symposium, DISC 2016, Paris, France, September 27-29, 2016. Proceedings, volume 9888 of Lecture Notes in Computer Science, pages 29–42. Springer, 2016. Amir Abboud, Keren Censor-Hillel, Seri Khoury, and Ami Paz. Smaller cuts, higher lower bounds. ACM Trans. Algorithms, 17(4):30:1–30:40, 2021. John Augustine, William K. Moses Jr., and Gopal Pandurangan. Awake complexity of distributed minimum spanning tree. In Yuval Emek, editor, Structural Information and Communication Complexity - 31st International Colloquium, SIROCCO 2024, Vietri sul Mare, Italy, May 27-29, 2024, Proceedings, volume 14662 of Lecture Notes in Computer Science, pages 45–63. Springer, 2024. Baruch Awerbuch, Oded Goldreich, David Peleg, and Ronen Vainish. A trade-off between information and communication in broadcast protocols. J. ACM, 37(2):238–256, 1990. Nir Bacrach, Keren Censor-Hillel, Michal Dory, Yuval Efron, Dean Leitersdorf, and Ami Paz. Hardness of distributed optimization. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, pages 238–247, 2019. Alkida Balliu, Pierre Fraigniaud, Dennis Olivetti, and Mikaël Rabie. Solving sequential greedy problems distributedly with sub-logarithmic energy cost. In Alkida Balliu and Fabian Kuhn, editors, Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC 2025, Hotel Las Brisas Huatulco, Huatulco, Mexico, June 16-20, 2025, pages 417–427. ACM, 2025. Dominick Banasik, Varsha Dani, Fabien Dufoulon, Aayush Gupta, Thomas P. Hayes, and Gopal Pandurangan. Energy-efficient maximal independent sets in radio networks. In Proceedings of the 39th International Symposium on Distributed Computing (DISC), pages 14:1–14:24, 2025. Boaz Barak, Mark Braverman, Xi Chen, and Anup Rao. How to compress interactive communication. In Leonard J. Schulman, editor, Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages 67–76. ACM, 2010. Leonid Barenboim and Tzalik Maimon. Deterministic logarithmic completeness in the distributed sleeping model. In 35th International Symposium on Distributed Computing, DISC, volume 209, pages 10:1–10:19, 2021. Keren Censor-Hillel, Yi-Jun Chang, François Le Gall, and Dean Leitersdorf. Tight distributed listing of cliques. In Proceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’21, page 2878–2891, USA, 2021. Society for Industrial and Applied Mathematics. Keren Censor-Hillel, Seri Khoury, and Ami Paz. Quadratic and near-quadratic lower bounds for the congest model. In 31 International Symposium on Distributed Computing, 2017. Yi-Jun Chang. The energy complexity of diameter and minimum cut computation in boundedgenus networks. Theoretical Computer Science, 982:114279, 2024. Yi-Jun Chang, Varsha Dani, Thomas P. Hayes, Qizheng He, Wenzheng Li, and Seth Pettie. The energy complexity of broadcast. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, pages 95–104, 2018. Yi-Jun Chang, Varsha Dani, Thomas P. Hayes, and Seth Pettie. The energy complexity of bfs in radio networks. In Proceedings of the 39th Symposium on Principles of Distributed Computing, pages 273–282, 2020. Yi-Jun Chang, Tsvi Kopelowitz, Seth Pettie, Ruosong Wang, and Wei Zhan. Exponential separations in the energy complexity of leader election. ACM Trans. Algorithms, 15(4):49:1– 49:31, 2019. Conference version: ACM STOC 2017. Yi-Jun Chang, Seth Pettie, Thatchaphol Saranurak, and Hengjie Zhang. Near-optimal distributed triangle enumeration via expander decompositions. J. ACM, 68(3), May 2021.

F. Dufoulon, G. Pandurangan, and P. Robinson

17

18 19 20

21

22

23 24

25

26

27

28 29

30

31

32

33

13:17

Soumyottam Chatterjee, Robert Gmyr, and Gopal Pandurangan. Sleeping is efficient: MIS in O(1)-rounds node-averaged awake complexity. In ACM Symposium on Principles of Distributed Computing, PODC, pages 99–108, 2020. T. Cover and J.A. Thomas. Elements of Information Theory, second edition. Wiley, 2006. Yuval Dagan, Yuval Filmus, Hamed Hatami, and Yaqiao Li. Trading information complexity for error. In 32nd Computational Complexity Conference, 2017. Varsha Dani, Aayush Gupta, Thomas P. Hayes, and Seth Pettie. Wake up and join me! an energy-efficient algorithm for maximal matching in radio networks. Distributed Comput., 36(3):373–384, 2023. Varsha Dani and Thomas P. Hayes. How to wake up your neighbors: Safe and nearly optimal generic energy conservation in radio networks. In Christian Scheideler, editor, 36th International Symposium on Distributed Computing, DISC 2022, October 25-27, 2022, Augusta, Georgia, USA, volume 246 of LIPIcs, pages 16:1–16:22, 2022. Atish Das Sarma, Stephan Holzer, Liah Kor, Amos Korman, Danupon Nanongkai, Gopal Pandurangan, David Peleg, and Roger Wattenhofer. Distributed verification and hardness of distributed approximation. SIAM J. Comput., 41(5):1235–1265, 2012. Fabien Dufoulon, Pierre Fraigniaud, Mikaël Rabie, and Hening Zheng. Distributed coloring in the SLEEPING model. CoRR, abs/2405.10058, 2024. Fabien Dufoulon, William K. Moses Jr., and Gopal Pandurangan. Distributed MIS in O(log log n) awake complexity. In Rotem Oshman, Alexandre Nolin, Magnús M. Halldórsson, and Alkida Balliu, editors, Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing, PODC 2023, Orlando, FL, USA, June 19-23, 2023, pages 135–145. ACM, 2023. Fabien Dufoulon, Shreyas Pai, Gopal Pandurangan, Sriram V. Pemmaraju, and Peter Robinson. The message complexity of distributed graph optimization. In Venkatesan Guruswami, editor, 15th Innovations in Theoretical Computer Science Conference, ITCS 2024, January 30 to February 2, 2024, Berkeley, CA, USA, volume 287 of LIPIcs, pages 41:1–41:26. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. Orr Fischer, Tzlil Gonen, Fabian Kuhn, and Rotem Oshman. Possibilities and impossibilities for distributed subgraph detection. In Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures, pages 153–162, 2018. Silvio Frischknecht, Stephan Holzer, and Roger Wattenhofer. Networks cannot compute their diameter in sublinear time. In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms, pages 1150–1162. SIAM, 2012. Mohsen Ghaffari and Julian Portmann. Average awake complexity of MIS and matching. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 45–55, 2022. Mohsen Ghaffari and Julian Portmann. Distributed MIS with low energy and time complexities. In Rotem Oshman, Alexandre Nolin, Magnús M. Halldórsson, and Alkida Balliu, editors, Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing, PODC 2023, Orlando, FL, USA, June 19-23, 2023, pages 146–156. ACM, 2023. Mohsen Ghaffari and Anton Trygub. A near-optimal low-energy deterministic distributed SSSP with ramifications on congestion and APSP. In Ran Gelles, Dennis Olivetti, and Petr Kuznetsov, editors, Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing, PODC 2024, Nantes, France, June 17-21, 2024, pages 401–411. ACM, 2024. Qiang-Sheng Hua, Haoqiang Fan, Lixiang Qian, Ming Ai, Yangyang Li, Xuanhua Shi, and Hai Jin. Brief announcement: A tight distributed algorithm for all pairs shortest paths and applications. In Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures, pages 439–441, 2016. Dawei Huang, Seth Pettie, Yixiang Zhang, and Zhijun Zhang. The communication complexity of set intersection and multiple equality testing. SIAM Journal on Computing, 50(2):674–717, 2021. Russell Impagliazzo and Ryan Williams. Communication complexity with synchronized clocks. In Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC 2010,

DISC 2026

13:18

Tight Energy Lower Bounds for Distributed Graph Algorithms

34

35 36 37 38

39

40 41 42

43 44

Cambridge, Massachusetts, USA, June 9-12, 2010, pages 259–269. IEEE Computer Society, 2010. Taisuke Izumi and François Le Gall. Triangle finding and listing in congest networks. In Proceedings of the ACM Symposium on Principles of Distributed Computing, pages 381–389, 2017. 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. Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer. Local computation: Lower and upper bounds. Journal of the ACM, 63(2), 2016. Shay Kutten, Gopal Pandurangan, David Peleg, Peter Robinson, and Amitabh Trehan. On the complexity of universal leader election. J. ACM, 62(1), 2015. Vignesh Manoharan and Vijaya Ramachandran. Brief announcement: Near optimal bounds for replacement paths and related problems in the congest model. In Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing, PODC’22, page 369–371, New York, NY, USA, 2022. Association for Computing Machinery. Vignesh Manoharan and Vijaya Ramachandran. Computing minimum weight cycle in the CONGEST model. In Ran Gelles, Dennis Olivetti, and Petr Kuznetsov, editors, Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing, PODC 2024, Nantes, France, June 17-21, 2024, pages 182–193. ACM, 2024. James L Massey. Guessing and entropy. In Proceedings of 1994 IEEE International Symposium on Information Theory, page 204. IEEE, 1994. Gopal Pandurangan, David Peleg, and Michele Scquizzato. Message lower bounds via efficient network synchronization. Theor. Comput. Sci., 810:82–95, 2020. Gopal Pandurangan, Peter Robinson, and Michele Scquizzato. On the distributed complexity of large-scale graph computations. ACM Transactions on Parallel Computing (TOPC), 8(2):1–28, 2021. David Peleg. Distributed Computing: A Locality-sensitive Approach. Society for Industrial and Applied Mathematics, 2000. Peter Robinson. Being fast means being chatty: The local information cost of graph spanners. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2105–2120. SIAM, 2021.

F. Dufoulon, G. Pandurangan, and P. Robinson

13:19

Appendix A

Proof of Lemma 1 (Cut-based Energy Lower Bound)

Consider an algorithm A that satisfies the premise of the lemma. In our analysis, we assume that |supp(Z)| ≤ 2c·L and mainly focus on proving (i). Wherever necessary, we explain how to make the argument work for (ii) (i.e., without the upper bound on the support size). ▶ Definition 12. The extended transcript Π̂ consists of the (non-empty) messages that the nodes in U receive from ∂U , whereby we augment each message with the corresponding round number in which it was sent. Formally, let random variable M be the total number of messages the nodes in U receive over all rounds from their neighbors in ∂U . We define Π̂ = ((R1 , Π̂1 ), . . . , (RM , Π̂M )). Random variables R1 ≤ · · · ≤ RM are specific round numbers; for convenience, we define R0 = 0. Each Π̂i corresponds to a non-empty message m that a node u ∈ U receives from a node in ∂U during round Ri . Note that Π̂i includes the source ID and destination ID. See Figure 1b for an example of an extended transcript. Note that it is perfectly possible (and even likely for some algorithms) that a node in U wakes up in some round without receiving any message from a neighbor in ∂U . We define the sequence of wasted awake rounds W = ((W1 , u1 ), (W2 , u2 ), . . .), where Wi ≤ Wi+1 , to be the sequence of round-node pairs, such that ui ∈ U wakes up in round Wi without receiving any (non-empty) message from ∂U . We cannot simply ignore such rounds, as a node in U may infer some information about Z also from the absence of any message from ∂U . Nevertheless, the reason why we do not need to explicitly include the wasted awake rounds in the extended transcript Π̂ is that the entire sequence can be computed from Π̂ and the initial state of the nodes in VA (which includes the nodes in U ). The next lemma formalizes this intuition. Its proof follows by induction over the extended transcript: ▶ Lemma 13. The sequence of wasted awake rounds W of the nodes in U is a deterministic function of the extended transcript Π̂ and the initial state SVA of the nodes in VA , Proof. The proof follows by induction over the extended transcript. To keep the notation simple, we assume that R1 < · · · < RM ; it is straightforward to extend the proof to the general case where R1 ≤ · · · ≤ RM . Formally, we show the following claim: For all i ∈ [M ], the prefix (R≤i−1 , Π̂≤i−1 ) of Π̂ together with the initial state SVA determine the prefix (W≤ji , u≤ji ) of W, where ji is the largest index such that rounds W1 ≤ · · · ≤ Wji < Ri . For the base case (i = 1), R0 = 0 and Π̂0 is empty by definition. Thus, it will be sufficient to show that all wasted awake rounds occurring prior to round R1 , i.e., before the first message from ∂U is received by some node in U , are fully determined by the initial state SVA . For every u ∈ U , the timing of u’s next wake up step is a deterministic function of SVA , as this determines all communication that u may receive from its neighbors in G \ ∂U , all of which are in VA . Thus the prefix (W≤j1 , u≤j1 ) of W is a function of SVA as well. For the induction step, assume that the statement holds for some i ∈ [M ], i.e., the prefix (R≤i−1 , Π̂≤i−1 ) and SVA already determine all wasted awake steps (W≤ji , u≤ji ) prior to round Ri . Our goal is to show that the additional knowledge of the pair (Ri , Π̂i ) suffices to compute all wasted awake steps prior to Ri+1 . By the inductive hypothesis, the prefix (W≤ji , uji ) up

DISC 2026

13:20

Tight Energy Lower Bounds for Distributed Graph Algorithms

to the end of round Ri − 1 is fully determined by SVA and the prefix (R≤i−1 , Π̂≤i−1 ). Clearly, this is also sufficient to determine the state of each node in VA at the start of round Ri . Consequently, knowing (Ri , Π̂i ) allows us to deterministically compute the state (and wake up steps) of all nodes in VA during round Ri , and, in fact, the same applies to all subsequent rounds in which no message is received by a node in U from ∂U . Hence, we have sufficient information to compute the states of the nodes in VA up until the end of round Ri+1 − 1. ◀ Since ΠU denotes only the transcript of the messages received by nodes in U from ∂U , whereas the extended transcript Π̂ contains these same messages together with their respective round numbers and source/destination IDs, ΠU is deterministically recoverable from Π̂. Thus, by the data processing inequality (see Fact 2.6), we have that h I Π̂ : Z

i SVA ≥ I[ΠU : Z | SVA ] ≥ L.

(13)

Before deriving an upper bound on the mutual information in (13), we first define some additional notation. In Figure 3, we provide a list of variables used throughout the proof. We use X<i as a shorthand for X1 , . . . , Xi−1 , when considering a sequence of random variables, and we define X≤i similarly. Below, we use |X| to denote the worst case length of an optimal encoding of a random variable X, i.e., |X| ≤ log2 |supp(X)|. We first state some bounds that we rely on in our analysis. By the premise of the lemma, we have L ≤ nc1 ,

(14)

for some constant c1 > 0. Moreover, recall that we assume that the message size is at most logarithmic, i.e., there is some constant c2 > 0 such that, for every i, we have |Π̂i | ≤ c2 log n.

(15)

Recall that c > 0 is the constant specified in Property (i) of the lemma. We also introduce a constant C, where C ≥ 4c(c1 + c2 + 2).

(16)

Finally, we define the bounds β and M̄ such that β=

L , C · dU log n

M̄ = 2c · β · dU .

(17) (18)

Note that we assume L = ω(dU log n) throughout the proof, as otherwise the resulting lower bound is trivial. We are now ready to start our analysis. Assume towards a contradiction that the given algorithm satisfies E[αU ] ≤ β.

(19)

Whenever a node u ∈ U is awake in a given round, it may receive messages from up to e(u, ∂U ) ≤ dU neighbors in ∂U . Thus, we can bound the expectation of the number M of pairs (Ri , Π̂i ) in Π̂ as E[M ] ≤ E[αU ] · dU . Notice that the event M ≤ M̄ occurs with

F. Dufoulon, G. Pandurangan, and P. Robinson

Variable αU β dU e(U, ∂U ) E, 1E L M̄ M Π̂ ΠU (Ri , Π̂i ) SVA U ∂U (VA , VB ) Z

13:21

Description total number of awake rounds summed over the nodes in U assumed upper bound on αU maximum number of neighbors in ∂U of any node in U the number of edges across the cut event E occurs if M ≤ M̄ ; 1E is its indicator random variable amount of information that the nodes in U need to learn about Π̂ upper bound on M actual length of the extended transcript Π̂ extended transcript (see Def. 12) transcript of messages sent from ∂U to U message Π̂i was sent in round Ri initial knowledge of the nodes in VA nodes in VA that have an edge to VB nodes in VB that have an edge to VA vertex cut that we are focusing on function of the graph about which the nodes in U need to learn something

Figure 3 List of variables and parameters used in the proof of Lemma 1. 1 probability at least 1 − 2c by Markov’s inequality. Let E denote the event M ≤ M̄ and let 1E be the indicator random variable for this event. By Fact 2.1, h i h i I Π̂ : Z SVA ≤ I Π̂ : 1E , Z SVA h i h i (by Fact 2.2) = I Π̂ : Z SVA , 1E + I Π̂ : 1E SVA h i (by Fact 2.5) ≤ I Π̂ : Z SVA , 1E + 1 h i h i (since ¬E is {M > M̄ }) = Pr[1E = 1] I Π̂ : Z SVA , E + Pr[1E = 0] I Π̂ : Z SVA , M > M̄ + 1 i h  1  ≤ I Π̂ : Z SVA , E + H Z M > M̄ + 1 2c h i
1 (by Fact 2.4) ≤ I Π̂ : Z SVA , E + log2 |supp(Z | M > M̄ )| + 1, 2c h i 1 ≤ I Π̂ : Z SVA , E + log2 (|supp(Z)|) + 1, 2c

where, in the final inequality, we have used the fact that conditioning on an event cannot increase the support of a random variable.4 Applying the upper bound on |supp(Z)| guaranteed by the premise in (i), we obtain h i h i L I Π̂ : Z SVA ≤ I Π̂ : Z SVA , E + + 1. (20) 2 To see why (20) also holds for algorithms satisfying only (ii) and not the bound on the support in (i), observe that the event M ≤ β · dU ≤ M̄ holds with probability 1 for algorithms that guarantee a worst case upper bound on the number of awake rounds. For any j ≥ M + 1, we define Rij = ∞ and Π̂j = ⟨⟩ (i.e., the empty message), which h in particular implies that H Rj , Π̂j = 0. Next, we derive an upper bound on the term

4

To see that |supp(Z | E)| ≤ |supp(Z)|, for any event E, it suffices to observe that ∀z : Pr[Z = z | E] = Pr[Z=z∧E] ≤ Pr[Z=z] Pr[E] Pr[E] . Note that conditioning on E may increase the entropy of Z nevertheless.

DISC 2026

13:22

Tight Energy Lower Bounds for Distributed Graph Algorithms

h I Π̂ : Z

i SVA , E on the right-hand side of (20). We get h I Π̂ : Z

i h SVA , E ≤ H Π̂

(by Fact 2.3 and Def. 12)

=

M̄ X

SVA , E

h H Ri , Π̂i

i

R<i , Π̂<i , SVA , E

i

(21)

i=1

Returning to (20), we get h I Π̂ : Z

M̄ i X h SVA ≤ H Ri , Π̂i i=1

i L R<i , Π̂<i , SVA , E + + 1. 2

(22)

Combining the upper bound in (22) with the lower bound in (13) shows that there must exist an index i∗ such that h i L/2 − 1 H Ri∗ , Π̂i∗ R<i∗ , Π̂<i∗ , SVA , E ≥ M̄ L/2 (by (18)) = − o(1) 2cβ · dU C (by (17)) = log n − o(1). (23) 4c Without loss of generality, assume that i∗ is the smallest such index. Rewriting the entropy on the left-hand side via the chain rule (see Fact 2.3) yields h i h i H Ri∗ , Π̂i∗ R<i∗ , Π̂<i∗ , SVA , E = H Ri∗ R<i∗ , Π̂<i∗ , SVA , E h i + H Π̂i∗ Ri∗ , R<i∗ , Π̂<i∗ , SVA , E h i (by Fact 2.5) ≤ H Ri∗ R<i∗ , Π̂<i∗ , SVA , E + |Π̂i∗ | h i (by (15)) ≤ H Ri∗ R<i∗ , Π̂<i∗ , SVA , E + c2 log n. Due to the lower bound in (23), we get  h i C ∗ ∗ ∗ H Ri R<i , Π̂<i , SVA , E ≥ − c2 log n − o(1). 4c

(24)

Let U∗ ⊆ U be the nodes that receive a message from some v ∈ ∂U in round Ri∗ . (Note that it may be the case that Ri∗ = Ri∗ +1 = · · · = Ri∗ +ℓ , and in that case, multiple nodes may receive a message from their neighbors in ∂U in the same round.) The intuition behind (24) is that the exact value of Ri∗ is not known to the nodes in U∗ and thus they may need to guess a number of times before one of them wakes up in the correct round. Of course, when “guessing” Ri∗ , the nodes in U∗ may take into account all earlier received messages and the respective rounds in which they were sent, as well as the earlier unsuccessful wake up attempts in which they did not receive any message. This is represented by the conditioning on events R<i∗ = r, Π̂<i∗ = π, SVA = s, and E. Note that we provide more power to the algorithm by assuming that all nodes in U∗ know SVA , as well as all messages received so far by any node in U . In fact, random variable R′ := (Ri∗ | R<i∗ = r, Π̂<i∗ = π, SVA = s, E) includes conditioning on the (joint) knowledge of the nodes in U∗ (as well as the initial states of all other nodes in VA ), and assumes that—in contrast to reality—the nodes even know that event E occurs, which can only strengthen the lower bound. In addition, every node in

F. Dufoulon, G. Pandurangan, and P. Robinson

13:23

U∗ knows, in round r, all earlier wake up steps of other nodes in U , in which they did not receive any message from ∂U , which is justified due to Lemma 13. Due to the assumption that (U, ∂U ) is an edge cut, it is clear that a node u ∈ U∗ cannot gain any information about R<i∗ by receiving a message from other nodes in U (or VA ), as that knowledge is already part of the given conditioning. Thus, we can interpret each subsequent wake-up of u in some round k as a single guess of the form “Ri∗ = k?”. The work of Massey [40] shows that guessing the value of a random variable X in this manner requires at least 2H[X]−2 + 1 guesses in expectation. Let T be the total number of times that some node in U∗ wakes up until one of them succeeds in guessing the correct round Ri∗ . Applying the aforementioned result of [40], we get h i   E T R<i∗ = r, Π̂<i∗ = π, SVA = s, E = Ω 2H[Ri∗ | R<i∗ =r,Π̂<i∗ =π,SVA =s,E ] . (25) Let 1E be the indicator random variable for event E, which is 1 if M ≤ M̄ . To shorten the notation, we define random variable Y = (R<i∗ , Π̂<i∗ , SVA ). We have h i E[αU ] ≥ E[T ] = E E[ T | Y = y, 1E = b] y∼Y,b∼1E   h i 1 1 (since Pr[E] ≥ 1 − ) ≥ 1− E E[ T | Y = y, E] E 2c 2c  h  i 1 E 2(H[Ri∗ | Y=y, E ] − 2) E (by (25)) ≥ 1− 2c   1 (by Jensen’s inequality) ≥ 1− 2(E[H[Ri∗ | Y=y, E ] | E ] − 2) 2c   1 (by (2)) ≥ 1− 2(H[Ri∗ | Y,E ] − 2) 2c   C 1 2( 4c −c2 ) log n−2−o(1) (by (24)) ≥ 1− 2c   C = Ω 2( 4c −c2 ) log n−3
(by (16)) = Ω nc1 +2 . (26) However, according to (14), we have L ≤ nc1 , and thus we have arrived at a contradiction to the assumed upper bound on E[αU ], which completes the proof of Property (i). Similarly to the above, we can conclude that Property (ii) also holds, due to the event E occurring with probability 1 for algorithms that have a (per node) worst case upper bound on the number of awake rounds. This completes the proof of Lemma 1.

DISC 2026

Related documents

• Towards tight communication lower bounds for distributed optimisation#308502
• Dense Interprocedural Dominance in Acyclic Graphs: Context Bounds and Compact Queries#1064362
• The 11/6 supremum of the Wang-Sitters rounding scheme for graph balancing#998384
• Distributed Stochastic Graph Algorithms#216792
• Distributed Santa Claus via Global Rounding#1084194