New paper proves energy savings impossible for key distributed graph algorithms

The SLEEPING model has emerged as a promising direction for energy-efficient distributed computing: nodes can sleep to save energy and only wake for a limited number of rounds. Prior work showed that fundamental problems like leader election, broadcast, MST, and MIS could achieve exponentially better energy complexity than their round complexity in the CONGEST model. That raised a tantalizing question: could similar huge energy gains be achieved for many other fundamental graph problems? A new paper from Fabien Dufoulon, Gopal Pandurangan, and Peter Robinson — accepted at DISC 2026 and available on arXiv (cs.DC/2608.18992) — answers that question with a firm no.

The authors develop a general information-theoretic framework that acts as a "plug-in" to derive energy lower bounds directly from known communication complexity lower bounds. Applying it to the standard CONGEST model, they obtain near-optimal (up to logarithmic factors) polynomial lower bounds on energy complexity — for both worst-case and average-case — for a host of important problems: triangle enumeration, All-Pairs Shortest Paths (APSP), diameter computation, minimum weight cycle, Maximum Independent Set (MaxIS), Minimum Dominating Set (MinDS), and Minimum Vertex Cover (MinVC). Crucially, these bounds exactly match the known round complexities of those problems. That means no algorithm can achieve the exponential energy savings seen for leader election or MST; the energy cost is intrinsically tied to the round cost. This settles a central open question in the SLEEPING model and gives algorithm designers a clear boundary: for these graph problems, energy is not a free lunch.