CS Paper Radar

Introducing the Self-Stabilizing SLEEPING Model

Tistou Fages, Colette Johnen, Mikaël Rabie

cs.DC ·submitted 2026-08-24 09:50 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Approximating Minimum Dominating Set with Few Awake Rounds

cs.DC ·2026-08-19 ·Hongyan Ji, Shreyas Pai, Sriram V. Pemmaraju
top venue similarity 0.70
Abstract · Full version of the conference paper published in the proceedings of the 40th International Symposium on Distributed Computing (DISC 2026)

We study the Minimum Dominating Set (MDS) problem in the sleeping CONGEST model (Chatterjee, Gmyr, and Pandurangan, PODC 2020), a generalization of the standard CONGEST model, in which a node may sleep in some rounds and can only compute, send messages, or receive messages when it is awake. The awake complexity of an algorithm in this model is the worst case number (over all inputs and all nodes) of rounds a node is awake for during the execution of the algorithm. While there are several $O(\log Δ)$-approximation algorithms (in expectation) for MDS that run in $O(\log^2 Δ)$ rounds, all of these have $Ω(\log^2 Δ)$ awake complexity. Whether this awake complexity can be improved is the question that drives our work. We present the first $O(\log Δ)$-approximation algorithm for MDS with $O(\log Δ)$ awake complexity. The approximation guarantee holds in expectation, and the algorithm runs in $O(\log^2Δ)$ rounds. We can reduce the awake complexity further, but at the cost of approximation: we present, for any $1<α\le\min\{Δ,\log n\}$, an algorithm in the sleeping CONGEST model that computes an $\tilde{O}(α\log_αΔ)$-approximate dominating set in expectation in $\tilde{O}(\logΔ\cdot \log_α Δ)$ rounds with $\tilde{O}(\log_α Δ)$ awake complexity. Our results depend on a generalization of the CONGEST model Set Cover algorithm of Grunau, Mitrović, Rubinfeld, and Vakilian (SODA 2020) that we develop. This generalization computes an $O(p\cdot q\cdot\log_pΔ)$-approximate dominating set in $O(\log_pΔ\cdot\log_qΔ)$ rounds for parameters $1<p,q\leΔ$. Our sleeping CONGEST algorithms apply a variety of techniques including sampling-based estimation and scheduling using virtual binary trees to the aforementioned 2-parameter Set Cover algorithm.

0.48

Tight Energy Lower Bounds for Distributed Graph Algorithms

cs.DC cs.DS ·2026-08-19 ·Fabien Dufoulon, Gopal Pandurangan, Peter Robinson
published similarity 0.59
Abstract · To appear at DISC 2026

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.

0.48

Fully Fluctuating Sleepy Consensus from Minimal Assumptions

cs.DC ·2026-09-02 ·Javier Nieto, Yuval Efron, Joachim Neu, Ling Ren
published similarity 0.57
Abstract

Bitcoin's proof-of-work (PoW)-based protocol is remarkable for how little it asks of its participants. Not only can miners take breaks from work whenever they please, but it is almost unique in offering a path of contrition: corrupt miners can reclaim honest status simply by resuming mining on the longest chain. The protocol only requires that honest miners hold the majority of computational power at any given time. Analogous proof-of-stake (PoS) protocols, usually formalized via the sleepy model of Pass and Shi (2017), have fallen short of matching this robustness. In fact, sleepy consensus protocols in the plain PKI model must heavily restrict fluctuations in adversarial participation over time. The recent work of Efron, Neu, and Pitassi (2025) enables fully fluctuating participation in the sleepy model by introducing the external adversary model. Their protocol, however, relies on verifiable delay functions (VDFs), a strong cryptographic primitive that somewhat resembles PoW, by assuming that the adversary cannot compute sequential work significantly faster than honest nodes. In this work, we design a sleepy consensus protocol for fully fluctuating participation with an external adversary under an honest majority, from minimal assumptions: a public key infrastructure (PKI) and a verifiable random function (VRF). In particular, we make no VDF or hardware assumptions. Our key technique is graded wakeness, a novel primitive that allows nodes to form consistent opinions on which other nodes are awake. We further extend our protocol to handle uncorruption, where corrupt nodes return to honesty. This extension requires only a mild additional assumption on the unpredictability of VRF outputs for liveness.

