The Topological Approach to Asynchronous Computability

选择基本的协调操作（无论是读写共享内存、消息传递还是更复杂的操作）已经成为一个关键的设计问题。要做出这样的选择，必须分析多进程执行的行为，对并发操作的多种可能组合进行推理。这是一项异常微妙和费力的任务。本研究的目的是用问题的几何表示上的组合条件来取代争论并发执行的需要。这应该允许研究人员和设计人员，而不是分析行为，应用强大的数学工具来识别某些协议何时是不可能的，评估替代同步原语的功能，或者明确地提出使给定问题可解决所需的假设。本课题研究的是在不同模型中对同步原语的能力进行表征和分类的问题。先前的研究开发了基于经典拓扑的强大的新工具，用于分析各种模型和体系结构中的容错并发算法和数据结构。这项研究表明，大量的同步问题可以与称为简单复合体的高维几何结构相关联，并且使用给定的底层架构解决问题的计算复杂性可以通过复合体的某些拓扑特性来捕获。这些属性用于给出异步读/写内存中可解决的同步问题的完整特征，并提供异步模型和同步消息传递模型中几个已知开放问题的不可能结果和下限。这些技术正被应用于多处理器同步的综合理论。＊＊＊

The choice of primitive coordination operations, whether reading and writing a shared memory, message-passing, or more complex operations, has become a crucial design issue. To make such choices, one must analyze the behavior of multi- process executions, reasoning about the multitude of possible combinations of concurrent operations. This is an unusually delicate and laborious task. The goal of this research is to replace this need to argue about concurrent executions with combinatorial conditions on the geometric representation of problems. This should allow researchers and designers, instead of analyzing behaviors, to apply powerful mathematical tools to recognize when certain protocols are impossible, to evaluate the power of alternative synchronization primitives, or to make explicit the assumptions needed to make a given problem solvable. This project pursues the problem of characterizing and classifying the power of synchronization primitives in different models. Prior research has developed powerful new tools based on classical topology for analyzing fault- tolerant concurrent alogrithms and data structures in a variety of models and architectures. This research has shown that a large class of synchronization problems can be associated with a high-dimensional geometric structure called a simplicial complex, and that the computational complexity of solving the problem using a given underlying architecture is captured by certain topological properties of the complex. These properties have been used to give a complete characterization of the synchronization problems solvable in asynchronous read/write memory, and to provide impossiblity results and lower bounds for several known open problems in both the asynchronous model and in the synchronous message-passing model. These techniques are being applied toward a comprehensive theory of multiprocessor synchronization. ***