分散合意のための1-ビットメッセージ最適早期停止アルゴリズム

参考文献10件

書誌事項

タイトル別名
  • An optimal early stopping algorithm with one-bit messages for distributed consensus

この論文をさがす

説明

同期式通信を行う分散システムを考える.n個のプロセッサからなり,そのうち最大t個は故障しているとする.各プロセッサは初期バイナリー値を持つとする.分散合意問題は,正常プロセッサ達が,故障プロセッサ達の如何なる振舞にも関わらず,自分達のうちのどれかが持っていた初期値を共通に決定するという問題である.この問題に対する多くの分散アルゴリズムが研究されている.本研究ではラウンド数と最大メッセージビット数が同時に最適の早期停止アルゴリズム(すなわち、アルゴリズム終了までのラウンド数が実際の故障数fに比例する)を示す。このアルゴリズムでは全プロセッサ数n≥(4t+1)(t+1)、ラウンド数r=min{f+2,t+1}、最大メッセージビットサイズm=1である.

収録刊行物

参考文献 (10)*注記

もっと見る

詳細情報 詳細情報について

  • CRID
    1573105977000141312
  • NII論文ID
    110002812317
  • NII書誌ID
    AN1009593X
  • ISSN
    09196072
  • 本文言語コード
    ja
  • データソース種別
    • CiNii Articles

問題の指摘

ページトップへ