Tight Energy Lower Bounds for Distributed Graph Algorithms

Fabien Dufoulon, Gopal Pandurangan, Peter Robinson

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…