Time-Optimal and Energy-Efficient Deterministic Consensus
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914123054317568 |
|---|---|
| author | Meir, Shachar Mirault, Hugo Peleg, David Robinson, Peter |
| author_facet | Meir, Shachar Mirault, Hugo Peleg, David Robinson, Peter |
| contents | 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 \emph{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 ${O}(\lceil f^2 / n \rceil)$ rounds, whereas for binary consensus, we show that ${O}(\lceil f / \sqrt{n} \rceil)$ rounds are possible. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_12282 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Time-Optimal and Energy-Efficient Deterministic Consensus Meir, Shachar Mirault, Hugo Peleg, David Robinson, Peter Distributed, Parallel, and Cluster Computing Data Structures and Algorithms 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 \emph{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 ${O}(\lceil f^2 / n \rceil)$ rounds, whereas for binary consensus, we show that ${O}(\lceil f / \sqrt{n} \rceil)$ rounds are possible. |
| title | Time-Optimal and Energy-Efficient Deterministic Consensus |
| topic | Distributed, Parallel, and Cluster Computing Data Structures and Algorithms |
| url | https://arxiv.org/abs/2506.12282 |