Reasoning about Nonblocking Concurrency

Lindsay Groves (Victoria University of Wellington, New Zealand)

Abstract: Verification of concurrent algorithms has been the focus of much research over a considerable period of time, and a variety of techniques have been developed that are suited to particular classes of algorithm, for example algorithms based on message passing or mutual exclusion. The development of nonblocking or lock-free algorithms, which rely only on hardware primitives such as Compare And Swap, present new challenges for verification, as they allow greater levels of currency and more complex interactions between processes.

In this paper, we describe and compare two approaches to reasoning about nonblocking algorithms. We give a brief overview of the simulation approach we have used in previous work. We then give a more detailed description of an approach based on Lipton's reduction method, and illustrate it by verifying two versions of a shared counter and two versions of a shared stack. Both approaches work by transforming a concurrent execution into an equivalent sequentia-execution, but they differ in the way that executions are transformed and the way that transformations are justified.

Keywords: atomicity, concurrency, linearisability, lock-free algorithms, nonblocking algorithms, reduction, shared memory, simulation relation, verification

Categories: D.1.3, D.2.4, F.3.1