WAIT-FREE LINEARIZATION WITH AN ASSERTIONAL PROOF

Given a sequential implementation of an arbitrary data object, a wait-free, linearizable concurrent implementation is constructed with space complexity quadratic in the number of processes. If processes do not concurrently invoke, the amortized time complexity of the invocations is independent of the number of processes. The worst case time complexity is linear in the number of processes. The construction is based on a compare&swap register. The correctness is proved by means of invariants and stability properties. Since it concerns memory reallocation by concurrent processes in a fault-tolerant setting, this proof is highly nontrivial.