Topology of the view complex (Q2354983)

The paper is devoted to questions of algebraic topology related with the theory of distributive computing. \textit{M. Herlihy} and \textit{N. Shavit} [J. ACM 46, No. 6, 858--923 (1999; Zbl 1161.68469)] gave necessary and sufficient combinatorial conditions characterizing the class of decision tasks that can be solved in a wait-free manner by asynchronous processes that communicate by reading and writing a shared memory. They introduced a formalism for tasks in which a task's possible input and output values each are associated with simplicial complexes. This allowed them to characterize computability in terms of the topological properties of the simplicial complexes. A distributed protocol solves the given task if it yields a correct output for any input simplex and any possible execution. It has been realized that it is fruitful to summarize the totality of all possible executions as a single simplicial complex, the \textit{protocol complex}. A crucial construction in understanding the topology of the broad class of protocol complexes for \(n+1\) processes is the \textit{standard chromatic subdivision} \(\chi(\Delta^n)\) [\textit{M. Herlihy} et al., Distributed computing through combinatorial topology. Amsterdam: Elsevier/Morgan Kaufmann (2014; Zbl 1341.68004)]. The author of the paper under review studies the analog of this construction, which is derived from the snapshot model. For any integer \(n\geq 0\), denote \([n]=\{0, \ldots, n\}\). Let \(n\geq 1\) be a natural number. An \textit{\(n\)-view} is a \(2\times t\)-matrix \[ W= \left( \begin{matrix} V_1 & \ldots & V_{t-1} & [n]\\ I_1 & \ldots & I_{t-1} & I_t \end{matrix} \right), \] where \(t\geq 1\), such that the following properties are satisfied: {\parindent=6mm \begin{itemize} \item[(1)] \(\emptyset\not=V_1\subset \cdots \subset V_{t-1}\subset [n]\); \item [(2)] the sets \(I_1, \ldots, I_t\) are disjoint; \item [(3)] \(\emptyset\not=I_k\subseteq V_k\), for \(k=1, \ldots, t-1\). \end{itemize}} The convention \(V_t=[n]\) is used. The \textit{dimension} of the \(n\)-view \(W\) is defined by \(dim W= |I_1|+ \cdots + |I_t|-1\). A \textit{local view} \(L=(V,x)\) is a pair where \(V\subseteq [n]\) and \(x\in V\). The local view \(L=(V,x)\) \textit{belongs to} \(W\), writing \(L\in W\), if there exists \(1\leq k\leq t\), such that \(V=V_k\) and \(x\in I_k\). Let \(V(W)\) denote the set of all local views belonging to \(W\). Clearly, \(|V(W)|=dim W +1\). In the paper under review, an \textit{abstract simplicial complex} \(K\) is defined as a set of subsets of a finite set \(S\) such that {\parindent=6mm \begin{itemize} \item[{\(\bullet\)}] \(\{x\}\in K\) for all \(x\in S\); \item [{\(\bullet\)}] if \(\tau\subset \sigma\), and \(\sigma\in K\), then \(\tau\in K\). \end{itemize}} The set \(S\) is called the \textit{vertex set} of \(K\). Each \(\sigma\in K\) is called a \textit{face}. The abstract simplicial complex \(K=2^S\) consisting of all subsets \(\sigma\subseteq S\) is called the \textit{simplex}. For any natural \(n\), a simplicial complex \(View^n\) is defined as follows: {\parindent=6mm \begin{itemize} \item[{\(\bullet\)}] the set of of vertices is the set of all local views \[ V(View^n)= \{(V,x)| x\in V\subseteq [n]\}; \] \item [{\(\bullet\)}] a subset \(S\subseteq V(View^n)\) forms a simplex if and only if \(S=V(W)\) for some \(n\)-view W. \end{itemize}} The \(n\)-views are identified with the corresponding simplices of \(View^n\). { Definition 3.6.} Assume \(n\) is a natural number. {\parindent=6mm \begin{itemize} \item[(1)] We call an \(n\)-view \[ W= \left( \begin{matrix} V_1 & \ldots & V_{t-1} & [n]\\ I_1 & \ldots & I_{t-1} & I_t \end{matrix} \right) \] an \textit{immediate snapshot view} if we have \(I_k\subseteq V_k\setminus V_{k-1}\) for all \(k= 2, \ldots,t\). \item [(2)] If \(W\) is an immediate snapshot view and \(U\subset W\), the \(U\) is also an immediate snapshot view. Therefore the immediate snapshot views form a simplicial subcomplex of \(View^n\), which we denote by \(\chi(\Delta^n)\). \end{itemize}} The simplicial complexes \(View^n\) and \(\chi(\Delta^n)\) are equipped with a canonical simplicial action of the permutation group \(\mathcal{S}_{[n]}\). This is the reflection of the fact that the considered protocols are symmetric with respect to the renaming of processors. Let \(K\) be an abstract simplicial complex. The set \(\mathcal{F}(K)\) of all its simplices is partially ordered by inclusion. It is called the \textit{face poset} of \(K\). For \(\sigma\in K\), denote by \(\mathcal{F}(K)_{\geq\sigma}\) the set \(\{\tau\in K| \sigma \subseteq \tau\}\) ordered by inclusion. Denote by \(\mathcal{B}_t\) the partially ordered set of all subsets of a set with \(t\) elements. A simplex \(\sigma\in K\) is \textit{free} if \(\mathcal{F}(K)_{\geq\sigma}\cong \mathcal{B}_t\) for some \(t\geq 1\). For a free simplex \(\sigma\), a \textit{collapse} of \(K\) associated to \(\sigma\) is the process of deleting from \(K\) all the simplices in \(\mathcal{F}(K)_{\geq\sigma}\). When \(M\) is a subcomplex of \(K\), we say that \(K\) is \textit{collapsible to} \(M\) if there exists a sequence of collapses leading from \(K\) to \(M\). We say that \(K\) is \textit{collapsible} if it is collapsible to the void simplicial complex. {Definition 4.1.} Assume \(K\) is an abstract simplicial complex with a simplicial action of a finite group \(G\). {\parindent=6mm \begin{itemize} \item[(a)] A simplex \(\sigma\) is called \textit{\(G\)-free} if it is free, and for all \(g\in G\), such that \(g(\sigma)\not=\sigma\), we have \[ \mathcal{F}_{\geq{\sigma}}\cap \mathcal{F}_{\geq{g(\sigma)}}= \emptyset. \] \item [(b)] If \(\sigma\) is \(G\)-free, we call the procedure of deleting all the simplices from the union \(\bigcup_{g\in G}\mathcal{F}(K)_{\geq g(\sigma)}\) the \textit{\(G\)-collapse} of \(K\). \end{itemize}} { Theorem 4.4.} For every natural number \(n\), the following statements are true. {\parindent=6mm \begin{itemize} \item[(1)] The simplicial complex \(View^n\) is \(\mathcal{S}_{[n]}\)-collapsible to \(\chi(\Delta^n)\). \item [(2)] The simplicial complex \(\chi(\Delta^n)\) is \(\mathcal{S}_{[n]}\)-collapsible. \end{itemize}} From Theorem 4.4 follows the statement that \(\chi(\Delta^n)\) is collapsible. Even this statement is new.