CONACyT: Applications of Algebraic Topology to Concurrent Computation

点击翻译按钮获取中文摘要

This NSF-CONACyT Collaborative research project concentrates on analyzing wait-free synchronous distributed systems. In particular, techniques from the abstract mathematical area of simplicial algebraic topology are applied as a powerful combinatorial tool. Specifically, as modern parallel and distributed systems scale up, there is an increasing need for algorithms and data structures to tolerate delays and failures. A data object or algorithm is wait-free if it guarantees that any process can execute any operation within a fixed number of steps, independent of the level of contention and the execution speeds of the other processes. The goal of this project is to work toward a comprehensive theory of wait-free synchronization. In the past few years, a number of researchers have developed powerful new tools, based on classical algebraic topology, for analyzing wait-free algorithms and data structures in a variety of models. These new techniques are used in developing a comprehensive theory of multiprocessor synchronization. The need for such a theory has become compelling as tec hnological advances have made concurrent and distributed platforms readily available. The topological approach to these problems may represent a powerful new combinatorial tool for Computer Science, not just for distributed computing, as for any problem area that requires reasoning about uncertainty and partial information.