Hostname: page-component-74656f9884-2dmjx Total loading time: 0 Render date: 2026-11-08T08:36:34.979Z Has data issue: false hasContentIssue false
  • English
  • Français

Algebraic spans

Published online by Cambridge University Press:  01 August 2000

MAURICE HERLIHY  and
SERGIO RAJSBAUM
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
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

Type
Research Article
Information
Mathematical Structures in Computer Science , Volume 10 , Issue 4 , August 2000 , pp. 549 - 573
Copyright
2000 Cambridge University Press

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.