License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.OPODIS.2021.13
URN: urn:nbn:de:0030-drops-157885
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15788/
Go to the corresponding LIPIcs Volume Portal

Yasumi, Hiroto ; Ooshita, Fukuhito ; Inoue, Michiko

Population Protocols for Graph Class Identification Problems

pdf-format:
LIPIcs-OPODIS-2021-13.pdf (0.7 MB)

Abstract

In this paper, we focus on graph class identification problems in the population protocol model. A graph class identification problem aims to decide whether a given communication graph is in the desired class (e.g. whether the given communication graph is a ring graph). Angluin et al. proposed graph class identification protocols with directed graphs and designated initial states under global fairness [Angluin et al., DCOSS2005]. We consider graph class identification problems for undirected graphs on various assumptions such as initial states of agents, fairness of the execution, and initial knowledge of agents. In particular, we focus on lines, rings, k-regular graphs, stars, trees, and bipartite graphs. With designated initial states, we propose graph class identification protocols for k-regular graphs and trees under global fairness, and propose a graph class identification protocol for stars under weak fairness. Moreover, we show that, even if agents know the number of agents n, there is no graph class identification protocol for lines, rings, k-regular graphs, trees, or bipartite graphs under weak fairness, and no graph class identification for lines, rings, k-regular graphs, stars, trees, or bipartite graphs with arbitrary initial states.

BibTeX - Entry

@InProceedings{yasumi_et_al:LIPIcs.OPODIS.2021.13,
  author =	{Yasumi, Hiroto and Ooshita, Fukuhito and Inoue, Michiko},
  title =	{{Population Protocols for Graph Class Identification Problems}},
  booktitle =	{25th International Conference on Principles of Distributed Systems (OPODIS 2021)},
  pages =	{13:1--13:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-219-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{217},
  editor =	{Bramas, Quentin and Gramoli, Vincent and Milani, Alessia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/15788},
  URN =		{urn:nbn:de:0030-drops-157885},
  doi =		{10.4230/LIPIcs.OPODIS.2021.13},
  annote =	{Keywords: population protocol, graph class identification, distributed protocol}
}

Keywords: population protocol, graph class identification, distributed protocol
Collection: 25th International Conference on Principles of Distributed Systems (OPODIS 2021)
Issue Date: 2022
Date of publication: 28.02.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI