We present a sequence of constructions of commuting synchronization objects
(e.g., fetch-and-increment and fetch-and-add) in a system of n processors
from any two processor synchronization objects whose consensus number is tw
o or more (Herlihy, "Proceedings of the Tenth ACM Symposium on Principles o
f Distributed Computing, 1991," pp. 11-22). Each implementation in the sequ
ence uses a particular type of shared memory snapshot as a building block.
Later implementations in the sequence are based on higher quality snapshots
. The first implementation of a fetch-and-increment uses the standard atomi
c snapshot concept, introduced by Afek et al. and Anderson (Afek et al., J.
Assoc. Comput. Mach. 40(4) (1993), 873-890; Anderson, "Proceedings of the
Ninth Annual Assoc. Comput. Mach. Symposium on Principles of Distributed Co
mputing, August 1990," pp. 15-29) while the last construction in the sequen
ce, of fetch-and-add, is based on the immediate snapshot concept introduced
in (Borowsky and Gafni, "Proceedings of the 12th Assoc. Comput. Mach. Symp
osium on Principles of Distributed Computing, August 1993," pp. 41-51). Thi
s last construction also yields an implementation of a stronger snapshot, w
hich we call Write-and-snapshot. In addition, this work solves an open ques
tion of Borowsky and Gafni by presenting an implementation of a multishot i
mmediate snapshot object. Additional implications of our constructions are
(1) the existence of fault-tolerant self implementations of commuting objec
ts, (2) improvements in the efficiency of randomized constructions of commu
ting objects from read/write registers, and (3) low contention construction
s Of commuting objects. (C) 1999 Academic Press.