A Concurrency Control Algorithm Using Serialization Graph Testing with Write Deferring

スポンサーリンク

概要

• 論文の詳細を見る

• Several scheduling algorithms for preserving the consistency of databases have been proposed. One of such algorithm is Serialization Graph Testing (SGT). Under SGT, a scheduler maintains a graph called a serialization graph (SG). Database consistency is preserved by ensuring that the SG is acyclic. The scheduler checks the acyclicity of the SG for every operation. If the SG comes to contain a cycle, the operation is rejected. It is known that SGT achieves higher concurrency than other scheduling algorithms. However, it has some drawbacks. First, operations are forced to wait for a long time so that the acyclicity of the serialization graph can be checked. Second, a phenomenon called cascading aborts may occur; that is, one abortion of a transaction may cause other abortions. To deal with the first drawback of SGT, we focused on the scheduling algorithm called SGT certification. Under SGT certification, a scheduler checks the acyclicity of the SG only once for each transaction, at its termination. Therefore, all operations are executed immediately, at the cost of a delay in cycle detection. As regards the second drawback, the scheduling method called Optimistic Concurrency Control (OCC) avoids cascading aborts by using internal buffer to defer substantial write operations. However, the consistency checking of OCC differs from that of SGT, and the concurrency of OCC is not so high. Therefore, we applied this write deferment approach to SGT certification. We call our algorithm Serialization Graph Testing with Write Deferring (SGT-WD). In this paper, we present the SGT-WD algorithm and show its correctness. We also evaluate SGT-WD, SGT, and SGT certification by means of simulations on distributed database systems. The simulation results show that SGT-WD is more effective than the others.

• 一般社団法人情報処理学会の論文
• 1997-10-15

著者

• Fujii M

  Faculty Of Engineering Science Osaka University

• TADA HARUMASA

  Faculty of Engineering Science, Osaka University

• FUJII MAMORU

  Faculty of Engineering Science, Osaka University

• Higuchi Masahiro

  Faculty Of Engineering Kansai University

• Tada H

  Osaka Univ.

関連論文

• The Energetic Particle Spectrometer HEP onboard the GEOTAIL Spacecraft
• A Verification Method via Invariant for Communication Protocols Modeled as Extended Communicating Finite-State Machines
• A Distributed Scheduling Algorithm Using Serialization Graph Testing with Fractional Tag
• Optimization of Grinding Conditions with Genetic Algorithm
• Protein Synthesis Algorithm and a New Metaphor for Selecting Optimum Tools
• A Concurrency Control Algorithm Using Serialization Graph Testing with Write Deferring

スポンサーリンク