| 講演名 | 2018-09-18 ラインおよびリングを形成する基地局を用いた仲介型個体群プロトコル 吉川 裕美(阪大), 首藤 裕一(阪大), 大下 福仁(奈良先端大), 角川 裕次(阪大), 増澤 利光(阪大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 仲介型個体群プロトコルモデルとは，膨大な数の計算能力の乏しい計算機(個体)で構成される無線ネットワークを抽象化したモデルである．このモデルでは，各個体と各個体ペアに状態が存在し，2つの個体の交流により，その2個体の状態とペアの状態が変化する．交流がシステム内で繰り返し発生することで，システム全体の状態が遷移し，計算やタスクが実行される．本報告では，基地局の存在と$k$-制限スケジューラを仮定し，ラインおよびリングを形成するプロトコルを提案する．基地局とは，ネットワーク中にただ一つ存在する，強力な計算能力を持つ特別な個体である．$k$-制限スケジューラとは，ある2個体間で$k+1$回の交流が発生する間にどの2個体間にも1回以上の交流が発生することを保証するスケジューラである．既存プロトコルは，実行開始時に各個体の状態が初期化されているという仮定のもとで，基地局を利用せずにこれらのトポロジを形成する．提案プロトコルは，基地局を利用することで，実行開始時に各個体が初期化されているという仮定のもとで個体の状態数を既存プロトコルより削減する．また，個体の状態数を増やすことで，実行開始時に各個体が初期化されていない場合でもトポロジの形成を実現する． |
| 抄録(英) | A mediated population protocol model is a computational model that abstracts a wireless network composed of numerous low-performance computers (particles). In this model, each particle and each pair of particles maintains a state which is updated when two particles interact. In this report, we propose protocols to construct lines and rings that assume the existence of a single base station, which is a particularly powerful particle. Previously proposed protocols construct lines and rings without a base station on the assumption that all particles are initialized. Our protocols using a single base station succeed to reduce the number of states of each particle when particles are initialized. In addition, we also propose a method to remove the assumption by additional states. |
| キーワード(和) | 仲介型個体群プロトコル / 基地局 / トポロジ形成 / 初期化 / 状態数削減 |
| キーワード(英) | mediated population protocols / base station / topology construction / initialization / reduce number of states |
| 資料番号 | COMP2018-12 |
| 発行日 | 2018-09-11 (COMP) |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2018/9/18(から1日開催) |
| 開催地（和） | 九州工業大学（飯塚キャンパス） |
| 開催地（英） | Kyusyu Institute of Technology |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | 藤戸 敏弘(豊橋技科大) |
| 委員長氏名（英） | Toshihiro Fujito(Toyohashi Univ. of Tech.) |
| 副委員長氏名（和） | 中野 眞一(群馬大) |
| 副委員長氏名（英） | Shinichi Nakano(Gunma Univ.) |
| 幹事氏名（和） | 玉置 卓(京大) / 大舘 陽太(熊本大) |
| 幹事氏名（英） | Suguru Tamaki(Kyoto Univ.) / Yota Otachi(Kumamoto Univ) |
| 幹事補佐氏名（和） | 脊戸 和寿(成蹊大) |
| 幹事補佐氏名（英） | Kazuhisa Seto(Seikei Univ.) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Theoretical Foundations of Computing |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | ラインおよびリングを形成する基地局を用いた仲介型個体群プロトコル |
| サブタイトル（和） | |
| タイトル（英） | Mediated population protocols with a base station for line and ring construction |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 仲介型個体群プロトコル / mediated population protocols |
| キーワード(2)（和/英） | 基地局 / base station |
| キーワード(3)（和/英） | トポロジ形成 / topology construction |
| キーワード(4)（和/英） | 初期化 / initialization |
| キーワード(5)（和/英） | 状態数削減 / reduce number of states |
| 第 1 著者 氏名（和/英） | 吉川 裕美 / Yuumi Yoshikawa |
| 第 1 著者 所属（和/英） | 大阪大学(略称：阪大) Osaka University(略称：Osaka Univ.) |
| 第 2 著者 氏名（和/英） | 首藤 裕一 / Yuuichi Sudou |
| 第 2 著者 所属（和/英） | 大阪大学(略称：阪大) Osaka University(略称：Osaka Univ.) |
| 第 3 著者 氏名（和/英） | 大下 福仁 / Fukuhito Ooshita |
| 第 3 著者 所属（和/英） | 奈良先端科学技術大学院大学(略称：奈良先端大) Nara Institute of Science and Technology(略称：NAIST) |
| 第 4 著者 氏名（和/英） | 角川 裕次 / Hirotsugu Kakugawa |
| 第 4 著者 所属（和/英） | 大阪大学(略称：阪大) Osaka University(略称：Osaka Univ.) |
| 第 5 著者 氏名（和/英） | 増澤 利光 / Toshimitsu Masuzawa |
| 第 5 著者 所属（和/英） | 大阪大学(略称：阪大) Osaka University(略称：Osaka Univ.) |
| 発表年月日 | 2018-09-18 |
| 資料番号 | COMP2018-12 |
| 巻番号（vol） | vol.118 |
| 号番号（no） | COMP-216 |
| ページ範囲 | pp.23-27(COMP), |
| ページ数 | 5 |
| 発行日 | 2018-09-11 (COMP) |