Energy-Efficient Distributed Algorithms for Synchronous Networks

Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport, Ioan Todinca

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review


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(\text {poly}(n))$$ rounds in n-node networks. However, we show that insisting on algorithms running in $$O(\text {poly}(n))$$ rounds in the CONGEST model comes with a severe cost in terms of energy. Namely, there are problems requiring $$\varOmega (\text {poly}(n))$$ edge-activations (and thus $$\varOmega (\text {poly}(n))$$ node-activations as well) in the CONGEST model whenever solved by algorithms bounded to run in $$O(\text {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(\text {poly}(n))$$ rounds. Specifically, under this constraint, there is a problem with O(1) edge-activation complexity but $$\tilde{\varOmega }(n^{1/4})$$ node-activation complexity.

Original languageEnglish
Title of host publicationStructural Information and Communication Complexity - 30th International Colloquium, SIROCCO 2023, Proceedings
EditorsSergio Rajsbaum, Sergio Rajsbaum, Alkida Balliu, Dennis Olivetti, Joshua J. Daymude
PublisherSpringer Science and Business Media Deutschland GmbH
Number of pages20
ISBN (Print)9783031327322
StatePublished - 2023
Externally publishedYes
Event30th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2023 - Alcalá de Henares, Spain
Duration: 6 Jun 20239 Jun 2023

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13892 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference30th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2023
CityAlcalá de Henares


  • Energy efficiency
  • LOCAL and CONGEST models
  • Synchronous distributed algorithms


Dive into the research topics of 'Energy-Efficient Distributed Algorithms for Synchronous Networks'. Together they form a unique fingerprint.

Cite this