A Primer on Algebraic Topology and Distributed Computing

Maurice Herlihy
Computer Science Department
Brown University
Providence RI 02912
herlihy@cs.brown.edu

Sergio Rajsbaum
Instituto de Matemáticas
U.N.A.M.
Mexico City, D.F. 04510, Mexico
rajsbaum@math.unam.mx

Abstract

Models and techniques borrowed from classical algebraic topology have recently yielded a variety of new lower bounds and impossibility results for distributed and concurrent computation. This paper explains the basic concepts underlying this approach, and shows how they apply to a simple distributed problem.

Postscript in Lecture Notes in Computer Science, Vol. 1000, pp. 203-217, 1995.