0.29

Self-stabilising approximate clock synchronisation requires linear time

cs.DC ·2026-11-03 ·Joel Rybicki
theory similarity 0.57
Abstract

Synchronising the clocks of processes is a fundamental problem in distributed computing. We consider message-passing systems in which processes start in an arbitrary initial state (self-stabilisation) and up to $f$ processes may be non-transiently faulty. It is well known that synchronising clocks \emph{exactly} is at least as hard as consensus and requires $Θ(f)$ time. In contrast, without self-stabilisation, clocks can be synchronised \emph{approximately} much faster, in time independent of the number of non-transient faults [Srikanth and Toueg, JACM 1987; Welch and Lynch, Inf. Comput. 1988]. In this work, we show that deterministic self-stabilising approximate clock synchronisation tasks require $Ω(f)$ time to stabilise. This gives the first non-trivial time lower bound for these tasks, whose time complexity has remained open for over two decades [Dolev and Welch, JACM 2004; Dolev, Függer, Schmid and Lenzen, JACM 2014]. In particular, this answers the open question whether self-stabilising approximate clock synchronisation tasks are as hard as consensus or as easy as approximate agreement [Lenzen and Rybicki, JACM 2019]. The results show that guaranteeing \emph{both} transient and non-transient fault-tolerance simultaneously is expensive even for approximate synchronisation tasks. The lower bounds hold in a very strong model: the faulty processes can only crash, the local clocks of processes have no clock drift, and the message delay is bounded and known to all processes. The proof is based on a combinatorial topological argument showing that no fast finite-state protocol can ensure that the clocks behave consistently across all executions. To our knowledge, this is the first use of topological arguments to prove time lower bounds in the self-stabilising setting.

0.14

Ride, Raise, or Wake: A Theory of Light-Thread Placement on Multi-Tier Processors

cs.PF ·2026-10-18 ·Mohamed Amine Bergach
similarity 0.57
Abstract

hones and laptops now mix several kinds of cores, and each kind sits in its own voltage and clock domain. When a light thread arrives, should it run beside heavy threads on a fast cluster that is already awake, or wake a cluster of efficient cores? We answer with three costs. A thread can \emph{ride} an awake domain at the voltage other threads hold, \emph{raise} that voltage for everyone, or \emph{wake} a sleeping domain and pay its fixed power. From these costs follows a simple rule: ride while the thread's demand is below $r^*=Φ/(e_h-e_l)$, the fixed power of the cluster it would wake over the gap in energy per operation; otherwise wake the smallest tier that can serve it. The best tier is not monotone in demand: tiny threads ride high, medium threads wake a low tier, heavy threads go high again. Two common designs err on opposite sides of the rule: grouping a light thread with the heavy threads of its application overpays above the threshold, and an energy model without idle costs overpays below it. In a model with five tiers, grouping costs 80 to 145\% more energy than the rule, and more as tiers are added. Measurements on an Apple M6 anchor the parameters.

0.26

Dynamic Wakeup under Costly Collisions

cs.DC ·2026-09-28 ·Umesh Biswas, Maxwell Young
theory similarity 0.52
Abstract

The wakeup problem captures a fundamental symmetry-breaking challenge among devices sharing a communication channel. We study the dynamic setting, where packets become active at arbitrary times on a time-slotted multiple access channel. In each slot, a transmission succeeds if and only if exactly one packet transmits; two or more simultaneous transmissions cause a collision. The goal is to obtain a successful transmission quickly. Prior work on wakeup has largely focused on the number of slots until the first success, referred to as the latency. However, a collision may incur substantial additional delay, represented by a per-collision cost $C$. We therefore seek to control both latency and the collision cost of an execution, defined as $C$ times its number of collisions. We design and analyze a randomized algorithm for dynamic wakeup, Lowball, without collision detection or knowledge of the number of packets, $n$. Fix a constant $0<ε\le 1/2$. There is a constant $K>0$ such that, when $C\ge K\lg^{1/ε} n$, Lowball has expected latency $O(C^{1/2+ε}\ln C)$ and expected collision cost $O(\sqrt{C})$. Below this threshold, both expectations are $O(n\log^{Θ(1/ε)} n)$. These guarantees hold against an adaptive, non-anticipating adversary, and the algorithm succeeds with probability 1. For algorithms in which each packet's transmission probability depends only on $C$ and the packet's local age, with packets activated together using the same probability schedule, we prove that the maximum of expected latency and expected collision cost is $Ω(\sqrt{C})$.

0.23

Discount Yourself: Self-inclusive Freshness-weighted Gossip for Decentralised Learning under Client Outages

cs.LG cs.DC ·2026-10-20 ·Qiyuan Wang, Ke Xiao, Christos Anagnostopoulos
similarity 0.50
Abstract · 52 pages, 9 figures, 35 tables; includes appendices

Decentralised federated learning (DFL) trains personalised models on devices that average with their neighbours rather than with a central server. Real devices, however, are often offline for hours or days, and a client returning from an outage can recover only by aggregating the models its neighbourhood holds. We observe that the stalest of these models is usually the client's own, a case that existing staleness-aware rules, which discount only the models a client receives, do not address. We formalise aggregation after an outage as estimating the state of a fully available network and derive three principles. First, the receiver must be discounted like any neighbour. Every rule that weights it at least as much as each neighbour has an error that grows without bound with the outage, whereas discounting all candidates by relative staleness keeps the error bounded. Second, staleness must be measured as inherited lag rather than age, since local training resets a model's age but not the lag it absorbed from stale neighbours. We introduce the effective lag, which tracks this quantity at the cost of one scalar per message. Third, the discount must be steep, because absorbed lag persists in every later round. These principles define Self-inclusive Freshness-weighted Gossip (SFG), a family of drop-in aggregation rules with the communication and computation of decentralised federated averaging, whose guarantees hold for the stale receiver itself. On three image benchmarks and eight outage processes, including real smartphone availability traces, the lag-based members SFG-L and SFG-Cut consistently outperform decentralised federated averaging and recent age-of-information rules, and ablations show that each principle is necessary. The analysis also explains why tuned limited merging from gossip learning is effective.

0.17

Governing Equations of Human Sleep Macro-Structure:Symbolic Discovery from 1,106 Nights

cs.AI q-bio.QM ·2026-10-31 ·Junhui Gao
similarity 0.50
Abstract · 14 pages, 9 figures

Human sleep is organized into a small number of cycles per night: deep sleep dominates early cycles, REM lengthens toward morning, and light sleep clusters at cycle boundaries. These regularities have long been described qualitatively but never distilled into closed-form laws from large-scale data. A total of 1,106 nights (Sleep-EDF 153 + SHHS 953) are segmented into REM-anchored cycles, and four cycle-indexed statistics follow simple closed-form equations: cycle length declines nearly linearly (R^2=0.996), REM duration follows an inverted U (R^2=0.873), deep-sleep (N3) run length decays exponentially (R^2=0.987) with a time constant of 2.94 cycles, consistent with the homeostatic Process S of the two-process model, and light-sleep (N1) run length follows a U shape (R^2=0.956), confirming a "long-short-long" pattern across the night. The laws are reproduced by per-night differentiable fitting (142/142 and 773/773 nights converge), by unconstrained symbolic regression (PySR), and by a 500-night generative synthesizer built from them. Their robustness is established against the two main methodological threats: bootstrap CIs computed by resampling whole nights (1,000 replications) exclude zero for every shape term, and a five-level scan of the REM-merge segmentation threshold preserves every qualitative form. These appear to be the first closed-form laws governing the macro-structure of sleep, distilled and tested across an age-mixed sample (healthy young adults and community-based older adults).

0.29