Article

Free access

Immediate atomic snapshots and fast renaming

Authors:

Elizabeth Borowsky,

Eli GafniAuthors Info & Claims

PODC '93: Proceedings of the twelfth annual ACM symposium on Principles of distributed computing

Pages 41 - 51

https://doi.org/10.1145/164051.164056

Published: 01 September 1993 Publication History

PDF eReader

References

[1]

Y. Afek, H. Attiya., D. Dolev, E. Ga.fni, M. Merritt, and N. Shavit, "Atomic Snai)shots of Shared Memory," Proc. 9th A CM,5"ymp. o~ Principles of Distributed Coputing pages 1- 14, 1990.

Crossref

Google Scholar

[2]

S. Owiki, "Axiomatic Proof Techniques for Parallel Programs," PhD Thesis, Cornell University, 1975.

Digital Library

Google Scholar

[3]

S. Owiki and D. Gries, "All Axiomatic Proof Technique for Parallel Programs," Acta Iaformatica, 6, 319-340. 1976.

Digital Library

Google Scholar

[4]

A. Bar-Noy, and D. Dolev, "Shared-Memory vs. Message-Passing in an Asynchronous Distributed Environment," Proc. 8 A CM Syrup. on Principles of Distributed Computing, pages 307-318, 1989.

Digital Library

Google Scholar

[5]

G.L. Peterson, "Myths about the Mutual Exclusion Problem," Infbrmation Processing Letters, 12, 115-116, 1981.

Crossref

Google Scholar

[6]

C. Paris and A. Shvartsman, "Efficient Parallel Algorithms on Restartable Fail-Stop Processors,'' Proc. 10 A CM Syrup. on Principles of' Distributed Computing, pages 23-37, 1991.

Digital Library

Google Scholar

[7]

L. La.mport, "A Fast Mutual Exclusion Algorithm,'' A CM Trans. Comp. Sys., 5, 1-11, 1987.

Digital Library

Google Scholar

[8]

H. Attiya, A. Bar-Noy, D. Dolev, D. Koller, D. Peleg, and R. Reischuk, "Achievable Cases in an Asynchronous Environment", Pvoc. 28th IE~E Syrup. on Fou~dations of Computer Science, pages 337-346, 1987.

Digital Library

Google Scholar

[9]

O. Biran, S. Moran, and S. Zaks, "A Combinatorial Characterization of the Distributed Tasks Which Are Solvable in the Presence of One Faulty Processor," Proc. 7th A UM Syrup. on Pri,~ciple.s of Distributed Computing, pages 263-275, 1988.

Digital Library

Google Scholar

[10]

A. Afek, D. Dotev. E. Gafni. ~I. Merritt, and N. Shavit, "First-in-First-Enabled 1- Exclusion,'' Proc. 4th Inter'national tForkshop on Distributed Algorithn,.s. 1990.

Digital Library

Google Scholar

[11]

M. Saks, and F. Za.ha.roglou." Wait-Free k- Set Agreement is Impossible: The Topology of Public Knowledge," to appear in STOC93.

Digital Library

Google Scholar

[12]

M. Herlihy and N. Shavit, "The Asynchronous Computability Theorem for t- Resilient Tasks," to appear in STOC93.

Digital Library

Google Scholar

[13]

E. Borowsky a.nd E. Gafi~i, "Generalized FLP Impossibility Result for t-Resilient. Asynchronous Computations," to appear ill STOC93.

Digital Library

Google Scholar

[14]

M. Choy and A.K. Singh, "Adaptive Solutions to the Mutual Exclusion Problem." this proceedings.

Digital Library

Google Scholar

[15]

H. Attiya, M. Herlihy, and O. Rachman, "Efficient Atomic Snapshots Using Lattice Agreement, ''Proc 6th lntcrnationetI IVovkshop o'l~ Distributed Algorithm.s, pages 35-53. 1992.

Digital Library

Google Scholar

Cited By

View all

Oliveira Vale AWang ZChen YYou PShao Z(2024)Compositionality and Observational Refinement for Linearizability with CrashesProceedings of the ACM on Programming Languages10.1145/36897928:OOPSLA2(2296-2324)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689792
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
Show More Cited By

Index Terms

Immediate atomic snapshots and fast renaming

Recommendations

Atomic snapshots of shared memory

This paper introduces a general formulation of atomic snapshot memory, a shared memory partitioned into words written (updated) by individual processes, or instantaneously read (scanned) in its entirety. This paper presents three wait-free ...
Atomic snapshots using lattice agreement

The snapshot object is an important tool for constructing wait-free asynchronous algorithms. We relate the snapshot object to the lattice agreement decision problem. It is shown that any algorithm for solving lattice agreement can be transformed into an ...
Fast non-blocking atomic commit: an inherent trade-off

This paper investigates the time-complexity of the non-blocking atomic commit (NBAC) problem in a synchronous distributed model where t out of n processes may fail by crashing. We exhibit for t ≥ 3 an inherent trade-off between the fast abort property ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

PODC '93: Proceedings of the twelfth annual ACM symposium on Principles of distributed computing

September 1993

271 pages

ISBN:0897916131

DOI:10.1145/164051

Chairmen:
Jim Anderson
Univ. of Maryland, College Park
,
Sam Toueg
Cornell Univ., Ithaca, NY

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 September 1993

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

PODC93

Sponsor:

PODC93: 12th Annual ACM Symposium on Principles of Distributed Computing

August 15 - 18, 1993

New York, Ithaca, USA

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

144
Total Citations
View Citations
877
Total Downloads

Downloads (Last 12 months)70
Downloads (Last 6 weeks)14

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Oliveira Vale AWang ZChen YYou PShao Z(2024)Compositionality and Observational Refinement for Linearizability with CrashesProceedings of the ACM on Programming Languages10.1145/36897928:OOPSLA2(2296-2324)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689792
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(113733)Online publication date: Feb-2023
https://doi.org/10.1016/j.tcs.2023.113733
Attiya HCastañeda ARajsbaum S(2023)Locally solvable tasks and the limitations of valency argumentsJournal of Parallel and Distributed Computing10.1016/j.jpdc.2023.02.002176(28-40)Online publication date: Jun-2023
https://doi.org/10.1016/j.jpdc.2023.02.002
Nishimura S(2023)Defining logical obstruction with fixpoints in epistemic logicJournal of Applied and Computational Topology10.1007/s41468-023-00151-88:4(941-970)Online publication date: 14-Nov-2023
https://doi.org/10.1007/s41468-023-00151-8
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
Raynal M(2022)Concurrent Crash-Prone Shared Memory Systems: A Few Theoretical NotionsSynthesis Lectures on Distributed Computing Theory10.2200/S01165ED1V01Y202202DCT01820:1(1-139)Online publication date: 21-Mar-2022
https://doi.org/10.2200/S01165ED1V01Y202202DCT018
Fraigniaud PLambein-Monette PRabie MMilani AWoelfel P(2022)Brief Announcement: Fault Tolerant Coloring of the Asynchronous CycleProceedings of the 2022 ACM Symposium on Principles of Distributed Computing10.1145/3519270.3538456(493-495)Online publication date: 20-Jul-2022
https://dl.acm.org/doi/10.1145/3519270.3538456
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

Atomic snapshots of shared memory

Atomic snapshots using lattice agreement

Fast non-blocking atomic commit: an inherent trade-off