The Topological Approach to Asynchronous Computability

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

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. ***