文献

J-GLOBAL ID：202002255188218196   整理番号：20A1410672

線形時間分散スワップエッジアルゴリズム【JST・京大機械翻訳】

Linear time distributed swap edge algorithms

著者 (5件)： Datta A.K. (Department of Computer Science, University of Nevada, USA) ,  Ferragina P. (Dipartimento di Informatica, Universita di Pisa, Italy) ,  Larmore L. (Department of Computer Science, University of Nevada, USA) ,  Pagli L. (Dipartimento di Informatica, Universita di Pisa, Italy) ,  Prencipe G. (Dipartimento di Informatica, Universita di Pisa, Italy)
資料名： Information Processing Letters  (Information Processing Letters)
巻： 161  ページ： Null  発行年： 2020年 
JST資料番号： E0513A  ISSN： 0020-0190  資料種別： 逐次刊行物 (A)
記事区分： 短報  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 本論文では,分散環境におけるすべての最良のスワップエッジ問題を考察した。著者らは,2エッジ接続正加重ネットワークXを与えて,そこで,すべての通信を,Xの根付きスパニング木Tを通して経路した。ツリーエッジe={x,y}が失敗するならば,通信ネットワークを切り離すであろう。しかしながら,Xは2エッジ接続であるので,通信は,eのスワップエッジと呼ばれる非ツリーエッジe′によってeを置き換えることにより回復することができ,その端はT→πe}の異なる成分にある。eの全ての可能なスワップエッジの中で,4つの異なる目的関数に従って,最良を選択するようにした。全体として,この問題はあらゆる木エッジに対して最良のスワップエッジを同定するので,任意のエッジ故障の場合,最良のスワップエッジを迅速に活性化できる。文献の多くの事例に対してこの問題に対する解決策がある。これらのすべての解決策の主要な関心事はメッセージの数を最小化することである。しかし,特に故障過渡環境においては,時間は重要な因子である。本論文では,時間展望からこの問題を扱う新しい手法を提案した。事実,著者らは,いくつかの異なる基準に対するTの高さhに関して線形時間で働く分散解を提示し,一方,各プロセッサxあたり,メッセージとO(Δx)空間の最適数を保持する。知る限りでは,漸近複雑度が3つの測度,即ち,時間,空間,およびメッセージの数,において,漸近的複雑性が整合する,すべての最良のスワップエッジ問題に対する事前アルゴリズムは存在しない。Copyright 2020 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *アルゴリズム ,  測度 ,  故障 ,  通信網 ,  ネットワーク ,  線形性 ,  目的関数 ,  分散処理 ,  演算プロセッサ ,  スパンニング木 ,  フォールトトレランス
準シソーラス用語： 複雑性 ,  分散環境 ,  複雑度 ,  *スワップ , 【Automatic Indexing@JST】

著者キーワード (5件)： スワップエッジ ,  エッジ故障 ,  分散コンピューティング ,  分散アルゴリズム ,  フォールトトレランス

分類 (3件)： 計算理論  (JB02000A) ,  計算機網  (JC03000K) ,  グラフ理論基礎  (IA02020S)

タイトルに関連する用語 (1件)： 線形