Please note: This master’s thesis presentation will be given online.
Gaetano
Coccimiglio, Master’s
candidate
David
R.
Cheriton
School
of
Computer
Science
Supervisor: Professor Trevor Brown
This work studies fence complexity of concurrent sets in the non-volatile shared memory model. We consider the case where CPU registers and cache memory remain volatile while main memory is non-volatile. Flush instructions are required to force shared state to be written back to non-volatile memory. These flush instructions must be accompanied by the use of expensive fence instructions to enforce ordering among such flushes. Collectively we refer to a flush and a fence as a psync. We consider lock-free implementations of list-based sets and prove two lower bounds.
First, we prove that it is impossible to implement strict-linearizable lock-free sets in which read-only (or search) operations do not flush or fence. Strict-linearizability forces crashed operations to take effect before the crash or not take effect at all; the weaker property of durable-linearizability enforces this requirement only for operations that have completed prior to the crash event. Second, we prove that for any durable-linearizable lock-free set there must exist an execution in which some process must perform at least one redundant psync as part of an update operation. We also present several implementations of persistent concurrent lock-free sets. We evaluate these implementations against existing persistent sets. This evaluation exposes the impact of algorithmic design and safety properties on psync complexity in practice as well as the cost of recovering the data structure following a system crash.
To join this master’s thesis presentation on Zoom, please go to https://uwaterloo.zoom.us/j/93342008681?pwd=VVBEUjJocWdBRnNpdHFFR0dZN3hRZz09.