ACM Portal
  Subscribe (Full Service)    Register (Limited Service, Free)    Login
  Search:   The ACM Digital Library   The Guide
  
ACM Home Page
Please provide us with feedback. Feedback
The asynchronous computability theorem for t-resilient tasks
Full text PdfPdf (915 KB)
Source Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-fifth annual ACM symposium on Theory of computing table of contents
San Diego, California, United States
Pages: 111 - 120  
Year of Publication: 1993
ISBN:0-89791-591-7
Authors
Maurice Herlihy
Nir Shavit
Sponsor
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
Publisher
ACM  New York, NY, USA
Bibliometrics
Downloads (6 Weeks): 1,   Downloads (12 Months): 25,   Citation Count: 43
Additional Information:

references   cited by   index terms   collaborative colleagues   peer to peer  

Tools and Actions: Review this Article  
Save this Article to a Binder    Display Formats: BibTex  EndNote ACM Ref   
DOI Bookmark: Use this link to bookmark this Article: http://doi.acm.org/10.1145/167088.167125
What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

1
Yehuda Afek , Danny Dolev , Hagit Attiya , Eli Gafni , Michael Merritt , Nir Shavit, Atomic snapshots of shared memory, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.1-13, August 22-24, 1990, Quebec City, Quebec, Canada  [doi>10.1145/93385.93394]
2
James Anderson, Composite registers, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.15-29, August 22-24, 1990, Quebec City, Quebec, Canada  [doi>10.1145/93385.93396]
3
Hagit Attiya , Amotz Bar-Noy , Danny Dolev, Sharing memory robustly in message-passing systems, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.363-375, August 22-24, 1990, Quebec City, Quebec, Canada  [doi>10.1145/93385.93441]
 
4
H. Attiya, A. Bar-Noy, D. Dolev, D. Koller, D. Peleg, and R. Reischuk. Achievable cases in an asynchronous environment. In Proceedings of the PSth IEEE Symposium on Foundations of Computer Science, pages 337-346, October 1987.
 
5
H. Attiya, N. Lynch, and N. Shavit. Are wait-free algorithms fast? In Proceedings of the 31st Annual Symposium on the Foundations of Computer Science, October 1990.
6
Ofer Biran , Shlomo Moran , Shmuel Zaks, A combinatorial characterization of the distributed tasks which are solvable in the presence of one faulty processor, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.263-275, August 15-17, 1988, Toronto, Ontario, Canada  [doi>10.1145/62546.62590]
7
Elizabeth Borowsky , Eli Gafni, Generalized FLP impossibility result for t-resilient asynchronous computations, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.91-100, May 16-18, 1993, San Diego, California, United States  [doi>10.1145/167088.167119]
8
Soma Chaudhuri, Agreement is harder than consensus: set consensus problems in totally asynchronous systems, Proceedings of the ninth annual ACM symposium on Principles of distributed computing, p.311-324, August 22-24, 1990, Quebec City, Quebec, Canada  [doi>10.1145/93385.93431]
9
Danny Dolev , Nancy A. Lynch , Shlomit S. Pinter , Eugene W. Stark , William E. Weihl, Reaching approximate agreement in the presence of faults, Journal of the ACM (JACM), v.33 n.3, p.499-516, July 1986  [doi>10.1145/5925.5931]
10
A D Fekete, Asymptotically optimal algorithms for approximate agreement, Proceedings of the fifth annual ACM symposium on Principles of distributed computing, p.73-87, August 11-13, 1986, Calgary, Alberta, Canada  [doi>10.1145/10590.10597]
11
Michael J. Fischer , Nancy A. Lynch , Michael S. Paterson, Impossibility of distributed consensus with one faulty process, Journal of the ACM (JACM), v.32 n.2, p.374-382, April 1985  [doi>10.1145/3149.214121]
12
Greg N. Frederickson , Nancy A. Lynch, Electing a leader in a synchronous ring, Journal of the ACM (JACM), v.34 n.1, p.98-115, Jan. 1987  [doi>10.1145/7531.7919]
 
13
P.J. Gibhn. Graphs, Surfaces, and Homology. Chapman and Hill, London and New York, 1981. Second edition.
 
14
M.J. Greenberg and J.R. Harper. Algebraic Topology: A First Course. Mathematics Lecture Notes Series. The Benjamin/Cummings Publishing Company, Reading MA, 1981.
15
Maurice Herlihy, Impossibility results for asynchronous PRAM (extended abstract), Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.327-336, July 21-24, 1991, Hilton Head, South Carolina, United States  [doi>10.1145/113379.113409]
16
Maurice Herlihy, Wait-free synchronization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.1, p.124-149, Jan. 1991  [doi>10.1145/114005.102808]
 
17
A. Israeli and M. Li. Bounded time-stamps. In Proceedings of the $8th IEEE Symposium on Foundations of Computer Science, pages 371-382, October 1987.
 
