Time-Optimal and Energy-Efficient Deterministic Consensus

2025/06/14 by Meir, Shachar, Hugo Mirault, Mirault, Hugo +3
Computer Science · #Caching and Content Delivery #Data Structures and Algorithms (cs.DS) #Distributed #Distributed and Parallel Computing Systems #Distributed systems and fault tolerance #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)

paper · pdf · doi:10.48550/arxiv.2506.12282

openalex publication_date 2025/06/14 · openalex created_date 2025/10/13 · openalex updated_date 2026/07/28

Abstract

We study fault-tolerant consensus in a variant of the synchronous message passing model, where, in each round, every node can choose to be awake or asleep. This is known as the sleeping model (Chatterjee, Gmyr, Pandurangan PODC 2020) and defines the awake complexity (also called energy complexity), which measures the maximum number of rounds that any node is awake throughout the execution. Only awake nodes can send and receive messages in a given round and all messages sent to sleeping nodes are lost. We present new deterministic consensus algorithms that tolerate up to f

Citations

• Optimal Good-Case Latency for Sleepy Consensus
• On the Limits of Consensus under Dynamic Availability and Reconfiguration
• Solving Sequential Greedy Problems Distributedly with Sub-Logarithmic Energy Cost
• A Near-Optimal Low-Energy Deterministic Distributed SSSP with Ramifications on Congestion and APSP
• TOB-SVD: Total-Order Broadcast with Single-Vote Decisions in the Sleepy Model
• Asynchrony-Resilient Sleepy Total-Order Broadcast Protocols
• Distributed MIS with Low Energy and Time Complexities
• Recent Latest Message Driven GHOST: Balancing Dynamic Availability With Asynchrony Resilience
• Consensus in the Unknown-Participation Message-Adversary Model
• Distributed MIS in O(loglogn ) Awake Complexity
• Deterministic Logarithmic Completeness in the Distributed Sleeping Model
• The Energy Complexity of BFS in Radio Networks
• Sleeping is Efficient: MIS in O(1)-rounds Node-averaged Awake Complexity
• The Energy Complexity of Broadcast
• Locality in Distributed Graph Algorithms
• Impossibility of distributed consensus with one faulty process
• Authenticated Algorithms for Byzantine Agreement
• The Byzantine Generals Problem
• Reaching Agreement in the Presence of Faults

Related

• Fast Deterministic Consensus in a Noisy Environment
• Awake Complexity of Distributed Minimum Spanning Tree
• Fast Consensus under Eventually Stabilizing Message Adversaries
• Agreement Tasks in Fault-Prone Synchronous Networks of Arbitrary Structure
• Fault-Tolerant Consensus in Unknown and Anonymous Networks