文献

J-GLOBAL ID：202002249496377555   整理番号：20A1510374

Ruを広げるか,そして歩行を行なうか?【JST・京大機械翻訳】

How to Spread a Rumor Call Your Neighbors or Take a Walk?

著者 (3件)： Giakkoupis George (Inria, Univ Rennes, CNRS, IRISA, Rennes, France) ,  Mallmann-Trenn Frederik (Massachusetts Institute of Technology, Cambridge, MA, USA) ,  Saribekyan Hayk (University of Cambridge, Cambridge, United Kingdom)
資料名： ACM Proceedings  (ACM Proceedings)
号： PODC ’19  ページ： 24-33  発行年： 2019年 
JST資料番号： D0698C  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： ネットワークにおけるランダム化情報普及の問題を研究した。独立ランダムウォークを実行するエージェントの収集により情報が普及するエージェントベース代替案と,現在標準PUSH-PULLプロトコルを比較した。VISIT-EXCHANGEプロトコルにおいて,ノードとエージェントは情報を保存し,各時間エージェントはノードを訪問し,2つの交換はそれらが持つ情報すべてを交換する。MEET-EXCHANGEプロトコルにおいて,エージェントは情報を保存するだけであり,それらの情報を各エージェントに交換する。定常分布から開始するエージェントの線形数を仮定して,上記3つのプロトコルに対するnノードグラフにおける情報の単一部分のブロードキャスト時間を考察した。エージェントベースプロトコルがPUSH-PULLよりも著しく速く,逆が真であるグラフが存在することを観測した。エージェントベースアルゴリズムの優れた性能を本質的に公正な帯域幅利用に属性し,ある設定において,エージェントベース情報普及は,別々に,あるいはPUSH-PULLとの組み合わせで,ブロードキャスト時間を著しく改善できると結論した。上記のグラフは高度に非正規である。著者らの主な技術的結果は,少なくとも対数度,PUSH-PULLおよびVISIT-EXCHANGEの任意の正規グラフが,同じ漸近ブロードキャスト時間を有することである。この証明は,VISIT-EXCHANGEにおけるランダムウォークとPUSH-PULLにおける頂点のランダム選択に関連する新しい結合議論を用いる。さらに,MEET-EXCHANGEのブロードキャスト時間は,すべての正規グラフ上で他の2つのものと同様に漸近的に少なく,いくつかの正規グラフ上で厳密に大きいことを示した。知る限りでは,これは,これらの非常に自然な情報普及プロトコルの実行時間の最初の系統的で完全な比較である。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】

著者キーワード (3件)： 情報配布 ,  ランダムウォーク ,  ドラムの広がり

分類 (2件)： 計算機網  (JC03000K) ,  人工知能  (JE08000Z)

タイトルに関連する用語 (2件)： Ru ,  歩行