A completeness theorem for a class of synchronization objects
Yehuda Afek, Eytan Weisberger, Hanan Weisman · 1993
We study a class of synchronization objects in shared memory concurrent systems, which we call common2.This class contains r-ead-modify-wr-ife objects that commute (e.g.fetch-and-add), or overwrite (e.g.swap) and queue shared objects.It is known that this class is contained in the consensus number 2 class of objects [Her91a], and most of the commonly used objects with consensus number 2 are included in it.We show that any object in the common~class can implement any other object in the class, in a system with an arbitrary number of processes.In fact we show that the objects