Iterated Chromatic Subdivisions are Collapsible
Tóm tắt
The standard chromatic subdivision of the standard simplex is a combinatorial algebraic construction, which was introduced in theoretical distributed computing, motivated by the study of the view complex of layered immediate snapshot protocols. A most important property of this construction is the fact that the iterated subdivision of the standard simplex is contractible, implying impossibility results in fault-tolerant distributed computing. Here, we prove this result in a purely combinatorial way, by showing that it is collapsible, studying along the way fundamental combinatorial structures present in the category of colored simplicial complexes.
Tài liệu tham khảo
Bing, R.H.: Some aspects of the topology of 3-manifolds related to the poincaré conjecture. Lect. Mod. Math. II, 93–128 (1964)
Biran, O., Moran, S., Zaks, S.: A combinatorial characterization of the distributed tasks which are solvable in the presence of one faulty processor. In: Proceedings of the seventh annual ACM symposium on principles of distributed computing, pp 263–275. ACM (1988)
Borowsky, E., Gafni, E.: Generalized FLP impossibility result for t-resilient asynchronous computations. In: Proceedings of the 25th STOC. ACM Press (1993)
Castañeda, A., Rajsbaum, S.: New combinatorial topology bounds for renaming: The upper bound. J. ACM 59(1), 3 (2012)
Cohen, M.M.: A course in simple-homotopy theory, vol.10 of Graduate Texts in Mathematics. Springer, New York (1973)
Ehlers, P., Porter, T.: Joins for (augmented) simplicial sets. J. Pure and Appl. Algebra 145(1), 37–44 (2000)
Fajstrup, L., Goubault, É., Haucourt, E., Mimram, S., Raußen, M.: Trace spaces: An efficient new technique for state-space reduction. In: ESOP, pp 274–294 (2012)
Fischer, M.J, Lynch, N.A., Paterson, M.S.: Impossibility of distributed consensus with one faulty process. J.ACM 32(2), 374–382 (1985)
Goerss, P.G., Jardine, J.F.: Simplicial Homotopy Theory, vol. 174. Springer (2009)
Goubault, É., Mimram, S.: Trace spaces: algorithmics and applications. Presentation in Applied Algebraic Topology conference (2011)
Grandis, M.: Directed Algebraic Topology: Models of Non-Reversible Worlds. Cambridge University Press, Cambridge (2009)
Herlihy, M., Kozlov, D., Rajsbaum, S.: Distributed Computing Through Combinatorial Topology. Elsevier, New York (2014)
Herlihy, M., Shavit, N.: The asynchronous computability theorem for t-resilient tasks. In: Proceedings of the twenty-fifth annual ACM symposium on theory of computing, pp 111–120. ACM (1993)
Herlihy, M., Shavit, N.: The topological structure of asynchronous computability. J. ACM 46(6), 858–923 (1999)
Kozlov, D.: Combinatorial Algebraic Topology, vol. 21. Springer, Berlin Heidelberg (2008)
Kozlov, D.: Chromatic subdivision of a simplicial complex. Homology, Homotopy and Appl. 14(2), 197–209 (2012)
Kozlov, D.: Topology of the view complex. arXiv preprint arXiv:1311.7283. (2013)
Lynch, N.A.: Distributed Algorithms. Morgan Kaufmann, San Mateo (1996)
MacLane, S.: Categories for the Working Mathematician, vol. 5. Springer, Berlin Heidelberg (1998)
MacLane, S., Moerdijk, I.: Sheaves in Geometry and Logic: A First Introduction to Topos Theory. Springer, Berlin Heidelberg (1992)
Saks, M.E., Zaharoglou, F.: Wait-free k-set agreement is impossible: the topology of public knowledge. In: STOC, pp 101–110 (1993)
Whitehead, J.H.C.: Simplicial spaces, nuclei and m-groups. Proc. Lond. Math. Soc. 2(1), 243–327 (1939)