確率的個体群プロトコルモデルにおける高速な情報収集

• Item type: SIG Technical Reports(1)
• 公開日: 2018-05-18
• タイトル: 確率的個体群プロトコルモデルにおける高速な情報収集
• タイトル / 言語: en
• タイトル: Fast Aggregation in Probabilistic Population Protocols
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 名古屋工業大学
• 著者所属: 名古屋工業大学
• 著者所属(英): en
• 著者所属(英): Nagoya Institute of Technology
• 著者所属(英): en
• 著者所属(英): Nagoya Institute of Technology
• 著者名: 江口, 僚太; 泉, 泰介
• 著者名(英): Ryota, Eguchi; Taisuke, Izumi
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本稿では，確率的スケジューラのもとでの基地局付き個体群プロトコルにおける新しい収集アルゴリズムを提案する．任意のモノイド (X，+) に対して，本稿で提案するアルゴリズムは求める総和 s = Σіxі(xi ∈ X) を高確率で計算する．その計算時間は期待値的にも高確率でも O (√n log² n) 時間であり，一般エージェントが使用する状態数は O (
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In this paper, we propose a new aggregation algorithm in probabilistic population protocol model with a base station. Specifically, for any monoid (X, +) the algorithm aggregates all inputs and outputs the sum of the input s = Σіsі with high probability. Its convergence time is within O (√n log²n) time both expectation and with high probability. The amount of states that ordinary agents use is O (
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2018-AL-168, 号 12, p. 1-8, 発行日 2018-05-18
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会