4 papers
Substep Linearizability: Relaxing Atomicity While Preserving Sequential Specification
Finn Hackett, Evan Wrench, Ivan Beschastnikh +1
Linearizability is a standard correctness condition for concurrent objects. It takes a correct by construction sequential specification of a concurrent data structure, and produces…
Concurrent Balanced Augmented Trees
Evan Wrench, Ajay Singh, Younghun Roh +4
Augmentation makes search trees tremendously more versatile, allowing them to support efficient aggregation queries, order-statistic queries, and range queries in addition to inser…
Trace Validation of Unmodified Concurrent Systems with OmniLink
Finn Hackett, Evan Wrench, Peter Macko +3
Concurrent systems are notoriously difficult to validate: subtle bugs may only manifest under rare thread interleavings, and existing tools often require intrusive instrumentation…
Recoverable Lock-Free Locks
Hagit Attiya, Panagiota Fatourou, Eleftherios Kosmas +1
This paper presents the first transformation that introduces both lock-freedom and recoverability. Our transformation starts with a lock-based implementation, and provides a recove…