BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-89-1280
       ENTRY:: January 05, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Sticky bits and universality of consensus
        TYPE:: Technical Report
      AUTHOR:: Plotkin, Serge A.
        DATE:: August 1989
       PAGES:: 20
    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.
       NOTES:: [Adminitrivia V1/RAM/19950105]
         END:: STAN//CS-TR-89-1280