On Quantitative Metrics for the Consistency and Availability in Distributed Databases
https://doi.org/10.25205/1818-7900-2022-20-2-18-26
Abstract
This article considers simultaneous attainability of consistency and availability. The approaches to determining the maximum possible levels of accessibility for different consistency models are compared. The necessity of introducing quantitative metrics for these two indicators and review the prior articles with quantitative estimates of consistency is advocated. The importance of this problem is confirmed, and directions for modeling the parameters of the applied problem using numerical experiments are proposed.
About the Authors
A. I. Zlygostev
Novosibirsk State University Novosibirsk
Russian Federation
Russian Federation
Anton I. Zlygostev, master’s student
Novosibirsk
B. N. Pishik
Novosibirsk State University Novosibirsk;
Federal Research Center for Informational and Computational Technologies
Russian Federation
Russian Federation
Boris N. Pishik, Candidate of Technical Sciences, senior researcher, Federal Research Center for Information and Computing Technologies (Novosibirsk, Russian Federation); Associate Professor, Department of Comruter Systems, Novosibirsk State University) (Novosibirsk, Russian Federation)
SPIN code: 4297-3046
AuthorID: 13080
Novosibirsk
References
1. Eswaran K. P., Gray J. N., Lorie R. A., Traiger I. L., The notions of consistency and predicate locks in a database system, Communications of the ACM, vol. 19, № 11, 1976.
2. Papadimitriou C. H., The serializability of concurrent database updates, Journal of ACM, vol. 26, № 4, 1979.
3. Rothnie J. B., Goodman N., A survey of research and development in distributed database management, Proceedings of the third international conference on Very large data bases, vol. 3, 1977.
4. Bernstein P. A., Goodman N., Timestamp-based algorithms for concurrency control in distributed database systems, Proceedings of the sixth international conference on Very Large Data Bases, vol. 6, 1980.
5. Bernstein P. A., Goodman N., Concurrency control in distributed database systems, ACM Computer Surveys, vol. 13, № 2, 1981.
6. Bernstein P. A., Goodman N., The failure and recovery problem for replicated databases, 1983.
7. Davidson S. B., Garcia-Molina H., Skeen D., Consistency in Partitioned Networks, Computing Surveys, vol. 17, № 3, 1985.
8. Davidson S. B., An optimistic protocol for partitioned distributed database systems, Princeton: Princeton University, 1982.
9. Birman K., Friedman R., Trading Consistency for Availability in Distributed Systems, Cornell University, Cornell, 1996.
10. Roh H.-G., Jeon M., Kim J.-S., Lee J., Replicated abstract data types: Building blocks for collaborative applications, Journal of Parallel and Distributed Computing, vol. 71, 2011.
11. Fox A., Brewer E. A., Harvest, Yield, and Scalable Tolerant Systems, Proceedings of the The Seventh Workshop on Hot Topics in Operating Systems, 1999.
12. Gilbert S., Lynch N., Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services, ACM SIGACT News, vol. 33, № 2, pp. 51–59, June 2002.
13. Fekete A., Goldrei S. N., Asenjo J. P.́, Quantifying Isolation Anomalies, Proceedings of the VLDB Endowment, Lyon, 2009.
14. Golab W., Li X., Shah M. A., Analyzing Consistency Properties for Fun and Profit, Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing, San Jose, 2011.
15. Bailis P., Venkataraman S., Franklin M. J., Hellerstein J. M., Stoica I., Probabilistically Bounded Staleness for Practical Partial Quorums, Proceedings of the VLDB Endowment, vol. 5, № 8, 2012.
16. Mahajan P., Alvisi L. и Dahlin M., Consistency, Availability, and Convergence, Department of Computer Science, The University of Texas, Austin, 2012.
17. Bailis P., Davidson A., Fekete A., Ghodsi A., Hellerstein J. M. и Stoica I., Highly Available Transactions: Virtues and Limitations, Proceedings of the VLDB Endowment, vol. 7, № 3, 2014.
18. Kleppmann M., A Critique of the CAP Theorem, arXiv preprint arXiv:1509.05393, 2015.
19. Perrin M., Distributed Systems, Concurrency and Consistency, London: ISTE Press Ltd, 2017.
20. Myter F., Scholliers C., De Meuter W., A CAPable Distributed Programming Model, Proceedings of the 2018 ACM SIGPLAN International Symposium on New Ideas, New Paradigms and Reflections on Programming and Software, Boston, 2018.
21. Pascual-Miret L., Gonz´alez de Mend´ıvil J. R., Bernab´eu-Aub´an J. M., Mu˜noz-Escoi F. D., Widening CAP Consistency, Universitario Mixto Tecnol´ogico de Inform´atica,Universitat Polit`ecnica de Val`encia, Valencia, 2015.
22. Mu˜noz-Esco´ı F. D., de Juan-Mar´ın R., Garc´ıa-Escriv´a J.-R., Gonz´alez de Mend´ıvil J., ernab´eu-Aub´an J. M., CAP Theorem: Revision of its Related Consistency Models, The Computer Journal, vol. 62, № 6, pp. 943-960, 2019.
23. Lee E. A., Bateni S., Lin S., Lohstroh M. и Menard C., Quantifying and Generalizing the CAP Theorem, 16 9 2021. [В Интернете]. Available: https://arxiv.org/abs/2109.07771. [Дата обращения: 13 10 2021].
Review
For citations:
Zlygostev A.I., Pishik B.N. On Quantitative Metrics for the Consistency and Availability in Distributed Databases. Vestnik NSU. Series: Information Technologies. 2022;20(2):18-26. (In Russ.) https://doi.org/10.25205/1818-7900-2022-20-2-18-26
Views:
216
Email this article 