Exponential Energy Savings in Local Distributed Graph Algorithms
This paper investigates the energy complexity of several well-studied (local) problems in distributed graph algorithms—namely, matching and vertex cover approximations, spanners, low-outdegree orientations, and set cover. We present randomized distributed algorithms that, while having round complexity almost matching the respective state of the art, achieve nearly exponentially smaller energy complexity. That is, in each of these algorithms, each node is awake for only an exponentially small fraction of the time, and the round complexity still remains almost the same as the best-known algorithm. During the rest of the rounds, the node does not perform any computation or communication (and any messages sent to it at that time go unheard). Some of our concrete results are as follows: • For (1 + ε)-approximate maximum matching and (2 + ε)-approximate minimum vertex cover, with any arbitrary constant ε > 0, we get energy complexity O(log log n) while retaining the familiar O(log n) round complexity. • For low out-degree orientation of edges, we get maximum outdegree O(λ)—where λ denotes the graph's arboricity—with O(log log n) energy complexity and in the familiar O(log n) round complexity, though assuming λ = Ω(log2 n). • We get linear size spanners with stretch O(log1+ε n), using O(log log n) energy and O(log1+ε n) rounds. These round complexity and stretch bounds almost match the familiar O(log n) bounds.