Article

(Almost) all objects are universal in message passing systems

Authors:

Carole Delporte-Gallet,

Hugues Fauconnier,

Rachid GuerraouiAuthors Info & Claims

DISC'05: Proceedings of the 19th international conference on Distributed Computing

Pages 184 - 198

https://doi.org/10.1007/11561927_15

Published: 26 September 2005 Publication History

Abstract

This paper shows that all shared atomic object types that can solve consensus among k >1 processes have the same weakest failure detector in a message passing system with process crash failures. In such a system, object types such as test-and-set, fetch-and-add, and queue, known to have weak synchronization power in a shared memory system are thus, in a precise sense, equivalent to universal types like compare-and-swap, known to have the strongest synchronization power. In the particular case of a message passing system of two processes, we show that, interestingly, even a register is in that sense universal.

References

[1]

P. Attie, R. Guerraoui, P. Kouznetsov, N. Lynch, and S. Rajsbaum. The impossibility of boosting distributed service resilience. In Proceedings of the 25th International Conference on Distributed Computing Systems. IEEE Computer Society Press, June 2005.

Digital Library

[2]

H. Attiya, A. Bar-Noy, and D. Dolev. Sharing memory robustly in message passing systems. J. ACM, 42(2):124-142, Jan. 1995.

Digital Library

[3]

R. A. Bazzi, G. Neiger, and G. L. Peterson. On the use of registers in achieving wait-free consensus. Distributed Computing, 10(3):117-127, 1997.

Digital Library

[4]

T. D. Chandra, V. Hadzilacos, and S. Toueg. The weakest failure detector for solving consensus. J. ACM, 43(4):685-722, July 1996.

Digital Library

[5]

T. D. Chandra and S. Toueg. Unreliable failure detectors for reliable distributed systems. J. ACM, 43(2):225-267, Mar. 1996.

Digital Library

[6]

C. Delporte-Gallet, H. Fauconnier, and R. Guerraoui. Shared memory vs message passing. Technical Report 200377, EPFL Lausanne, 2003.

[7]

C. Delporte-Gallet, H. Fauconnier, and R. Guerraoui. Implementing atomic objects in a message passing system. Technical report, EPFL Lausanne, 2005.

[8]

C. Delporte-Gallet, H. Fauconnier, R. Guerraoui, V. Hadzilacos, P. Koutnetzov, and S. Toueg. The weakest failure detectors to solve certain fundamental problems in distributed computing. In 23th ACM Symposium on Principles of Distributed Computing, July 2004.

Digital Library

[9]

M. J. Fischer, N. A. Lynch, and M. S. Paterson. Impossibility of distributed consensus with one faulty process. J. ACM, 32(2):374-382, Apr. 1985.

Digital Library

[10]

R. Guerraoui and P. Kouznetsov. On failure detectors and type boosters. In Proceedings of the 17th International Symposium on Distributed Computing, LNCS 2848, pages 292-305. Springer-Verlag, 2003.

[11]

M. Herlihy and J. M. Wing. Linearizability: A correctness condition for concurrent objects. ACM Trans. Program. Lang. Syst., 12(3):463-492, 1990.

Digital Library

[12]

M. P. Herlihy. Wait-free synchronization. ACM Trans. Prog. Lang. Syst., 13(1):123-149, Jan. 1991.

Digital Library

[13]

P. Jayanti. On the robustness of herlihy's hierarchy. In 12th ACM Symposium on Principles of Distributed Computing, pages 145-157, 1993.

Digital Library

[14]

L. Lamport. On interprocess communication; part I and II. Distributed Computing, 1(2):77-101, 1986.

[15]

W.-K. Lo and V. Hadzilacos. Using failure detectors to solve consensus in asynchronous shared memory systems. In Proceedings of the 8th International Workshop on Distributed Algorithms, LNCS 857, pages 280-295, Sept. 1994.

Digital Library

[16]

M. Loui and H. Abu-Amara. Memory requirements for agreement among unreliable asynchronous processes. Advances in Computing Research, 4:163-183, 1987.

[17]

G. Neiger. Failure detectors and the wait-free hierarchy. In 14th ACM Symposium on Principles of Distributed Computing, 1995.

Digital Library

Cited By

Abboud MDelporte-Gallet CFauconnier HBenslimane DOuksel A(2008)Agreement and consistency without knowing the number of processesProceedings of the 8th international conference on New technologies in distributed systems10.1145/1416729.1416777(1-8)Online publication date: 23-Jun-2008
https://dl.acm.org/doi/10.1145/1416729.1416777
Delporte-Gallet CFauconnier HGuerraoui RBazzi RPatt-Shamir B(2008)Sharing is harder than agreeingProceedings of the twenty-seventh ACM symposium on Principles of distributed computing10.1145/1400751.1400764(85-94)Online publication date: 18-Aug-2008
https://dl.acm.org/doi/10.1145/1400751.1400764
Mostefaoui ARajsbaum SRaynal MTravers C(2008)On the computability power and the robustness of set agreement-oriented failure detector classesDistributed Computing10.1007/s00446-008-0064-221:3(201-222)Online publication date: 1-Sep-2008
https://dl.acm.org/doi/10.1007/s00446-008-0064-2
Show More Cited By

Recommendations

Order types: static reasoning about message races in asynchronous message passing concurrency
AGERE 2017: Proceedings of the 7th ACM SIGPLAN International Workshop on Programming Based on Actors, Agents, and Decentralized Control

Asynchronous message passing concurrency with higher level concurrency constructs including activities, asynchronous method invocations and future return values is gaining increased popularity, as an alternative to shared memory concurrency with lower ...
Implementing Snapshot Objects on Top of Crash-Prone Asynchronous Message-Passing Systems
In asynchronous crash-prone read/write shared-memory systems there is the notion of a <italic>snapshot object, </italic> which simulates the behavior of an array of single-writer/multi-reader (SWMR) shared registers that can be read atomically. Processes ...
A coded shared atomic memory algorithm for message passing architectures

This paper considers the communication and storage costs of emulating atomic (linearizable) multi-writer multi-reader shared memory in distributed message-passing systems. The paper contains three main contributions: (1) we present an atomic shared-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

DISC'05: Proceedings of the 19th international conference on Distributed Computing

September 2005

518 pages

ISBN:3540291636

Editor:
Pierre Fraigniaud
CNRS and University Paris Diderot

Sponsors

Université Paris-Sud 11: Université Paris-Sud 11
Universitas Varsoviensis: Universitas Varsoviensis
CNRS: Centre National De La Rechercue Scientifique
University of Liverpool
INRIA: Institut Natl de Recherche en Info et en Automatique

In-Cooperation

Warsaw Univ.: Warsaw University
Jagiellonian Univ.: Jagiellonian University

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 26 September 2005

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Abboud MDelporte-Gallet CFauconnier HBenslimane DOuksel A(2008)Agreement and consistency without knowing the number of processesProceedings of the 8th international conference on New technologies in distributed systems10.1145/1416729.1416777(1-8)Online publication date: 23-Jun-2008
https://dl.acm.org/doi/10.1145/1416729.1416777
Delporte-Gallet CFauconnier HGuerraoui RBazzi RPatt-Shamir B(2008)Sharing is harder than agreeingProceedings of the twenty-seventh ACM symposium on Principles of distributed computing10.1145/1400751.1400764(85-94)Online publication date: 18-Aug-2008
https://dl.acm.org/doi/10.1145/1400751.1400764
Mostefaoui ARajsbaum SRaynal MTravers C(2008)On the computability power and the robustness of set agreement-oriented failure detector classesDistributed Computing10.1007/s00446-008-0064-221:3(201-222)Online publication date: 1-Sep-2008
https://dl.acm.org/doi/10.1007/s00446-008-0064-2
Mostefaoui ARajsbaum SRaynal MTravers CRuppert EMalkhi D(2006)Irreducibility and additivity of set agreement-oriented failure detector classesProceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing10.1145/1146381.1146406(153-162)Online publication date: 23-Jul-2006
https://dl.acm.org/doi/10.1145/1146381.1146406

View Options

View options

Media

Figures

Other

Tables

View Table of Contents