CONACyT: Applications of Algebraic Topology to Concurrent Computation

这个NSF-CONACyT合作研究项目集中在分析无等待的同步分布式系统。 特别是，从单纯代数拓扑的抽象数学领域的技术应用作为一个强大的组合工具。具体而言，随着现代并行和分布式系统的规模扩大，越来越需要算法和数据结构来容忍延迟和故障。 一个数据对象或算法是无等待的，如果它保证任何进程都可以在固定数量的步骤内执行任何操作，而与其他进程的争用级别和执行速度无关。 这个项目的目标是致力于一个全面的无等待同步理论。 在过去的几年里，许多研究人员已经开发出强大的新工具，基于经典的代数拓扑，用于分析各种模型中的无等待算法和数据结构。 这些新技术用于发展多处理机同步的综合理论。 随着技术的进步使得并发和分布式平台变得容易获得，对这种理论的需求变得迫切。 这些问题的拓扑方法可能代表了计算机科学的一个强大的新的组合工具，而不仅仅是分布式计算，因为任何问题领域，需要推理的不确定性和部分信息。

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.