An Exercise in Concurrency: From Non-blocking Objects to Fair Objects

A non-blocking implementation of a concurrent object is an implementation that does not prevent concurrent accesses to the internal representation of the object, while guaranteeing the deadlock-freedom progress condition without using locks. Considering a failure free context, this paper presents a simple modular approach to transform a non-blocking implementation into a starvation-free implementation satisfying a strong fairness requirement. This approach, which is due to G. Taubenfeld, is illustrated with the implementation of a concurrent stack. The spirit of the paper is mainly pedagogical. Its aim is not to introduce new concepts or algorithms, but to show that a powerful, simple, and modular transformation can provide concurrent objects with strong fairness properties.