Introducing the Self-Stabilizing SLEEPING Model
2026-08-24 • Distributed, Parallel, and Cluster Computing
Distributed, Parallel, and Cluster Computing
AI summaryⓘ
The authors introduce a way to save energy in distributed computing systems by allowing nodes to sleep or wake up during operation, which reduces how often they need to be active. They extend this idea to self-stabilizing systems, where nodes must eventually fix errors on their own. Their work focuses on balancing how quickly the system stabilizes with how much energy nodes use by being awake. They provide new energy-efficient algorithms for classic network problems and methods to adapt existing algorithms to use these energy-saving techniques.
Distributed algorithmsSynchronous LOCAL modelSelf-stabilizationAwake complexityEnergy efficiencyGraph coloringMaximal Independent SetMaximal MatchingSilent algorithms
Authors
Tistou Fages, Colette Johnen, Mikaël Rabie
Abstract
The SLEEPING LOCAL model introduces a new complexity parameter, the awake complexity, to make distributed algorithms energy-efficient. In the synchronous LOCAL model, nodes can now decide to be awake or asleep in each round. In a round, only awake nodes can communicate to share information, which consumes energy. The awake complexity is the maximum number of times a node is activated to produce an output. In particular, it often comes at the cost of the total number of rounds required to solve a problem, compared with algorithms in which every node is awake in every round. In this article, we adapt the notion of awaken rounds to the context of self-stabilization, introducing the Self-Stabilizing SLEEPING model. Nodes are no longer required to remain awake at all times. However, in self-stabilization, nodes must be activated infinitely often to detect any issue in the system's current state. In this model, the complexities are: * How many synchronous rounds are needed to reach a legitimate configuration? * How many times does a node need to be awake to reach this configuration? * How often does a node need to be awake once this configuration is reached? The goal is to minimize those three metrics, and we can expect different trade-offs. We present energy-efficient algorithms to solve the problems of finding a $(Δ+1)$-coloring, a Maximal Independent Set, and a Maximal Matching, thanks to new ad hoc sleeping techniques that reduce the awake complexity (i.e., energy consumption) during the convergence phase. We also propose two transformers that adapt silent self-stabilizing algorithms to the SLEEPING setup. The first transformer is pretty simple and deals with low-complexity algorithms. The second is more elaborate and is more energy-efficient when it transforms slow self-stabilizing algorithms.