Article

Free access

Wait-free data structures in the asynchronous PRAM model

Authors:

J. Aspnes,

M. HerlihyAuthors Info & Claims

SPAA '90: Proceedings of the second annual ACM symposium on Parallel algorithms and architectures

Pages 340 - 349

https://doi.org/10.1145/97444.97701

Published: 01 May 1990 Publication History

PDF eReader

References

[1]

Y. Afek, H. Attiya, D. Dolev, E. Gafni, M. Merritt, and N. Shavit. Atomic snapshots. Ninth ACM Symposium on Principles of Distributed Computing, to appear., 1990.

Digital Library

Google Scholar

[2]

Anderson. Composite registers. Tcchnlcal Report TR- 89-25, University of Texas at Austin, September 1989.

Digital Library

Google Scholar

[3]

J. Aspnes and M.P. Herlihy. Randomized algorithms for wait-free synchronization. Submitted for publication.

Google Scholar

[4]

P.A. Beznstein and N. Goodman. Concurrency control in distributed database systems. A CM Computing Surveys, 13(2):185-222, June 1981.

Digital Library

Google Scholar

[5]

B. Bloom. Constructing two-writer atomic registers. In Proceedings of the Sixth A CM Symposium on Principles o} Distributed Computing, pages 249-259, 1987.

Digital Library

Google Scholar

[6]

J.E. Burns and G.L. Peterson. Constructing multireader atomic values from non-atomic values. In Proceedings of the Sixth A CM Symposium on Principles of Distributed Computing, pages 222-231, 1987.

Digital Library

Google Scholar

[7]

It. Cole and O. Zajiec. The apram: incorporating asynchrony into the prom model. In Proceedings of the 1989 Symposium on Parallel Algorithms and Architectures, pages 169-178, Santa Fe, NM, June 1989.

Digital Library

Google Scholar

[8]

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

Digital Library

Google Scholar

[9]

P.B. Gibbons. A more practical prom model. In Proceedings of the 1989 Symposium on Parallel Algorithms and Architectures, pages 158-168, Santa Fe, NM, June 1989.

Digital Library

Google Scholar

[10]

M.P. Herlihy. Wait-free synchronization. Accepted for publication, ACM TOPLAS.

Digital Library

Google Scholar

[11]

M.P. Herlihy. Impossibility and universality results for walt-free synchronization. In Seventh A CM SIGA CT- SIGOPS Symposium on Principles of Distributed Computing, August 1988.

Digital Library

Google Scholar

[12]

M.P. Herlihy and J.M. Wing. Linearizabilty: a correctness condition for concurrent objects. Accepted for publication, ACM TOPLAS.

Digital Library

Google Scholar

[13]

M.P. Herlihy and J.M. Wing. Axioms for concurrent objects. In 1jth A CM Symposium on Principlea of Programming Languages, pages 13-26, January 1987.

Digital Library

Google Scholar

[14]

L. Lamport. Concurrent reading and writing. Communications of the A CM, 20(11):806-811, November 1977.

Digital Library

Google Scholar

[15]

L. Lamport. Time, clocks, and the ordering of events in a distributed system. Communications of the A CM, 21(7):558-565, July 1978.

Digital Library

Google Scholar

[16]

L. Lamport. How to make a multiprocessor computer that correctly executes multiprocess programs. IEEE Transactions on Computers, C-28(9):690, September 1979.

Digital Library

Google Scholar

[17]

L. Lamport. On interprocess communication, parts i and ii. Distributed Computing, 1:77-101, 1986.

Crossref

Google Scholar

[18]

N.A. Lyltch and M.R. Turtle. An introduction to input/output automata. Technical Report MIT/LCS/TM-373, MIT Laboratory for Computer Science, November 1988.

Google Scholar

[19]

It. Newman-Wolfe. A protocol for wait-free, atomic, multi-reader shared variables. In Proceedings of the Sixth A CM Symposium on Principles of Distributed Computing, pages 232-249, 1987.

Digital Library

Google Scholar

[20]

C.H. Papadlmitriou. The serlalizability of concurrent database updates. Journal o} the A CM, 26(4):631-653, October 1979.

Digital Library

Google Scholar

[21]

G.L. Peterson. Concurrent reading while writing. A CM Transactions on Programming Languages and Systems, 5(1):46-55, January 1983.

Digital Library

Google Scholar

[22]

G.L. Pctcrson and J.E. Burns. Concurrent ~eading while writing ii: the multi-writer case. Technical Report GIT-ICS-86/26, Georgia Institute of Technology, December 1986.

Google Scholar

[23]

A.K. Singh, J.H. Anderson, and M.G. Gouda. The elusive atomic register revisited. In Proceedings of the Sixth A CM Symposium on Principles of Distributed Computing, pages 206-221, August 1987.

Digital Library

Google Scholar

[24]

P. Vitanyi and B. Awerbuch. Atomic shared register access by asynchronous hardware. In Proceedings of of the ~Tth IEEE Symposium on Foundations of Computer Science, pages 223-243, 1986. See also errata in SIGACT News 18(4), Summer, 1987.

Digital Library

Google Scholar

[25]

W.E. Wcihl. Specification and implementation of atomic data types. Technical Report TR-314, MIT Laboratory for Computer Science, March 1984.

Digital Library

Google Scholar

Cited By

View all

