Hostname: page-component-78c5997874-94fs2 Total loading time: 0 Render date: 2024-11-16T19:24:44.219Z 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: [email protected]
SERGIO RAJSBAUM
Affiliation:
Instituto de Matemáticas, U.N.A.M., Ciudad Universitaria, D.F. 04510, México. Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

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
Information
Mathematical Structures in Computer Science , Volume 10 , Issue 4 , August 2000 , pp. 549 - 573
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.