Topological Methods in Distributed and Concurrent Computatioin

主要研究者：机构：Brown UniversityProposal NumberL 9912401摘要：从组合拓扑学和代数拓扑学中借用的概念和技术已被证明是分析分布式和并发计算的有效工具。 这一办法取得了各种成就，包括新的成果和更好地阐述以前的成果。 这里描述的研究计划是在两个方向上扩展这项工作。 首先，它侧重于从代数和组合拓扑学到更适合建模计算的组合形式的经典概念的重新表述。 这些概念可以简化和统一各种计算模式的分析。 第二，互补的重点是利用代数不变量发现的拓扑方法分类的计算能力的各种同步原语。

PI: Maurice HerlihyInstitution: Brown UniversityProposal NumberL 9912401Abstract:Concepts and techniques borrowed from combinatorial and algebraic topology have proved to be effective tools of for analyzing distributed and concurrent computation. This approach has yielded a variety of accomplishments, including new results and better formulations of earlier results. The research program described here is extending this work in tow directions. First, it focuses on reformulation classical notions from algebraic and combinatorial topology into a more combinatorial form better-suited to modeling computation. These notions can simplify and unify the analysis of a variety of computational modes. A second, complementary focus is on exploiting algebraic invariants uncovered by topological methods to classify the computational power of various synchronization primitives.