Jayanti PJayanti SJayanti SKuznetsov PGelles ROlivetti D(2024)MemSnap: A Fast Adaptive Snapshot Algorithm for RMWable Shared-MemoryProceedings of the 43rd ACM Symposium on Principles of Distributed Computing10.1145/3662158.3662820(25-35)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3662158.3662820
Kallimanis NKanellou EKiosterakis CLiagkou V(2023)Exploring Trade-Offs in Partial Snapshot ImplementationsStabilization, Safety, and Security of Distributed Systems10.1007/978-3-031-44274-2_8(90-105)Online publication date: 30-Sep-2023
https://doi.org/10.1007/978-3-031-44274-2_8
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
Show More Cited By

Index Terms

Wait-free data structures in the asynchronous PRAM model

Recommendations

The Queue-Read Queue-Write Asynchronous PRAM Model
A practical wait-free simulation for lock-free data structures
PPoPP '14: Proceedings of the 19th ACM SIGPLAN symposium on Principles and practice of parallel programming

Lock-free data structures guarantee overall system progress, whereas wait-free data structures guarantee the progress of each and every thread, providing the desirable non-starvation guarantee for concurrent data structures. While practical lock-free ...
A practical wait-free simulation for lock-free data structures
PPoPP '14

Lock-free data structures guarantee overall system progress, whereas wait-free data structures guarantee the progress of each and every thread, providing the desirable non-starvation guarantee for concurrent data structures. While practical lock-free ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SPAA '90: Proceedings of the second annual ACM symposium on Parallel algorithms and architectures

May 1990

417 pages

ISBN:0897913701

DOI:10.1145/97444

Chairman:
F. T. Leighton
Massachusetts Institute of Technology, Cambridge, MA

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 May 1990

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SPAA90

Sponsor:

Computer Tech Inst.
CTI
SIGACT
SIGARCH
EATCS
IEEE-CS

SPAA90: 2nd Annual ACM Symposium on Parallel Algorithms & Architecture

July 2 - 6, 1990

Island of Crete, Greece

Acceptance Rates

Overall Acceptance Rate 447 of 1,461 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

81
Total Citations
View Citations
584
Total Downloads

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

Reflects downloads up to 30 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Jayanti PJayanti SJayanti SKuznetsov PGelles ROlivetti D(2024)MemSnap: A Fast Adaptive Snapshot Algorithm for RMWable Shared-MemoryProceedings of the 43rd ACM Symposium on Principles of Distributed Computing10.1145/3662158.3662820(25-35)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3662158.3662820
Kallimanis NKanellou EKiosterakis CLiagkou V(2023)Exploring Trade-Offs in Partial Snapshot ImplementationsStabilization, Safety, and Security of Distributed Systems10.1007/978-3-031-44274-2_8(90-105)Online publication date: 30-Sep-2023
https://doi.org/10.1007/978-3-031-44274-2_8
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
Adas DFriedman R(2022)A Fast Wait-Free Multi-Producers Single-Consumer QueueProceedings of the 23rd International Conference on Distributed Computing and Networking10.1145/3491003.3491004(77-86)Online publication date: 4-Jan-2022
https://dl.acm.org/doi/10.1145/3491003.3491004
Garg VKumar STseng LZheng X(2022)Fault-tolerant Snapshot Objects in Message Passing Systems2022 IEEE International Parallel and Distributed Processing Symposium (IPDPS)10.1109/IPDPS53621.2022.00113(1129-1139)Online publication date: May-2022
https://doi.org/10.1109/IPDPS53621.2022.00113
Attiya HCastañeda AHendler DPerrin M(2022)Separating lock-freedom from wait-freedom at every level of the consensus hierarchyJournal of Parallel and Distributed Computing10.1016/j.jpdc.2022.01.025163(181-197)Online publication date: May-2022
https://doi.org/10.1016/j.jpdc.2022.01.025
Imbs DMostéfaoui APerrin MRaynal M(2021)Set-constrained delivery broadcast: A communication abstraction for read/write implementable distributed objectsTheoretical Computer Science10.1016/j.tcs.2021.06.044Online publication date: Jul-2021
https://doi.org/10.1016/j.tcs.2021.06.044
Ovens SWoelfel PRobinson PEllen F(2019)Strongly Linearizable Implementations of Snapshots and Other TypesProceedings of the 2019 ACM Symposium on Principles of Distributed Computing10.1145/3293611.3331632(197-206)Online publication date: 16-Jul-2019
https://dl.acm.org/doi/10.1145/3293611.3331632
Attiya HCastañeda AHendler DPerrin MNewport CKeidar I(2018)Separating Lock-Freedom from Wait-FreedomProceedings of the 2018 ACM Symposium on Principles of Distributed Computing10.1145/3212734.3212739(41-50)Online publication date: 23-Jul-2018
https://dl.acm.org/doi/10.1145/3212734.3212739
Imbs DMostéfaoui APerrin MRaynal M(2018)Set-Constrained Delivery BroadcastProceedings of the 19th International Conference on Distributed Computing and Networking10.1145/3154273.3154296(1-10)Online publication date: 4-Jan-2018
https://dl.acm.org/doi/10.1145/3154273.3154296
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

The Queue-Read Queue-Write Asynchronous PRAM Model

A practical wait-free simulation for lock-free data structures

A practical wait-free simulation for lock-free data structures