摘要: One of the most exciting developments in theory distributed computing recent years has been application powerful concepts from topology to prove results about computability resilient systems. Topology is a branch mathematics that deals with connectivity and convergence certain types objects. As it turns out, higher dimensional properties these special objects are related solvability tasks. In this survey, we thoroughly investigate topological approach computing, especially how use techniques combinatorial algebraic impossibility lower bound for important problems
参考文章(26)
Guanfeng Liang, Nitin Vaidya, Multiparty equality function computation in networks with point-to-point links international conference on structural information and communication complexity. pp. 258- 269 ,(2011) , 10.1007/978-3-642-22212-2_23
Maurice Herlihy, Sergio Rajsbaum, Algebraic topology and distributed computing a primer Computer Science Today. pp. 203- 217 ,(1995) , 10.1007/BFB0015245
James R. Munkres, Elements of Algebraic Topology ,(1984)
Hagit Attiya, Jennifer L. Welch, Distributed Computing: Fundamentals, Simulations and Advanced Topics ,(1998)
Maurice Herlihy, Sergio Rajsbaum, New Perspectives in Distributed Computing mathematical foundations of computer science. pp. 170- 186 ,(1999) , 10.1007/3-540-48340-3_16
Michael J. Fischer, The Consensus Problem in Unreliable Distributed Systems (A Brief Survey) fundamentals of computation theory. pp. 127- 140 ,(1983) , 10.1007/3-540-12689-9_99
M. J. Ablowitz, Afra J. Zomorodian, E. J. Hinch, A. Iserles, S. H. Davis, P. J. Olver, J. Ockendon, Topology for Computing (Cambridge Monographs on Applied and Computational Mathematics) Cambridge University Press. ,(2005)
Maurice Herlihy, Nir Shavit, The asynchronous computability theorem for t-resilient tasks Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93. pp. 111- 120 ,(1993) , 10.1145/167088.167125
Michael Saks, Fotios Zaharoglou, Wait-Free k -Set Agreement is Impossible: The Topology of Public Knowledge SIAM Journal on Computing. ,vol. 29, pp. 1449- 1483 ,(2000) , 10.1137/S0097539796307698
Eli Gafni, Elias Koutsoupias, 3-processor tasks are undecidable principles of distributed computing. pp. 271- ,(1995) , 10.1145/224964.225009