| 講演名 | 2024-03-14 Time Analysis of Space Efficient Uniform Partitioning in Population Protocols パスカル ザーナー(奈良先端大/RWTH Aachen), 江口 僚太(奈良先端大), 大下 福仁(福井工大), 井上 美智子(奈良先端大), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | |
| 抄録(英) | Population protocols are a theoretical model for modeling a set of units with low computational capabilities - so called agents - that can communicate with each other pairwise. Their possible applications are, for example, nano-robots consisting of only a few molecules or mobile sensors in a sensor network. Despite the performance limitations of a single agent, the entire population can fulfill global tasks that go beyond this limitation. For this purpose, it is often helpful to divide the agents into separate groups. In this way, for example, task distribution can be achieved. Exactly this subdivision, the exact k-partition problem, was dealt with in the doctoral dissertation [Yas22]. In addition to lower bounds on space complexity, upper bounds in the form of concrete protocols are also given. However, since the focus of the work is space complexity, the time complexity was only estimated using simulations. Therefore, in this work we focus on the time complexity aspect of those protocols and problems. |
| キーワード(和) | |
| キーワード(英) | population protocoluniform k-partition problem,distributed systemdistributed algorithmtime complexity analysis |
| 資料番号 | COMP2023-34 |
| 発行日 | 2024-03-07 (COMP) |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2024/3/14(から1日開催) |
| 開催地（和） | 電気通信大学 |
| 開催地（英） | The University of Electro-Communications |
| テーマ（和） | 理論計算機科学，一般 |
| テーマ（英） | Theoretical Computer Science, etc |
| 委員長氏名（和） | 宇野 裕之(大阪公立大) |
| 委員長氏名（英） | Hiroyuki Uno(Osaka Metropolitan Univ.) |
| 副委員長氏名（和） | 来嶋 秀治(滋賀大) |
| 副委員長氏名（英） | Shuji Kijima(Shiga Univ.) |
| 幹事氏名（和） | 和佐 州洋(法政大) / 横井 優(東工大) |
| 幹事氏名（英） | Kunihiro Wasa(Hosei Univ.) / Yu Yokoi(Tokyo Inst. of Tech) |
| 幹事補佐氏名（和） | 安藤 映(専修大) |
| 幹事補佐氏名（英） | Ei Ando(Senshu Univ.) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Theoretical Foundations of Computing |
|---|---|
| 本文の言語 | ENG |
| タイトル（和） | |
| サブタイトル（和） | |
| タイトル（英） | Time Analysis of Space Efficient Uniform Partitioning in Population Protocols |
| サブタイトル（和） | |
| キーワード(1)（和/英） | / population protocoluniform k-partition problem,distributed systemdistributed algorithmtime complexity analysis |
| 第 1 著者 氏名（和/英） | パスカル ザーナー / Pascal Sahner |
| 第 1 著者 所属（和/英） | 奈良先端科学技術大学院大学/RWTH Aachen(略称：奈良先端大/RWTH Aachen) Nara Insitute of Science and Technology/RWTH Aachen(略称：NAIST/RWTH Aachen) |
| 第 2 著者 氏名（和/英） | 江口 僚太 / Ryota Eguchi |
| 第 2 著者 所属（和/英） | 奈良先端科学技術大学院大学(略称：奈良先端大) Nara Insitute of Science and Technology(略称：NAIST) |
| 第 3 著者 氏名（和/英） | 大下 福仁 / Fukuhito Ooshita |
| 第 3 著者 所属（和/英） | 福井工業大学(略称：福井工大) Fukui University of Technology(略称：FUT) |
| 第 4 著者 氏名（和/英） | 井上 美智子 / Michiko Inoue |
| 第 4 著者 所属（和/英） | 奈良先端科学技術大学院大学(略称：奈良先端大) Nara Insitute of Science and Technology(略称：NAIST) |
| 発表年月日 | 2024-03-14 |
| 資料番号 | COMP2023-34 |
| 巻番号（vol） | vol.123 |
| 号番号（no） | COMP-444 |
| ページ範囲 | pp.34-41(COMP), |
| ページ数 | 8 |
| 発行日 | 2024-03-07 (COMP) |