3 papers
cs.DC2024
Determining Recoverable Consensus Numbers
Sean Ovens
Herlihy's wait-free consensus hierarchy classifies the power of object types in asynchronous shared memory systems where processes can permanently crash (i.e. stop taking steps). I…
cs.DC2023
The Space Complexity of Consensus from Swap
Sean Ovens
Nearly thirty years ago, it was shown that registers are needed to solve obstruction-free consensus among processes. This lower bound was improved to register…
cs.DC2019
Strongly Linearizable Implementations of Snapshots and Other Types
Sean Ovens, Philipp Woelfel
Linearizability is the gold standard of correctness conditions for shared memory algorithms, and historically has been considered the practical equivalent of atomicity. However, it…