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

article

Free access

Sharing memory robustly in message-passing systems

Authors:

Danny DolevAuthors Info & Claims

Journal of the ACM (JACM), Volume 42, Issue 1

Pages 124 - 142

https://doi.org/10.1145/200836.200869

Published: 03 January 1995 Publication History

Abstract

Emulators that translate algorithms from the shared-memory model to two different message-passing models are presented. Both are achieved by implementing a wait-free, atomic, single-writer multi-reader register in unreliable, asynchronous networks. The two message-passing models considered are a complete network with processor failures and an arbitrary network with dynamic link failures.

These results make it possible to view the shared-memory model as a higher-level language for designing algorithms in asynchronous distributed systems. Any wait-free algorithm based on atomic, single-writer multi-reader registers can be automatically emulated in message-passing systems, provided that at least a majority of the processors are not faulty and remain connected. The overhead introduced by these emulations is polynomial in the number of processors in the system.

Immediate new results are obtained by applying the emulators to known shared-memory algorithms. These include, among others, protocols to solve the following problems in the message-passing model in the presence of processor or link failures: multi-writer multi-reader registers, concurrent time-stamp systems, l-exclusion, atomic snapshots, randomized consensus, and implementation of data structures.

References

[1]

~ABRAHAMSON, K. 1988. On achieving consensus using a shared memory. In Proceedings of the ~7th Annual ACM Symposium on Principles of Distributed Computing (Toronto, Ont., Canada, ~~ ~Aug ~15-17). ACM, New York, pp. 291-302.

[2]

~AFEK, Y., ATrlYA, H., DOLEV, D., GAFNI, E., MERRITT, M., AND SHAVlT, N. 1993. Atomic ~snapshots of shared memory. J. ACM 40, 4 (Sept.), 873-890.

[3]

~AFEK, Y., AWERBUCH, B., AND GAFNI, E. 1987. Applying static network protocols to dynamic ~networks. In Proceedings of the 28th Symposium on Foundations of Computer Science. IEEE, ~New York, pp. 358-369.

[4]

~AFEK, Y., DOLEV, D., GAFNI, E., MERRITT, M., AND SHAVIT, N. 1990. A bounded first-in ~first-enabled-solution to the /-exclusion problem. In Proceedings of the International ~~ ~Workshop~on Distributed Algorithms. Lecture Notes in Computer Science, vol. 486, ~~ ~Springer-Verlag, New~York.

[5]

~FEK, Y. AND GAFNI, E. 1988. End-to-end communication in unreliable networks. In ~Proceed- ~ings of the 7th Annual ACM Symposium on Principles of Distributed Computing (Toronto, Ont., ~Canada, Aug. 15-17). ACM, New York, pp. 131-147.

[6]

~AFEK, Y. AND GAFNL E. 1991. Bootstrap network resynchronization. In Proceedings of the lOth ~Annual ACM Symposium on Principles of Distributed Computing (Montreal, Que., Canada, Aug. ~19-21~). ACM, New York, pp. 295-307.

[7]

~ANDERSON, J.H. 1993. Composite registers. Dist. Computing 6, 3, 141-154.

[8]

~ASPNES, J., AND MERLIHY, M. 1990a. Fast randomized consensus using shared memory. J. ~Algorithms 15, 1 (Sept.), 441-460.

[9]

~ASPNES, J., AND HERLIHY, M.P. 1990b. Wait-free data structures in the asynchronous PRAM ~model. In Proceedings of the 22nd Annual ACM Symposium on Parallel Algorithms and Architec- ~tures (Island of Crete, Greece, July 2-6). ACM, New York, pp. 340-349.

[10]

~ATrlYA, H., BAR-No~, A., DOLEV, D., PELEO, D. AND REISCHUK, R. 1990. Renaming in an ~asynchronous environment. J. ACM 37, 3 (July), 524-548.

[11]

~ATrIYA, H., DOLEV, D. AND SHAVIT, N. 1987. Bounded polynomial randomized consensus. In ~Proceedings of the 8th Annual ACM Symposium on Principles' of Distributed Computing (Edmon- ~ton, Alb., Canada, Aug. 14-16). ACM, New York, pp. 281-293.

[12]

~AWERBUCH, B. 1987. Optimal distributed algorithms for minimum weight spanning tree, count- ~ing, leader election and related problems. In Proceedhzgs of the 19th Symposium on Theory of ~Computing. (New York, N.Y., May 25-27). ACM, New York, pp. 230-240.

[13]

~AWERBUCH, B., MANSOUR, Y., AND SHAVIT, N. 1989. Polynomial end-to-end comnmnication. In ~Proceedings of the 30th Symposium of Computer Science. IEEE, New York, pp. 358-363.

[14]

~BAR-NOY, A. AND DOLEV, D. 1989. Shared-memory vs. message-passing in an asynchronous ~distributed environment. In Proceedings of the 8th Annual ACM Symposium on Principles of ~Distributed Computing (Edmonton, Alb., Canada, Aug. 14-16). ACM, New York, pp. 307-318.

[15]

~BEN-OR, M. 1983. Another advantage of free choice: Completely asynchronous agreement ~protocols. In Proceedings of the 2nd Annual ACM Symposium on Principles of Distributed ~Computing (Montreal, Que., Canada, Aug. 17-19). ACM, New York, pp. 27-30.

[16]

~BURNS, J. E., AND PETERSON, G.L. 1989. The ambiguity of choosing. In Proceedings of the 8th ~Annual ACM Symposium on Principles of Distributed Computing (Edmonton, Alb., Canada, Aug. ~14-16). ACM, New York, pp. 145-157.

[17]

~CHOR, B., ISRAELI, A., AND CI, M. 1987. On processor coordination using asynchronous ~hardware. In Proceedings of the 6th Annual ACM Symposium on Pnnciples of Distributed ~Computing (Vancouver, B.C., Canada, Aug. 10-12). ACM, New York, pp. 86-97.

[18]

~CHOR, B., MERRITT, M., AND SHMOYS, D. 1985. Simple constant-time consensus protocols in ~realistic failure models. In Proceedings of the 4th Annual ACM Symposium on Principles of ~Distributed Computing (Minakk Ont., Canada, Aug. 5-7). ACM, New York, pp. 152-160.

[19]

~CHOR, B., AND MoscovIcI, L. 1989. Solvability in asynchronous environments. In Proceedings ~of the 30th Symposium on Foundations of Computer Science. IEEE, New York, pp. 422-427.

[20]

~DIJKSTRA, E. W., AND SCHOLTEN, C.S. 1988. Termination detection for diffusing computations. ~Inf. Proc. Lett., 1, i (Aug)., 1-4.

[21]

~DOLEV, D., GAFNI, E., AND SHAVIT, N. 1988. Toward a non-atomic era: /-exclusion as a test ~case. In Proceedings of the 20th Annual A CM Symposium on Theory of Computing (Chicago, IlL, ~May 2-4). ACM, New York, pp. 78 92.

[22]

~DOLEV, D., AND SHAVIT, N. 1987. Unpublished manuscript. July. Cited in Awerbuch et al. {1989}.

[23]

~DOLEV, D., AND SHAVIT, N. 1989. Bounded concurrent time-stamp systems are constructible. ~SIAM J. Computing, to appear. Also: Proceedings of the 21st Symposium on Theory of Computing ~(Seattle, Wash., May 15-17), ACM, New York, pp. 454-466.

[24]

~DWORK, C., SHMOYS, D., AND STOCKMEYER, L. 1986. Flipping persuasively in constant expected ~time. In Proceedings of the 27th Symposmm on Foundations of Computer Science, IEEE, New ~York, pp. 222-232.

[25]

