分散合意のための1ビットメッセージ最適早期停止アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
分散合意問題は, 同期式通信を行う分散システムにおいて, 0または1の初期値を持つ正常プロセッサ達が, 故障プロセッサ達のいかなる振舞いにもかかわらず, 自分達のうちのどれかが持っていた初期値を共通に決定するための通信アルゴリズムを与える問題である. 本研究ではラウンド数と最大メッセージビット数が同時に最適の早期停止アルゴリズムを示す. 早期停止アルゴリズムとは, アルゴリズム終了までのラウンド数が, 最大故障数ではなく実際の故障数に比例するものである. システムがn個のプロセッサからなり, そのうち最大t個が故障している可能性があり, 実際の故障数はfであるとする. このアルゴリズムでは, 全プロセッサ数n≥(4t+1)(t+1) のシステムにおいて, 1ビットのメッセージを用いてラウンド数r=min{f+2, t+1}で合意に到達する.
- 一般社団法人情報処理学会の論文
- 1998-01-15
著者
関連論文
- 放送通信融合環境におけるストリーミング配信の受信端末選択手法(セッション放送システム)
- 再生中断時間短縮のための端末伝送型インターネット放送システムの評価
- IPネットワークにおける分割放送型システムの途切れ時間に関する評価(一般,研究開発テストベッド構築・利用,一般)
- インターネット放送のための分割放送型配信システムの設計と実装(放送システム,通信技術の未来を拓く学生論文)
- 並列プログラムのバッチ処理環境における自動キュー選択型スケジューリングの性能評価
- 異種クライアント環境における連続メディアデータ放送のための待ち時間短縮手法(データ放送,データ工学論文)
- 選択型コンテンツのオンデマンド配信における待ち時間短縮のためのスケジューリング手法(ネットワークサービス,情報洪水時代のネットワークサービス)
- 選択型コンテンツの放送型配信における視聴順序を考慮した待ち時間短縮手法(MBL)
- バッチ処理型プログラム実行環境における資源制約を考慮したキュー選択の評価
- バッチ処理型プログラム実行環境におけるキュー選択方式に関するシミュレーション評価
- 選択型コンテンツの放送型配信におけるスケジューリング手法(データベースシステム)
- グリッドコンピューティングのためのウェブブラウザを用いたクライアント環境の構築(2006年並列/分散/協調処理に関する『高知』サマー・ワークショップ(SWoPP高知2006)
- 選択型コンテンツの放送型配信における遷移確率を考慮したスケジューリング手法(並列型,夏のデータベースワークショップDBWS 2006)
- 選択型コンテンツの放送型配信における遷移確率を考慮したスケジューリング手法(並列型)
- 直方体要素用高速多重極法によるマイクロマグネティックス計算の高速化
- 京都大学におけるATMネットワークの構成と利用(マルチメディアを利用したキャンパスネットワーク)
- IPのためのATMシグナリングプロトコルIP-SVC
- ネットワーク仮想記憶を利用した連続メディアの伝送方式
- 並列計算機上でのKyotoモデルによる興奮伝播シミュレーション(EVA-1:システム評価)
- 細胞生理学モデルの構築支援を目的とした既存要素モデルのオントロジー対応化手法(情報表現)
- オントロジーを用いた細胞生理学モデルの構築支援
- 電磁界数値解析におけるIDR(s)法の有効性評価
- SMPにおけるスレッド並列の台数効果と高速化手法について(EVA-1: 性能評価, 2005年並列/分散/協調処理に関する『武雄』サマー・ワークショップ(SWoPP武雄2005)-研究会・連続同時開催-)
- 時間周期有限要素法とEEC法に基づく非線形過渡電磁場解析における時間積分の収束性改善
- 時間周期有限要素法とEEC法に基づく非線形過渡電磁場解析の収束特性改善に関する基礎的検討
- 不完全コレスキー分解とEEC法に基づく新たな前処理によるA法の高速化
- 画面操作用インタフェースによるPCを活用した授業の円滑化に関する研究(認知と学習・教育用インタフェース/一般)
- 分散メモリ型ベクトル並列計算機上での高速整数ソーティングアルゴリズムの実装
- 並列ベクトル計算機VPP上のHPFの性能評価
- 分散メモリ型ベクトル並列計算機上での高速ソーティングアルゴリズム
- 並列ベクトル計算機VPP上のHPFの性能評価
- 分散メモリ型ベクトル並列計算機上での高速ソーティングアルゴリズム
- 3bit compactionと冗長2進を用いたFPGA向き乗算器
- 3bit compactionと冗長2進を用いたFPGA向き乗算器
- 3bit compactionと冗長2進を用いたFPGA向き乗算器
- 選択確率を考慮した選択型コンテンツの放送型配信における待ち時間短縮手法
- 没入型ボリュームレンダリング向け画像重畳技術
- QoS保証マルチキャスト対応IPネットワークにおける課金プロトコルの提案
- DT-MRIを使った脳神経線維の類似判定法
- マルチプラットフォーム上でのHPFコンパイラの評価
- VGクラスタにおけるパラレルポートを利用した低コストハードウェアバリアの性能評価
- ホスト・パソコン連繋による性能測定システム及びプロトタイプ版の概要
- 京都大学統合情報通信システムKUINSの基本概念とシステム設計
- DHCP/DNS/HTTPの連携による家電機器の自動設定及び閲覧システムの試作
- 多次元パラメータ階層型データのためのパラメータ選択法
- HPC2500による興奮伝播シミュレーションにおける並列化ICCGソルバの性能評価
- FHNモデルによる心臓の興奮伝播シミュレーションにおける線形反復解法に関する一検討
- 並列化ICCG法ソルバによるSMPクラスタ型並列計算機HPC2500のベンチマーク評価
- VGクラスタにおけるパラレルポートを利用した低コストハードウェアバリアの性能評価
- 携帯端末から利用可能なグリッドのためのウェブフレームワーク(グリッド(1), 「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2005))
- 携帯端末から利用可能なグリッドのためのウェブフレームワーク(グリッド(1), 「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2005))
- 携帯端末から利用可能なグリッドのためのウェブフレームワーク
- バウンディング・ボリュームによるボリュームレンダリングの高速化
- 有限要素解析用並列化ICCGゾルバの開発について
- Oblivious BPとSyntactic BPの計算時間による指数的分離
- ボリュームデータ検索用インデクスとしてのCPGの妥当性の検討
- 317 方向線素特徴を利用した特異点グラフの類似判定法(J11-1 流体情報学と可視化(1),J11 流体情報学と可視化,2005年度年次大会)
- 手書き文字認識技術を利用した特異点グラフの類似度判定
- D-1-2 Oblivious Branching Programのサイズの下限について
- 選択型コンテンツの放送型配信における視聴順序を考慮した待ち時間短縮手法(MBL)
- 京都大学統合情報通信システムKUINSにおける基幹ループLANの機能
- VR 環境における PDA を用いたパラメータ操作と注釈付与が可能な可視化システムの実装と評価(マルチメディア処理)
- 放送型配信における受信待ち時間を考慮した選択型コンテンツのスケジューリング手法(セッション3: 放送スケジューリング)
- 放送型配信における受信待ち時間を考慮した選択型コンテンツのスケジューリング手法(セッション3: 放送スケジューリング)
- 京都大学統合情報通信システムKUINSにおける複合交換網の実現
- SATに対する局所探索法のベクトル化
- 輻輳したATM網においてTCPのデッドロックを回避する動的粒度制御アルゴリズム
- 4P-3 災害時に耐障害性を有するネットワークのためのルーティング
- NPBを用いたHPF / JA拡張のVPP上での評価
- NPBを用いたHPF / JA拡張のVPP上での評価
- データ並列型言語VPP Fortranによる線形計算ライブラリScaLAPACKの実現(並列処理)
- 複数OSからのスーパーコンピュータの利用方式の開発
- 共同利用計算機におけるファイル管理に関する一考察
- 分散合意のための1ビットメッセージ最適早期停止アルゴリズム
- ScaLAPACKのVPP500への移植
- An Unbiased Global Coin Flipping Protocol on Synchronous Distributed Systems
- 分散合意のための1-ビットメッセージ最適早期停止アルゴリズム
- IPネットワークにおける連続メディアデータの分割放送型システムの設計と実装(情報配信サービス)
- IPネットワークにおける連続メディアデータの分割放送型システムの設計と実装(情報配信サービス)
- QoS保証マルチキャストプロトコルSRSVPにおける階層化PathQoS
- グリッドコンピューティング環境におけるプロセス連携機能を用いたジョブ管理システム
- 京都無線インターネットプロジェクトみあこネットの設計と運用
- 京都無線インターネットプロジェクトみあこネットの設計と運用