Hostname: page-component-7c8c6479df-nwzlb Total loading time: 0 Render date: 2024-03-27T11:50:17.523Z Has data issue: false hasContentIssue false

Algebraic spans

Published online by Cambridge University Press:  01 August 2000

MAURICE HERLIHY
Affiliation:
Computer Science Department, Brown University, Providence RI 02912. Email: herlihy@cs.brown.edu
SERGIO RAJSBAUM
Affiliation:
Instituto de Matemáticas, U.N.A.M., Ciudad Universitaria, D.F. 04510, México. Email: rajsbaum@math.unam.mx

Abstract

Topological methods have yielded a variety of lower bounds and impossibility results for distributed computing. In this paper, we introduce a new tool for proving impossibility results, which is based on a core theorem of algebraic topology, the acyclic carrier theorem, and unifies, generalizes and extends earlier results.

Type
Research Article
Copyright
2000 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

A preliminary version of this paper appeared in the Proceedings of the 14th ACM Symposium on Principles of Distributed Computing (PODC ’95), Aug. 20–23, Ottawa, Canada, 1995, pages 90–99.