WAIT-FREE LINEARIZATION WITH A MECHANICAL PROOF

The correctness of a program for wait-free linearization of an arbitrary shared data object in bounded memory is verified mechanically. The program uses atomic read-write registers, an array of consensus registers and one compare and swap register. In the program, a number of processes concurrently inspect and modify a pointer structure without waiting. Consequently, the proof of correctness is very delicate. The theorem prover NQTHM of Boyer and Moore has been used to mechanically certify the correctness.