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

research-article

The topology of shared-memory adversaries

Authors:

Maurice Herlihy,

Sergio RajsbaumAuthors Info & Claims

PODC '10: Proceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing

Pages 105 - 113

https://doi.org/10.1145/1835698.1835724

Published: 25 July 2010 Publication History

Abstract

Failure patterns in modern parallel and distributed system are not necessarily uniform. The notion of an adversary scheduler is a natural way to extend the classical wait-free and t-faulty models of computation. A well-established way to characterize an adversary is by its set of cores, where a core is any minimal set of processes that cannot all fail in any execution. We show that the protocol complex associated with an adversary is (c-2)-connected, where c is the size of the adversary's smallest core. This implies, among other results, that such an adversary can solve c-set agreement, but not (c-1)-set agreement. The proofs are combinatorial, relying on a novel application of the Nerve Theorem of modern combinatorial topology.

References

[1]

Yehuda Afek, Hagit Attiya, Danny Dolev, Eli Gafni, Michael Merritt, and Nir Shavit. Atomic snapshots of shared memory. Journal of the ACM, 40(4):873--890, 1993.

Digital Library

[2]

Hagit Attiya, Amotz Bar-Noy, Danny Dolev, David Peleg, and Rudiger Reischuk. Renaming in an asynchronous environment. Journal of the ACM, July 1990.

Digital Library

[3]

Ofer Biran, Shlomo Moran, and Shmuel Zaks. A combinatorial characterization of the distributed 1-solvable tasks. J. Algorithms, 11(3):420--440, 1990.

Digital Library

[4]

A. Björner. Topological methods. pages 1819--1872, 1995.

[5]

Elizabeth Borowsky and Eli Gafni. Immediate atomic snapshots and fast renaming. In PODC '93: Proceedings of the twelfth annual ACM symposium on Principles of distributed computing, pages 41--51, New York, NY, USA, 1993. ACM.

Digital Library

[6]

Elizabeth Borowsky and Eli Gafni. A simple algorithmically reasoned characterization of wait-free computations (extended abstract). In PODC '97: Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, pages 189--198, New York, NY, USA, 1997. ACM.

Digital Library

[7]

Elizabeth Borowsky, Eli Gafni, Nancy Lynch, and Sergio Rajsbaum. The bg distributed simulation algorithm. Distributed Computing, 14(3):127--146, 2001.

Digital Library

[8]

Soma Chaudhuri. More choices allow more faults: Set consensus problems in totally asynchronous systems. Information and Computation, 105(1):132--158, July 1993. A preliminary version appeared in ACM PODC, 1990.

Digital Library

[9]

Carole Delporte-Gallet, Hugues Fauconnier, Rachid Guerraoui, and Andreas Tielmann. The disagreement power of an adversary: extended abstract. In Proceedings of the 28th ACM symposium on Principles of distributed computing, pages 288--289, New York, NY, USA, 2009. ACM.

Digital Library

[10]

Alan David Fekete. Asynchronous approximate agreement. Inf. Comput., 115(1):95--124, 1994.

Digital Library

[11]

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

Digital Library

[12]

Eli Gafni and Elias Koutsoupias. Three-processor tasks are undecidable. SIAM J. Comput., 28(3):970--983, 1999.

Digital Library

[13]

Eli Gafni and Sergio Rajsbaum. Distributed programming with tasks. Technical Report 100001, Los Angeles, CA, USA, november 2009.

[14]

Eli Gafni, Sergio Rajsbaum, and Maurice Herlihy. Subconsensus tasks: Renaming is weaker than set agreement. In Distributed Computing, 20th International Symposium, Stockholm, Sweden, September 18-20, 2006, Proceedings (DISC), volume 4167 of Lecture Notes in Computer Science, pages 329--338. Springer, 2006.

Digital Library

[15]

Maurice Herlihy and Sergio Rajsbaum. Set consensus using arbitrary objects (preliminary version). In PODC '94: Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, pages 324--333, New York, NY, USA, 1994. ACM.

