Article

Free access

A simple algorithmically reasoned characterization of wait-free computation (extended abstract)

Authors:

Elizabeth Borowsky,

Eli GafniAuthors Info & Claims

PODC '97: Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing

Pages 189 - 198

https://doi.org/10.1145/259380.259439

Published: 01 August 1997 Publication History

PDF eReader

References

[1]

Y. Afek, H. Attiya, D. Dolev, E. Gafni, M. Merrit, and N. Shavit, "Atomic Snapshots of Shared Memory," in Proceedings of the 9th A CM Symposium on Principles of Distributed Computing, pp. 1-13, 1990.

Digital Library

Google Scholar

[2]

M. Fischer, N. Lynch, and M. Paterson, "Impossibility of Distributed Consensus with One Faulty Process," Journal of the A CM, vol. 32, no. 2, pp. 374-382, 1985.

Digital Library

Google Scholar

[3]

O. Biran, S. Moran, and S. Zaks, "A Combinatorial Characterization of the Distributed Tasks which Are Solvable in the Presence of One Faulty Processor," in Proceedings of the 7th A CM Symposium on Principles of Distributed Computing, pp. 263-275, 1988.

Digital Library

Google Scholar

[4]

S. Chaudhuri, "More choices allow more faults: Set consensus problems in totally asynchronous systems," Information and Computation, vol. 105, pp. 132 - 158, jul 1993. supercedes 1990 PODC version.

Digital Library

Google Scholar

[5]

M. Saks and F. Zaharoglou, "Wait-Free k- Set Agreement is Impossible: The Topology of Public Knowledge," in Proceedings of the 26th A CM Symposium on the Theory of Computing, pp. 101-110, 1993.

Digital Library

Google Scholar

[6]

M. Herlihy and N. Shavit, "The Asynchronous Computability Theorem for t- Resilient Tasks," in Proceedings of the 25th A CM Symposium on the Theory of Computing, pp. 111-120, 1993.

Digital Library

Google Scholar

[7]

E. Borowsky and E. Gafni, "Generalized FLP Impossibility Result for t-Resilient Asynchronous Computations," in Proceedings of the 25th A CM Symposium on the Theory of Computing, pp. 91-100, 1993.

Digital Library

Google Scholar

[8]

E. Borowsky and E. Gafni, "immediate Atomic Snapshots and Fast Renaming," in Proceedings of the 12th A CM Symposium on Principles of Distributed Computing, pp. 41- 51, 1993.

Digital Library

Google Scholar

[9]

E. Gafni and E. Koutsoupias, "3-processor tasks are undecidable," in Proceedings of the ldth Annual A CM Symposium on Principles of Distributed Computing, p. 271, ACM, Aug. 1995.

Digital Library

Google Scholar

[10]

E. Borowsky, "Capturing the Power of Resiliency and Set Consensus in Distributed Systems,'' tech. rep., University of California, Los Angeles, Oct 15, 1995.

Google Scholar

[11]

E. Gafni and E. Koutsoupias, "New characterization of resiliency and consensus,"

Google Scholar

[12]

M. Herlihy and N. Shavit, "A Simple Constructive Computability Theorem for Waitfree Computation," in Proceedings of the 26th A CM Symposium on the Theory of Computing, 1994.

Digital Library

Google Scholar

[13]

H. Attiya and S. Rajsbaum, "The combinatorial structure of wait-free solvable tasks," Lecture Notes in Computer Science, vol. 1151, pp. 322-??, 1996.

Digital Library

Google Scholar

[14]

M. Mavronicolas, "Wait-free solvability via combinatorial topology," PODC96, Brief Announcement, 1996.

Digital Library

Google Scholar

[15]

C. P. Rourke and B. J. Sanderson, Introduction to Piecewise-Linear Topology. Springer Verlag, 1982.

Google Scholar

[16]

M. Herlihy and N. Shavit, "Th,~ topological structure of asynchronous computability," preprint, January 1996. stoc93, stoc94 of authors, long-awaited-new-improved.

Digital Library

Google Scholar

Cited By

View all

Delporte-Gallet CFauconnier HFraigniaud PRajsbaum STravers CKuznetsov PGelles ROlivetti D(2024)The Computational Power of Distributed Shared-Memory Models with Bounded-Size RegistersProceedings of the 43rd ACM Symposium on Principles of Distributed Computing10.1145/3662158.3662789(310-320)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3662158.3662789
Castañeda Avan Ditmarsch HRosenblueth DVelázquez D(2024)Pattern Models: A Dynamic Epistemic Logic For Distributed SystemsThe Computer Journal10.1093/comjnl/bxae01667:7(2421-2440)Online publication date: 17-Feb-2024
https://doi.org/10.1093/comjnl/bxae016
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: 27-May-2024
https://dl.acm.org/doi/10.1007/978-3-031-60603-8_25
Show More Cited By

