多数決投票を用いた分散システムの可用性の最大化

• Item type: Journal(1)
• 公開日: 2014-03-15
• タイトル: 多数決投票を用いた分散システムの可用性の最大化
• タイトル / 言語: en
• タイトル: Maximizing the Availability of Distributed Systems That Use Voting
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: [一般論文(推薦論文)] レプリケーション，多数決投票，可用性，パーティション，SMT
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 大阪大学大学院情報科学研究科
• 著者所属: 大阪大学大学院情報科学研究科
• 著者所属: 大阪大学大学院情報科学研究科
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Technology, Osaka University
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Technology, Osaka University
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Science and Technology, Osaka University
• 著者名: 松井, 佑記; 小島, 英春; 土屋, 達弘
• 著者名(英): Yuki, Matsui; Hideharu, Kojima; Tatsuhiro, Tsuchiya
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本研究では，ネットワーク上に分散したレプリカからなる多重化データの可用性を最大化する手法について議論する．障害が生じる状況下において，データのレプリカに対する一貫性を提供する機構として，多数決投票システムが知られている．多数決投票システムにおけるレプリカへの票割当ては，このシステムにおけるデータ可用性に大きな影響を与える．そこで，本研究では，可用性を最大化する票割当てをMAX-SMT問題と呼ばれる組合せ最適化問題として定式化し，高速なMAX-SMTソルバを用いて，票割当て問題の解を求める手法を提案する．提案手法の有効性を評価するため，トポロジと故障・修復を考慮したネットワークのモデルを構築し，その上で稼動する分散システムを想定して提案手法の評価を行った．その結果，レプリカ数10以下のシステムであれば，実用的な時間で提案手法を適用し可用性を最大化する票割当てを求めることができること，および，最適な票割当てを用いることで，障害が生じる状況におけるデータ可用性が大きく改善できることが分かった．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: We address the issue of maximization of the availability of replicated data that are distributed in a wide area network. We consider a system that uses majority voting, which is a common mechanism for providing consistency of replicated data in the presence of failures. The data availability provided by this mechanism critically depends on the vote assignment to the replicas. In this paper we formulate the problem of finding the optimal vote assignment into a specific form of a combinatorial optimization problem, namely the MAX-SMT problem. This formulation allows us to use a modern, fast MAX-SMT solver to solve the vote assignment problem. To evaluate the effectiveness of this approach, we build a failure-repair model of underlying networks and perform an experiment using that model. The results of the experiment show that if the number of replicas does not exceed 10, then the proposed approach can produce the optimal vote assignment practically, and that data availability can be significantly improved using the optimal vote assignment in the presence of failures.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 55, 号 3, p. 1177-1185, 発行日 2014-03-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764