{"id":"63e79fd0-75c0-4098-b317-770ec37fc98d","arxiv_id":"1908.11850","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"MOD turns functional data structures into durable, failure-atomic persistent-memory data structures with a single fence per update in the common case, beating PMDK STM on Optane by 36 to 43 percent.","lead":"This systems paper presents MOD, a C++ library that makes persistent-memory data structures crash-safe with just one ordering step per update, and reports roughly 40 percent speedups over Intel's transactional library on real Optane hardware. It matters because persistent memory is reaching production, but building crash-consistent software by hand is difficult and slow.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The failure-atomicity guarantee is contingent on nvm_malloc's persistent metadata surviving crashes; §5.3's recovery GC scans datastructure nodes but does not establish allocator consistency, so the central claim needs a fault-injection check of the underlying heap.","rationale":"The reader's weakest assumption and my own review converge on the same load-bearing dependency: MOD's crash consistency is only as strong as the persistent allocator's crash consistency. The paper describes a recovery-time mark-sweep over datastructure nodes, but it never establishes that nvm_malloc's metadata can survive a crash during allocation. Without that, 'one ordering point per FASE' does not by itself guarantee failure atomicity. This concern does not contradict the paper's internal logic; it identifies an unanalyzed external dependency. The performance measurements on real Optane hardware are credible, and the paper openly discloses the vector slowdown, so I do not see grounds to reject the work. However, the lack of a code artifact and the missing allocator analysis make the current evidence insufficient for unconditional acceptance. The reader's conditional verdict already captures this; my review does not change that verdict. A targeted fault-injection test would settle whether the concern is real: if nvm_malloc metadata survives all injected crashes and recovery GC never frees live data, the concern is resolved; if not, the central claim is invalidated at the heap layer.","tokens_in":18186,"tokens_out":4074,"duration_ms":43597,"concrete_test":"Run a fault-injection campaign on real Optane hardware or in a simulator with crash injection: execute each MOD microbenchmark (map, set, stack, queue) in a loop and interrupt execution at randomized points inside nvm_malloc's malloc/free paths and inside MOD update operations, then run MOD's recovery GC. Check three properties after every crash: (1) nvm_malloc's own consistency check reports valid heap metadata; (2) the set of reachable nodes from the persistent root pointer is exactly the last committed version, with no live node reclaimed; and (3) all shadow allocations from incomplete FASEs are reclaimed. Repeat for at least 10,000 injection points. If any run loses a live node or corrupts allocator state, the failure-atomicity claim fails at the heap layer.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is that MOD provides failure-atomic updates with one ordering point per operation. That claim holds only if the persistent heap itself remains recoverable after a crash. Section 4.2 states that MOD uses the off-the-shelf nvm_malloc allocator, and Section 5.3 states: 'We rely on garbage collection during recovery to clean up allocated memory from an incomplete FASE... Any unmarked data remaining in the persistent heap is a PM leak and can be reclaimed at this point.' This assumes that the allocator's own persistent metadata — block headers, free lists, allocation state — is crash-consistent. The paper provides no analysis of nvm_malloc's crash behavior, no argument that a crash during malloc/free leaves the metadata in a consistent state, and no mechanism for the recovery GC to validate or repair allocator metadata before reclaiming unmarked regions. If a power failure interrupts an allocation in the middle of a header write or free-list update, the GC's mark-sweep pass may reclaim blocks that are actually live, double-free blocks, or fail to traverse a corrupted heap. The failure-atomicity guarantee would then fail not in the MOD datastructure layer but in the heap layer it silently depends on. This is not an internal contradiction in MOD's design, but it is an unverified, load-bearing dependency.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes Minimally Ordered Durable (MOD) datastructures, a C++ library of persistent datastructures (map, set, stack, queue, vector) that use functional shadowing with structural sharing to provide failure-atomic updates while minimizing ordering points. The design has a Basic interface for single updates and a Composition interface for multi-update FASEs, with one sfence per FASE in the common case. The authors evaluate on real Intel Optane hardware against PMDK v1.5, reporting average speedups of 43% for pointer-based microbenchmarks and 36% for application benchmarks, while honestly disclosing vector slowdowns. The paper also contributes a recipe for porting existing functional datastructures, a recovery scheme based on reference counting and a recovery garbage collector, an automated testing framework, and an analytical model for flush latency.","tokens_in":18428,"tokens_out":14398,"duration_ms":131897,"significance":"If the design is correct, MOD offers a practical middle ground between hand-crafted persistent datastructures and general-purpose PM-STM, and the real-hardware evaluation demonstrates that reducing ordering constraints is a effective strategy. The paper also provides a credible recipe for constructing additional recoverable datastructures and releases an implementation, both of which are useful to the community. However, the central failure-atomicity claim depends on an unverified assumption about the crash consistency of the underlying allocator, and the correctness argument contains an ambiguity about where reference counts are stored. These issues must be resolved before the headline claims can be accepted.","major_comments":[{"comment":"The failure-atomicity claim of the abstract and Section 1 depends on the persistent heap remaining recoverable after a crash, but the paper uses the off-the-shelf nvm_malloc allocator without analyzing its crash behavior. Section 5.3 states that recovery garbage collection can reclaim 'any unmarked data remaining in the persistent heap,' but this is only sound if nvm_malloc's block headers, free lists, and allocation state are themselves crash-consistent. A crash during a malloc/free can leave metadata inconsistent, making the heap untraversable and invalidating the mark-sweep recovery. Please add a fault-injection test of the allocator, a crash-consistency argument, or a modification of the allocator to make its metadata failure-atomic; as written, the central guarantee is unverified.","section":"4.2, 5.3"},{"comment":"There is an internal inconsistency in the correctness argument. Section 5.2 and Section 5.4 require that all PM writes outside Commit be restricted to newly allocated data, but Section 5.3 describes reference counting in which 'we increment reference counts of nodes that are reused on an update operation.' If these reference counts are stored in PM nodes, an update writes to pre-existing persistent data, violating the invariant. If reference counts are kept in volatile memory, the paper should state this explicitly and explain how recovery reconstructs them; if they are in PM but are exempt from flushing and reset on crash, the invariant in Section 5.4 needs to be amended to exclude refcount fields. Please clarify and make the testing framework consistent with the storage location of reference counts.","section":"5.2, 5.3, 5.4"},{"comment":"The paper's verification of failure atomicity is limited to trace-based invariant checking on successful runs; there is no crash-injection test that powers off the machine mid-FASE and checks that recovery restores a consistent version. Since the central claim concerns behavior on crashes, please add such a test (at least a kill -9 or power-loss simulation) for all datastructures and for the allocator, and report the recovery outcomes.","section":"5.4, 6"}],"minor_comments":[{"comment":"The abstract reports 40%/38% microbenchmark/application speedups, while Section 1 reports 43%/36%; please reconcile these numbers and the 'hurts vector by 122%' phrasing with Figure 9.","section":"Abstract, Section 1"},{"comment":"Table 3 reports that MOD vector consumes 131x memory at 2M elements versus 1M, which is surprising for a structural-sharing implementation; please explain or correct this value.","section":"Table 3"},{"comment":"The analytical model in Section 3 (listed as a contribution) is an Amdahl's law curve fit with a fitted parallel fraction f=0.82 rather than a mechanistic model; the text already acknowledges the hardware is a black box, so consider describing this as a descriptive fit, not an analytical model.","section":"Section 3"},{"comment":"Section 6.1 should report the number of runs and variance for the timing experiments; without repeated runs it is unclear whether the 43%/36% differences are within noise.","section":"Section 6.1"},{"comment":"Reference [45] contains typos ('Stroage' should be 'Storage') and the venue is 'FAST' rather than 'FASE'.","section":"References"},{"comment":"The introduction says the implementation is released, but no repository URL is provided; please include one.","section":"Section 1"}],"recommendation":"major_revision","confidential_remarks":"The paper's central idea is promising and the real-hardware evaluation is valuable. The blocking issue is the unverified dependency on nvm_malloc's crash consistency, which is directly load-bearing for the failure-atomicity claim. I would require the authors to either provide a fault-injection study of the allocator or explicitly scope the paper's guarantee. The reference-count storage ambiguity in Section 5.3 also needs to be resolved, as it affects the correctness argument and the automated testing framework."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The core idea here is good and the paper deserves a serious look. Combining shadow paging with structural sharing from functional datastructures is a new combination, and it pays off: the map, set, stack, and queue microbenchmarks show real speedups over PMDK v1.5 on actual Optane hardware, and the paper is honest about the 2.2x vector regression. The Composition interface for atomically updating multiple datastructures through a single pointer write in the common case is clean. The recipe for turning functional datastructures into PM datastructures is also a nice practical contribution, and the space-overhead numbers (under 0.01% per update) are striking.\n\nThe evaluation is above average for this area: real Optane DCPMM, clear methodology, and a reasonable comparison against PMDK v1.4 and v1.5. The flushing-latency analysis of the hardware itself is useful, though calling an Amdahl fit an \"analytical model\" is a stretch; the paper labels it as a side note and discloses f=0.82, so that is a minor wording issue rather than a hidden move.\n\nThe real soft spot is the allocator. Section 5.3 relies on a recovery GC that marks reachable nodes and reclaims everything else, but the heap is an off-the-shelf nvm_malloc whose metadata (free lists, headers) is never analyzed for crash consistency. If a crash corrupts that metadata, the recovery GC could reclaim live data or double-free blocks, and the one-fence failure-atomicity guarantee would break at the heap layer, not the MOD layer. The stress-test summary is right about this. I do not think it sinks the design, since the MOD-level correctness argument is solid and the dependency is explicit, but a fault-injection test or at least a careful argument about nvm_malloc's behavior is required before I would trust the guarantee in production.\n\nSmaller issues: the abstract numbers (40%/38%) do not match the intro numbers (43%/36%), and there are no error bars or repeated-run statistics. These are minor but should be cleaned up. Also, the paper claims to release the implementation but gives no link or hash in the text; the artifact needs to be actually findable.\n\nOverall: a strong systems paper with a real contribution and honest evaluation. It deserves a serious referee; the referee should push on the allocator question and ask for the artifact. I would cite this if I were working on PM datastructures.","headline":"MOD gives the persistent-memory community a genuinely useful middle ground between hand-crafted datastructures and PM-STM, measured on real Optane hardware, but the failure-atomicity story has a load-bearing gap around the allocator's own crash consistency.","tokens_in":18971,"tokens_out":1567,"would_cite":true,"duration_ms":17835,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proposes MOD datastructures that make failure-atomic persistent-memory updates cost one ordering point per operation, outperforming general-purpose transactions on real hardware.","keywords":["persistent memory","non-volatile memory","crash consistency","failure-atomicity","durable datastructures","functional shadowing","structural sharing","ordering points"],"falsifier":"A fault-injection campaign that crashes a MOD workload at every instruction boundary during an update and then runs recovery, marking every reachable node, would settle the central claim: if recovery frees any reachable node or retains any unreachable block, failure-atomicity fails.","tokens_in":17964,"feed_emoji":"⚡","tokens_out":9215,"duration_ms":86457,"temperature":0.7,"pith_summary":"MOD aims to be the middle ground between hand-tuned durable datastructures and general-purpose persistent-memory transactions: a C++ library of map, set, stack, queue, and vector that hides crash-consistency details from programmers. The paper's central claim is that a failure-atomic update can be made durable with one ordering point if the update is written out of place and only the final pointer swap is ordered. This matters because current transactional approaches spend most of their execution time flushing and logging, and the paper identifies ordering constraints, not write volume, as the main bottleneck. On real persistent-memory hardware, MOD reports roughly 40 percent speedups on pointer-based containers and 38 percent on applications over the state-of-the-art transactional baseline. If the design holds up, recoverable applications become both easier to write and faster to run.","feed_headline":"One ordering point per update speeds persistent-memory code by 40 percent","feed_subtitle":"By writing updates out of place and swapping one pointer, MOD beats transaction-based persistent memory.","key_machinery":"Functional Shadowing: each update writes a new version entirely out of place, flushing dirty cachelines with unordered cacheline-flush instructions and no fences; a single ordering point then makes the shadow durable before an 8-byte atomic pointer write swaps in the new root. Structural sharing, borrowed from purely functional datastructures, keeps the shadow small by reusing untouched sub-trees. The Commit step comes in three forms—single, siblings, and unrelated—so the common cases keep exactly one ordering point per failure-atomic section.","core_discovery":"The central claim is that the dominant cost of failure-atomic updates to persistent memory is ordering, not write volume, and that this cost can be reduced to a single fence per operation. MOD datastructures implement every update as an out-of-place write: a new \"shadow\" version of the datastructure is built from freshly allocated nodes, reusing untouched sub-trees of the old version through structural sharing. Because the shadow shares no persistent pointers with the old version, its dirty cachelines can be flushed in any order with no logging, and one ordering point before an atomic 8-byte pointer swap makes the new version durable and atomically replaces the old. The paper shows on real persistent-memory hardware that this design improves map, set, stack, and queue microbenchmarks by 40 percent and application benchmarks by 38 percent relative to the state-of-the-art transactional baseline, while vector workloads are slower. It also presents a recipe for turning existing purely functional datastructures into MOD datastructures and a composition interface that commits multi-structure updates with one ordering point in the common cases.","pith_inferences":["A fault-injection crash study, which the paper does not report, is the natural next test: crash at different points inside allocation and commit and check that no reachable node is reclaimed and no unreachable block survives.","MOD's advantage should widen on hardware with higher flush latency and narrow if future hardware makes ordering points cheap; the paper's Amdahl-style latency model suggests the scaling curve.","Trying the recipe on other functional collections, such as priority queues, tries, or ropes, would show how far the one-fence design generalizes, with the vector slowdown warning that dense layouts may not fit.","The volatile reference-count reset assumes single-parent sharing in the surviving version; datastructures that share a subtree among multiple parents in one version would need a different reclamation rule."],"forward_implications":["Failure recovery no longer needs log replay: after a crash the latest committed root pointer still identifies a consistent durable version, and uncommitted shadows are garbage.","Pointer-based containers gain roughly 40 percent over the transactional baseline on current hardware, and whole applications gain about 36-38 percent.","A single ordering point per operation suffices for one datastructure or for multiple datastructures under a common parent; only unrelated datastructures need a short transaction.","Any existing purely functional datastructure can be converted into a recoverable MOD datastructure by allocating its state in persistent memory and flushing modified cachelines without ordering.","The benefit does not extend to array-like containers: MOD's vector is slower because the tree-based functional layout sacrifices dense memory."],"supporting_citations":[{"why":"The transactional library used as the performance baseline that MOD must beat.","marker":"[18]"},{"why":"Defines failure-atomic sections, the abstraction MOD's Basic and Composition interfaces implement.","marker":"[5]"},{"why":"The original shadow-paging proposal whose out-of-place update strategy Functional Shadowing adapts.","marker":"[33]"},{"why":"Classic work on multi-version persistent data structures that contributes structural sharing.","marker":"[13]"},{"why":"The functional hash-array mapped trie used as the basis for MOD's map and set.","marker":"[43]"},{"why":"The relaxed radix-balanced tree used as the basis for MOD's vector.","marker":"[44]"},{"why":"The persistent-memory allocator that places MOD datastructure state in durable memory.","marker":"[2]"},{"why":"The persistent-memory workload analysis and fence/flush cost measurements that motivate minimizing ordering points.","marker":"[34]"}],"fun_headline_variants":["MOD: one ordering point per update, 40% faster than STM","Out-of-place updates: one fence, 40% speedup on PM","Single pointer swap makes PM updates atomic and 40% faster","MOD cuts PM ordering to a single point, gains 40% performance","Less ordering, more speed: MOD beats STM by 40% on PM"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"Failure-atomicity holds only if the persistent allocator's internal bookkeeping survives crashes consistently and its recovery pass frees exactly the unreachable blocks — an assumption the paper borrows from an off-the-shelf allocator without analyzing its crash behavior.","fun_headline_variants_meta":{"raw":{"variants":["MOD: one ordering point per update, 40% faster than STM","Out-of-place updates: one fence, 40% speedup on PM","Single pointer swap makes PM updates atomic and 40% faster","MOD cuts PM ordering to a single point, gains 40% performance","Less ordering, more speed: MOD beats STM by 40% on PM"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000692,"raw_usage":{"total_tokens":3189,"prompt_tokens":1062,"completion_tokens":2127,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":678,"completion_tokens_details":{"reasoning_tokens":2029}},"tokens_in":678,"tokens_out":2127,"duration_ms":15407,"temperature":1.0,"reasoning_tokens":2029,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T11:54:01.114632+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A fault-injection campaign that crashes a MOD workload at every instruction boundary during an update and then runs recovery, marking every reachable node, would settle the central claim: if recovery frees any reachable node or retains any unreachable block, failure-atomicity fails.","supporting_citations":[{"cited_title":"Persistent memory development kit","cited_arxiv_id":null,"evidence_quote":"The transactional library used as the performance baseline that MOD must beat."},{"cited_title":"Chakrabarti, Hans-J","cited_arxiv_id":null,"evidence_quote":"Defines failure-atomic sections, the abstraction MOD's Basic and Composition interfaces implement."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The original shadow-paging proposal whose out-of-place update strategy Functional Shadowing adapts."},{"cited_title":"Driscoll, Neil Sarnak, Daniel D","cited_arxiv_id":null,"evidence_quote":"Classic work on multi-version persistent data structures that contributes structural sharing."},{"cited_title":"Steindorfer and Jurgen J","cited_arxiv_id":null,"evidence_quote":"The functional hash-array mapped trie used as the basis for MOD's map and set."},{"cited_title":"Rrb vec- tor: A practical general purpose immutable sequence","cited_arxiv_id":null,"evidence_quote":"The relaxed radix-balanced tree used as the basis for MOD's vector."},{"cited_title":"nvm malloc: Memory allocation for nvram","cited_arxiv_id":null,"evidence_quote":"The persistent-memory allocator that places MOD datastructure state in durable memory."},{"cited_title":"Nalli, S","cited_arxiv_id":null,"evidence_quote":"The persistent-memory workload analysis and fence/flush cost measurements that motivate minimizing ordering points."}],"review_version":1}