多数決投票を用いた分散システムの可用性の最大化
スポンサーリンク
概要
- 論文の詳細を見る
本研究では,ネットワーク上に分散したレプリカからなる多重化データの可用性を最大化する手法について議論する.障害が生じる状況下において,データのレプリカに対する一貫性を提供する機構として,多数決投票システムが知られている.多数決投票システムにおけるレプリカへの票割当ては,このシステムにおけるデータ可用性に大きな影響を与える.そこで,本研究では,可用性を最大化する票割当てをMAX-SMT問題と呼ばれる組合せ最適化問題として定式化し,高速なMAX-SMTソルバを用いて,票割当て問題の解を求める手法を提案する.提案手法の有効性を評価するため,トポロジと故障・修復を考慮したネットワークのモデルを構築し,その上で稼動する分散システムを想定して提案手法の評価を行った.その結果,レプリカ数10以下のシステムであれば,実用的な時間で提案手法を適用し可用性を最大化する票割当てを求めることができること,および,最適な票割当てを用いることで,障害が生じる状況におけるデータ可用性が大きく改善できることが分かった.
- 2014-03-15
著者
関連論文
- ラウンドモデルからの変換による非同期コンセンサスアルゴリズムの導出(ネットワーク環境でのディペンダビリティ)
- 3状態相互排他アルゴリズムの安定時間の下限について
- 非構造化オーバーレイネットワーク構築におけるメトロポリス法を用いたアルゴリズムの評価(ディペンダブルコンピュータシステムとセキュリティ技術及び一般)
- ペアワイズテスト : ソフトウェアテストの効率化を求めて
- モデル検査入門
- モデル検査を用いたコンセンサスアルゴリズムの合意性検証(ネットワーク環境でのディペンダビリティ)
- Interpolantを利用したモデル検査による機能競合の検証(ネットワーク環境でのディペンダビリティ)
- 耐故障分散アルゴリズムに対するPROMELAモデルの生成(ディペンダブルコンピューティングシステム及び一般)
- モデル検査器NuSMVを利用したテストケース自動生成(テスト・高信頼,組込技術とネットワークに関するワークショップETNET2008)
- ホームネットワークシステムにおける連携サービスのモデル検査による検証
- モデル検査による分散システムにおける合意アルゴリズムの安全性の検証(ディペンダブルソフトウェアとネットワーク及び一般)
- 整数上の論理式の充足可能性判定に基づく限定モデル検査手法の提案(安全性及び一般)
- 整数上の論理式の充足可能性判定に基づく限定モデル検査手法の提案
- ペトリネットに対する充足可能性判定を利用した検証手法の提案(コンカレント工学一般)
- ペトリネットに対するSATを利用したモデル検査の効率化
- 充足可能性判定を用いたモデル検査ツールの実装
- MANETプロトコルの仕様適合性試験のための状態遷移図縮退手法(ネットワークソフトウェア論文)
- 非構造化オーバーレイネットワーク構築におけるメトロポリス法を用いたアルゴリズムの評価(ディペンダブルコンピュータシステムとセキュリティ技術及び一般)
- ウインターワークショップ2010・イン・倉敷開催報告
- ウインターワークショップ2010・イン・倉敷開催報告
- GPUを用いた状態可到達性解析の高速化(ネットワーク環境でのディペンダビリティ,及び一般)
- Webアプリケーションの脆弱性検出を目的とした自動テストツールの性能評価(ネットワーク環境でのディペンダビリティ,及び一般)
- ピアの近接性を考慮したスキップグラフの構築
- ピアの近接性を考慮したスキップグラフの構築
- ピアの近接性を考慮したスキップグラフの構築
- ウインターワークショップ2010・イン・倉敷開催報告
- AndroidとMANETに基づいた自律構成可能な新世代児童見守りシステム (アドホックネットワーク)
- ゴシップ型ブロードキャストの高信頼化のための適応的再送手法の提案(ネットワーク,SWoPP2006)
- スケールフリーネットワークに対するゴシップアルゴリズムの高信頼化手法の提案(データ工学, ディペンダビリティ, 一般)
- スケールフリーネットワークに対するゴシップアルゴリズムの高信頼化手法の提案(データ工学, ディペンダビリティ, 一般)
- AT-3-3 モデル検査のためのコンカレントシステムの仕様記述(AT-3.コンカレントシステム理論の新しい流れ,チュートリアルセッション,ソサイエティ企画)
- B-19-7 Androidと自律分散クラスタリングを用いた新世代児童見守りシステムの構築に向けて(B-19.ネットワークソフトウェア,一般セッション)
- ピアの近接性を考慮したスキップグラフの構築
- ピアの近接性を考慮したスキップグラフの構築
- 記号モデル検査を用いた自己安定アルゴリズムの検証法の提案
- 記号モデル検査を用いた自己安定アルゴリズムの検証法の提案
- 物理ネットワークの構造を反映したオーバーレイネットワークの構築と信頼性評価(データ工学, ディペンダビリティ, 一般)
- 物理ネットワークの構造を反映したオーバーレイネットワークの構築と信頼性評価(データ工学, ディペンダビリティ, 一般)
- C-010 アドホックネットワークに対するゴシップ型ブロードキャストプロトコルの信頼性の分析(C.アーキテクチャ・ハードウェア)
- システム特性を考慮したペアワイズテストの改良
- サーベイ論文「ペアワイズテスト-ソフトウェアテストの効率化を求めて-」に関する訂正と補足
- 情報家電システムの安全検証(「信頼性・保全性・安全性の事例:情報処理・ソフトウェア編」〜信頼性ハンドブック出版から10年を経て〜)
- 単一多数決器を用いたカスケード式TMRの最適構成の導出(ディペンダブルコンピューティングシステム及び一般)
- 単一多数決器を用いたカスケード式TMRの最適構成の導出(ディペンダブルコンピューティングシステム及び一般)
- 耐故障分散アルゴリズムに対するPROMELAモデルの生成(ディペンダブルコンピューティングシステム及び一般)
- コントロールフローグラフにおける辺のペアを考慮したコードカバレッジの提案と評価 (ソフトウェアサイエンス)
- テスト実行コストを考慮したペアワイズテストセット生成法の提案(DC-2テスト,インターネット環境でのデータ工学とディペンダビリティ,及び一般)
- テスト実行コストを考慮したペアワイズテストセット生成法の提案(DC-2テスト,インターネット環境でのデータ工学とディペンダビリティ,及び一般)
- BS-12-6 アドホックネットワークテストベッドフレームワークにおける自律分散クラスタリングの実装と基本的評価(BS-12.アドホックネットワークのテストベッドと実証実験,シンポジウム)
- B-21-25 アドホックネットワークルーティングのためのテストベッドフレームワーク(B-21.アドホックネットワーク, 通信2)
- モデル検査器NuSMVを利用したテストケース自動生成(テスト・高信頼,組込技術とネットワークに関するワークショップETNET2008)
- モデル検査器NuSMVを利用したテストケース自動生成(テスト・高信頼,組込技術とネットワークに関するワークショップETNET2008)
- モデル検査器NuSMVを利用したテストケース自動生成(テスト・高信頼,組込技術とネットワークに関するワークショップETNET2008)
- オーバーレイネットワークにおける遠距離通信のホップ数削減の試み(インターネット環境でのデータ工学とディペンダビリティ)
- オーバーレイネットワークにおける遠距離通信のホップ数削減の試み(インターネット環境でのデータ工学とディペンダビリティ)
- マルチプロセッサスケジューリングのGA解法に対する精度向上
- C-009 ゴシップ型マルチキャストにおけるメンバーシップビューの構造化が信頼性に及ぼす影響に関する研究(C.アーキテクチャ・ハードウェア)
- ウィンターワークショップ2011・イン・修善寺開催報告
- リンク故障を考慮したkコテリーの信頼性評価手法
- アドホックネットワークにおける可変送信出力を用いた省電力ブロードキャスト手法の提案(解析・省電力,SWoPP2006)
- 無線モバイルマイクロセンサーネットワークにおける自己組織的センサー配置手法の提案
- Erasure符号によるゴシップ型ブロードキャストの高信頼化手法の提案(DC-1ネットワーク,インターネット環境でのデータ工学とディペンダビリティ,及び一般)
- Erasure符号によるゴシップ型ブロードキャストの高信頼化手法の提案(DC-1ネットワーク,インターネット環境でのデータ工学とディペンダビリティ,及び一般)
- Erasure符号によるゴシップ型ブロードキャストの信頼性向上について(高信頼・高可用システム,ディペンダブルコンピュータシステムとセキュリティ技術及び一般)
- Erasure符号によるゴシップ型ブロードキャストの信頼性向上について(高信頼・高可用システム,ディペンダブルコンピュータシステムとセキュリティ技術及び一般)
- AndroidとMANETに基づいた自律構成可能な新世代児童見守りシステム(モバイルユビキタス/センサ技術,アドホックネットワーク,RFID,一般及び技術展示)
- AndroidとMANETに基づいた自律構成可能な新世代児童見守りシステム(モバイルユビキタス/センサ技術,アドホックネットワーク,RFID,一般及び技術展示)
- コントロールフローグラフにおける辺のペアを考慮したコードカバレッジの提案と評価
- IRISソフトリアルタイムタスクの複数サーバ上への効果的なスケジューリング法の提案
- [3-2] ハードウェアRAMフォールトに対するソフトウェアによる監視方法(セッション3 試験,解析,一般,日本信頼性学会 第14回春季信頼性シンポジウム 報告)
- 3-2 ハードウェアRAMフォールトに対するソフトウェアによる監視方法(試験、解析、一般,セッション3)
- A-042 p-median問題に対するアントアルゴリズムの適用(A.モデル・アルゴリズム・プログラミング)
- 記号モデル検査を用いたステートチャートの検証
- BS-8-6 MANETにおけるBluetooth通信を用いたマルチコネクションの効率化(BS-8. ネットワークソフトウェア特別ポスターセッション,シンポジウムセッション)
- マルチプロセッサシステムのためのプログラム構造を考慮したフォールトトレラントスケジューリング
- あるマルチプロセッサ上でのフォールトトレラントスケジューリングアルゴリズムの提案
- 充足可能性判定を用いたモデル検査ツールの実装
- B-19-2 MANET自律分散クラスタリングの仕様適合性テストのためのFSM(B-19.ネットワークソフトウェア,一般講演)
- メタヒューリスティックを用いた組合せテスト用テストセットの生成法(安全性及び一般)
- 上界のない整数型変数を有する並行システムに対するk帰納法を用いたモデル検査(ネットワーク環境でのディペンダビリティ,及び一般)
- ネットワークコーディングに基づくゴシップの提案(ネットワーク環境でのディペンダビリティ,及び一般)
- 分散システムにおける信頼性最大の資源配置について
- ペトリネットに対する充足可能性判定を用いた検証法の提案
- ワークステーションクラスタを用いた耐故障並列分枝限定法の実装
- BS-8-5 Android端末を用いたBluetooth MANETにおける自律的衝突回避手法(BS-8.ネットワークソフトウェア特別ポスターセッション,シンポジウムセッション)
- 充足可能性判定を利用したモデル検査
- Android端末で構成するBluetooth MANETを用いた新世代児童見守りシステム(技術展示,モバイルユビキタス/センサ技術,アドホックネットワーク,RFID,一般及び技術展示)
- Android端末で構成するBluetooth MANETを用いた新世代児童見守りシステム(技術展示,モバイルユビキタス/センサ技術,アドホックネットワーク,RFID,一般及び技術展示)
- ランダムテストを利用した制約のあるインタラクションテストの効率的なテストケース生成
- 制御システム分野におけるモデル検査の応用
- パラメータ値に関する制約を考慮したランダムテストのためのテストケース生成手法(ネットワーク環境でのディペンダビリティー)
- 鉄道車両制御の分散処理のための車上アプリケーション再構築とワークフロー管理方式の提案(ソフトウェアシステム,システム開発論文)
- パラメータ値に関する制約を考慮したランダムテストの不具合検出率について(テスト)
- 多数決投票を用いた分散システムの可用性の最大化
- パラメータ値に対する重み付けを考慮したテストケース集合の拡張(ディペンダブルコンピューティングシステム及び一般)
- パラメータ値に対する重み付けを考慮したテストケース集合の拡張(ディペンダブルコンピューティングシステム及び一般)