More Web Proxy on the site http://driver.im/

article

Algebraic spans

Authors:

Maurice Herlihy,

Sergio RajsbaumAuthors Info & Claims

Mathematical Structures in Computer Science, Volume 10, Issue 4

Pages 549 - 573

https://doi.org/10.1017/S0960129500003170

Published: 01 August 2000 Publication History

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.

References

[1]

Attiya, H., Bar-Noy, A., Dolev, D., Peleg, D. and Reischuk, R. (1990) Renaming in an asynchronous environment. Journal of the ACM 37 (3) 524-548.

Digital Library

[2]

Attiya, H. and Rajsbaum, S. (1996) A combinatorial topology framework for wait-free computability. In: Proc. 10th International Workshop on Distributed Algorithms. Springer-Verlag Lecture Notes in Computer Science 1151 321-343.

[3]

Attiya, H. and Welch, J. (1998) Distributed Computing: Fundamentals, Simulations and Advanced Topics (First Edition), McGraw-Hill.

[4]

Bar-Noy, A. and Dolev, D. (1989) Shared memory vs. message passing in an asynchronous distributed environment. In: Proceedings of the 8th Annual ACM Symposium on Principles of Distributed Computing 371-382.

[5]

Biran, O., Moran, S. and Zaks, S. (1990) A combinatorial characterization of the distributed 1-solvable tasks. Journal of Algorithms 11 420-440.

Digital Library

[6]

Borowsky, E. and Gafni, E. (1993a) Generalized FLP impossibility result for t-resilient asynchronous computations. In: Proceedings of the 1993 ACM Symposium on Theory of Computing 91-100.

[7]

Borowsky, E. and Gafni, E. (1993b) The implication of the Borowsky-Gafni simulation on the set consensus hierarchy. Technical Report 930021, UCLA Computer Science Dept.

[8]

Chaudhuri, S. (1993) More choices allow more faults: Set consensus problems in totally asynchronous systems. Information and Computation 105 (1) 132-158.

Digital Library

[9]

Chaudhuri, S., Herlihy, M., Lynch, N. and Tuttle, M. (1993) A tight lower bound for k-set agreement. In: Proceedings of the 34th IEEE Symposium on Foundations of Computer Science 206-215.

[10]

Fischer, M., Lynch, N. and Paterson, M. (1985) Impossibility of distributed commit with one faulty process. Journal of the ACM 32 (2) 374-382.

Digital Library

[11]

Herlihy, M. and Rajsbaum, S. (1994) Set consensus using arbitrary objects. In: Proceedings of the 13th Annual ACM Symposium on Principles of Distributed Computing 324-333.

[12]

Herlihy, M. and Rajsbaum, S. (1995) A Primer on Algebraic Topology and Distributed Computing. Springer-Verlag Lecture Notes in Computer Science 1000 203-217.

[13]

Herlihy, M. and Rajsbaum, S. (1999) New perspectives in distributed computing. In: Proc. of the 24th Mathematical Foundations of Computer Science. Springer-Verlag Lecture Notes in Computer Science 1672 170-186.

[14]

Herlihy, M., Rajsbaum, S. and Tuttle, M. (1998) Unifying synchronous and asynchronous message-passing models. In: Proceedings of the 17th Annual ACM Symposium on Principles of Distributed Computing 133-142.

[15]

Herlihy, M. and Shavit, N. (1993) The asynchronous computability theorem for t-resilient tasks. In: Proceedings of the 1993 ACM Symposium on Theory of Computing 111-120.

[16]

Herlihy, M. and Shavit, N. (1994) A simple constructive computability theorem for wait-free computation. In: Proceedings of the 1994 ACM Symposium on Theory of Computing 243-252.

[17]

Herlihy, M. and Shavit, N. (1999) The topological structure of asynchronous computability. In: Journal of the ACM (to appear).

[18]

Herlihy, M. P. and Tuttle, M. R. (1990) Wait-free computation in message-passing systems: Preliminary report. In: Proceedings of the 9th Annual ACM Symposium on Principles of Distributed Computing 347-362.

[19]

Lynch, N. (1996) Distributed Algorithms (First Edition), Morgan Kaufmann Publishers.

[20]

Lynch, N. and Rajsbaum, S. (1996) On the borowsky-gafni simulation algorithm. In: 4th Israeli Symposium on Theory of Computing and Systems 4-15.

[21]

Munkres, J. (1984) Elements Of Algebraic Topology, Addison Wesley.

[22]

Saks, M. and Zaharoglou, F. (1993) Wait-free k-set agreement is impossible: The topology of public knowledge. In: Proceedings of the 1993 ACM Symposium on Theory of Computing 101-110.

[23]

tom Dieck, T. (1987) Transformation groups. de Gruiter Studies in Mathematics 8 126.

[24]

tom Dieck, T. and Petrie, T. (1982) Publ. maths. ihes. de Gruiter Studies in Mathematics 56 337-377.

Cited By

