Energy-efficient distributed algorithms for synchronous networks

DOI10.1007/978-3-031-32733-9_21MaRDI QIDQ6148079zbMATH OpenOpenAlexFDO

Authors Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport, Ioan Todinca

Publication date 11 January 2024

Published in Structural Information and Communication Complexity (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2301.11988

zbMATH Keywords

energy efficiencysynchronous distributed algorithmsLOCAL and CONGEST models

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer system organization (68Mxx) Communication complexity, information complexity (68Q11)

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

Cites work

• scientific article; zbMATH DE number 7774261 (Why is no real title available?)
• Communication Complexity
• Distributed Computing: A Locality-Sensitive Approach
• Logical locality entails frugal distributed computation over graphs (extended abstract)
• On the power of the congested clique model
• Rounds in Communication Complexity Revisited
• Sleeping is Efficient: MIS in O (1)-rounds Node-averaged Awake Complexity
• The energy complexity of broadcast

Cited in

(1)

• Distributed MIS in O( n) awake complexity

This page was built for publication: Energy-efficient distributed algorithms for synchronous networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6148079)