Mathematical Study for Proving Correctness of the Serial Graph-Validation Queue Scheme - Salsabila, Fitra Nuvus; Bukhari, Fahren; Nurdiati, Sri (Journal of the Indonesian Mathematical Society, 2025)
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.