Kajian Matematis untuk Pembuktian Kebenaran Skema Serial Graph-Validation Queue (SG-VQ)

Abstract

Selama beberapa tahun terakhir, terdapat peningkatan signifikan dalam kemampuan melakukan pekerjaan berbasis informasi dari jarak jauh. Peningkatan ini didukung oleh meluasnya penerapan aplikasi berbasis real-time collaboration. Aplikasi real-time collaboration memungkinkan banyak pengguna untuk bekerja secara bersamaan, bahkan ketika masing-masing berada terpisah secara geografis. Adapun aplikasi dengan fitur real-time collaboration biasanya mengadopsi arsitektur klien-server. Karena klien dapat mengakses server secara bersamaan, bahkan melakukan perubahan data, sistem klien-server memerlukan mekanisme kontrol konkurensi untuk menjaga konsistensi data. Sejumlah penelitian telah dilakukan untuk mengembangkan skema yang dapat diterapkan pada sistem klien-server, seperti skema Validation Queue (VQ) yang menggunakan cache objek di sisi klien. Skema ini kemudian dimodifikasi menjadi skema Serial Graph-Validation Queue (SG-VQ), yang menggunakan algoritma validasi berdasarkan queue di sisi klien dan graph di sisi server. Penelitian ini berfokus pada verifikasi kebenaran skema SG-VQ dengan menggunakan serializability sebagai indikator. Menerapkan grafik transaksi bebas siklus adalah syarat perlu dan syarat cukup untuk mencapai serializability. Untuk membuktikan Teorema, telah dirumuskan pernyataan matematika yang melibatkan sepuluh definisi, dua proposisi, dan tiga lemma. Pembuktian diawali dengan Lemma 1 yang menjamin bahwa urutan eksekusi secara global akan direfleksikan secara konsisten pada setiap klien k yang memunculkan transaksi terkait. Selanjutnya, Lemma 2 dan Lemma 3 menunjukkan bahwa transaksi konkuren pada skema SG-VQ dapat diserialkan. Hasil penelitian ini menunjukkan bahwa skema SG-VQ dapat menjalankan operasinya dengan benar, sesuai dengan Teorema Serializability Skema SG-VQ yang menyatakan bahwa setiap history (H) dari SG-VQ bersifat serializable.

Over the past few years, there has been a significant increase in the ability to perform information-based work remotely. The widespread adoption of real-time collaboration applications has supported this increase. These applications enable many users to work simultaneously, even when geographically separated. Applications with real-time collaboration features typically adopt a client-server architecture. Since clients can access the server simultaneously and change data, the client-server system requires a concurrency control mechanism to maintain data consistency. Several studies have been conducted to develop 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 was later modified into the Serial Graph-Validation Queue (SG-VQ) scheme, which uses a validation algorithm based on a queue on the client side and a graph on the server side. This research focuses on verifying the correctness of the SG-VQ scheme using serializability as an indicator. Applying a cycle-free transaction graph is a necessary and sufficient condition for achieving serializability. A mathematical statement has been formulated to prove the theorem involving ten definitions, two propositions, and three lemmas. The proof begins with Lemma 1, which ensures that the execution order is globally reflected consistently on each client k that issues the related transactions. Subsequently, Lemma 2 and Lemma 3 demonstrate that concurrent transactions in the SG-VQ scheme can be serialized. The results of this study indicate that the SG-VQ scheme can operate correctly, following the SG-VQ Scheme Serializability Theorem, which states that every history (H) of SG-VQ is serializable.