2026-07-25T02:30:41Z
https://drops.dagstuhl.de/oai
oai:drops-oai.dagstuhl.de:25188
2026-03-19T12:59:22Z
ddc:004
open_access
Time-Optimal and Energy-Efficient Deterministic Consensus
Meir, Shachar
Mirault, Hugo
Peleg, David
Robinson, Peter
Distributed computing
Crash faults
Consensus
Energy complexity
Sleeping model
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 < n crash failures, where n is the number of nodes. Our algorithms match the optimal time complexity lower bound of f+1 rounds. For multi-value consensus, where the input values are chosen from some possibly large set, we achieve an energy complexity of πͺ(β fΒ² / n β) rounds, whereas for binary consensus, we show an algorithm to achieve πͺ(β f / βn β) energy complexity.
Schloss Dagstuhl β Leibniz-Zentrum fΓΌr Informatik
Shachar Meir and Hugo Mirault and David Peleg and Peter Robinson
2026
Is Part Of LIPIcs, Volume 361, 29th International Conference on Principles of Distributed Systems (OPODIS 2025)
InProceedings
Text
doc-type:ResearchArticle
publishedVersion
application/pdf
doi:10.4230/LIPIcs.OPODIS.2025.15
urn:nbn:de:0030-drops-251881
https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2025.15
eng
https://creativecommons.org/licenses/by/4.0/legalcode