DROPS

Document

DOI: 10.4230/LIPIcs.OPODIS.2025.15

Time-Optimal and Energy-Efficient Deterministic Consensus

Authors: Shachar Meir, Hugo Mirault, David Peleg, and Peter Robinson

Published in: LIPIcs, Volume 361, 29th International Conference on Principles of Distributed Systems (OPODIS 2025)

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 < 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.

Cite as

Shachar Meir, Hugo Mirault, David Peleg, and Peter Robinson. Time-Optimal and Energy-Efficient Deterministic Consensus. In 29th International Conference on Principles of Distributed Systems (OPODIS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 361, pp. 15:1-15:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{meir_et_al:LIPIcs.OPODIS.2025.15,
  author =	{Meir, Shachar and Mirault, Hugo and Peleg, David and Robinson, Peter},
  title =	{{Time-Optimal and Energy-Efficient Deterministic Consensus}},
  booktitle =	{29th International Conference on Principles of Distributed Systems (OPODIS 2025)},
  pages =	{15:1--15:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-409-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{361},
  editor =	{Arusoaie, Andrei and Onica, Emanuel and Spear, Michael and Tucci-Piergiovanni, Sara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2025.15},
  URN =		{urn:nbn:de:0030-drops-251881},
  doi =		{10.4230/LIPIcs.OPODIS.2025.15},
  annote =	{Keywords: Distributed computing, Crash faults, Consensus, Energy complexity, Sleeping model}
}

Search Results

Documents authored by Mirault, Hugo

Time-Optimal and Energy-Efficient Deterministic Consensus

Abstract

Cite as

Thanks for your feedback!

Could not send message