講演抄録/キーワード |
講演名 |
2024-03-14 16:00
Time Analysis of Space Efficient Uniform Partitioning in Population Protocols ○Pascal Sahner(NAIST/RWTH Aachen)・Ryota Eguchi(NAIST)・Fukuhito Ooshita(FUT)・Michiko Inoue(NAIST) COMP2023-34 |
抄録 |
(和) |
(まだ登録されていません) |
(英) |
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 protocol / uniform k-partition problem, / distributed system / distributed algorithm / time complexity analysis / / / |
文献情報 |
信学技報, vol. 123, no. 444, COMP2023-34, pp. 34-41, 2024年3月. |
資料番号 |
COMP2023-34 |
発行日 |
2024-03-07 (COMP) |
ISSN |
Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2023-34 |
|