A Distributed Scheduling Algorithm Using Serialization Graph Testing with Fractional Tag

概要

論文の詳細を見る
Many scheduling algorithms which preserve database consistency have been proposed. It is known that Serialization Graph Testing (SGT) achieves higher concurrency than other scheduling algorithms. In SGT, database consistency is preserved by ensuring that the serialization graph (SG) remains acyclic. The scheduler checks the SG before the execution of an operation 0, and if 0 does not cause any cycle to the SG, then 0 is executed immediately, otherwise 0 is rejected. When SGT is implemented by the distributed scheduler in a distributed database system, a naive way is that each site maintains a local subgraph of SG which is concerned with its local data items. Here, there still exists a problem how to detect global cycles, i.e., cycles which do not appear in any local subgraphs. In this paper, we consider a method for detecting such global cycles using fractional tags and propose a scheduling algorithm for a distributed scheduler. Since the algorithm deals with only subgraphs which are needed to detect cycles, the number of intersite communication is small when the locality of data accesses is high. We show the correctness of the proposed algorithm and evaluate its performance by simulations.
一般社団法人情報処理学会の論文
1997-01-15