Digital Library

[16]

Maurice Herlihy and Sergio Rajsbaum. Algebraic spans. In PODC '95: Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, pages 90--99, New York, NY, USA, 1995. ACM.

Digital Library

[17]

Maurice Herlihy and Sergio Rajsbaum. The decidability of distributed decision tasks (extended abstract). In STOC '97: Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, pages 589--598, New York, NY, USA, 1997. ACM.

Digital Library

[18]

Maurice Herlihy and Sergio Rajsbaum. Algebraic spans. Mathematical Structures in Computer Science, 10(4):549--573, 2000.

Digital Library

[19]

Maurice Herlihy and Sergio Rajsbaum. A classification of wait-free loop agreement tasks. Theor. Comput. Sci., 291(1):55--77, 2003.

Digital Library

[20]

Maurice Herlihy, Sergio Rajsbaum, and Mark Tuttle. An axiomatic approach to computing the connectivity of synchronous and asynchronous systems. Electron. Notes Theor. Comput. Sci., 230:79--102, 2009.

Digital Library

[21]

Maurice Herlihy, Sergio Rajsbaum, and Mark R. Tuttle. Unifying synchronous and asynchronous message-passing models. In PODC '98: Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, pages 133--142, New York, NY, USA, 1998. ACM.

Digital Library

[22]

Maurice Herlihy and Nir Shavit. The topological structure of asynchronous computability. J. ACM, 46(6):858--923, 1999.

Digital Library

[23]

Flavio Junqueira and Keith Marzullo. A framework for the design of dependent-failure algorithms: Research articles. Concurr. Comput. : Pract. Exper., 19(17):2255--2269, 2007.

Digital Library

[24]

Flavio Paiva Junqueira and Keith Marzullo. Designing algorithms for dependent process failures. In Future Directions in Distributed Computing, pages 24--28, 2003.

Digital Library

[25]

Sergio Rajsbaum, Michel Raynal, and Corentin Travers. The iterated restricted immediate snapshot model. In Computing and Combinatorics, 14th Annual International Conference, COCOON 2008, Dalian, China, June 27-29, 2008, Proceedings, volume 5092 of Lecture Notes in Computer Science, pages 487--497. Springer, 2008.

Digital Library

[26]

Michael Saks and Fotios Zaharoglou. Wait-free k-set agreement is impossible: The topology of public knowledge. SIAM J. Comput., 29(5):1449--1483, 2000.

Digital Library

Cited By

Toyos-Marfurt GKuznetsov P(2024)On the Bit Complexity of Iterated MemoryStructural Information and Communication Complexity10.1007/978-3-031-60603-8_25(456-477)Online publication date: 23-May-2024
https://doi.org/10.1007/978-3-031-60603-8_25
Conde RRajsbaum S(2023)The Solvability of Consensus in Iterated Models Extended with Safe-ConsensusTheory of Computing Systems10.1007/s00224-023-10125-z67:5(901-955)Online publication date: 17-Jul-2023
https://doi.org/10.1007/s00224-023-10125-z
Zhao D(2022)Cross-Blockchain Transactions: Systems, Protocols, and Topological TheoryHandbook on Blockchain10.1007/978-3-031-07535-3_5(157-193)Online publication date: 4-Nov-2022
https://doi.org/10.1007/978-3-031-07535-3_5
Show More Cited By

Index Terms

The topology of shared-memory adversaries
1. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
2. Theory of computation
  1. Logic
  2. Models of computation

Recommendations

Teaching shared memory parallel concepts with OpenMP (abstract only)
SIGCSE '14: Proceedings of the 45th ACM technical symposium on Computer science education

Curriculum 2013 brings parallelism into the CS curricular mainstream. This hands-on workshop is intended for faculty with little or no background in parallel computing. OpenMP is a platform independent, industry-standard library for shared-memory ...
Variable Dimension Complexes Part II: A Unified Approach to Some Combinatorial Lemmas in Topology

<P>Part II of this study uses the path-following theory of labelled V-complexes developed in Part I to provide constructive algorithmic proofs of a variety of combinatorial lemmas in topology. We demonstrate two new dual lemmas on the n-dimensional cube,...
Brief Announcement: Asynchronous Secure Distributed Computing with Transferrable Non-equivocation Revisited
PODC '18: Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing

In this paper, we consider two fundamental problems in secure distributed computing, namely Asynchronous Byzantine Agreement (ABA) and Asynchronous Secure Multi-party Computation (ASMPC). Our focus is on the honest majority setting, involving a set of n ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PODC '10: Proceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing

July 2010

494 pages

ISBN:9781605588889

DOI:10.1145/1835698

General Chairs:
Andrea Richa
Arizona State University, USA
,
Rachid Guerraoui
EPFL, Switzerland

Copyright © 2010 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 July 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

PODC '10

Sponsor:

PODC '10: ACM Symposium on Principles of Distributed Computing

July 25 - 28, 2010

Zurich, Switzerland

Acceptance Rates

Overall Acceptance Rate 740 of 2,477 submissions, 30%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

26
Total Citations
View Citations
413
Total Downloads

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

Reflects downloads up to 31 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Toyos-Marfurt GKuznetsov P(2024)On the Bit Complexity of Iterated MemoryStructural Information and Communication Complexity10.1007/978-3-031-60603-8_25(456-477)Online publication date: 23-May-2024
https://doi.org/10.1007/978-3-031-60603-8_25
Conde RRajsbaum S(2023)The Solvability of Consensus in Iterated Models Extended with Safe-ConsensusTheory of Computing Systems10.1007/s00224-023-10125-z67:5(901-955)Online publication date: 17-Jul-2023
https://doi.org/10.1007/s00224-023-10125-z
Zhao D(2022)Cross-Blockchain Transactions: Systems, Protocols, and Topological TheoryHandbook on Blockchain10.1007/978-3-031-07535-3_5(157-193)Online publication date: 4-Nov-2022
https://doi.org/10.1007/978-3-031-07535-3_5
Yanagisawa N(2019)Wait-free Solvability of Colorless Tasks in Anonymous Shared-memory ModelTheory of Computing Systems10.1007/s00224-017-9819-063:2(219-236)Online publication date: 1-Feb-2019
https://dl.acm.org/doi/10.1007/s00224-017-9819-0
Delporte-Gallet CFauconnier HRajsbaum SYanagisawa N(2018)A Characterization of t-Resilient Colorless Task Anonymous SolvabilityStructural Information and Communication Complexity10.1007/978-3-030-01325-7_18(178-192)Online publication date: 31-Oct-2018
https://doi.org/10.1007/978-3-030-01325-7_18
Kuznetsov PRieutord T(2017)Agreement Functions for Distributed Computing ModelsNetworked Systems10.1007/978-3-319-59647-1_14(175-190)Online publication date: 14-May-2017
https://doi.org/10.1007/978-3-319-59647-1_14
Yanagisawa N(2016)Wait-Free Solvability of Colorless Tasks in Anonymous Shared-Memory ModelStabilization, Safety, and Security of Distributed Systems10.1007/978-3-319-49259-9_32(415-429)Online publication date: 3-Nov-2016
https://doi.org/10.1007/978-3-319-49259-9_32
Mendes HTasson CHerlihy MShmoys D(2014)Distributed computability in Byzantine asynchronous systemsProceedings of the forty-sixth annual ACM symposium on Theory of computing10.1145/2591796.2591853(704-713)Online publication date: 31-May-2014
https://dl.acm.org/doi/10.1145/2591796.2591853
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 SRaynal MStainer J(2014)Computing in the Presence of Concurrent Solo ExecutionsLATIN 2014: Theoretical Informatics10.1007/978-3-642-54423-1_19(214-225)Online publication date: 2014
https://doi.org/10.1007/978-3-642-54423-1_19
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents