Specification and Verification of a Transient StackDistinguished Paper AwardRemote
A transient data structure is a package of an ephemeral data structure, a persistent data structure, and fast conversions between them. In this paper, we describe the specification and proof of a transient stack and its iterators. This data structure is a scaled-down version of the general-purpose transient sequence data structure implemented in the OCaml library Sek. Internally, it relies on fixed-capacity arrays, or chunks, which can be shared between several ephemeral and persistent stacks. Dynamic tests are used to determine whether a chunk can be updated in place or must be copied: a chunk can be updated if it is uniquely owned or if the update is monotonic. Using CFML, which implements Separation Logic with Time Credits inside Coq, we verify the functional correctness and the amortized time complexity of this data structure and of its iterators. The specification of iterators describes what the operations on iterators do, how much they cost, and under what circumstances an iterator is invalidated.
Presentation Slides (slides.pdf) | 454KiB |
Mon 17 JanDisplayed time zone: Eastern Time (US & Canada) change
10:20 - 12:00 | |||
10:20 25mTalk | Specification and Verification of a Transient StackDistinguished Paper AwardRemote CPP DOI Pre-print Media Attached File Attached | ||
10:45 25mTalk | Mechanized Verification of a Fine-Grained Concurrent Queue from Meta’s Folly LibraryRemote CPP Simon Friis Vindum Aarhus University, Lars Birkedal Aarhus University, Daniel Frumin University of Groningen Pre-print Media Attached | ||
11:10 25mTalk | Applying Formal Verification to Microkernel IPC at MetaInPerson CPP Quentin Carbonneaux Meta, Noam Zilberstein Cornell University, Christoph Klee Facebook, Peter W. O'Hearn Meta; University College London, Francesco Zappa Nardelli Meta Pre-print | ||
11:35 25mTalk | Certified Abstract Machines for Skeletal SemanticsRemote CPP Pre-print Media Attached |