Index Terms

Recommendations

Wait-n-GoTM: improving HTM performance by serializing cyclic dependencies
ASPLOS '13

Transactional memory (TM) has been proposed to alleviate some key programmability problems in chip multiprocessors. Most TMs optimistically allow concurrent transactions, detecting read-write or write-write conflicts. Upon conflicts, existing hardware ...
Wait-n-GoTM: improving HTM performance by serializing cyclic dependencies
ASPLOS '13

Transactional memory (TM) has been proposed to alleviate some key programmability problems in chip multiprocessors. Most TMs optimistically allow concurrent transactions, detecting read-write or write-write conflicts. Upon conflicts, existing hardware ...
Wait-n-GoTM: improving HTM performance by serializing cyclic dependencies
ASPLOS '13: Proceedings of the eighteenth international conference on Architectural support for programming languages and operating systems

Transactional memory (TM) has been proposed to alleviate some key programmability problems in chip multiprocessors. Most TMs optimistically allow concurrent transactions, detecting read-write or write-write conflicts. Upon conflicts, existing hardware ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

PODC '97: Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing

August 1997

297 pages

ISBN:0897919521

DOI:10.1145/259380

Chairmen:
James E. Burns
Bellcore
,
Hagit Attiya
Technion

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 August 1997

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

PODC97

Sponsor:

PODC97: Sixteenth ACM Symposium on Principles of Distributed Computing

August 21 - 24, 1997

California, Santa Barbara, USA

Acceptance Rates

PODC '97 Paper Acceptance Rate 46 of 149 submissions, 31%;

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

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

76
Total Citations
View Citations
535
Total Downloads

Downloads (Last 12 months)64
Downloads (Last 6 weeks)10

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Delporte-Gallet CFauconnier HFraigniaud PRajsbaum STravers CKuznetsov PGelles ROlivetti D(2024)The Computational Power of Distributed Shared-Memory Models with Bounded-Size RegistersProceedings of the 43rd ACM Symposium on Principles of Distributed Computing10.1145/3662158.3662789(310-320)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3662158.3662789
Castañeda Avan Ditmarsch HRosenblueth DVelázquez D(2024)Pattern Models: A Dynamic Epistemic Logic For Distributed SystemsThe Computer Journal10.1093/comjnl/bxae01667:7(2421-2440)Online publication date: 17-Feb-2024
https://doi.org/10.1093/comjnl/bxae016
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: 27-May-2024
https://dl.acm.org/doi/10.1007/978-3-031-60603-8_25
Alistarh DEllen FRybicki J(2023)Wait-free approximate agreement on graphsTheoretical Computer Science10.1016/j.tcs.2023.113733948:COnline publication date: 28-Feb-2023
https://dl.acm.org/doi/10.1016/j.tcs.2023.113733
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
Yue YLiu XLei FWu J(2022)A Topological Characterization to Arbitrary Resilient Asynchronous ComplexityMathematics10.3390/math1015272010:15(2720)Online publication date: 1-Aug-2022
https://doi.org/10.3390/math10152720
Fraigniaud PPaz ARajsbaum SMilani AWoelfel P(2022)A Speedup Theorem for Asynchronous Computation with Applications to Consensus and Approximate AgreementProceedings of the 2022 ACM Symposium on Principles of Distributed Computing10.1145/3519270.3538422(460-470)Online publication date: 20-Jul-2022
https://dl.acm.org/doi/10.1145/3519270.3538422
Delporte CFauconnier HRajsbaum SRaynal M(2022)Distributed computability: Relating k-immediate snapshot and x-set agreementInformation and Computation10.1016/j.ic.2021.104815285(104815)Online publication date: May-2022
https://doi.org/10.1016/j.ic.2021.104815
Velázquez DCastañeda ARosenblueth D(2021)Communication Pattern Models: An Extension of Action Models for Dynamic-Network Distributed SystemsElectronic Proceedings in Theoretical Computer Science10.4204/EPTCS.335.29335(307-321)Online publication date: 22-Jun-2021
https://doi.org/10.4204/EPTCS.335.29
Alistarh DEllen FRybicki J(2021)Wait-Free Approximate Agreement on GraphsStructural Information and Communication Complexity10.1007/978-3-030-79527-6_6(87-105)Online publication date: 20-Jun-2021
https://doi.org/10.1007/978-3-030-79527-6_6
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

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

Cited By

Index Terms

Recommendations

Wait-n-GoTM: improving HTM performance by serializing cyclic dependencies

Wait-n-GoTM: improving HTM performance by serializing cyclic dependencies

Wait-n-GoTM: improving HTM performance by serializing cyclic dependencies