2026-08-10T12:04:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8005 2024-03-06T10:41:41Z ddc:004 open_access

Recovering Shared Objects Without Stable Storage Michael, Ellis Ports, Dan R. K. Sharma, Naveen Kr. Szekeres, Adriana asynchronous system fault-tolerance crash-recovery R/W register state machine replication This paper considers the problem of building fault-tolerant shared objects when processes can crash and recover but lose their persistent state on recovery. This Diskless Crash-Recovery (DCR) model matches the way many long-lived systems are built. We show that it presents new challenges, as operations that are recorded at a quorum may not persist after some of the processes in that quorum crash and then recover. To address this problem, we introduce the notion of crash-consistent quorums, where no recoveries happen during the quorum responses. We show that relying on crash-consistent quorums enables a recovery procedure that can recover all operations that successfully finished. Crash-consistent quorums can be easily identified using a mechanism we term the crash vector, which tracks the causal relationship between crashes, recoveries, and other operations. We apply crash-consistent quorums and crash vectors to build two storage primitives. We give a new algorithm for multi-writer, multi-reader atomic registers in the DCR model that guarantees safety under all conditions and termination under a natural condition. It improves on the best prior protocol for this problem by requiring fewer rounds, fewer nodes to participate in the quorum, and a less restrictive liveness condition. We also present a more efficient single-writer, single-reader atomic set - a virtual stable storage abstraction. It can be used to lift any existing algorithm from the traditional Crash-Recovery model to the DCR model. We examine a specific application, state machine replication, and show that existing diskless protocols can violate their correctness guarantees, while ours offers a general and correct solution. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ellis Michael and Dan R. K. Ports and Naveen Kr. Sharma and Adriana Szekeres 2017 Is Part Of LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2017.36 urn:nbn:de:0030-drops-80055 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.36 eng https://creativecommons.org/licenses/by/3.0/legalcode