A Note on the Homotopy Type of Wait-Free Atomic Snapshot Protocol Complexes

Abstract

In the atomic snapshot system model, the processes of an asynchronous distributed system communicate by atomic write and atomic snapshot read operations on a shared memory consisting of single-writer multiple-reader registers. The processes may fail by crashing. It is shown that in this model, a wait-free full-information protocol complex is homotopy equivalent to the underlying input complex. A span in the sense of Herlihy and Shavit provides the homotopy equivalence. It follows that the protocol and input complexes are indistinguishable by ordinary homology or homotopy groups.