Wait-Free Concurrency

Abstract

In a shared memory multiprocessor, the biggest problem is preventing conflicting access to a memory location. The standard solution is for any processor wanting access to a shared memory location is to somehow lock the relevant location. The problem with using locks is that a processor having acquired a lock may be delayed, for example, by a page fault. In that case no other processor requiring access to that location can make progress.

Methodologies for transforming sequential algorithms into concurrent ones using synchronization primitives other than locking have been discussed in the literature.

In this report I describe an abstract computational model which allows to concentrate on the aspect of concurrency while reasoning about protocols. Starting with some simple algorithms, a methodology is developed which is similar to one introduced by Herlihy. The Guided Copy Method however is superior to existing methodologies as it explains how to improve space and thus time efficiency.

This report contains a brief history of wait-free protocols, an abstract description of data structures, and comments on memory management. Proofs are kept informal for readability and brevity.