2026-07-23T22:07:02Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13130 2024-03-06T10:51:38Z ddc:004 open_access

Brief Announcement: Building Fast Recoverable Persistent Data Structures with Montage Wen, Haosen Cai, Wentao Du, Mingzhe Valpey, Benjamin Scott, Michael L. Durable linearizability consistency persistence fault tolerance The recent emergence of fast, dense, nonvolatile main memory suggests that certain long-lived data structures might remain in their natural, pointer-rich format across program runs and hardware reboots. Operations on such structures must be instrumented with explicit write-back and fence instructions to ensure consistency in the wake of a crash. Techniques to minimize the cost of this instrumentation are an active topic of current research. We present what we believe to be the first general-purpose approach to building buffered durably linearizable persistent data structures, and a system, Montage, to support that approach. Montage is built on top of the Ralloc nonblocking persistent allocator. It employs a slow-ticking epoch clock, and ensures that no operation appears to span an epoch boundary. If a crash occurs in epoch e, all work performed in epochs e and e-1 is lost, but all work from prior epochs is preserved. We describe the implementation of Montage, argue its correctness, and report on experiments confirming excellent performance for operations on queues, sets/mappings, and general graphs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Haosen Wen and Wentao Cai and Mingzhe Du and Benjamin Valpey and Michael L. Scott 2020 Is Part Of LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2020.52 urn:nbn:de:0030-drops-131304 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.52 eng https://creativecommons.org/licenses/by/3.0/legalcode