講演抄録/キーワード |
講演名 |
2020-09-02 10:30
Uniform Bipartition in Population Protocol Model over Arbitrary Communication Networks ○Hiroto Yasumi・Fukuhito Ooshita・Michiko Inoue(NAIST)・Sebastien Tixeuil(Sorbonne Universite) COMP2020-8 |
抄録 |
(和) |
In this paper, we focus on the uniform bipartition problem in the population protocol model. This problem aims to divide a population into two groups of equal size. In particular, we consider the problem in the context of emph{arbitrary} communication graphs. As a result, we clarify the solvability of the uniform bipartition problem with arbitrary communication graphs when agents in the population have designated initial states, under various assumptions such as the existence of a base station, symmetry of the protocol, and fairness of the execution. When the problem is solvable, we present protocols for uniform bipartition. When global fairness is assumed, the space complexity of our solutions is tight. |
(英) |
In this paper, we focus on the uniform bipartition problem in the population protocol model. This problem aims to divide a population into two groups of equal size. In particular, we consider the problem in the context of emph{arbitrary} communication graphs. As a result, we clarify the solvability of the uniform bipartition problem with arbitrary communication graphs when agents in the population have designated initial states, under various assumptions such as the existence of a base station, symmetry of the protocol, and fairness of the execution. When the problem is solvable, we present protocols for uniform bipartition. When global fairness is assumed, the space complexity of our solutions is tight. |
キーワード |
(和) |
個体群プロトコル / 半数分割問題 / 分散プロトコル / / / / / |
(英) |
population protocol / uniform bipartition problem / distributed protocol / / / / / |
文献情報 |
信学技報, vol. 120, no. 152, COMP2020-8, pp. 17-24, 2020年9月. |
資料番号 |
COMP2020-8 |
発行日 |
2020-08-25 (COMP) |
ISSN |
Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2020-8 |