Dmitry N. Kozlov - Witness structures and immediate snapshot complexes

dmtcs:3122 - Discrete Mathematics & Theoretical Computer Science, November 28, 2017, Vol. 19 no. 3 - https://doi.org/10.23638/DMTCS-19-3-12
Witness structures and immediate snapshot complexesArticle

Authors: Dmitry N. Kozlov

    In this paper we introduce and study a new family of combinatorial simplicial complexes, which we call immediate snapshot complexes. Our construction and terminology is strongly motivated by theoretical distributed computing, as these complexes are combinatorial models of the standard protocol complexes associated to immediate snapshot read/write shared memory communication model. In order to define the immediate snapshot complexes we need a new combinatorial object, which we call a witness structure. These objects are indexing the simplices in the immediate snapshot complexes, while a special operation on them, called ghosting, describes the combinatorics of taking simplicial boundary. In general, we develop the theory of witness structures and use it to prove several combinatorial as well as topological properties of the immediate snapshot complexes.


    Volume: Vol. 19 no. 3
    Section: Distributed Computing and Networking
    Published on: November 28, 2017
    Accepted on: November 10, 2017
    Submitted on: February 5, 2017
    Keywords: Computer Science - Distributed, Parallel, and Cluster Computing,57-XX

    Consultation statistics

    This page has been seen 418 times.
    This article's PDF has been downloaded 256 times.