~FELDMAN, J. A., AND NIGAM, m. 1980. A model and proof technique for message-based ~systems. SIAM J. Computing 9, 4 (Nov). 768-784.

[26]

~FINN, S.G. 1979. Resynch procedures and a fail-safe network protocol. IEEE Trans. Comm. ~COM-27, 840-845.

[27]

~FISCHER, M. J., LYNCH, N. A., AND PATERSON, M.S. 1985. Impossibility of distributed consen- ~sus with one faulty processor. J. ACM 32, 2 (Apr.), 374-382.

[28]

~HERHHY, M.P. 1988. Impossibility and universality results for wait-free synchronization. In ~Proceedings of the 7th Annual A CM Symposium on Principles of Distributed Computing (Toronto, ~Ont., Canada, Aug. t5-17). ACM, New York, pp. 276-290.

[29]

~HERLIHY, M.P. 1991. Wait-free synchronization. ACM Trans. Prog. Lang. Syst. 13, t (Jan.), ~124-149. (Earlier version appeared as: Randomized wait-free concurrent objects. In Proceed- ~ings of the lOth Annual ACM Symposium on Principles of Distributed Computmg (Montreal, Que., ~Canada, Aug. 19-21). ACM, New York, pp. 11-21.

[30]

ISRAELI, h., AND LI, M. 1993. Bounded time-stamps. Dist. Comput. 6, 4, 205-209.

[31]

LAMPORT, L. 1986. On interprocess communication: Part I and II. Dist. Comput. 1, 77-101.

[32]

~LI, M., TROMP, J. AND VITANYI, P. 1989. How to share concurrent wait-free variables. Report ~CS-R8916. CWI, Amsterdam, The Netherlands.

[33]

~PETERSON, G. L., AND BURNS. J.E. 1987. Concurrent reading while writing II: The multiwriter ~case. In Proceedings of the 28th Symposmm on Foundations of Computer Science. IEEE, New ~York, pp. 383-392.

[34]

~VISHK~N, U. 1983. A distributed orientation algorithm. IEEE Trans. Inf. Theory (June).

[35]

~VITANYI, P., AND AWERBUCH, B. 1986. Atomic shared register access by asynchronous hard- ~ware. In Proceedings of the 27th Symposium on Foundations of Computer Science. IEEE, New ~York, pp. 233-243.

Cited By

Zarnstorff JLebow LSiems CRemuck DRuiz CTseng L(2024)Racos: Improving Erasure Coding State Machine Replication using Leaderless ConsensusProceedings of the 2024 ACM Symposium on Cloud Computing10.1145/3698038.3698511(600-617)Online publication date: 20-Nov-2024
https://dl.acm.org/doi/10.1145/3698038.3698511
Murat ABurgelin CXygkis AZablotchi IAguilera MGuerraoui RWitchel EArpaci-Dusseau ARossbach CKeeton K(2024)SWARM: Replicating Shared Disaggregated-Memory Data in No TimeProceedings of the ACM SIGOPS 30th Symposium on Operating Systems Principles10.1145/3694715.3695945(24-45)Online publication date: 4-Nov-2024
https://dl.acm.org/doi/10.1145/3694715.3695945
Georgiou CNicolaou NTrigeorgi AGramoli V(2024)Tracing the Latencies of Ares: A DSM Case StudyProceedings of the 2024 Workshop on Advanced Tools, Programming Languages, and PLatforms for Implementing and Evaluating algorithms for Distributed systems10.1145/3663338.3665826(1-6)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3663338.3665826
Show More Cited By

Index Terms

Sharing memory robustly in message-passing systems

Recommendations

Efficient and Robust Sharing of Memory in Message-Passing Systems

A simulation of a wait-free, atomic, single-writer multireader register in an asynchronous message passing system is presented. The simulation can withstand the failure of up to half of the processors and requires O(n) messages (for each read or write ...
WFR-TM

Transactional Memory (TM) is a promising concurrent programming paradigm which employs transactions to achieve synchronization in accessing common data known as transactional variables. A transaction may either commit, making its updates to ...
Constructing regular variables in message passing systems

Developing fault-tolerant programs for distributed systems is a difficult task. It seems that it is more difficult to develop fault-tolerant programs for message passing systems than for shared memory systems. Consequently, there has been a lot of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of the ACM

Journal of the ACM Volume 42, Issue 1

Jan. 1995

289 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/200836

Issue’s Table of Contents

Copyright © 1995 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 03 January 1995

Published in JACM Volume 42, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

371
Total Citations
View Citations
3,693
Total Downloads

Downloads (Last 12 months)658
Downloads (Last 6 weeks)138

Reflects downloads up to 30 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zarnstorff JLebow LSiems CRemuck DRuiz CTseng L(2024)Racos: Improving Erasure Coding State Machine Replication using Leaderless ConsensusProceedings of the 2024 ACM Symposium on Cloud Computing10.1145/3698038.3698511(600-617)Online publication date: 20-Nov-2024
https://dl.acm.org/doi/10.1145/3698038.3698511
Murat ABurgelin CXygkis AZablotchi IAguilera MGuerraoui RWitchel EArpaci-Dusseau ARossbach CKeeton K(2024)SWARM: Replicating Shared Disaggregated-Memory Data in No TimeProceedings of the ACM SIGOPS 30th Symposium on Operating Systems Principles10.1145/3694715.3695945(24-45)Online publication date: 4-Nov-2024
https://dl.acm.org/doi/10.1145/3694715.3695945
Georgiou CNicolaou NTrigeorgi AGramoli V(2024)Tracing the Latencies of Ares: A DSM Case StudyProceedings of the 2024 Workshop on Advanced Tools, Programming Languages, and PLatforms for Implementing and Evaluating algorithms for Distributed systems10.1145/3663338.3665826(1-6)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3663338.3665826
Kowalski VMostefaoui APerrin MGramoli V(2024)Invited Paper: Causal Mutual Byzantine BroadcastProceedings of the 2024 Workshop on Advanced Tools, Programming Languages, and PLatforms for Implementing and Evaluating algorithms for Distributed systems10.1145/3663338.3663679(1-8)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3663338.3663679
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
Georgiou CNicolaou NTrigeorgi A(2024)Ares II: Tracing the Flaws of a (Storage) God2024 43rd International Symposium on Reliable Distributed Systems (SRDS)10.1109/SRDS64841.2024.00027(187-197)Online publication date: 30-Sep-2024
https://doi.org/10.1109/SRDS64841.2024.00027
Vincent KAchour MMatthieu P(2024)An Optimal Byzantine SCD-Broadcast Protocol2024 19th European Dependable Computing Conference (EDCC)10.1109/EDCC61798.2024.00036(139-146)Online publication date: 8-Apr-2024
https://doi.org/10.1109/EDCC61798.2024.00036
Ait Messaoud ABen Mokhtar SSimonet-Boulogne A(2024)Tee-based key-value stores: a surveyThe VLDB Journal10.1007/s00778-024-00877-634:1Online publication date: 18-Dec-2024
https://doi.org/10.1007/s00778-024-00877-6
Hu XToueg S(2024)On implementing SWMR registers from SWSR registers in systems with Byzantine failuresDistributed Computing10.1007/s00446-024-00465-537:2(145-175)Online publication date: 1-Jun-2024
https://dl.acm.org/doi/10.1007/s00446-024-00465-5
Raynal M(2024)Invited Paper: Distributed Computability: A Few Results Masters Students Should KnowDistributed Computing and Intelligent Technology10.1007/978-3-031-81404-4_3(24-44)Online publication date: 31-Dec-2024
https://doi.org/10.1007/978-3-031-81404-4_3
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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 Article

Media

Figures

Other

Tables

View Issue’s Table of Contents