Topological Methods in Distributed and Concurrent Computatioin

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

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.