| IEICE Technical Committee Submission System Conference Paper's Information |
Online Proceedings [Sign in] Tech. Rep. Archives |
| Go Top Page | Go Previous | [Japanese] / [English] |
| Paper Abstract and Keywords | ||
| Presentation | 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 |
|
| Abstract | (in Japanese) | (See Japanese page) |
| (in English) | 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. | |
| Keyword | (in Japanese) | (See Japanese page) |
| (in English) | population protocol / uniform bipartition problem / distributed protocol / / / / / | |
| Reference Info. | IEICE Tech. Rep., vol. 120, no. 152, COMP2020-8, pp. 17-24, Sept. 2020. | |
| Paper # | COMP2020-8 | |
| Date of Issue | 2020-08-25 (COMP) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| Copyright and reproduction |
All rights are reserved and no part of this publication may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopy, recording, or any information storage and retrieval system, without permission in writing from the publisher. Notwithstanding, instructors are permitted to photocopy isolated articles for noncommercial classroom use without fee. (License No.: 10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| Download PDF | COMP2020-8 |
|
| Conference Information | |
| Committee | COMP IPSJ-AL |
| Conference Date | 2020-09-01 - 2020-09-02 |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | Online |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Paper Information | |
| Registration To | COMP |
| Conference Code | 2020-09-COMP-AL |
| Language | English |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Uniform Bipartition in Population Protocol Model over Arbitrary Communication Networks |
| Sub Title (in English) | |
| Keyword(1) | population protocol |
| Keyword(2) | uniform bipartition problem |
| Keyword(3) | distributed protocol |
| Keyword(4) | |
| Keyword(5) | |
| Keyword(6) | |
| Keyword(7) | |
| Keyword(8) | |
| 1st Author's Name | Hiroto Yasumi |
| 1st Author's Affiliation | Nara Institute of Science and Technology (NAIST) |
| 2nd Author's Name | Fukuhito Ooshita |
| 2nd Author's Affiliation | Nara Institute of Science and Technology (NAIST) |
| 3rd Author's Name | Michiko Inoue |
| 3rd Author's Affiliation | Nara Institute of Science and Technology (NAIST) |
| 4th Author's Name | Sebastien Tixeuil |
| 4th Author's Affiliation | Sorbonne Universite (Sorbonne Universite) |
| 5th Author's Name | |
| 5th Author's Affiliation | () |
| 6th Author's Name | |
| 6th Author's Affiliation | () |
| Speaker | Author-1 |
| Date Time | 2020-09-02 10:30:00 |
| Presentation Time | 30 minutes |
| Registration for | COMP |
| Paper # | COMP2020-8 |
| Volume (vol) | vol.120 |
| Number (no) | no.152 |
| Page | pp.17-24 |
| #Pages | 8 |
| Date of Issue | 2020-08-25 (COMP) |
[Return to Top Page]