Witness structures and immediate snapshot complexes

In this paper we introduce and study a new family of combinatorial simplicialcomplexes, which we call immediate snapshot complexes. Our construction andterminology is strongly motivated by theoretical distributed computing, asthese complexes are combinatorial models of the standard protocol complexesassociated to immediate snapshot read/write shared memory communication model.In order to define the immediate snapshot complexes we need a new combinatorialobject, which we call a witness structure. These objects are indexing thesimplices in the immediate snapshot complexes, while a special operation onthem, called ghosting, describes the combinatorics of taking simplicialboundary. In general, we develop the theory of witness structures and use it toprove several combinatorial as well as topological properties of the immediatesnapshot complexes.Comment: 27 pages, full paper version of the 1st part of the preprint arXiv:1402.470