The instancy of snapshots and commuting objects

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.