Topological Methods in Distributed and Concurrent Computatioin

Brown University, Providence RI

Investigators

Abstract

PI: Maurice Herlihy Institution: Brown University Proposal NumberL 9912401 Abstract: 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.