Solving Sequential Greedy Problems Distributedly with Sub-Logarithmic Energy Cost
Alkida Balliu, Pierre Fraigniaud, Dennis Olivetti, Mikaël Rabie · 2025
We study the awake complexity of graph problems that belong to the class O-LOCAL, which includes a subset of problems solvable by sequential greedy algorithms, such as (Δ + 1)-coloring and maximal independent set. It is known from previous work that, in n-node graphs of maximum degree Δ, any problem in the class O-LOCAL can be solved by a deterministic distributed algorithm with awake complexity O (log Δ + log* n).