Report Number: CS-TR-89-1280
Institution: Stanford University, Department of Computer Science
Title: Sticky bits and universality of consensus
Author: Plotkin, Serge A.
Date: August 1989
Abstract: In this paper we consider implementation of atomic wait-free objects in the context of a shared-memory multiprocessor. We introduce a new primitive object, the "Sticky-Bit", and show its universality by proving that any safe implementation of a sequential object can be transformed into a wait-free atomic one using only Sticky Bits and safe registers. The Sticky Bit may be viewed as a memory-oriented version of consensus. In particular, the results of this paper imply "universality of consensus" in the sense that given an algorithm to achieve n-processor consensus, we can transform any safe implementation of a sequential object into a wait-free atomic one using polynomial number of additional safe bits. The presented results also imply that the Read-Modify-Write (RMW) hierarchy "collapses". More precisely, we show that although an object that supports a 1-bit atomic wait-free RMW is strictly more powerful than safe register and an object that supports 3-valued atomic wait-free RMW is strictly more powerful than 1-bit RMW, the 3-value RMW is universal in the sense that any RMW can be atomically implemented from a 3-value atomic RMW in a wait-free fashion.
http://i.stanford.edu/pub/cstr/reports/cs/tr/89/1280/CS-TR-89-1280.pdf