Castañeda AFraigniaud PPaz ARajsbaum SRoy MTravers C(2019)A Topological Perspective on Distributed Network AlgorithmsStructural Information and Communication Complexity10.1007/978-3-030-24922-9_1(3-18)Online publication date: 1-Jul-2019
https://dl.acm.org/doi/10.1007/978-3-030-24922-9_1
Attiya HPaz A(2016)Counting-based impossibility proofs for set agreement and renamingJournal of Parallel and Distributed Computing10.1016/j.jpdc.2015.09.00287:C(1-12)Online publication date: 1-Jan-2016
https://dl.acm.org/doi/10.1016/j.jpdc.2015.09.002
Gafni EKuznetsov PManolescu CHalldórsson MDolev S(2014)A generalized asynchronous computability theoremProceedings of the 2014 ACM symposium on Principles of distributed computing10.1145/2611462.2611477(222-231)Online publication date: 15-Jul-2014
https://dl.acm.org/doi/10.1145/2611462.2611477
Show More Cited By

Algebraic spans
1. Software and its engineering
  1. Software organization and properties
    1. Software system structures
2. Theory of computation

Recommendations

Representations of Algebraic Domains and Algebraic L-domains by Information Systems

Information systems play an important role in characterizing order structures. In this paper, we introduce the notions of the algebraic information system and algebraic L-information system. They are of the same logic-oriented style as the information ...
Algebraic Functions

Let A be an algebra. We say that the functions f ₁, . . . , f _m : A ⁿ A are algebraic on A provided there is a finite system of term-equalities $${{\bigwedge t_{k}(\overline{x}, \overline{z}) = s_{k}(\overline{x}, \overline{z})}}$$ satisfying that for each $${{\overline{a} \in A^{n}}}$$ , the m -tuple $${{(f_{1}(\overline{a}), \ldots , f_{m}(\overline{a}))}}$$ is the unique solution in A ^m to the ...
Algebraic structures on double and plane posets

We study the Hopf algebra of double posets and two of its Hopf subalgebras, the Hopf algebras of plane posets and of posets "without N". We prove that they are free, cofree, self-dual, and we give an explicit Hopf pairing on these Hopf algebras. We also ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Mathematical Structures in Computer Science

Mathematical Structures in Computer Science Volume 10, Issue 4

August 2000

162 pages

ISSN:0960-1295

Issue’s Table of Contents

Publisher

Cambridge University Press

United States

Publication History

Published: 01 August 2000

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

28
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Castañeda AFraigniaud PPaz ARajsbaum SRoy MTravers C(2019)A Topological Perspective on Distributed Network AlgorithmsStructural Information and Communication Complexity10.1007/978-3-030-24922-9_1(3-18)Online publication date: 1-Jul-2019
https://dl.acm.org/doi/10.1007/978-3-030-24922-9_1
Attiya HPaz A(2016)Counting-based impossibility proofs for set agreement and renamingJournal of Parallel and Distributed Computing10.1016/j.jpdc.2015.09.00287:C(1-12)Online publication date: 1-Jan-2016
https://dl.acm.org/doi/10.1016/j.jpdc.2015.09.002
Gafni EKuznetsov PManolescu CHalldórsson MDolev S(2014)A generalized asynchronous computability theoremProceedings of the 2014 ACM symposium on Principles of distributed computing10.1145/2611462.2611477(222-231)Online publication date: 15-Jul-2014
https://dl.acm.org/doi/10.1145/2611462.2611477
Castañeda AHerlihy MRajsbaum S(2014)An Equivariance Theorem with Applications to RenamingAlgorithmica10.1007/s00453-013-9855-370:2(171-194)Online publication date: 1-Oct-2014
https://dl.acm.org/doi/10.1007/s00453-013-9855-3
Herlihy MRajsbaum S(2013)The topology of distributed adversariesDistributed Computing10.1007/s00446-013-0189-926:3(173-192)Online publication date: 1-Jun-2013
https://dl.acm.org/doi/10.1007/s00446-013-0189-9
Castañeda ARajsbaum S(2012)An Inductive-style Procedure for Counting Monochromatic Simplexes of Symmetric Subdivisions with Applications to Distributed ComputingElectronic Notes in Theoretical Computer Science (ENTCS)10.5555/2952796.2952911283:C(13-27)Online publication date: 15-Jun-2012
https://dl.acm.org/doi/10.5555/2952796.2952911
Herlihy MRajsbaum SKowalski DPanconesi A(2012)Simulations and reductions for colorless tasksProceedings of the 2012 ACM symposium on Principles of distributed computing10.1145/2332432.2332483(253-260)Online publication date: 16-Jul-2012
https://dl.acm.org/doi/10.1145/2332432.2332483
Castañeda ARajsbaum S(2012)New combinatorial topology bounds for renamingJournal of the ACM10.1145/2108242.210824559:1(1-49)Online publication date: 2-Mar-2012
https://dl.acm.org/doi/10.1145/2108242.2108245
Attiya HPaz A(2012)Counting-based impossibility proofs for renaming and set agreementProceedings of the 26th international conference on Distributed Computing10.1007/978-3-642-33651-5_25(356-370)Online publication date: 16-Oct-2012
https://dl.acm.org/doi/10.1007/978-3-642-33651-5_25
Castañeda AHerlihy MRajsbaum S(2012)An equivariance theorem with applications to renamingProceedings of the 10th Latin American international conference on Theoretical Informatics10.1007/978-3-642-29344-3_12(133-144)Online publication date: 16-Apr-2012
https://dl.acm.org/doi/10.1007/978-3-642-29344-3_12
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents