When is Recoverable Consensus Harder Than Consensus?

DOI10.1145/3519270.3538418MaRDI QIDQ6120964zbMATH OpenOpenAlexFDO

Authors Carole Delporte-Gallet, Panagiota Fatourou, Hugues Fauconnier, Eric Ruppert

Publication date 26 March 2024

Published in Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2205.14213

zbMATH Keywords

asynchronous consensus hierarchy crash and recovery non-volatile memory readable objects recoverable consensus shared memory wait-free

Mathematics Subject Classification ID

Distributed systems (68M14) Distributed algorithms (68W15)

Abstract: We study the ability of different shared object types to solve recoverable consensus using non-volatile shared memory in a system with crashes and recoveries. In particular, we compare the difficulty of solving recoverable consensus to the difficulty of solving the standard wait-free consensus problem in a system with halting failures. We focus on the model where individual processes may crash and recover and the large class of object types that are equipped with a read operation. We characterize the readable object types that can solve recoverable consensus among a given number of processes. Using this characterization, we show that the number of processes that can solve consensus using a readable type can be larger than the number of processes that can solve recoverable consensus using that type, but only slightly larger.

Cited in

(2)

This page was built for publication: When is Recoverable Consensus Harder Than Consensus?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6120964)