Witness structures and immediate snapshot complexes
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 compl...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2017-11-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/3122/pdf |
| _version_ | 1797270092716703744 |
|---|---|
| author | Dmitry N. Kozlov |
| author_facet | Dmitry N. Kozlov |
| author_sort | Dmitry N. Kozlov |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-25T01:58:47Z |
| format | Article |
| id | doaj.art-a8f1eef7713c44e18cbbdc911208c024 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T01:58:47Z |
| publishDate | 2017-11-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-a8f1eef7713c44e18cbbdc911208c0242024-03-07T15:34:15ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502017-11-01Vol. 19 no. 3Distributed Computing and...10.23638/DMTCS-19-3-123122Witness structures and immediate snapshot complexesDmitry N. KozlovIn 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.https://dmtcs.episciences.org/3122/pdfcomputer science - distributed, parallel, and cluster computing57-xx |
| spellingShingle | Dmitry N. Kozlov Witness structures and immediate snapshot complexes Discrete Mathematics & Theoretical Computer Science computer science - distributed, parallel, and cluster computing 57-xx |
| title | Witness structures and immediate snapshot complexes |
| title_full | Witness structures and immediate snapshot complexes |
| title_fullStr | Witness structures and immediate snapshot complexes |
| title_full_unstemmed | Witness structures and immediate snapshot complexes |
| title_short | Witness structures and immediate snapshot complexes |
| title_sort | witness structures and immediate snapshot complexes |
| topic | computer science - distributed, parallel, and cluster computing 57-xx |
| url | https://dmtcs.episciences.org/3122/pdf |
| work_keys_str_mv | AT dmitrynkozlov witnessstructuresandimmediatesnapshotcomplexes |