文献

J-GLOBAL ID：202002226660088222   整理番号：20A0776688

自己安定化Byzantineクロック同期化はコンセンサスと同様に容易である【JST・京大機械翻訳】

Self-Stabilising Byzantine Clock Synchronisation Is Almost as Easy as Consensus

著者 (2件)： Lenzen Christoph (Max Planck Institute for Informatics, Saarland Informatics Campus, Saarbruecken, Germany) ,  Rybicki Joel (Institute of Science and Technology Austria (IST Austria), Klosterneuburg, Austria)
資料名： Journal of the ACM (Association for Computing Machinery)  (Journal of the ACM (Association for Computing Machinery))
巻： 66  号： 5  ページ： 1-56  発行年： 2019年 
JST資料番号： C0267A  ISSN： 0004-5411  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 各nノードがそれ自身のクロックを持つ分散システムにおける同期性を確立するためのフォールトトレラントアルゴリズムを与えた。著者らのアルゴリズムは非常に強い故障モデルで動作する。すなわち,自己安定化を必要とする。すなわち,システムの初期状態は任意である可能性があり,また,任意の方法でプロトコルから逸脱するノードのような,最大f<n/3のByzantine故障が存在する。さらに,ノードの局所クロックが異なる速度(クロックドリフト)で進行し,通信が有界遅延を持つと仮定した。このモデルでは,パルス同期化問題を研究する。そこでは,タスクは,最終的にすべての正しいノードが,同期化された方法で,良く分離された局所的なパルスイベント(すなわち,ラベル付けされていない論理クロック)を生成することを保証する。以前の研究と比較して,安定化時間と通信ビット数における指数関数的改善を達成し,問題に対する最初のサブ線形時間アルゴリズムを与えた。決定論的設定において,最先端の解は時間Θ(f)で安定化し,時間単位当たり各ノードブロードキャストΘ(flog f)ビットを持つ。同じ安定化時間を保持しながら,時間単位当たりのビット数をΘ(log f)に指数関数的に減少させたが,ランダム化設定において,最先端の解は時間Θ(f)で安定化し,各ノードブロードキャストO(1)ビットを時間単位当たりに持つ。各ノードが時間単位当たりのポリログfビットを放送する間,安定化時間を指数関数的に減少させた。これらの結果は,同期モデルにおける非自己安定化二値コンセンサスに対する有界遅延モデルにおける自己安定化パルス同期化の上記タスクを低減する再帰的アプローチにより得られる。一般的に,著者らのアプローチは,基礎となるコンセンサスルーチン上の安定化時間と放送ビットに関して,ほとんどの対数オーバーヘッドで導入される。Please refer to this article’s citation page on the publisher website for specific rights information. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： アルゴリズム ,  分散系 ,  故障 ,  放送 ,  *クロック ,  指数関数 ,  同時性 ,  ドリフト ,  通信 ,  パルス ,  対数 ,  フォールトトレランス
準シソーラス用語： 故障モデル ,  オーバヘッド ,  有界 , 【Automatic Indexing@JST】

著者キーワード (4件)： 過渡故障 ,  合意 ,  ビザンチン断層 ,  クロックドリフト

分類 (2件)： グラフ理論基礎  (IA02020S) ,  計算理論  (JB02000A)

タイトルに関連する用語 (3件)： 自己安定化 ,  クロック同期 ,  コンセンサス