article

Client-centric consistency formalization and verification for system with large-scale distributed data storage

Authors:

Jianmin WangAuthors Info & Claims

Future Generation Computer Systems, Volume 26, Issue 8

Pages 1180 - 1188

https://doi.org/10.1016/j.future.2010.06.006

Published: 01 October 2010 Publication History

Abstract

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 requirements, but the properties of system implementations that satisfy client-centric consistency are not clear. So constraints on implementation and costs in performance are not known. In this paper, we formally define the four client-centric consistencies and their basis, i.e. eventual consistency, borrowing the framework from the theory of database concurrency control. Based on their definitions, we prove relations among these consistencies. Such relations imply how the implementation of one consistency can be made upon another. Besides, with these formal definitions, we can make simple consistency verification on system implementations.

References

[1]

Brewer, E.A., Towards robust distributed systems (abstract). In: PODC'00: Proceedings of the Nineteenth Annual ACM Symposium on Principles of Distributed Computing, ACM, Portland, Oregon, United States. pp. 7

Digital Library

[2]

Tanenbaum, A.S. and Steen, M.V., Distributed Systems: Principles and Paradigms. 2006. 2nd ed. Prentice Hall, Inc., Upper Saddle River, NJ, USA.

[3]

Terry, D.B., Demers, A.J., Petersen, K., Spreitzer, M., Theimer, M. and Welch, B.W., Session guarantees for weakly consistent replicated data. In: PDIS'94: Proceedings of the Third International Conference on Parallel and Distributed Information Systems, IEEE Computer Society, Washington, DC, USA. pp. 140-149.

[4]

Grossman, R.L., Gu, Y., Sabala, M. and Zhang, W., Compute and storage clouds using wide area high performance networks. Future Gener. Comput. Syst. v25 i2. 179-183.

[5]

Tang, M., Lee, B.-S., Tang, X. and Yeo, C.-K., The impact of data replication on job scheduling performance in the data grid. Future Gener. Comput. Syst. v22 i3. 254-268.

[6]

W. Vogels, Data access patterns in the amazon.com technology platform, in: VLDB'07: Proceedings of the 33rd International Conference on Very Large Data Bases, VLDB Endowment, 2007, p.¿1.

Digital Library

[7]

DeCandia, G., Hastorun, D., Jampani, M., Kakulapati, G., Lakshman, A., Pilchin, A., Sivasubramanian, S., Vosshall, P. and Vogels, W., Dynamo: Amazon's highly available key-value store. SIGOPS Oper. Syst. Rev. v41 i6. 205-220.

[8]

B.F. Cooper, R. Ramakrishnan, U. Srivastava, A. Silberstein, P. Bohannon, H.-A. Jacobsen, N. Puz, D. Weaver, R. Yerneni, Pnuts: Yahoo!'s hosted data serving platform, Proc. VLDB Endow. 1 (2) (2008) 1277-1288.

Digital Library

[9]

Terry, D.B., Petersen, K., Spreitzer, M.J. and Theimer, M.M., The case for non-transparent replication: examples from Bayou. IEEE Data Eng. Bull. v21 i4. 12-20.

[10]

T. Kraska, M. Hentschel, G. Alonso, D. Kossmann, Consistency rationing in the cloud: pay only when it matters, Proc. VLDB Endow. 2 (1) (2009) 253-264.

Digital Library

[11]

Zhou, W., Wang, L. and Jia, W., An analysis of update ordering in distributed replication systems. Future Gener. Comput. Syst. v20 i4. 565-590.

[12]

Saito, Y. and Shapiro, M., Optimistic replication. ACM Comput. Surv. v37 i1. 42-81.

[13]

Gray, J. and Reuter, A., Transaction Processing: Concepts and Techniques. 1992. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA.

[14]

Agrawal, R., Ailamaki, A., Bernstein, P.A., Brewer, E.A., Carey, M.J., Chaudhuri, S., Doan, A., Florescu, D., Franklin, M.J., Garcia-Molina, H., Gehrke, J., Gruenwald, L., Haas, L.M., Halevy, A.Y., Hellerstein, J.M., Ioannidis, Y.E., Korth, H.F., Kossmann, D., Madden, S., Magoulas, R., Ooi, B.C., O'Reilly, T., Ramakrishnan, R., Sarawagi, S., Stonebraker, M., Szalay, A.S. and Weikum, G., The claremont report on database research. Commun. ACM. v52 i6. 56-65.

[15]

Brzezinski, J., Sobaniec, C. and Wawrzyniak, D., Session guarantees to achieve pram consistency of replicated shared objects. In: Parallel Processing and Applied Mathematics, pp. 1-8.

[16]

J. Brzezinski, A. Kobusinska, M. Szychowiak, Checkpointing and rollback-recovery protocol for mobile systems with MW session guarantee, in: Parallel and Distributed Processing Symposium, 2006, IPDPS 2006, 20th International, 2006, pp. 8-15.

Cited By

He H(2020)A Novel Data Consistence Model Based on Virtual Peers in Peer-to-Peer SystemsInternational Journal of e-Collaboration10.4018/IJeC.202007010116:3(1-16)Online publication date: 1-Jul-2020
https://dl.acm.org/doi/10.4018/IJeC.2020070101
Nasibullin ANovikov B(2020)Replication in Distributed Systems: Models, Methods, and ProtocolsProgramming and Computing Software10.1134/S036176882005006046:5(341-350)Online publication date: 1-Sep-2020
https://dl.acm.org/doi/10.1134/S0361768820050060
Nejati Sharif Aldin HDeldari HMoattar MRazavi Ghods M(2020)Strict Timed Causal Consistency as a Hybrid Consistency Model in the Cloud EnvironmentFuture Generation Computer Systems10.1016/j.future.2019.11.038105:C(259-274)Online publication date: 1-Apr-2020
https://dl.acm.org/doi/10.1016/j.future.2019.11.038
Show More Cited By

Index Terms

Client-centric consistency formalization and verification for system with large-scale distributed data storage
1. Software and its engineering
  1. Software organization and properties
    1. Software system structures
      1. Distributed systems organizing principles

Recommendations

Managing consistency anomalies in distributed integrated databases with relaxed ACID properties
ICUIMC '14: Proceedings of the 8th International Conference on Ubiquitous Information Management and Communication

In central databases the consistency of data is normally implemented by using the ACID (Atomicity, Consistency, Isolation and Durability) properties of a DBMS (Data Base Management System). This is not possible if distributed and/or mobile databases are ...
Consistency in Non-Transactional Distributed Storage Systems

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 ...
Safe Combination of Data-Centric and Operation-Centric Consistency
SPLASH 2023: Companion Proceedings of the 2023 ACM SIGPLAN International Conference on Systems, Programming, Languages, and Applications: Software for Humanity

Programming distributed systems requires maintaining consistency among data replicas. In recent years, various frameworks have proposed language-level abstractions for this, falling into two fundamental approaches: data-centric and operation-centric ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Future Generation Computer Systems

Future Generation Computer Systems Volume 26, Issue 8

October, 2010

394 pages

ISSN:0167-739X

Issue’s Table of Contents

Copyright © Elsevier B.V. © 2010.

Publisher

Elsevier Science Publishers B. V.

Netherlands

Publication History

Published: 01 October 2010

Author Tags

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 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

He H(2020)A Novel Data Consistence Model Based on Virtual Peers in Peer-to-Peer SystemsInternational Journal of e-Collaboration10.4018/IJeC.202007010116:3(1-16)Online publication date: 1-Jul-2020
https://dl.acm.org/doi/10.4018/IJeC.2020070101
Nasibullin ANovikov B(2020)Replication in Distributed Systems: Models, Methods, and ProtocolsProgramming and Computing Software10.1134/S036176882005006046:5(341-350)Online publication date: 1-Sep-2020
https://dl.acm.org/doi/10.1134/S0361768820050060
Nejati Sharif Aldin HDeldari HMoattar MRazavi Ghods M(2020)Strict Timed Causal Consistency as a Hybrid Consistency Model in the Cloud EnvironmentFuture Generation Computer Systems10.1016/j.future.2019.11.038105:C(259-274)Online publication date: 1-Apr-2020
https://dl.acm.org/doi/10.1016/j.future.2019.11.038
Rahman MGolab WAuYoung AKeeton KWylie JFreedman MSuri N(2012)Toward a principled framework for benchmarking consistencyProceedings of the Eighth USENIX conference on Hot Topics in System Dependability10.5555/2387858.2387866(8-8)Online publication date: 7-Oct-2012
https://dl.acm.org/doi/10.5555/2387858.2387866

View Options

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 Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents