Mathematical Study for Proving Correctness of the Serial Graph-Validation Queue Scheme
Abstract
Numerous studies have been conducted to develop concurency control schemes that can be applied to client-server systems, such as the Validation Queue (VQ) scheme, which uses object caching on the client side. This scheme has been modified into the Serial Graph-Validation Queue (SG-VQ) scheme, which employs validation algorithms based on queues on the client side and graphs on the server side. This study focuses on verifying the correctness of the SG-VQ scheme by using serializability as a mathematical tool. The results of this study demonstrate that the SG-VQ scheme can execute its operations correctly, in accordance with Theorem 4.16, which states that every history (H) of SG-VQ is serializable. Implementing a cycle-free transaction graph is a necessary and sufficient condition to achieve serializability. To prove Theorem 4.16, mathematical statements involving ten definitions, two propositions, and three lemmas have been formulated.
Full text article
References
S. Ali, R. Alauldeen, and R. A. Khamees, “What is client-server system: Architecture, issues and challenge of client-server system (review),” Recent Trends in Cloud Computing and Web Engineering, vol. 2, no. 1, pp. 1–6, 2020. https://doi.org/10.5281/zenodo.3673071.
Q.-V. Dang and C.-L. Ignat, “Performance of real-time collaborative editors at large scale: User perspective,” in 2016 IFIP Networking Conference (IFIP Networking) and Workshops, pp. 548–553, IEEE, May 2016. https://doi.org/10.1109/IFIPNetworking.2016.7497258.
M. Hartwig and S. Gartz, “Mobile modeling with real-time collaboration support,” J. Object Technol., vol. 21, no. 3, pp. 1–15, 2022. https://doi.org/10.5381/jot.2022.21.3.a2.
S. Kumar, “A review on client-server based applications and research opportunity,” Int. J. Recent Sci. Res., vol. 10, no. 7, pp. 33857–33862, 2019. https://doi.org/10.24327/ijrsr.2019.1007.3768.
M. Kaur and H. Kaur, “Concurrency control in distributed database system,” International Journal of Advanced Research in Computer Science and Software Engineering, vol. 3, no. 7, pp. 1443–1447, 2013. https://api.semanticscholar.org/CorpusID:7899973.
M. F. Jauhari, “Skema serial graph-validation queue pada sistem klien-server,” Magister Theses, IPB University, 2024. https://repository.ipb.ac.id/handle/123456789/152689.
F. Rezaei and B. H. Khalaj, “Stability, rate, and delay analysis of single bottleneck cachingnetworks,” IEEE Trans Commun., vol. 64, no. 1, pp. 300–313, 2016. https://doi.org/10.1109/TCOMM.2015.2498177.
F. Bukhari and S. Shrivastava, “An efficient distributed concurrency control scheme for transactional systems with client-side caching,” in Proc. 14th International Conference on High Performance Computing and 9th International Conference on Embedded Software and Systems, 2012. https://doi.org/10.1109/HPCC.2012.157.
T. Wang, R. Johnson, A. Fekete, and I. Pandis, “Efficiently making (almost) any concurrency control mechanism serializable,” VLDB J., vol. 26, no. 4, pp. 537–562, 2017. https://doi.org/10.1007/s00778-017-0463-8.
F. Bukhari, “Maintaining consistency in client-server database systems with client-side caching,” Doctoral dissertation, Newcastle University. http://theses.ncl.ac.uk/jspui/handle/10443/1789.
A. Mhatre and R. Shedge, “Comparative study of concurrency control techniques in distributed databases,” in Proc. 4th International Conference on Communication Systems and Network Technologies, 2014. https://doi.org/10.1109/CSNT.2014.81.
P. A. Bernstein, V. Hadzilacos, and N. Goodman, Concurrency Control and Recovery in Database System. Addison-Wesley Longman, 1987. https://www.sigmod.org/publications/dblp/db/books/dbtext/bernstein87.html.
T. Connolly and C. Begg, Database Systems: A Practical Approach in Design, Implementation, and Management Database, Sixth Edition. Pearson Education, 2015.
P. A. Bernstein and N. Goodman, “Concurrency control in distributed database systems,”ACM Comput. Surv., vol. 13, no. 2, pp. 185–221, 1981. https://doi.org/10.1145/356842.
Authors
Copyright (c) 2025 Journal of the Indonesian Mathematical Society
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
Article Details