18
Prasad Jayanti , Sam Toueg, Some Results on the Impossibility, Universality, and Decidability of Consensus, Proceedings of the 6th International Workshop on Distributed Algorithms, p.69-84, November 02-04, 1992
 
19
S. Lefschetz. Introduction to Topology. Princeton University Press, Princeton, New Jersey, 1949.
 
20
M. Li, J. Tromp, and P.M. Vit~nyi. How to share concurrent wait-free variables. Technical Report CT-91-02, University of Amsterdam, Amsterdam, Netherlands, March 1991.
 
21
N.A. Lynch and M.R. Turtle. An introduction to input/output automata. Technical Report MIT/LCS/TM-373, MIT Laboratory for Computer Science, November 1988.
22
Stephen R. Mahaney , Fred B. Schneider, Inexact agreement: accuracy, precision, and graceful degradation, Proceedings of the fourth annual ACM symposium on Principles of distributed computing, p.237-249, August 1985, Minaki, Ontario, Canada  [doi>10.1145/323596.323618]
23
Michael Saks , Fotios Zaharoglou, Wait-free k-set agreement is impossible: the topology of public knowledge, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.101-110, May 16-18, 1993, San Diego, California, United States  [doi>10.1145/167088.167122]
 
24
E.H. Spanier, Algebraic Topology. Springer-Verlag, New York, 1966.

CITED BY  43
Eli Gafni, Simulation as an iterated task, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.278, May 23-26, 1996, Philadelphia, Pennsylvania, United States
Wai-Kau Lo, More on t-resilience vs. wait-freedom (extended abstract), Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.110-119, August 20-23, 1995, Ottowa, Ontario, Canada
Hagit Attiya, A direct lower bound for k-set consensus, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.314, June 28-July 02, 1998, Puerto Vallarta, Mexico
Elizabeth Borowsky , Eli Gafni, A simple algorithmically reasoned characterization of wait-free computation (extended abstract), Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.189-198, August 21-24, 1997, Santa Barbara, California, United States
Dimitris Michailidis, Fast set agreement in the presence of timing uncertainty, Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing, p.249-256, May 04-06, 1999, Atlanta, Georgia, United States
Marios Mavronicolas, Wait-free solvability via combinatorial topology, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing, p.277, May 23-26, 1996, Philadelphia, Pennsylvania, United States
Roberto De Prisco , Dahlia Malkhi , Michael K. Reiter, On k-set consensus problems in asynchronous systems, Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing, p.257-265, May 04-06, 1999, Atlanta, Georgia, United States
Achour Mostéfaoui , Michel Raynal, k-set agreement with limited accuracy failure detectors, Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing, p.143-152, July 16-19, 2000, Portland, Oregon, United States
 
Ronit Lubitch , Shlomo Moran, Closed schedulers: a novel technique for analyzing asynchronous protocols, Distributed Computing, v.8 n.4, p.203-210, June 1995
Achour Mostefaoui , Michel Raynal, Randomized k-set agreement, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.291-297, July 2001, Crete Island, Greece
Hagit Attiya , Arie Fouren, Adaptive wait-free algorithms for lattice agreement and renaming (extended abstract), Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.277-286, June 28-July 02, 1998, Puerto Vallarta, Mexico
Rachid Guerraoui , Maurice Herlihy , Petr Kouznetsov , Nancy Lynch , Calvin Newport, On the weakest failure detector ever, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA
Harry Buhrman , Juan A. Garay , Jaap-Henki Hoepman , Mark Moir, Long-lived renaming made fast, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.194-203, August 20-23, 1995, Ottowa, Ontario, Canada
Prasad Jayanti, Robust wait-free hierarchies, Journal of the ACM (JACM), v.44 n.4, p.592-614, July 1997
Eli Gafni, Round-by-round fault detectors (extended abstract): unifying synchrony and asynchrony, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.143-152, June 28-July 02, 1998, Puerto Vallarta, Mexico
Maurice Herlihy , Nir Shavit, A simple constructive computability theorem for wait-free computation, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.243-252, May 23-25, 1994, Montreal, Quebec, Canada
Maurice Herlihy , Sergio Rajsbaum, Set consensus using arbitrary objects (preliminary version), Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.324-333, August 14-17, 1994, Los Angeles, California, United States
Yehuda Afek , Michael Merritt, Fast, wait-free (2k-1)-renaming, Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing, p.105-112, May 04-06, 1999, Atlanta, Georgia, United States
Yehuda Afek , Gideon Stupp, Delimiting the power of bounded size synchronization objects (extended abstract), Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.42-51, August 14-17, 1994, Los Angeles, California, United States
Elizabeth Borowsky , Eli Gafni , Yehuda Afek, Consensus power makes (some) sense! (extended abstract), Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.363-372, August 14-17, 1994, Los Angeles, California, United States
Michael Saks , Fotios Zaharoglou, Wait-free k-set agreement is impossible: the topology of public knowledge, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.101-110, May 16-18, 1993, San Diego, California, United States
Elizabeth Borowsky , Eli Gafni, Immediate atomic snapshots and fast renaming, Proceedings of the twelfth annual ACM symposium on Principles of distributed computing, p.41-51, August 15-18, 1993, Ithaca, New York, United States
Elizabeth Borowsky , Eli Gafni, Generalized FLP impossibility result for t-resilient asynchronous computations, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.91-100, May 16-18, 1993, San Diego, California, United States
Maurice Herlihy , Sergio Rajsbaum, Algebraic spans, Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing, p.90-99, August 20-23, 1995, Ottowa, Ontario, Canada
Benny Chor , Lee-Bath Nelson, Resilience of general interactive tasks, Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing, p.173-182, August 14-17, 1994, Los Angeles, California, United States
Eli Gafni , Michael Merritt , Gadi Taubenfeld, The concurrency hierarchy, and algorithms for unbounded concurrency, Proceedings of the twentieth annual ACM symposium on Principles of distributed computing, p.161-169, August 2001, Newport, Rhode Island, United States
 
Harry Buhrman , Alessandro Panconesi , Riccardo Silvestri , Paul Vitanyi, On the importance of having an identity or, is consensus really universal?, Distributed Computing, v.18 n.3, p.167-176, February 2006
 
Maurice Herlihy , Sergio Rajsbaum, Algebraic spans, Mathematical Structures in Computer Science, v.10 n.4, p.549-573, August 2000
Prasad Jayanti, A lower bound on the local time complexity of universal constructions, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.183-192, June 28-July 02, 1998, Puerto Vallarta, Mexico
 
Alessandro Panconesi , Marina Papatriantafilou , Philippas Tsigas , Paul Vitányi, Randomized naming using wait-free shared variables, Distributed Computing, v.11 n.3, p.113-124, August 1998
Maurice Herlihy , Sergio Rajsbaum , Mark R. Tuttle, Unifying synchronous and asynchronous message-passing models, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.133-142, June 28-July 02, 1998, Puerto Vallarta, Mexico
Eric Goubault, Schedulers as abstract interpretations of higher-dimensional automata, Proceedings of the 1995 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, p.134-145, June 21-23, 1995, La Jolla, California, United States
Yoram Moses , Sergio Rajsbaum, The unified structure of consensus: a layered analysis approach, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.123-132, June 28-July 02, 1998, Puerto Vallarta, Mexico
 
Yehuda Afek , Gideon Stupp , Dan Touitou, Long lived adaptive splitter and applications, Distributed Computing, v.15 n.2, p.67-86, April 2002
 
John Havlicek, Computable obstructions to wait-free computability, Distributed Computing, v.13 n.2, p.59-83, April 2000
 
Roberto de Prisco , Dahlia Malkhi , Michael Reiter, On k-Set Consensus Problems in Asynchronous Systems, IEEE Transactions on Parallel and Distributed Systems, v.12 n.1, p.7-21, January 2001
Gunnar Hoest , Nir Shavit, Towards a topological characterization of asynchronous complexity, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.199-208, August 21-24, 1997, Santa Barbara, California, United States
 
Maurice Herlihy , Sergio Rajsbaum, A classification of wait-free loop agreement tasks, Theoretical Computer Science, v.291 n.1, p.55-77, 4 January 2003
Maurice Herlihy , Nir Shavit, The topological structure of asynchronous computability, Journal of the ACM (JACM), v.46 n.6, p.858-923, Nov. 1999
Maurice Herlihy , Sergio Rajsbaum, The decidability of distributed decision tasks (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.589-598, May 04-06, 1997, El Paso, Texas, United States
Marcos K. Aguilera, A pleasant stroll through the land of infinitely many creatures, ACM SIGACT News, v.35 n.2, June 2004
 
Eric Goubault, Geometry and concurrency: a user's guide, Mathematical Structures in Computer Science, v.10 n.4, p.411-425, August 2000
 
Lisbeth Fajstrup , Martin Raußen , Eric Goubault, Algebraic topology and concurrency, Theoretical Computer Science, v.357 n.1, p.241-278, 25 July 2006

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Computability theory

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms


General Terms:
Algorithms, Theory

Collaborative Colleagues:
Maurice Herlihy: colleagues
Nir Shavit: colleagues

Peer to Peer - Readers of this Article have also read:

The ACM Portal is published by the Association for Computing Machinery. Copyright © 2008 ACM, Inc.
Terms of Usage   Privacy Policy   Code of Ethics   Contact Us

Useful downloads: Adobe Acrobat    QuickTime    Windows Media Player    Real Player