11 Search Results for "Masuzawa, Toshimitsu"

Document
DOI: 10.4230/LIPIcs.OPODIS.2022.11
Computational Power of a Single Oblivious Mobile Agent in Two-Edge-Connected Graphs

Authors: Taichi Inoue, Naoki Kitamura, Taisuke Izumi, and Toshimitsu Masuzawa

Published in: LIPIcs, Volume 253, 26th International Conference on Principles of Distributed Systems (OPODIS 2022)

Abstract
We investigated the computational power of a single mobile agent in an n-node graph with storage (i.e., node memory). Generally, a system with one-bit agent memory and O(1)-bit storage is as powerful as that with O(n)-bit agent memory and O(1)-bit storage. Thus, we focus on the difference between one-bit memory and oblivious (i.e., zero-bit memory) agents. Although their computational powers are not equivalent, all the known results exhibiting such a difference rely on the fact that oblivious agents cannot transfer any information from one side to the other across the bridge edge. Hence, our main question is as follows: Are the computational powers of one-bit memory and oblivious agents equivalent in 2-edge-connected graphs or not? The main contribution of this study is to answer this question under the relaxed assumption that each node has O(logΔ)-bit storage (where Δ is the maximum degree of the graph). We present an algorithm for simulating any algorithm for a single one-bit memory agent using an oblivious agent with O(n²)-time overhead per round. Our results imply that the topological structure of graphs differentiating the computational powers of oblivious and non-oblivious agents is completely characterized by the existence of bridge edges.
Cite as

Taichi Inoue, Naoki Kitamura, Taisuke Izumi, and Toshimitsu Masuzawa. Computational Power of a Single Oblivious Mobile Agent in Two-Edge-Connected Graphs. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 11:1-11:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{inoue_et_al:LIPIcs.OPODIS.2022.11,
  author =	{Inoue, Taichi and Kitamura, Naoki and Izumi, Taisuke and Masuzawa, Toshimitsu},
  title =	{{Computational Power of a Single Oblivious Mobile Agent in Two-Edge-Connected Graphs}},
  booktitle =	{26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
  pages =	{11:1--11:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-265-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{253},
  editor =	{Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.11},
  URN =		{urn:nbn:de:0030-drops-176311},
  doi =		{10.4230/LIPIcs.OPODIS.2022.11},
  annote =	{Keywords: mobile agent, depth-first search, space complexity}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2022.14
Gathering of Mobile Robots with Defected Views

Authors: Yonghwan Kim, Masahiro Shibata, Yuichi Sudo, Junya Nakamura, Yoshiaki Katayama, and Toshimitsu Masuzawa

Published in: LIPIcs, Volume 253, 26th International Conference on Principles of Distributed Systems (OPODIS 2022)

Abstract
An autonomous mobile robot system consisting of many mobile computational entities (called robots) attracts much attention of researchers, and it is an emerging issue for a recent couple of decades to clarify the relation between the capabilities of robots and solvability of the problems. Generally, each robot can observe all other robots as long as there are no restrictions on visibility range or obstructions, regardless of the number of robots. In this paper, we provide a new perspective on the observation by robots; a robot cannot necessarily observe all other robots regardless of distances to them. We call this new computational model the defected view model. Under this model, in this paper, we consider the gathering problem that requires all the robots to gather at the same non-predetermined point and propose two algorithms to solve the gathering problem in the adversarial (N,N-2)-defected model for N ≥ 5 (where each robot observes at most N-2 robots chosen adversarially) and the distance-based (4,2)-defected model (where each robot observes at most two robots closest to itself), respectively, where N is the number of robots. Moreover, we present an impossibility result showing that there is no (deterministic) gathering algorithm in the adversarial or distance-based (3,1)-defected model, and we also show an impossibility result for the gathering in a relaxed (N, N-2)-defected model.
Cite as

Yonghwan Kim, Masahiro Shibata, Yuichi Sudo, Junya Nakamura, Yoshiaki Katayama, and Toshimitsu Masuzawa. Gathering of Mobile Robots with Defected Views. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 14:1-14:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{kim_et_al:LIPIcs.OPODIS.2022.14,
  author =	{Kim, Yonghwan and Shibata, Masahiro and Sudo, Yuichi and Nakamura, Junya and Katayama, Yoshiaki and Masuzawa, Toshimitsu},
  title =	{{Gathering of Mobile Robots with Defected Views}},
  booktitle =	{26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
  pages =	{14:1--14:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-265-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{253},
  editor =	{Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.14},
  URN =		{urn:nbn:de:0030-drops-176349},
  doi =		{10.4230/LIPIcs.OPODIS.2022.14},
  annote =	{Keywords: mobile robot, gathering, defected view model}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2022.46
Brief Announcement: Gathering Despite Defected View

Authors: Yonghwan Kim, Masahiro Shibata, Yuichi Sudo, Junya Nakamura, Yoshiaki Katayama, and Toshimitsu Masuzawa

Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)

Abstract
In this paper, we provide a new perspective on the observation by robots; a robot cannot necessarily observe all other robots regardless of distances to them. We introduce a new computational model with defected views called a (N,k)-defected model where k robots among N-1 other robots can be observed. We propose two gathering algorithms: one in the adversarial (N,N-2)-defected model for N ≥ 5 (where N is the number of robots) and the other in the distance-based (4,2)-defected model. Moreover, we present two impossibility results for a (3,1)-defected model and a relaxed (N, N-2)-defected model respectively. This announcement is short; the full paper is available at [Yonghwan Kim and others, 2022].
Cite as

Yonghwan Kim, Masahiro Shibata, Yuichi Sudo, Junya Nakamura, Yoshiaki Katayama, and Toshimitsu Masuzawa. Brief Announcement: Gathering Despite Defected View. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 46:1-46:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{kim_et_al:LIPIcs.DISC.2022.46,
  author =	{Kim, Yonghwan and Shibata, Masahiro and Sudo, Yuichi and Nakamura, Junya and Katayama, Yoshiaki and Masuzawa, Toshimitsu},
  title =	{{Brief Announcement: Gathering Despite Defected View}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{46:1--46:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.46},
  URN =		{urn:nbn:de:0030-drops-172377},
  doi =		{10.4230/LIPIcs.DISC.2022.46},
  annote =	{Keywords: mobile robot, gathering, defected view model}
}
Document
DOI: 10.4230/LIPIcs.DISC.2021.40
Time-Optimal Loosely-Stabilizing Leader Election in Population Protocols

Authors: Yuichi Sudo, Ryota Eguchi, Taisuke Izumi, and Toshimitsu Masuzawa

Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)

Abstract
We consider the leader election problem in the population protocol model. In pragmatic settings of population protocols, self-stabilization is a highly desired feature owing to its fault resilience and the benefit of initialization freedom. However, the design of self-stabilizing leader election is possible only under a strong assumption (i.e., the knowledge of the exact size of a network) and rich computational resource (i.e., the number of states). Loose-stabilization is a promising relaxed concept of self-stabilization to address the aforementioned issue. Loose-stabilization guarantees that starting from any configuration, the network will reach a safe configuration where a single leader exists within a short time, and thereafter it will maintain the single leader for a long time, but not necessarily forever. The main contribution of this paper is giving a time-optimal loosely-stabilizing leader election protocol. The proposed protocol with design parameter τ ≥ 1 attains O(τ log n) parallel convergence time and Ω(n^τ) parallel holding time (i.e., the length of the period keeping the unique leader), both in expectation. This protocol is time-optimal in the sense of both the convergence and holding times in expectation because any loosely-stabilizing leader election protocol with the same length of the holding time is known to require Ω(τ log n) parallel time.
Cite as

Yuichi Sudo, Ryota Eguchi, Taisuke Izumi, and Toshimitsu Masuzawa. Time-Optimal Loosely-Stabilizing Leader Election in Population Protocols. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 40:1-40:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{sudo_et_al:LIPIcs.DISC.2021.40,
  author =	{Sudo, Yuichi and Eguchi, Ryota and Izumi, Taisuke and Masuzawa, Toshimitsu},
  title =	{{Time-Optimal Loosely-Stabilizing Leader Election in Population Protocols}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{40:1--40:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-210-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{209},
  editor =	{Gilbert, Seth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.40},
  URN =		{urn:nbn:de:0030-drops-148427},
  doi =		{10.4230/LIPIcs.DISC.2021.40},
  annote =	{Keywords: population protocols, leader election, loose-stabilization, self-stabilization}
}
Document
DOI: 10.4230/LIPIcs.DISC.2020.11
Communication Efficient Self-Stabilizing Leader Election

Authors: Xavier Défago, Yuval Emek, Shay Kutten, Toshimitsu Masuzawa, and Yasumasa Tamura

Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)

Abstract
This paper presents a randomized self-stabilizing algorithm that elects a leader r in a general n-node undirected graph and constructs a spanning tree T rooted at r. The algorithm works under the synchronous message passing network model, assuming that the nodes know a linear upper bound on n and that each edge has a unique ID known to both its endpoints (or, alternatively, assuming the KT₁ model). The highlight of this algorithm is its superior communication efficiency: It is guaranteed to send a total of Õ (n) messages, each of constant size, till stabilization, while stabilizing in Õ (n) rounds, in expectation and with high probability. After stabilization, the algorithm sends at most one constant size message per round while communicating only over the (n - 1) edges of T. In all these aspects, the communication overhead of the new algorithm is far smaller than that of the existing (mostly deterministic) self-stabilizing leader election algorithms. The algorithm is relatively simple and relies mostly on known modules that are common in the fault free leader election literature; these modules are enhanced in various subtle ways in order to assemble them into a communication efficient self-stabilizing algorithm.
Cite as

Xavier Défago, Yuval Emek, Shay Kutten, Toshimitsu Masuzawa, and Yasumasa Tamura. Communication Efficient Self-Stabilizing Leader Election. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 11:1-11:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{defago_et_al:LIPIcs.DISC.2020.11,
  author =	{D\'{e}fago, Xavier and Emek, Yuval and Kutten, Shay and Masuzawa, Toshimitsu and Tamura, Yasumasa},
  title =	{{Communication Efficient Self-Stabilizing Leader Election}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{11:1--11:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-168-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{179},
  editor =	{Attiya, Hagit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.11},
  URN =		{urn:nbn:de:0030-drops-130892},
  doi =		{10.4230/LIPIcs.DISC.2020.11},
  annote =	{Keywords: self-stabilization, leader election, communication overhead}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2019.22
Tight Bounds on Distributed Exploration of Temporal Graphs

Authors: Tsuyoshi Gotoh, Paola Flocchini, Toshimitsu Masuzawa, and Nicola Santoro

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

Abstract
Temporal graphs (or evolving graphs) are time-varying graphs where time is assumed to be discrete. In this paper, we consider for the first time the problem of exploring temporal graphs of arbitrary unknown topology. We study the feasibility of exploration, under both the Fsync and Ssync schedulers, focusing on the number of agents necessary and sufficient to explore such graphs. We first consider the minimal (i.e., less restrictive) assumption on the dynamics of the graph under which exploration is still feasible: temporal connectivity. Let ℋ be the class of temporally connected graphs; we show that for any temporal graph ? ∈ ℋ the number of agents sufficient to perform exploration is related to the number of its transient edges, a parameter η(?) we call evanescence of the graph. More precisely, any ? ∈ ℋ can be explored by a team of k ≥ 2 η(?) +1 agents; this bound is tight as we prove there are ? ∈ ℋ that cannot be explored by 2 η(?) agents. We then turn our attention to the well-known stronger assumption on the dynamics of the graph, called 1-interval connectivity: the graph is connected at any time step. Let ? ⊂ ℋ be the class of these always-connected temporal graphs. For this class, we prove the existence of a difference between Fsync and Ssync when there is a bound ? on the number of edges missing at each time. In fact, we show a tight bound of 2 ? +1 on the number of agents necessary and sufficient in Ssync, and a smaller tight bound of 2 ? in Fsync. As a corollary, we re-establish two recently published bounds for 1-interval connected rings.
Cite as

Tsuyoshi Gotoh, Paola Flocchini, Toshimitsu Masuzawa, and Nicola Santoro. Tight Bounds on Distributed Exploration of Temporal Graphs. In 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, pp. 22:1-22:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{gotoh_et_al:LIPIcs.OPODIS.2019.22,
  author =	{Gotoh, Tsuyoshi and Flocchini, Paola and Masuzawa, Toshimitsu and Santoro, Nicola},
  title =	{{Tight Bounds on Distributed Exploration of Temporal Graphs}},
  booktitle =	{23rd International Conference on Principles of Distributed Systems (OPODIS 2019)},
  pages =	{22:1--22: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.22},
  URN =		{urn:nbn:de:0030-drops-118082},
  doi =		{10.4230/LIPIcs.OPODIS.2019.22},
  annote =	{Keywords: Distributed algorithm, Mobile agents, Exploration of dynamic networks, Arbitrary footprint}
}
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
DOI: 10.4230/LIPIcs.OPODIS.2018.31
Self-Stabilizing Token Distribution with Constant-Space for Trees

Authors: Yuichi Sudo, Ajoy K. Datta, Lawrence L. Larmore, and Toshimitsu Masuzawa

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

Abstract
Self-stabilizing and silent distributed algorithms for token distribution in rooted tree networks are given. Initially, each process of a graph holds at most l tokens. Our goal is to distribute the tokens in the whole network so that every process holds exactly k tokens. In the initial configuration, the total number of tokens in the network may not be equal to nk where n is the number of processes in the network. The root process is given the ability to create a new token or remove a token from the network. We aim to minimize the convergence time, the number of token moves, and the space complexity. A self-stabilizing token distribution algorithm that converges within O(n l) asynchronous rounds and needs Theta(nh epsilon) redundant (or unnecessary) token moves is given, where epsilon = min(k,l-k) and h is the height of the tree network. Two novel ideas to reduce the number of redundant token moves are presented. One reduces the number of redundant token moves to O(nh) without any additional costs while the other reduces the number of redundant token moves to O(n), but increases the convergence time to O(nh l). All algorithms given have constant memory at each process and each link register.
Cite as

Yuichi Sudo, Ajoy K. Datta, Lawrence L. Larmore, and Toshimitsu Masuzawa. Self-Stabilizing Token Distribution with Constant-Space for Trees. In 22nd International Conference on Principles of Distributed Systems (OPODIS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 125, pp. 31:1-31:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{sudo_et_al:LIPIcs.OPODIS.2018.31,
  author =	{Sudo, Yuichi and Datta, Ajoy K. and Larmore, Lawrence L. and Masuzawa, Toshimitsu},
  title =	{{Self-Stabilizing Token Distribution with Constant-Space for Trees}},
  booktitle =	{22nd International Conference on Principles of Distributed Systems (OPODIS 2018)},
  pages =	{31:1--31: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.31},
  URN =		{urn:nbn:de:0030-drops-100918},
  doi =		{10.4230/LIPIcs.OPODIS.2018.31},
  annote =	{Keywords: token distribution, self-stabilization, constant-space algorithm}
}
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.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}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2015.16
Maximum Matching for Anonymous Trees with Constant Space per Process

Authors: Ajoy K. Datta, Lawrence L. Larmore, and Toshimitsu Masuzawa

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

Abstract
We give a silent self-stabilizing protocol for computing a maximum matching in an anonymous network with a tree topology. The round complexity of our protocol is O(diam), where diam is the diameter of the network, and the step complexity is O(n*diam), where n is the number of processes in the network. The working space complexity is O(1) per process, although the output necessarily takes O(log(delta)) space per process, where delta is the degree of that process. To implement parent pointers in constant space, regardless of degree, we use the cyclic Abelian group Z_7.
Cite as

Ajoy K. Datta, Lawrence L. Larmore, and Toshimitsu Masuzawa. Maximum Matching for Anonymous Trees with Constant Space per Process. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 16:1-16:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{datta_et_al:LIPIcs.OPODIS.2015.16,
  author =	{Datta, Ajoy K. and Larmore, Lawrence L. and Masuzawa, Toshimitsu},
  title =	{{Maximum Matching for Anonymous Trees with Constant Space per Process}},
  booktitle =	{19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
  pages =	{16:1--16: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.16},
  URN =		{urn:nbn:de:0030-drops-66074},
  doi =		{10.4230/LIPIcs.OPODIS.2015.16},
  annote =	{Keywords: anonymous tree, maximum matching, self-stabilization, unfair daemon}
}
  • Refine by Author
  • 11 Masuzawa, Toshimitsu
  • 7 Sudo, Yuichi
  • 3 Datta, Ajoy K.
  • 3 Kakugawa, Hirotsugu
  • 3 Larmore, Lawrence L.
  • Show More...

  • Refine by Classification
  • 4 Theory of computation → Self-organization
  • 3 Theory of computation → Distributed algorithms
  • 1 Computer systems organization → Fault-tolerant network topologies
  • 1 Computing methodologies → Self-organization
  • 1 Theory of computation → Distributed computing models

  • Refine by Keyword
  • 4 self-stabilization
  • 3 Loose-stabilization
  • 3 Population protocols
  • 2 defected view model
  • 2 gathering
  • Show More...

  • Refine by Type
  • 11 document

  • Refine by Publication Year
  • 2 2016
  • 2 2019
  • 2 2020
  • 2 2023
  • 1 2018
  • 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