survey

Consistency in Non-Transactional Distributed Storage Systems

Authors:

Marko VukolićAuthors Info & Claims

ACM Computing Surveys (CSUR), Volume 49, Issue 1

Article No.: 19, Pages 1 - 34

https://doi.org/10.1145/2926965

Published: 29 June 2016 Publication History

Abstract

Over the years, different meanings have been associated with the word consistency in the distributed systems community. While in the ’80s “consistency” typically meant strong consistency, later defined also as linearizability, in recent years, with the advent of highly available and scalable systems, the notion of “consistency” has been at the same time both weakened and blurred.

In this article, we aim to fill the void in the literature by providing a structured and comprehensive overview of different consistency notions that appeared in distributed systems, and in particular storage systems research, in the last four decades. We overview more than 50 different consistency notions, ranging from linearizability to eventual and weak consistency, defining precisely many of these, in particular where the previous definitions were ambiguous. We further provide a partial order among different consistency predicates, ordering them by their semantic “strength,” which we believe will be useful in future research. Finally, we map the consistency semantics to different practical systems and research prototypes.

The scope of this article is restricted to non-transactional semantics, that is, those that apply to single storage object operations. As such, our article complements the existing surveys done in the context of transactional, database consistency semantics.

References

[1]

Sarita Adve and Mark D. Hill. 1990. Weak ordering—A new definition. In International Symposium on Computer Architecture. 2--14.

Digital Library

[2]

Sarita V. Adve and Kourosh Gharachorloo. 1996. Shared memory consistency models: A tutorial. IEEE Computer 29, 12 (1996), 66--76.

Digital Library

[3]

Sarita V. Adve and Mark D. Hill. 1993. A unified formalization of four shared-memory models. IEEE Transactions on Parallel and Distributed Systems 4, 6 (1993), 613--624.

Digital Library

[4]

Atul Adya. 1999. Weak Consistency: A Generalized Theory and Optimistic Implementations for Distributed Transactions. Ph.D. Dissertation. MIT, Cambridge, MA. Also as Technical Report MIT/LCS/TR-786.

Digital Library

[5]

Mustaque Ahamad, Rida A. Bazzi, Ranjit John, Prince Kohli, and Gil Neiger. 1993. The power of processor consistency. In ACM Symposium on Parallel Algorithms and Architectures (SPAA’93), 1993. 251--260.

Digital Library

[6]

Mustaque Ahamad, Gil Neiger, James E. Burns, Prince Kohli, and Phillip W. Hutto. 1995. Causal memory: Definitions, implementation, and programming. Distributed Computing 9, 1 (1995), 37--49.

Digital Library

[7]

Amitanand S. Aiyer, Lorenzo Alvisi, and Rida A. Bazzi. 2005. On the availability of non-strict quorum systems. In Distributed Computing (DISC’05). 48--62.

Digital Library

[8]

Sérgio Almeida, João Leitão, and Luís Rodrigues. 2013. ChainReaction: A causal+ consistent datastore based on chain replication. In European Conference on Computer Systems (EuroSys’13), 2013. 85--98.

Digital Library

[9]

Peter Alvaro, Neil Conway, Joseph M. Hellerstein, and David Maier. 2014. Blazes: Coordination analysis for distributed programs. In IEEE Conference on Data Engineering (ICDE’14). 52--63.

[10]

Peter Alvaro, Neil Conway, Joseph M. Hellerstein, and William R. Marczak. 2011. Consistency analysis in bloom: A CALM and collected approach. In Conference on Innovative Data Systems Research (CIDR’11). 249--260. http://www.cidrdb.org/cidr2011/Papers/CIDR11_Paper35.pdf.

[11]

David G. Andersen, Jason Franklin, Michael Kaminsky, Amar Phanishayee, Lawrence Tan, and Vijay Vasudevan. 2009. FAWN: A fast array of wimpy nodes. In ACM Symposium on Operating Systems Principles (SOSP’09). 1--14.

Digital Library

[12]

Eric Anderson, Xiaozhou Li, Mehul A. Shah, Joseph Tucek, and Jay J. Wylie. 2010. What consistency does your key-value store actually provide? In Hot Topics in System Dependability (HotDep’10). USENIX Association, Berkeley, CA, 1--16. http://dl.acm.org/citation.cfm?id=1924908.1924919

Digital Library

[13]

Hagit Attiya, Amotz Bar-Noy, and Danny Dolev. 1995. Sharing memory robustly in message-passing systems. Journal of the ACM 42, 1 (1995), 124--142.

Digital Library

[14]

Hagit Attiya, Faith Ellen, and Adam Morrison. 2015. Limitations of highly-available eventually-consistent data stores. In ACM Symposium on Principles of Distributed Computing (PODC’15). ACM, 385--394.

Digital Library

[15]

Hagit Attiya and Roy Friedman. 1992. A correctness condition for high-performance multiprocessors (extended abstract). In ACM Symposium on Theory of Computing, 1992. 679--690.

Digital Library

[16]

Hagit Attiya and Jennifer Welch. 1994. Sequential consistency versus linearizability. ACM Transactions on Computer Systems (TOCS) 12, 2 (May 1994), 99--122.

Digital Library

[17]

Peter Bailis, Alan Fekete, Ali Ghodsi, Joseph M. Hellerstein, and Ion Stoica. 2012. The potential dangers of causal consistency and an explicit solution. In ACM Symposium on Cloud Computing (SOCC’12). 22.

Digital Library

[18]

Peter Bailis, Alan Fekete, Joseph M. Hellerstein, Ali Ghodsi, and Ion Stoica. 2014. Scalable atomic visibility with RAMP transactions. In ACM International Conference on Management of Data (SIGMOD’14). 27--38.

Digital Library

[19]

Peter Bailis and Ali Ghodsi. 2013. Eventual consistency today: Limitations, extensions, and beyond. Queue 11, 3 (March 2013), 20:20--20:32.

Digital Library

[20]

Peter Bailis, Ali Ghodsi, Joseph M. Hellerstein, and Ion Stoica. 2013. Bolt-on causal consistency. In ACM SIGMOD International Conference on Management of Data (SIGMOD’13). 761--772.

Digital Library

[21]

Peter Bailis, Shivaram Venkataraman, Michael J. Franklin, Joseph M. Hellerstein, and Ion Stoica. 2012. Probabilistically bounded staleness for practical partial quorums. VLDB Journal 5, 8 (2012), 776--787.

Digital Library

[22]

Peter Bailis, Shivaram Venkataraman, Michael J. Franklin, Joseph M. Hellerstein, and Ion Stoica. 2014. Quantifying eventual consistency with PBS. VLDB Journal 23, 2 (2014), 279--302.

[23]

Jason Baker, Chris Bond, James C. Corbett, J. J. Furman, Andrey Khorlin, James Larson, Jean-Michel Leon, Yawei Li, Alexander Lloyd, and Vadim Yushprakh. 2011. Megastore: Providing scalable, highly available storage for interactive services. In Conference on Innovative Data Systems Research (CIDR’11). 223--234.

[24]

Valter Balegas, Sérgio Duarte, Carla Ferreira, Rodrigo Rodrigues, Nuno M. Preguiça, Mahsa Najafzadeh, and Marc Shapiro. 2015. Putting consistency back into eventual consistency. In European Conference on Computer Systems (EuroSys’15). 6.

Digital Library

[25]

Jordi Bataller and José M. Bernabéu-Aubán. 1997. Synchronized DSM models. In Parallel Processing (Euro-Par’97). 468--475.

Digital Library

[26]

Nalini Moti Belaramani, Michael Dahlin, Lei Gao, Amol Nayate, Arun Venkataramani, Praveen Yalagandula, and Jiandan Zheng. 2006. PRACTI replication. In Symposium on Networked Systems Design and Implementation (NSDI’06). http://www.usenix.org/events/nsdi06/tech/belaramani.html.

Digital Library

[27]

David Bermbach and Jörn Kuhlenkamp. 2013. Consistency in distributed storage systems--An overview of models, metrics and measurement approaches. In Networked Systems (NETYS’13). 175--189.

Digital Library

[28]

David Bermbach and Stefan Tai. 2011. Eventual consistency: How soon is eventual? An evaluation of amazon S3’s consistency behavior. In Workshop on Middleware for Service Oriented Computing (MW4SOC’11). ACM, New York, NY, 1:1--1:6.

Digital Library

[29]

Philip A. Bernstein and Sudipto Das. 2013. Rethinking eventual consistency. In ACM SIGMOD International Conference on Management of Data (SIGMOD’13). 923--928.

Digital Library

[30]

Brian N. Bershad and Matthew J. Zekauskas. 1991. Midway: Shared Memory Parallel Programming with Entry Consistency for Distributed Memory Multiprocessors. Technical Report.

[31]

Alysson Neves Bessani, Miguel Correia, Bruno Quaresma, Fernando André, and Paulo Sousa. 2013. DepSky: Dependable and secure storage in a cloud-of-clouds. ACM Transactions on Storage (TOS) 9, 4 (2013), 12.

Digital Library

[32]

Alysson Neves Bessani, Ricardo Mendes, Tiago Oliveira, Nuno Ferreira Neves, Miguel Correia, Marcelo Pasin, and Paulo Veríssimo. 2014. SCFS: A shared cloud-backed file system. In USENIX Annual Technical Conference (ATC’14). 169--180. https://www.usenix.org/conference/atc14/technical-sessions/presentation/bessani.

Digital Library

[33]

Kenneth Birman, Andre Schiper, and Pat Stephenson. 1991. Lightweight causal and atomic group multicast. ACM Transactions on Computer Systems (TOCS) 9, 3 (1991), 272--314.

Digital Library

[34]

Vita Bortnikov, Gregory Chockler, Alexey Roytman, and Mike Spreitzer. 2010. Bulletin board: A scalable and robust eventually consistent shared memory over a peer-to-peer overlay. Operating Systems Review 44, 2 (April 2010), 64--70.

Digital Library

[35]

Marcus Brandenburger, Christian Cachin, and Nikola Knezevic. 2015. Don’t trust the cloud, verify: Integrity and consistency for cloud object stores. In ACM International Systems and Storage Conference (SYSTOR’15). 16:1--16:11. http://doi.acm.org/10.1145/2757667.2757681

Digital Library

[36]

Eric A. Brewer. 2000. Towards robust distributed systems (abstract). In ACM Symposium on Principles of Distributed Computing (PODC’00). 7.

Digital Library

[37]

Nathan Bronson, Zach Amsden, George Cabrera, Prasad Chakka, Peter Dimov, Hui Ding, Jack Ferris, Anthony Giardullo, Sachin Kulkarni, Harry C. Li, Mark Marchukov, Dmitri Petrov, Lovro Puzar, Yee Jiun Song, and Venkateshwaran Venkataramani. 2013. TAO: Facebook’s distributed data store for the social graph. In USENIX Annual Technical Conference (ATC’13). 49--60. https://www.usenix.org/conference/atc13/technical-sessions/presentation/bronson.

Digital Library

[38]

Jerzy Brzezinski, Cezary Sobaniec, and Dariusz Wawrzyniak. 2003. Session guarantees to achieve PRAM consistency of replicated shared objects. In Parallel Processing and Applied Mathematics (PPAM’03). 1--8.

[39]

Jerzy Brzezinski, Cezary Sobaniec, and Dariusz Wawrzyniak. 2004. From session causality to causal consistency. In Workshop on Parallel, Distributed and Network-Based Processing (PDP’04). 152--158.

[40]

Sebastian Burckhardt. 2014. Principles of Eventual Consistency. Foundations and Trends in Programming Languages, Vol. 1. now publishers. 1--150 pages. http://research.microsoft.com/apps/pubs/default.aspx?id=230852.

Digital Library

[41]

Sebastian Burckhardt, Manuel Fähndrich, Daan Leijen, and Benjamin P. Wood. 2012. Cloud types for eventual consistency. In Object-Oriented Programming (ECOOP’12). 283--307.

Digital Library

[42]

Sebastian Burckhardt, Alexey Gotsman, Hongseok Yang, and Marek Zawirski. 2014. Replicated data types: Specification, verification, optimality. In ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL’14). 271--284.

Digital Library

[43]

Sebastian Burckhardt, Daan Leijen, Manuel Fähndrich, and Mooly Sagiv. 2012. Eventually consistent transactions. In European Symposium on Programming (ESOP’12), Held as Part of ETAPS 2012. 67--86.

Digital Library

[44]

Michael Burrows. 2006. The chubby lock service for loosely-coupled distributed systems. In Symposium on Operating Systems Design and Implementation (OSDI’06). 335--350. http://www.usenix.org/events/osdi06/tech/burrows.html.

Digital Library

[45]

Christian Cachin, Idit Keidar, and Alexander Shraer. 2009a. Fork sequential consistency is blocking. Information Processing Letters 109, 7 (2009), 360--364.

Digital Library

[46]

Christian Cachin, Idit Keidar, and Alexander Shraer. 2009b. Trusting the cloud. SIGACT News 40, 2 (2009), 81--86.

Digital Library

[47]

Christian Cachin, Idit Keidar, and Alexander Shraer. 2011. Fail-aware untrusted storage. SIAM Journal on Computing (SICOMP) 40, 2 (2011), 493--533.

Digital Library

[48]

Christian Cachin, Abhi Shelat, and Alexander Shraer. 2007. Efficient fork-linearizable access to untrusted shared memory. In ACM Symposium on Principles of Distributed Computing (PODC’07). 129--138.

Digital Library

[49]

Brad Calder, Ju Wang, Aaron Ogus, Niranjan Nilakantan, Arild Skjolsvold, Sam McKelvie, Yikang Xu, Shashwat Srivastav, Jiesheng Wu, Huseyin Simitci, Jaidev Haridas, Chakravarthy Uddaraju, Hemal Khatri, Andrew Edwards, Vaman Bedekar, Shane Mainali, Rafay Abbasi, Arpit Agarwal, Mian Fahim ul Haq, Muhammad Ikram ul Haq, Deepali Bhardwaj, Sowmya Dayanand, Anitha Adusumilli, Marvin McNett, Sriram Sankaran, Kavitha Manivannan, and Leonidas Rigas. 2011. Windows azure storage: A highly available cloud storage service with strong consistency. In ACM Symposium on Operating Systems Principles (SOSP’11). 143--157.

Digital Library

[50]

Andrea Cerone, Giovanni Bernardi, and Alexey Gotsman. 2015. A framework for transactional consistency models with atomic visibility. In Conference on Concurrency Theory (CONCUR’15). 58--71.

[51]

Houssem-Eddine Chihoub, Shadi Ibrahim, Gabriel Antoniu, and María S. Pérez-Hernández. 2012. Harmony: Towards automated self-adaptive consistency in cloud storage. In IEEE International Conference on Cluster Computing (CLUSTER’12). 293--301.

Digital Library

[52]

Houssem-Eddine Chihoub, Shadi Ibrahim, Gabriel Antoniu, and María S. Pérez-Hernández. 2013. Consistency in the cloud: When money does matter&excl; In Symposium on Cluster, Cloud, and Grid Computing (CCGrid’13). 352--359.

[53]

Brian A. Coan, Brian M. Oki, and Elliot K. Kolodner. 1986. Limitations on database availability when networks partition. In ACM Symposium on Principles of Distributed Computing, 1986. 187--194.

Digital Library

[54]

Neil Conway, William R. Marczak, Peter Alvaro, Joseph M. Hellerstein, and David Maier. 2012. Logic and lattices for distributed programming. In ACM Symposium on Cloud Computing (SOCC’12). 1.

Digital Library

[55]

Brian F. Cooper, Raghu Ramakrishnan, Utkarsh Srivastava, Adam Silberstein, Philip Bohannon, Hans-Arno Jacobsen, Nick Puz, Daniel Weaver, and Ramana Yerneni. 2008. PNUTS: Yahoo&excl;’s hosted data serving platform. VLDB Journal 1, 2 (2008), 1277--1288.

Digital Library

[56]

James C. Corbett, Jeffrey Dean, Michael Epstein, Andrew Fikes, Christopher Frost, J. J. Furman, Sanjay Ghemawat, Andrey Gubarev, Christopher Heiser, Peter Hochschild, Wilson C. Hsieh, Sebastian Kanthak, Eugene Kogan, Hongyi Li, Alexander Lloyd, Sergey Melnik, David Mwaura, David Nagle, Sean Quinlan, Rajesh Rao, Lindsay Rolig, Yasushi Saito, Michal Szymaniak, Christopher Taylor, Ruth Wang, and Dale Woodford. 2013. Spanner: Google’s globally distributed database. ACM Transactions on Computer Systems (TOCS) 31, 3 (2013), 8.

Digital Library

[57]

Susan B. Davidson, Hector Garcia-Molina, and Dale Skeen. 1985. Consistency in partitioned networks. Computer Surveys 17, 3 (1985), 341--370.

Digital Library

[58]

Giuseppe DeCandia, Deniz Hastorun, Madan Jampani, Gunavardhan Kakulapati, Avinash Lakshman, Alex Pilchin, Swaminathan Sivasubramanian, Peter Vosshall, and Werner Vogels. 2007. Dynamo: Amazon’s highly available key-value store. In ACM Symposium on Operating Systems Principles (SOSP’07). 205--220.

Digital Library

[59]

Dan Dobre, Paolo Viotti, and Marko Vukolić. 2014. Hybris: Robust hybrid cloud storage. In ACM Symposium on Cloud Computing (SOCC’14). 12:1--12:14.

Digital Library

[60]

Jiaqing Du, Calin Iorgulescu, Amitabha Roy, and Willy Zwaenepoel. 2014. GentleRain: Cheap and scalable causal consistency with physical clocks. In ACM Symposium on Cloud Computing (SOCC’14). 4:1--4:13.

Digital Library

[61]

Michel Dubois, Christoph Scheurich, and Faye A. Briggs. 1986. Memory access buffering in multiprocessors. In International Symposium on Computer Architecture (ISCA’86). 434--442.

Digital Library

[62]

Dmytro Dziuma, Panagiota Fatourou, and Eleni Kanellou. 2014. Consistency for transactional memory computing. Bulletin of the EATCS 113 (2014). http://eatcs.org/beatcs/index.php/beatcs/article/view/288.

[63]

Alan Fekete, David Gupta, Victor Luchangco, Nancy A. Lynch, and Alexander A. Shvartsman. 1996. Eventually-serializable data services. In ACM Symposium on Principles of Distributed Computing, 1996. 300--309.

Digital Library

[64]

Ariel J. Feldman, William P. Zeller, Michael J. Freedman, and Edward W. Felten. 2010. SPORC: Group collaboration using untrusted cloud resources. In Symposium on Operating Systems Design and Implementation (OSDI’10). 337--350. http://www.usenix.org/events/osdi10/tech/full_papers/Feldman.pdf.

Digital Library

[65]

Michael J. Fischer, Nancy A. Lynch, and Mike Paterson. 1985. Impossibility of distributed consensus with one faulty process. Journal of the ACM 32, 2 (1985), 374--382.

Digital Library

[66]

Roy Friedman, Roman Vitenberg, and Gregory Chockler. 2003. On the composability of consistency conditions. Information Processing Letters 86, 4 (2003), 169--176.

Digital Library

[67]

Guang R. Gao and Vivek Sarkar. 2000. Location consistency-A new memory model and cache consistency protocol. IEEE Transactionas on Computers 49, 8 (2000), 798--813.

Digital Library

[68]

Kourosh Gharachorloo, Daniel Lenoski, James Laudon, Phillip B. Gibbons, Anoop Gupta, and John L. Hennessy. 1990. Memory consistency and event ordering in scalable shared-memory multiprocessors. In International Symposium on Computer Architecture. 15--26.

Digital Library

[69]

Phillip B. Gibbons and Ephraim Korach. 1997. Testing shared memories. SIAM Journal on Computing (SICOMP) 26, 4 (1997), 1208--1244.

Digital Library

[70]

Seth Gilbert and Nancy A. Lynch. 2002. Brewer’s conjecture and the feasibility of consistent, available, partition-tolerant web services. SIGACT News 33, 2 (2002), 51--59.

Digital Library

[71]

Lisa Glendenning, Ivan Beschastnikh, Arvind Krishnamurthy, and Thomas E. Anderson. 2011. Scalable consistency in scatter. In ACM Symposium on Operating Systems Principles (SOSP’11). 15--28.

Digital Library

[72]

Wojciech M. Golab, Xiaozhou Li, and Mehul A. Shah. 2011. Analyzing consistency properties for fun and profit. In ACM Symposium on Principles of Distributed Computing (PODC’11). 197--206.

Digital Library

[73]

Wojciech M. Golab, Muntasir Raihan Rahman, Alvin AuYoung, Kimberly Keeton, and Indranil Gupta. 2014. Client-centric benchmarking of eventual consistency for cloud storage systems. In IEEE Conference on Distributed Computing Systems (ICDCS’14). 493--502.

Digital Library

[74]

James R. Goodman. 1989. Cache Consistency and Sequential Consistency. Technical Report no. 61. SCI Commitee.

[75]

Alexey Gotsman, Hongseok Yang, Carla Ferreira, Mahsa Najafzadeh, and Marc Shapiro. 2016. ’Cause I’m strong enough: Reasoning about consistency choices in distributed systems. In ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL’16). http://lip6.fr/Marc.Shapiro/papers/CISE-POPL-2016.pdf.

Digital Library

[76]

Rachid Guerraoui and Marko Vukolic. 2006. How fast can a very robust read be? In ACM Symposium on Principles of Distributed Computing (PODC’06). 248--257.

Digital Library

[77]

Vassos Hadzilacos and Sam Toueg. 1994. A Modular Approach to Fault-Tolerant Broadcasts and Related Problems. Technical Report. Cornell University, Department of Computer Science.

[78]

Seungyeop Han, Haichen Shen, Taesoo Kim, Arvind Krishnamurthy, Thomas E. Anderson, and David Wetherall. 2015. MetaSync: File synchronization across multiple untrusted storage services. In USENIX Annual Technical Conference (ATC’15). 83--95. https://www.usenix.org/conference/atc15/technical-session/presentation/han.

Digital Library

[79]

Tim Harris, James R. Larus, and Ravi Rajwar. 2010. Transactional Memory, 2nd ed. Morgan & Claypool Publishers.

Digital Library

[80]

Pat Helland. 2007. Life beyond distributed transactions: An Apostate’s opinion. In Conference on Innovative Data Systems Research (CIDR’07). 132--141. http://www.cidrdb.org/cidr2007/papers/cidr07p15.pdf.

[81]

Maurice Herlihy and Nir Shavit. 2008. The Art of Multiprocessor Programming. Morgan Kaufmann. I--XX, 1--508 pages.

Digital Library

[82]

Maurice Herlihy and Jeannette M. Wing. 1990. Linearizability: A correctness condition for concurrent objects. ACM Transactions on Programming Languages and Systems (TOPLAS) 12, 3 (1990), 463--492.

Digital Library

[83]

Phillip W. Hutto and Mustaque Ahamad. 1990. Slow memory: Weakening consistency to enhance concurrency in distributed shared memories. In International Conference on Distributed Computing Systems (ICDCS’90). 302--309.

[84]

Liviu Iftode, Cezary Dubnicki, Edward W. Felten, and Kai Li. 1996a. Improving release-consistent shared virtual memory using automatic update. In IEEE International Symposium on High-Performance Computer Architecture (HPCA’96). 14--25.

Digital Library

[85]

Liviu Iftode, Jaswinder Pal Singh, and Kai Li. 1996b. Scope consistency: A bridge between release consistency and entry consistency. In ACM Symposium on Parallel Algorithms and Architectures (SPAA’96), 1996. 277--287.

Digital Library

[86]

Paul R. Johnson and Robert H. Thomas. 1975. Maintenance of Duplicate Databases. RFC 677. RFC Editor. http://www.rfc-editor.org/rfc/rfc677.txthttp://www.rfc-editor.org/rfc/rfc677.txt.

Digital Library

[87]

Peter J. Keleher, Alan L. Cox, and Willy Zwaenepoel. 1992. Lazy release consistency for software distributed shared memory. In International Symposium on Computer Architecture, 1992. 13--21.

Digital Library

[88]

Tim Kraska, Martin Hentschel, Gustavo Alonso, and Donald Kossmann. 2009. Consistency rationing in the cloud: Pay only when it matters. VLDB Journal 2, 1 (2009), 253--264.

Digital Library

[89]

Sudha Krishnamurthy, William H. Sanders, and Michel Cukier. 2002. An adaptive framework for tunable consistency and timeliness using replication. In Dependable Systems and Networks (DSN’02). 17--26.

Digital Library

[90]

Rivka Ladin, Barbara Liskov, Liuba Shrira, and Sanjay Ghemawat. 1992. Providing high availability using lazy replication. ACM Transactions on Computer Systems (TOCS) 10, 4 (1992), 360--391.

Digital Library

[91]

Avinash Lakshman and Prashant Malik. 2010. Cassandra: A decentralized structured storage system. Operating Systems Review 44, 2 (2010), 35--40.

Digital Library

[92]

Subramanian Lakshmanan, Mustaque Ahamad, and H. Venkateswaran. 2001. A secure and highly available distributed store for meeting diverse data storage needs. In Dependable Systems and Networks (DSN’01). 251--260.

Digital Library

[93]

Leslie Lamport. 1978. Time, clocks, and the ordering of events in a distributed system. Communications of the ACM (CACM) 21, 7 (1978), 558--565.

Digital Library

[94]

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

Digital Library

[95]

Leslie Lamport. 1983. Specifying concurrent program modules. ACM Transactions on Programming Languages and Systems (TOPLAS) 5, 2 (1983), 190--222.

Digital Library

[96]

Leslie Lamport. 1986a. On interprocess communication. Part I: Basic formalism. Distributed Computing 1, 2 (1986), 77--85.

[97]

Leslie Lamport. 1986b. On interprocess communication. Part II: Algorithms. Distributed Computing 1, 2 (1986), 86--101.

[98]

Leslie Lamport. 2001. Paxos made simple. SIGACT News 32, 4 (2001), 51--58.

[99]

Leslie Lamport, Robert E. Shostak, and Marshall C. Pease. 1982. The Byzantine generals problem. ACM Transactions on Programming Languages and Systems (TOPLAS) 4, 3 (1982), 382--401.

Digital Library

[100]

Collin Lee, Seo Jin Park, Ankita Kejriwal, Satoshi Matsushita, and John K. Ousterhout. 2015. Implementing linearizability at large scale and low latency. In ACM Symposium on Operating Systems Principles (SOSP’15). 71--86.

Digital Library

[101]

Mohsen Lesani, Christian J. Bell, and Adam Chlipala. 2016. Chapar: Certified causally consistent distributed key-value stores. In ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL’16). http://doi.acm.org/10.1145/2837614.2837622

Digital Library

[102]

Cheng Li, João Leitão, Allen Clement, Nuno M. Preguiça, Rodrigo Rodrigues, and Viktor Vafeiadis. 2014. Automating the choice of consistency levels in replicated systems. In USENIX Annual Technical Conference (ATC’14). 281--292. https://www.usenix.org/conference/atc14/technical-sessions/presentation/li_cheng_2.

Digital Library

[103]

Cheng Li, Daniel Porto, Allen Clement, Johannes Gehrke, Nuno Preguiça, and Rodrigo Rodrigues. 2012. Making geo-replicated systems fast as possible, consistent when necessary. In Symposium on Operating Systems Design and Implementation (OSDI’12). USENIX Association, Berkeley, CA, 265--278. http://dl.acm.org/citation.cfm?id=2387880.2387906

Digital Library

[104]

Jinyuan Li, Maxwell N. Krohn, David Mazières, and Dennis Shasha. 2004. Secure untrusted data repository (SUNDR). In Symposium on Operating System Design and Implementation (OSDI’04). 121--136.

Digital Library

[105]

Jinyuan Li and David Mazières. 2007. Beyond one-third faulty replicas in Byzantine fault tolerant systems. In Symposium on Networked Systems Design and Implementation (NSDI’07).

Digital Library

[106]

Richard J. Lipton and Jonathan S. Sandberg. 1988. PRAM: A Scalable Shared Memory. Technical Report CS-TR-180-88. Princeton University.

[107]

Wyatt Lloyd, Michael J. Freedman, Michael Kaminsky, and David G. Andersen. 2011. Don’t settle for eventual: Scalable causal consistency for wide-area storage with COPS. In ACM Symposium on Operating Systems Principles (SOSP’11). 401--416.

Digital Library

[108]

Wyatt Lloyd, Michael J. Freedman, Michael Kaminsky, and David G. Andersen. 2013. Stronger semantics for low-latency geo-replicated storage. In Symposium on Networked Systems Design and Implementation (NSDI’13). USENIX Association, Berkeley, CA, 313--328. http://dl.acm.org/citation.cfm?id=2482626.2482657

Digital Library

[109]

Haonan Lu, Kaushik Veeraraghavan, Philippe Ajoux, Jim Hunt, Yee Jiun Song, Wendy Tobagus, Sanjeev Kumar, and Wyatt Lloyd. 2015. Existential consistency: Measuring and understanding consistency at facebook. In ACM Symposium on Operating Systems Principles (SOSP’15). 295--310.

Digital Library

[110]

Nancy A. Lynch and Mark R. Tuttle. 1989. An introduction to input/output automata. CWI Quarterly 2 (1989), 219--246.

[111]

Prince Mahajan, Lorenzo Alvisi, and Mike Dahlin. 2011. Consistency, Availability, and Convergence. Technical Report TR-11-22. Computer Science Department, University of Texas at Austin.

[112]

Prince Mahajan, Srinath T. V. Setty, Sangmin Lee, Allen Clement, Lorenzo Alvisi, Michael Dahlin, and Michael Walfish. 2010. Depot: Cloud storage with minimal trust. In Symposium on Operating Systems Design and Implementation (OSDI’10). 307--322.

Digital Library

[113]

Dahlia Malkhi and Michael K. Reiter. 1998a. Byzantine quorum systems. Distributed Computing 11, 4 (1998), 203--213.

Digital Library

[114]

Dahlia Malkhi and Michael K. Reiter. 1998b. Secure and scalable replication in phalanx. In Symposium on Reliable Distributed Systems (SRDS’98). 51--58.

Digital Library

[115]

David Mazières and Dennis Shasha. 2002. Building secure file systems out of Byzantine storage. In ACM Symposium on Principles of Distributed Computing (PODC’02). 108--117.

Digital Library

[116]

Jayadev Misra. 1986. Axioms for memory access in asynchronous hardware systems. ACM Transactions on Programming Languages and Systems (TOPLAS) 8, 1 (1986), 142--153.

Digital Library

[117]

Iulian Moraru, David G. Andersen, and Michael Kaminsky. 2013. There is more consensus in Egalitarian parliaments. In ACM Symposium on Operating Systems Principles (SOSP’13). 358--372.

Digital Library

[118]

David Mosberger. 1993. Memory consistency models. Operating Systems Review 27, 1 (1993), 18--26.

Digital Library

[119]

Alina Oprea and Michael K. Reiter. 2006. On consistency of encrypted files. In Distributed Computing (DISC’06). 254--268.

Digital Library

[120]

Swapnil Patil, Milo Polte, Kai Ren, Wittawat Tantisiriroj, Lin Xiao, Julio López, Garth Gibson, Adam Fuchs, and Billie Rinaldi. 2011. YCSB++: Benchmarking and performance debugging advanced features in scalable table stores. In ACM Symposium on Cloud Computing (SOCC’11) in Conjunction with SOSP 2011. 9.

Digital Library

[121]

Dorian Perkins, Nitin Agrawal, Akshat Aranya, Curtis Yu, Younghwan Go, Harsha V. Madhyastha, and Cristian Ungureanu. 2015. Simba: Tunable end-to-end data consistency for mobile apps. In European Conference on Computer Systems (EuroSys’15). 7.

Digital Library

[122]

Karin Petersen, Mike Spreitzer, Douglas B. Terry, Marvin Theimer, and Alan J. Demers. 1997. Flexible update propagation for weakly consistent replication. In ACM Symposium on Operating Systems Principles (SOSP’97). 288--301.

Digital Library

[123]

Muntasir Raihan Rahman, Wojciech M. Golab, Alvin AuYoung, Kimberly Keeton, and Jay J. Wylie. 2012. Toward a principled framework for benchmarking consistency. Computing Research Repository abs/1211.4290 (2012).

[124]

Jun Rao, Eugene J. Shekita, and Sandeep Tata. 2011. Using paxos to build a scalable, consistent, and highly available datastore. VLDB Journal 4, 4 (2011), 243--254.

Digital Library

[125]

Michel Raynal and André Schiper. 1997. A suite of definitions for consistency criteria in distributed shared memories. Annales des Télécommunications 52, 11--12 (1997), 652--661.

[126]

Peter L. Reiher, John S. Heidemann, David Ratner, Gregory Skinner, and Gerald J. Popek. 1994. Resolving file conflicts in the ficus file system. In USENIX Summer 1994 Technical Conference, 1994. 183--195. https://www.usenix.org/conference/usenix-summer-1994-technical-conference /resolving-file-conflicts-ficus-file-system.

Digital Library

[127]

Hyun-Gul Roh, Myeongjae Jeon, Jinsoo Kim, and Joonwon Lee. 2011. Replicated abstract data types: Building blocks for collaborative applications. Journal of Parallel and Distributed Computing 71, 3 (2011), 354--368.

Digital Library

[128]

Yasushi Saito and Marc Shapiro. 2005. Optimistic replication. Computer Surveys 37, 1 (2005), 42--81.

Digital Library

[129]

Nuno Santos, Luís Veiga, and Paulo Ferreira. 2007. Vector-field consistency for ad-hoc gaming. In ACM/IFIP/USENIX Middleware Conference, 2007. 80--100.

Digital Library

[130]

Marco Serafini, Dan Dobre, Matthias Majuntke, Péter Bokor, and Neeraj Suri. 2010. Eventually linearizable shared objects. In ACM Symposium on Principles of Distributed Computing (PODC’10). 95--104.

Digital Library

[131]

Marc Shapiro, Nuno M. Preguiça, Carlos Baquero, and Marek Zawirski. 2011a. Conflict-free replicated data types. In Stabilization, Safety, and Security of Distributed Systems (SSS’11). 386--400.

Digital Library

[132]

Marc Shapiro, Nuno M. Preguiça, Carlos Baquero, and Marek Zawirski. 2011b. Convergent and commutative replicated data types. Bulletin of the EATCS 104 (2011), 67--88.

[133]

Alexander Shraer, Christian Cachin, Asaf Cidon, Idit Keidar, Yan Michalevsky, and Dani Shaket. 2010. Venus: Verification for untrusted cloud storage. In ACM Cloud Computing Security Workshop (CCSW’10). 19--30.

Digital Library

[134]

Atul Singh, Pedro Fonseca, Petr Kuznetsov, Rodrigo Rodrigues, and Petros Maniatis. 2009. Zeno: Eventually consistent Byzantine-fault tolerance. In Symposium on Networked Systems Design and Implementation (NSDI’09). 169--184. http://www.usenix.org/events/nsdi09/tech/full_papers/singh/singh.pdf.

Digital Library

[135]

Aman Singla, Umakishore Ramachandran, and Jessica K. Hodgins. 1997. Temporal notions of synchronization and consistency in beehive. In ACM Symposium on Parallel Algorithms and Architectures (SPAA’97). 211--220.

Digital Library

[136]

Krishnamoorthy C. Sivaramakrishnan, Gowtham Kaki, and Suresh Jagannathan. 2015. Declarative programming over eventually consistent data stores. In ACM SIGPLAN Conference on Programming Language Design and Implementation, 2015. 413--424.

Digital Library

[137]

Robert C. Steinke and Gary J. Nutt. 2004. A unified theory of shared memory consistency. Journal of the ACM 51, 5 (2004), 800--849.

Digital Library

[138]

Andrew S. Tanenbaum and Maarten van Steen. 2007. Distributed Systems---Principles and Paradigms, 2nd ed. Pearson Education. I--XVIII, 1--686 pages.

Digital Library

[139]

Doug Terry. 2013. Replicated data consistency explained through baseball. Communications of the ACM (CACM) 56, 12 (2013), 82--89.

Digital Library

[140]

Douglas B. Terry, Alan J. Demers, Karin Petersen, Mike Spreitzer, Marvin Theimer, and Brent B. Welch. 1994. Session guarantees for weakly consistent replicated data. In Parallel and Distributed Information Systems (PDIS’94). 140--149.

Digital Library

[141]

Douglas B. Terry, Vijayan Prabhakaran, Ramakrishna Kotla, Mahesh Balakrishnan, Marcos K. Aguilera, and Hussam Abu-Libdeh. 2013. Consistency-based service level agreements for cloud storage. In ACM Symposium on Operating Systems Principles (SOSP’13). 309--324.

Digital Library

[142]

Douglas B. Terry, Marvin Theimer, Karin Petersen, Alan J. Demers, Mike Spreitzer, and Carl Hauser. 1995. Managing update conflicts in Bayou, a weakly connected replicated storage system. In ACM Symposium on Operating Systems Principles (SOSP’95). 172--183.

Digital Library

[143]

Francisco J. Torres-Rojas, Mustaque Ahamad, and Michel Raynal. 1999. Timed consistency for shared distributed objects. In ACM Symposium on Principles of Distributed Computing (PODC’99). 163--172.

Digital Library

[144]

Francisco J. Torres-Rojas and Esteban Meneses. 2005. Convergence through a weak consistency model: Timed causal consistency. CLEI Electronic Journal 8, 2 (2005).

[145]

Werner Vogels. 2008. Eventually consistent. Queue 6, 6 (Oct. 2008), 14--19.

Digital Library

[146]

Marko Vukolić. 2010. The Byzantine empire in the intercloud. SIGACT News 41, 3 (Sept. 2010), 105--111.

Digital Library

[147]

Hiroshi Wada, Alan Fekete, Liang Zhao, Kevin Lee, and Anna Liu. 2011. Data consistency properties and the trade-offs in commercial cloud storage: The consumers’ perspective. In Conference on Innovative Data Systems Research (CIDR’11). 134--143.

[148]

Zhe Wu, Michael Butkiewicz, Dorian Perkins, Ethan Katz-Bassett, and Harsha V. Madhyastha. 2013. SPANStore: Cost-effective geo-replicated storage spanning multiple cloud services. In ACM Symposium on Operating Systems Principles (SOSP’13). 292--308.

Digital Library

[149]

Haifeng Yu and Amin Vahdat. 2002. Design and evaluation of a conit-based continuous consistency model for replicated services. ACM Transactions on Computer Systems (TOCS) 20, 3 (2002), 239--282.

Digital Library

[150]

Marek Zawirski, Nuno Preguiça, Sérgio Duarte, Annette Bieniusa, Valter Balegas, and Marc Shapiro. 2015. Write fast, read in the past: Causal consistency for client-side applications. In ACM/IFIP/USENIX Middleware Conference, 2015.

Digital Library

Cited By

Nikolic LDimitrieski VCelikovic M(2024)An approach for supporting transparent acid transactions over heterogeneous data stores in microservice architecturesComputer Science and Information Systems10.2298/CSIS221210006N21:1(167-202)Online publication date: 2024
https://doi.org/10.2298/CSIS221210006N
Almeida P(2024)Approaches to Conflict-free Replicated Data TypesACM Computing Surveys10.1145/369524957:2(1-36)Online publication date: 9-Sep-2024
https://dl.acm.org/doi/10.1145/3695249
Psistakis AChaix FTorrellas J(2024)MINOS: Distributed Consistency and Persistency Protocol Implementation & Offloading to SmartNICs2024 IEEE International Symposium on High-Performance Computer Architecture (HPCA)10.1109/HPCA57654.2024.00076(1-17)Online publication date: 2-Mar-2024
https://doi.org/10.1109/HPCA57654.2024.00076
Show More Cited By

Recommendations

Distributed Transactional Systems Cannot Be Fast
SPAA '19: The 31st ACM Symposium on Parallelism in Algorithms and Architectures

We prove that no fully transactional system can provide fast read transactions (including read-only ones that are considered the most frequent in practice). Specifically, to achieve fast read transactions, the system has to give up support of ...
Consistency in Distributed Storage Systems
NETYS 2013: Revised Selected Papers of the First International Conference on Networked Systems - Volume 7853

Due to the advent of eventually consistent storage systems, consistency has become a focus of research. Still, a clear overview of consistency in distributed systems is missing. In this work, we define and describe consistency, show how different ...
Client-centric consistency formalization and verification for system with large-scale distributed data storage

Customized consistency is necessary in systems with large-scale distributed data storage, which have to make a tradeoff between consistency and performance. Client-centric consistency is intuitive for applications to specify their consistency ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Computing Surveys

ACM Computing Surveys Volume 49, Issue 1

March 2017

705 pages

ISSN:0360-0300

EISSN:1557-7341

DOI:10.1145/2911992

Editor:
Sartaj Sahni
Department of Computer and Information Science and Engineering/University of Florida/Gainesville, FL

Issue’s Table of Contents

Copyright © 2016 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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 29 June 2016

Accepted: 01 April 2016

Revised: 01 March 2016

Received: 01 December 2015

Published in CSUR Volume 49, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Survey
Research
Refereed

Funding Sources

SUPERCLOUD Horizon 2020 program
EU projects CloudSpaces

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

76
Total Citations
View Citations
1,863
Total Downloads

Downloads (Last 12 months)245
Downloads (Last 6 weeks)27

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Nikolic LDimitrieski VCelikovic M(2024)An approach for supporting transparent acid transactions over heterogeneous data stores in microservice architecturesComputer Science and Information Systems10.2298/CSIS221210006N21:1(167-202)Online publication date: 2024
https://doi.org/10.2298/CSIS221210006N
Almeida P(2024)Approaches to Conflict-free Replicated Data TypesACM Computing Surveys10.1145/369524957:2(1-36)Online publication date: 9-Sep-2024
https://dl.acm.org/doi/10.1145/3695249
Psistakis AChaix FTorrellas J(2024)MINOS: Distributed Consistency and Persistency Protocol Implementation & Offloading to SmartNICs2024 IEEE International Symposium on High-Performance Computer Architecture (HPCA)10.1109/HPCA57654.2024.00076(1-17)Online publication date: 2-Mar-2024
https://doi.org/10.1109/HPCA57654.2024.00076
Frey DGuillou LRaynal MTaïani F(2024)Process-commutative distributed objects: From cryptocurrencies to Byzantine-Fault-Tolerant CRDTsTheoretical Computer Science10.1016/j.tcs.2024.1147941017(114794)Online publication date: Nov-2024
https://doi.org/10.1016/j.tcs.2024.114794
Xu ZDong YLou JWang YFu Y(2024)Edge AI-driven neural network predictions for replica sync optimizationApplied Soft Computing10.1016/j.asoc.2024.112083(112083)Online publication date: Aug-2024
https://doi.org/10.1016/j.asoc.2024.112083
Gessert FWingerath WRitter NGessert FWingerath WRitter N(2024)Caching in Forschung und IndustrieSchnelles und skalierbares Cloud-Datenmanagement10.1007/978-3-031-54388-3_5(91-140)Online publication date: 3-May-2024
https://doi.org/10.1007/978-3-031-54388-3_5
Gessert FWingerath WRitter NGessert FWingerath WRitter N(2024)Systeme für skalierbares DatenmanagementSchnelles und skalierbares Cloud-Datenmanagement10.1007/978-3-031-54388-3_4(61-90)Online publication date: 3-May-2024
https://doi.org/10.1007/978-3-031-54388-3_4
Diamant JLandau Feibish SRamos FShahbaz MGurevich VSignorello S(2023)Poster: Maintaining Sets With Deletions in the Data PlaneProceedings of the 6th on European P4 Workshop10.1145/3630047.3630195(57-60)Online publication date: 8-Dec-2023
https://dl.acm.org/doi/10.1145/3630047.3630195
Ahmad MAli STariq MJafri SAbbas AZaidi SAwan MUzmi ZQazi Z(2023)Neutrino: A Fast and Consistent Edge-Based Cellular Control PlaneIEEE/ACM Transactions on Networking10.1109/TNET.2022.320249631:2(754-769)Online publication date: Apr-2023
https://doi.org/10.1109/TNET.2022.3202496
Jiang XWei HHuang Y(2023)Tunable Causal Consistency: Specification and Implementation2022 IEEE 28th International Conference on Parallel and Distributed Systems (ICPADS)10.1109/ICPADS56603.2022.00030(169-176)Online publication date: Jan-2023
https://doi.org/10.1109/ICPADS56603.2022.00030
Show More Cited By

View Options

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents