Uniform Bipartition in the Population Protocol Model with Arbitrary Communication Graphs
| Autor: | Yasumi, Hiroto, Ooshita, Fukuhito, Inoue, Michiko, Tixeuil, S��bastien |
|---|---|
| Přispěvatelé: | Tixeuil, Sébastien, Nara Institute of Science and Technology - Graduate School of Information Science (NAIST), Nara Institute of Science and Technology, Networks and Performance Analysis (NPA), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Laboratory of Information, Network and Communication Sciences (LINCS), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut Mines-Télécom [Paris] (IMT)-Sorbonne Université (SU), ANR-19-CE25-0005,SAPPORO,Sûreté et preuve de protocoles adaptatifs pour robots oublieux(2019) |
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
FOS: Computer and information sciences
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC] [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] distributed protocol [INFO] Computer Science [cs] uniform bipartition population protocol [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI] Computer Science - Distributed Parallel and Cluster Computing Theory of computation → Concurrent algorithms [INFO.INFO-DC] Computer Science [cs]/Distributed Parallel and Cluster Computing [cs.DC] Distributed algorithms [INFO]Computer Science [cs] Distributed Parallel and Cluster Computing (cs.DC) Theory of computation → Distributed algorithms Concurrent algorithms phrases population protocol [INFO.INFO-DC]Computer Science [cs]/Distributed Parallel and Cluster Computing [cs.DC] MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | 24th International Conference on Principles of Distributed Systems (OPODIS 2020) 24th International Conference on Principles of Distributed Systems (OPODIS 2020), Dec 2020, Strasbourg, France. pp.33:1--33:16, ⟨10.4230/LIPIcs.OPODIS.2020.33⟩ |
| DOI: | 10.4230/LIPIcs.OPODIS.2020.33⟩ |
| Popis: | 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 arbitrary communication graphs. As a result, we investigate 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. LIPIcs, Vol. 184, 24th International Conference on Principles of Distributed Systems (OPODIS 2020), pages 33:1-33:16 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|