Search papers, labs, and topics across Lattice.
This paper introduces a novel information-theoretic technique to establish tight energy lower bounds for distributed graph algorithms in the SLEEPING model, focusing on minimizing the awake complexity of nodes. By leveraging known lower bounds on communication complexity, the authors derive nearly optimal polynomial lower bounds for various fundamental problems, including triangle enumeration and All-Pairs Shortest Paths, demonstrating that significant energy savings are not achievable beyond the established round complexities. The findings reveal that the energy complexities for these problems align closely with their round complexities, indicating inherent limitations in energy efficiency for distributed algorithms.
Energy savings in distributed graph algorithms may be fundamentally limited, as shown by new lower bounds that match existing round complexities across multiple problems.
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.
