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 complex and the input complex are indistinguishable by ordinary homology or homotopy groups.
An AS protocol complex is not generally homeomorphic to the underlying input complex, but it is homotopy equivalent to it REF .
A Note on the Homotopy Type of Wait-free Atomic Snapshot Protocol Complexes
Mathematics Computer Science