research-article

A paradox of eventual linearizability in shared memory

Authors:

Rachid Guerraoui,

Eric RuppertAuthors Info & Claims

PODC '14: Proceedings of the 2014 ACM symposium on Principles of distributed computing

Pages 40 - 49

https://doi.org/10.1145/2611462.2611484

Published: 15 July 2014 Publication History

Abstract

This paper compares, for the first time, the computational power of linearizable objects with that of eventually linearizable ones. We present the following paradox. We show that, unsurprisingly, no set of eventually linearizable objects can (1) implement any non-trivial linearizable object, nor (2) boost the consensus power of simple objects like linearizable registers. We also show, perhaps surprisingly, that any implementation of an eventually linearizable complex object like a fetch&increment counter (from linearizable base objects), can itself be viewed as a fully linearizable implementation of the same fetch&increment counter (using the exact same set of base objects).

References

[1]

P. Bailis and A. Ghodsi. Eventual consistency today: Limitations, extensions and beyond. Commun. ACM, 56(5):55--63, May 2013.

Digital Library

[2]

A. Bouajjani, C. Enea, and J. Hamza. Verifying eventual consistency of optimistic replication systems. In Proc. 41st ACM Symposium on Principles of Programming Languages, pages 285--296, 2014.

Digital Library

[3]

C. Delporte-Gallet, H. Fauconnier, and R. Guerraoui. Tight failure detection bounds on atomic object implementations. J. ACM, 57(4), Apr. 2010.

Digital Library

[4]

A. Demers, D. Greene, C. Hauser, W. Irish, J. Larson, S. Shenker, H. Sturgis, D. Swinehart, and D. Terry. Epidemic algorithms for replicated database maintenance. In Proc. 6th ACM Symposium on Principles of Distributed Computing, pages 1--12, 1987.

Digital Library

[5]

S. Dubois, R. Guerraoui, P. Kouznetsov, F. Petit, and P. Sens. The weakest failure detector for eventual consistency. Unpublished manuscript, 2014.

[6]

A. Fekete, D. Gupta, V. Luchangco, N. Lynch, and A. Shvartsman. Eventually-serializable data services. Theoretical Comput. Sci., 220(1):113--156, June 1999.

Digital Library

[7]

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

[8]

R. Guerraoui and E. Ruppert. Linearizability is not always a safety property. In Proc. 2nd International Conference on Networked Systems, 2014. To appear.

[9]

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

Digital Library

[10]

M. Herlihy and N. Shavit. On the nature of progress. In Proc. 15th International Conference on Principles of Distributed Systems, pages 313--328, 2011.

Digital Library

[11]

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

Digital Library

[12]

M. C. Loui and H. H. Abu-Amara. Memory requirements for agreement among unreliable asynchronous processes. In F. P. Preparata, editor, Advances in Computing Research, volume 4, pages 163--183. JAI Press, Greenwich, Connecticut, 1987.

[13]

N. Lynch. Distributed Algorithms, chapter 13. Morgan Kaufmann, 1996.

Digital Library

[14]

Y. Saito and M. Shapiro. Optimistic replication.\balancecolumns ACM Computing Surveys, 37(1):42--81, Mar. 2005.

Digital Library

[15]

A. G. Sebastien Burckhard and H. Yang. Understanding eventual consistency. Technical report, Microsoft, 2013.

[16]

M. Serafini, D. Dobre, M. Majuntke, P. Bokor, and N. Suri. Eventually linearizable shared objects. In Proc. 29th ACM Symposium on Principles of Distributed Computing, pages 95--104, 2010. Full version available from http://labs.yahoo.com/files/aurora.pdf.

Digital Library

[17]

A. Singh, P. Fonseca, P. Kuznetsov, R. Rodrigues, and P. Maniatis. Zeno: Eventually consistent byzantine-fault tolerance. In Proc. 6th USENIX Symposium on Networked Systems Design and Implementation, pages 169--184, 2009.

Digital Library

[18]

D. B. Terry, M. M. Theimer, K. Petersen, A. J. Demers, M. J. Spreitzer, and C. H. Hauser. Managing update conflicts in Bayou, a weakly connected replicated storage system. In Proc. 15th ACM Symposium on Operating Systems Principles, pages 172--182, 1995.

Digital Library

[19]

W. Vogels. Eventually consistent. Commun. ACM, 52(1):40--44, Jan. 2009.

Digital Library

Cited By

Dubois SGuerraoui RKuznetsov PPetit FSens P(2017)The weakest failure detector for eventual consistencyDistributed Computing10.1007/s00446-016-0292-932:6(479-492)Online publication date: 5-Jan-2017
https://doi.org/10.1007/s00446-016-0292-9
Kokociński MKobus TWojciechowski PGeorgiou CSpirakis P(2015)Brief AnnouncementProceedings of the 2015 ACM Symposium on Principles of Distributed Computing10.1145/2767386.2767448(237-239)Online publication date: 21-Jul-2015
https://dl.acm.org/doi/10.1145/2767386.2767448
Dubois SGuerraoui RKuznetsov PPetit FSens PGeorgiou CSpirakis P(2015)The Weakest Failure Detector for Eventual ConsistencyProceedings of the 2015 ACM Symposium on Principles of Distributed Computing10.1145/2767386.2767404(375-384)Online publication date: 21-Jul-2015
https://dl.acm.org/doi/10.1145/2767386.2767404

Index Terms

A paradox of eventual linearizability in shared memory
1. Computing methodologies
  1. Concurrent computing methodologies
    1. Concurrent programming languages
2. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language types
        Concurrent programming languages

Recommendations

Strongly linearizable implementations: possibilities and impossibilities
PODC '12: Proceedings of the 2012 ACM symposium on Principles of distributed computing

Herlihy and Wing [11] established that the set of possible outcomes of a shared memory distributed algorithm remains unchanged when atomic objects are replaced by their linearizable implementations. Since then, linearizability has been the correctness ...
Single-scanner multi-writer snapshot implementations are fast!
PODC '06: Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing

Snapshot objects allow processes to obtain consistent global views of shared memory. A snapshot object consists of m components each capable of storing a value. The processes execute UPDATE operations to write new values in any of the components and ...
An optimal multi-writer snapshot algorithm
STOC '05: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing

An m-component, n-process snapshot object is an abstraction of shared memory that consists of m words and allows up to n processes to concurrently execute the following two types of operations: write(i,v), which writes v into the ith word, and scan(), ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PODC '14: Proceedings of the 2014 ACM symposium on Principles of distributed computing

July 2014

444 pages

ISBN:9781450329446

DOI:10.1145/2611462

General Chair:
Magnús Halldórsson
Reykjavik Universite, Iceland
,
Program Chair:
Shlomi Dolev
Ben-Gurion University, Israel

Copyright © 2014 ACM.

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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 15 July 2014

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

PODC '14

Sponsor:

PODC '14: ACM Symposium on Principles of Distributed Computing

July 15 - 18, 2014

Paris, France

Acceptance Rates

PODC '14 Paper Acceptance Rate 39 of 141 submissions, 28%;

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
321
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)1

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Dubois SGuerraoui RKuznetsov PPetit FSens P(2017)The weakest failure detector for eventual consistencyDistributed Computing10.1007/s00446-016-0292-932:6(479-492)Online publication date: 5-Jan-2017
https://doi.org/10.1007/s00446-016-0292-9
Kokociński MKobus TWojciechowski PGeorgiou CSpirakis P(2015)Brief AnnouncementProceedings of the 2015 ACM Symposium on Principles of Distributed Computing10.1145/2767386.2767448(237-239)Online publication date: 21-Jul-2015
https://dl.acm.org/doi/10.1145/2767386.2767448
Dubois SGuerraoui RKuznetsov PPetit FSens PGeorgiou CSpirakis P(2015)The Weakest Failure Detector for Eventual ConsistencyProceedings of the 2015 ACM Symposium on Principles of Distributed Computing10.1145/2767386.2767404(375-384)Online publication date: 21-Jul-2015
https://dl.acm.org/doi/10.1145/2767386.2767404

View Options

Get Access

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 Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents