## 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(\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 language | English |
---|---|

Title of host publication | Structural Information and Communication Complexity - 30th International Colloquium, SIROCCO 2023, Proceedings |

Editors | Sergio Rajsbaum, Sergio Rajsbaum, Alkida Balliu, Dennis Olivetti, Joshua J. Daymude |

Publisher | Springer Science and Business Media Deutschland GmbH |

Pages | 482-501 |

Number of pages | 20 |

ISBN (Print) | 9783031327322 |

DOIs | |

State | Published - 2023 |

Externally published | Yes |

Event | 30th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2023 - Alcalá de Henares, Spain Duration: 6 Jun 2023 → 9 Jun 2023 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 13892 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 30th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2023 |
---|---|

Country/Territory | Spain |

City | Alcalá de Henares |

Period | 6/06/23 → 9/06/23 |

## Keywords

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