A Distributed Scheduling Algorithm Using Serialization Graph Testing with Fractional Tag

• Item type: Journal(1)
• 公開日: 1997-01-15
• タイトル: A Distributed Scheduling Algorithm Using Serialization Graph Testing with Fractional Tag
• タイトル / 言語: en
• タイトル: A Distributed Scheduling Algorithm Using Serialization Graph Testing with Fractional Tag
• 言語: eng
• キーワード / 主題Scheme: Other
• キーワード / 主題: 論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• その他タイトル / その他のタイトル: データベース
• 著者所属: Faculty of Engineering Science Osaka University
• 著者所属: Faculty of Engineering Science Osaka University
• 著者所属: Faculty of Engineering Science Osaka University
• 著者所属: Central Research Laboratories Corporate Research Division Matsushita Electric Industrial Co. Ltd
• 著者所属(英): en
• 著者所属(英): Faculty of Engineering Science, Osaka University
• 著者所属(英): en
• 著者所属(英): Faculty of Engineering Science, Osaka University
• 著者所属(英): en
• 著者所属(英): Faculty of Engineering Science, Osaka University
• 著者所属(英): en
• 著者所属(英): Central Research Laboratories, Corporate Research Division, Matsushita Electric Industrial Co., Ltd
• 著者名: Harumasa, Tada; Masahiro, Higuchi; Mamoru, Fujii; Jun, Okui
• 著者名(英): Harumasa, Tada; Masahiro, Higuchi; Mamoru, Fujii; Jun, Okui
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 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.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 38, 号 1, p. 90-100, 発行日 1997-01-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764