10 Search Results for "Ooshita, Fukuhito"

Document
DOI: 10.4230/LIPIcs.OPODIS.2021.9
Asynchronous Gathering in a Torus

Authors: Sayaka Kamei, Anissa Lamani, Fukuhito Ooshita, Sébastien Tixeuil, and Koichi Wada

Published in: LIPIcs, Volume 217, 25th International Conference on Principles of Distributed Systems (OPODIS 2021)

Abstract
We consider the gathering problem for asynchronous and oblivious robots that cannot communicate explicitly with each other but are endowed with visibility sensors that allow them to see the positions of the other robots. Most investigations on the gathering problem on the discrete universe are done on ring shaped networks due to the number of symmetric configurations. We extend in this paper the study of the gathering problem on torus shaped networks assuming robots endowed with local weak multiplicity detection. That is, robots cannot make the difference between nodes occupied by only one robot from those occupied by more than one robot unless it is their current node. Consequently, solutions based on creating a single multiplicity node as a landmark for the gathering cannot be used. We present in this paper a deterministic algorithm that solves the gathering problem starting from any rigid configuration on an asymmetric unoriented torus shaped network.
Cite as

Sayaka Kamei, Anissa Lamani, Fukuhito Ooshita, Sébastien Tixeuil, and Koichi Wada. Asynchronous Gathering in a Torus. In 25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, pp. 9:1-9:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{kamei_et_al:LIPIcs.OPODIS.2021.9,
  author =	{Kamei, Sayaka and Lamani, Anissa and Ooshita, Fukuhito and Tixeuil, S\'{e}bastien and Wada, Koichi},
  title =	{{Asynchronous Gathering in a Torus}},
  booktitle =	{25th International Conference on Principles of Distributed Systems (OPODIS 2021)},
  pages =	{9:1--9:17},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2021.9},
  URN =		{urn:nbn:de:0030-drops-157845},
  doi =		{10.4230/LIPIcs.OPODIS.2021.9},
  annote =	{Keywords: Autonomous distributed systems, Robots gathering, Torus}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2021.13
Population Protocols for Graph Class Identification Problems

Authors: Hiroto Yasumi, Fukuhito Ooshita, and Michiko Inoue

Published in: LIPIcs, Volume 217, 25th International Conference on Principles of Distributed Systems (OPODIS 2021)

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.
Cite as

Hiroto Yasumi, Fukuhito Ooshita, and Michiko Inoue. Population Protocols for Graph Class Identification Problems. In 25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, pp. 13:1-13:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2021.13},
  URN =		{urn:nbn:de:0030-drops-157885},
  doi =		{10.4230/LIPIcs.OPODIS.2021.13},
  annote =	{Keywords: population protocol, graph class identification, distributed protocol}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2020.33
Uniform Bipartition in the Population Protocol Model with Arbitrary Communication Graphs

Authors: Hiroto Yasumi, Fukuhito Ooshita, Michiko Inoue, and Sébastien Tixeuil

Published in: LIPIcs, Volume 184, 24th International Conference on Principles of Distributed Systems (OPODIS 2020)

Abstract
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.
Cite as

Hiroto Yasumi, Fukuhito Ooshita, Michiko Inoue, and Sébastien Tixeuil. Uniform Bipartition in the Population Protocol Model with Arbitrary Communication Graphs. In 24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, pp. 33:1-33:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{yasumi_et_al:LIPIcs.OPODIS.2020.33,
  author =	{Yasumi, Hiroto and Ooshita, Fukuhito and Inoue, Michiko and Tixeuil, S\'{e}bastien},
  title =	{{Uniform Bipartition in the Population Protocol Model with Arbitrary Communication Graphs}},
  booktitle =	{24th International Conference on Principles of Distributed Systems (OPODIS 2020)},
  pages =	{33:1--33:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-176-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{184},
  editor =	{Bramas, Quentin and Oshman, Rotem and Romano, Paolo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2020.33},
  URN =		{urn:nbn:de:0030-drops-135182},
  doi =		{10.4230/LIPIcs.OPODIS.2020.33},
  annote =	{Keywords: population protocol, uniform bipartition, distributed protocol}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2019.8
Uniform Partition in Population Protocol Model Under Weak Fairness

Authors: Hiroto Yasumi, Fukuhito Ooshita, and Michiko Inoue

Published in: LIPIcs, Volume 153, 23rd International Conference on Principles of Distributed Systems (OPODIS 2019)

Abstract
We focus on a uniform partition problem in a population protocol model. The uniform partition problem aims to divide a population into k groups of the same size, where k is a given positive integer. In the case of k=2 (called uniform bipartition), a previous work clarified space complexity under various assumptions: 1) an initialized base station (BS) or no BS, 2) weak or global fairness, 3) designated or arbitrary initial states of agents, and 4) symmetric or asymmetric protocols, except for the setting that agents execute a protocol from arbitrary initial states under weak fairness in the model with an initialized base station. In this paper, we clarify the space complexity for this remaining setting. In this setting, we prove that P states are necessary and sufficient to realize asymmetric protocols, and that P+1 states are necessary and sufficient to realize symmetric protocols, where P is the known upper bound of the number of agents. From these results and the previous work, we have clarified the solvability of the uniform bipartition for each combination of assumptions. Additionally, we newly consider an assumption on a model of a non-initialized BS and clarify solvability and space complexity in the assumption. Moreover, the results in this paper can be applied to the case that k is an arbitrary integer (called uniform k-partition).
Cite as

Hiroto Yasumi, Fukuhito Ooshita, and Michiko Inoue. Uniform Partition in Population Protocol Model Under Weak Fairness. In 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, pp. 8:1-8:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{yasumi_et_al:LIPIcs.OPODIS.2019.8,
  author =	{Yasumi, Hiroto and Ooshita, Fukuhito and Inoue, Michiko},
  title =	{{Uniform Partition in Population Protocol Model Under Weak Fairness}},
  booktitle =	{23rd International Conference on Principles of Distributed Systems (OPODIS 2019)},
  pages =	{8:1--8:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-133-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{153},
  editor =	{Felber, Pascal and Friedman, Roy and Gilbert, Seth and Miller, Avery},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2019.8},
  URN =		{urn:nbn:de:0030-drops-117947},
  doi =		{10.4230/LIPIcs.OPODIS.2019.8},
  annote =	{Keywords: population protocol, uniform k-partition, distributed protocol}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2019.27
Gathering on Rings for Myopic Asynchronous Robots With Lights

Authors: Sayaka Kamei, Anissa Lamani, Fukuhito Ooshita, Sébastien Tixeuil, and Koichi Wada

Published in: LIPIcs, Volume 153, 23rd International Conference on Principles of Distributed Systems (OPODIS 2019)

Abstract
We investigate gathering algorithms for asynchronous autonomous mobile robots moving in uniform ring-shaped networks. Different from most work using the Look-Compute-Move (LCM) model, we assume that robots have limited visibility and lights. That is, robots can observe nodes only within a certain fixed distance, and emit a color from a set of constant number of colors. We consider gathering algorithms depending on two parameters related to the initial configuration: M_{init}, which denotes the number of nodes between two border nodes, and O_{init}, which denotes the number of nodes hosting robots between two border nodes. In both cases, a border node is a node hosting one or more robots that cannot see other robots on at least one side. Our main contribution is to prove that, if M_{init} or O_{init} is odd, gathering is always feasible with three or four colors. The proposed algorithms do not require additional assumptions, such as knowledge of the number of robots, multiplicity detection capabilities, or the assumption of towerless initial configurations. These results demonstrate the power of lights to achieve gathering of robots with limited visibility.
Cite as

Sayaka Kamei, Anissa Lamani, Fukuhito Ooshita, Sébastien Tixeuil, and Koichi Wada. Gathering on Rings for Myopic Asynchronous Robots With Lights. In 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, pp. 27:1-27:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{kamei_et_al:LIPIcs.OPODIS.2019.27,
  author =	{Kamei, Sayaka and Lamani, Anissa and Ooshita, Fukuhito and Tixeuil, S\'{e}bastien and Wada, Koichi},
  title =	{{Gathering on Rings for Myopic Asynchronous Robots With Lights}},
  booktitle =	{23rd International Conference on Principles of Distributed Systems (OPODIS 2019)},
  pages =	{27:1--27:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-133-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{153},
  editor =	{Felber, Pascal and Friedman, Roy and Gilbert, Seth and Miller, Avery},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2019.27},
  URN =		{urn:nbn:de:0030-drops-118139},
  doi =		{10.4230/LIPIcs.OPODIS.2019.27},
  annote =	{Keywords: LCM robot system, ASYNC schedulers, myopic, luminous, ring networks}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2019.43
Brief Announcement: Neighborhood Mutual Remainder and Its Self-Stabilizing Implementation of Look-Compute-Move Robots

Authors: Shlomi Dolev, Sayaka Kamei, Yoshiaki Katayama, Fukuhito Ooshita, and Koichi Wada

Published in: LIPIcs, Volume 146, 33rd International Symposium on Distributed Computing (DISC 2019)

Abstract
In this paper, we define a new concept neighborhood mutual remainder (NMR). An NMR distributed algorithms should satisfy global fairness, l-exclusion and repeated local rendezvous requirements. We give a simple self-stabilizing algorithm to demonstrate the design paradigm to achieve NMR, and also present applications of NMR to a Look-Compute-Move robot system.
Cite as

Shlomi Dolev, Sayaka Kamei, Yoshiaki Katayama, Fukuhito Ooshita, and Koichi Wada. Brief Announcement: Neighborhood Mutual Remainder and Its Self-Stabilizing Implementation of Look-Compute-Move Robots. In 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 146, pp. 43:1-43:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{dolev_et_al:LIPIcs.DISC.2019.43,
  author =	{Dolev, Shlomi and Kamei, Sayaka and Katayama, Yoshiaki and Ooshita, Fukuhito and Wada, Koichi},
  title =	{{Brief Announcement: Neighborhood Mutual Remainder and Its Self-Stabilizing Implementation of Look-Compute-Move Robots}},
  booktitle =	{33rd International Symposium on Distributed Computing (DISC 2019)},
  pages =	{43:1--43:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-126-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{146},
  editor =	{Suomela, Jukka},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2019.43},
  URN =		{urn:nbn:de:0030-drops-113504},
  doi =		{10.4230/LIPIcs.DISC.2019.43},
  annote =	{Keywords: neighborhood mutual remainder, self-stabilization, LCM robot}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2018.30
Loosely-Stabilizing Leader Election with Polylogarithmic Convergence Time

Authors: Yuichi Sudo, Fukuhito Ooshita, Hirotsugu Kakugawa, Toshimitsu Masuzawa, Ajoy K. Datta, and Lawrence L. Larmore

Published in: LIPIcs, Volume 125, 22nd International Conference on Principles of Distributed Systems (OPODIS 2018)

Abstract
A loosely-stabilizing leader election protocol with polylogarithmic convergence time in the population protocol model is presented in this paper. In the population protocol model, which is a common abstract model of mobile sensor networks, it is known to be impossible to design a self-stabilizing leader election protocol. Thus, in our prior work, we introduced the concept of loose-stabilization, which is weaker than self-stabilization but has similar advantage as self-stabilization in practice. Following this work, several loosely-stabilizing leader election protocols are presented. The loosely-stabilizing leader election guarantees that, starting from an arbitrary configuration, the system reaches a safe configuration with a single leader within a relatively short time, and keeps the unique leader for an sufficiently long time thereafter. The convergence times of all the existing loosely-stabilizing protocols, i.e., the expected time to reach a safe configuration, are polynomial in n where n is the number of nodes (while the holding times to keep the unique leader are exponential in n). In this paper, a loosely-stabilizing protocol with polylogarithmic convergence time is presented. Its holding time is not exponential, but arbitrarily large polynomial in n.
Cite as

Yuichi Sudo, Fukuhito Ooshita, Hirotsugu Kakugawa, Toshimitsu Masuzawa, Ajoy K. Datta, and Lawrence L. Larmore. Loosely-Stabilizing Leader Election with Polylogarithmic Convergence Time. In 22nd International Conference on Principles of Distributed Systems (OPODIS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 125, pp. 30:1-30:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{sudo_et_al:LIPIcs.OPODIS.2018.30,
  author =	{Sudo, Yuichi and Ooshita, Fukuhito and Kakugawa, Hirotsugu and Masuzawa, Toshimitsu and Datta, Ajoy K. and Larmore, Lawrence L.},
  title =	{{Loosely-Stabilizing Leader Election with Polylogarithmic Convergence Time}},
  booktitle =	{22nd International Conference on Principles of Distributed Systems (OPODIS 2018)},
  pages =	{30:1--30:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-098-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{125},
  editor =	{Cao, Jiannong and Ellen, Faith and Rodrigues, Luis and Ferreira, Bernardo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2018.30},
  URN =		{urn:nbn:de:0030-drops-100901},
  doi =		{10.4230/LIPIcs.OPODIS.2018.30},
  annote =	{Keywords: Loose-stabilization, Population protocols, and Leader election}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2018.52
Brief Announcement: Loosely-stabilizing Leader Election with Polylogarithmic Convergence Time

Authors: Yuichi Sudo, Fukuhito Ooshita, Hirotsugu Kakugawa, and Toshimitsu Masuzawa

Published in: LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018)

Abstract
We present a fast loosely-stabilizing leader election protocol in the population protocol model. It elects a unique leader in a poly-logarithmic time and holds the leader for a polynomial time with arbitrarily large degree in terms of parallel time, i.e, the number of steps per the population size.
Cite as

Yuichi Sudo, Fukuhito Ooshita, Hirotsugu Kakugawa, and Toshimitsu Masuzawa. Brief Announcement: Loosely-stabilizing Leader Election with Polylogarithmic Convergence Time. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 52:1-52:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{sudo_et_al:LIPIcs.DISC.2018.52,
  author =	{Sudo, Yuichi and Ooshita, Fukuhito and Kakugawa, Hirotsugu and Masuzawa, Toshimitsu},
  title =	{{Brief Announcement: Loosely-stabilizing Leader Election with Polylogarithmic Convergence Time}},
  booktitle =	{32nd International Symposium on Distributed Computing (DISC 2018)},
  pages =	{52:1--52:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-092-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{121},
  editor =	{Schmid, Ulrich and Widder, Josef},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2018.52},
  URN =		{urn:nbn:de:0030-drops-98410},
  doi =		{10.4230/LIPIcs.DISC.2018.52},
  annote =	{Keywords: Self-stabilization, Loose-stabilization, Population protocols}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2017.19
Constant-Space Population Protocols for Uniform Bipartition

Authors: Hiroto Yasumi, Fukuhito Ooshita, Ken'ichi Yamaguchi, and Michiko Inoue

Published in: LIPIcs, Volume 95, 21st International Conference on Principles of Distributed Systems (OPODIS 2017)

Abstract
In this paper, we consider a uniform bipartition problem in a population protocol model. The goal of the uniform bipartition problem is to divide a population into two groups of the same size. We study the problem under various assumptions: 1) a population with or without a base station, 2) weak or global fairness, 3) symmetric or asymmetric protocols, and 4) designated or arbitrary initial states. As a result, we completely clarify constant-space solvability of the uniform bipartition problem and, if solvable, propose space-optimal protocols.
Cite as

Hiroto Yasumi, Fukuhito Ooshita, Ken'ichi Yamaguchi, and Michiko Inoue. Constant-Space Population Protocols for Uniform Bipartition. In 21st International Conference on Principles of Distributed Systems (OPODIS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 95, pp. 19:1-19:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{yasumi_et_al:LIPIcs.OPODIS.2017.19,
  author =	{Yasumi, Hiroto and Ooshita, Fukuhito and Yamaguchi, Ken'ichi and Inoue, Michiko},
  title =	{{Constant-Space Population Protocols for Uniform Bipartition}},
  booktitle =	{21st International Conference on Principles of Distributed Systems (OPODIS 2017)},
  pages =	{19:1--19:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-061-3},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{95},
  editor =	{Aspnes, James and Bessani, Alysson and Felber, Pascal and Leit\~{a}o, Jo\~{a}o},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2017.19},
  URN =		{urn:nbn:de:0030-drops-86482},
  doi =		{10.4230/LIPIcs.OPODIS.2017.19},
  annote =	{Keywords: population protocol, uniform bipartition, distributed protocol}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2015.14
Loosely-Stabilizing Leader Election on Arbitrary Graphs in Population Protocols Without Identifiers nor Random Numbers

Authors: Yuichi Sudo, Fukuhito Ooshita, Hirotsugu Kakugawa, and Toshimitsu Masuzawa

Published in: LIPIcs, Volume 46, 19th International Conference on Principles of Distributed Systems (OPODIS 2015)

Abstract
In the population protocol model Angluin et al. proposed in 2004, there exists no self-stabilizing leader election protocol for complete graphs, arbitrary graphs, trees, lines, degree-bounded graphs and so on unless the protocol knows the exact number of nodes. To circumvent the impossibility, we introduced the concept of loose-stabilization in 2009, which relaxes the closure requirement of self-stabilization. A loosely-stabilizing protocol guarantees that starting from any initial configuration a system reaches a safe configuration, and after that, the system keeps its specification (e.g. the unique leader) not forever, but for a sufficiently long time (e.g. exponentially large time with respect to the number of nodes). Our previous works presented two loosely-stabilizing leader election protocols for arbitrary graphs; One uses agent identifiers and the other uses random numbers to elect a unique leader. In this paper, we present a loosely-stabilizing protocol that solves leader election on arbitrary graphs without agent identifiers nor random numbers. By the combination of virus-propagation and token-circulation, the proposed protocol achieves polynomial convergence time and exponential holding time without such external entities. Specifically, given upper bounds N and Delta of the number of nodes n and the maximum degree of nodes delta respectively, it reaches a safe configuration within O(m*n^3*d + m*N*Delta^2*log(N)) expected steps, and keeps the unique leader for Omega(N*e^N) expected steps where m is the number of edges and d is the diameter of the graph. To measure the time complexity of the protocol, we assume the uniformly random scheduler which is widely used in the field of the population protocols.
Cite as

Yuichi Sudo, Fukuhito Ooshita, Hirotsugu Kakugawa, and Toshimitsu Masuzawa. Loosely-Stabilizing Leader Election on Arbitrary Graphs in Population Protocols Without Identifiers nor Random Numbers. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 14:1-14:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{sudo_et_al:LIPIcs.OPODIS.2015.14,
  author =	{Sudo, Yuichi and Ooshita, Fukuhito and Kakugawa, Hirotsugu and Masuzawa, Toshimitsu},
  title =	{{Loosely-Stabilizing Leader Election on Arbitrary Graphs in Population Protocols Without Identifiers nor Random Numbers}},
  booktitle =	{19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
  pages =	{14:1--14:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-98-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{46},
  editor =	{Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.14},
  URN =		{urn:nbn:de:0030-drops-66054},
  doi =		{10.4230/LIPIcs.OPODIS.2015.14},
  annote =	{Keywords: Loose-stabilization, Population protocols, Leader election}
}
  • Refine by Author
  • 10 Ooshita, Fukuhito
  • 4 Inoue, Michiko
  • 4 Yasumi, Hiroto
  • 3 Kakugawa, Hirotsugu
  • 3 Kamei, Sayaka
  • Show More...

  • Refine by Classification
  • 6 Theory of computation → Distributed algorithms
  • 3 Theory of computation → Concurrent algorithms
  • 2 Theory of computation → Self-organization

  • Refine by Keyword
  • 4 distributed protocol
  • 4 population protocol
  • 3 Loose-stabilization
  • 3 Population protocols
  • 2 uniform bipartition
  • Show More...

  • Refine by Type
  • 10 document

  • Refine by Publication Year
  • 2 2018
  • 2 2019
  • 2 2020
  • 2 2022
  • 1 2016
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact