23 Search Results for "Sudo, Yuichi"

Document
DOI: 10.4230/LIPIcs.ITCS.2026.36
Beyond 2-Edge-Connectivity: Algorithms and Impossibility for Content-Oblivious Leader Election

Authors: Yi-Jun Chang, Lyuting Chen, and Haoran Zhou

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
The content-oblivious model, introduced by Censor-Hillel, Cohen, Gelles, and Sela (PODC 2022; Distributed Computing 2023), captures an extremely weak form of communication where nodes can only send asynchronous, content-less pulses. They showed that in 2-edge-connected networks, any distributed algorithm can be simulated in the content-oblivious model, provided that a unique leader is designated a priori. Subsequent works of Frei, Gelles, Ghazy, and Nolin (DISC 2024) and Chalopin et al. (DISC 2025) developed content-oblivious leader election algorithms, first for unoriented rings and then for general 2-edge-connected graphs. These results establish that all graph problems are solvable in content-oblivious, 2-edge-connected networks. Much less is known about networks that are not 2-edge-connected. Censor-Hillel, Cohen, Gelles, and Sela showed that no non-constant function f(x,y) can be computed correctly by two parties using content-oblivious communication over a single edge, where one party holds x and the other holds y. This seemingly ruled out many natural graph problems on non-2-edge-connected graphs. In this work, we show that, with the knowledge of network topology G, leader election is possible in a wide range of graphs. Our main contributions are as follows: Impossibility: Graphs symmetric about an edge admit no randomized terminating leader election algorithm, even when nodes have unique identifiers and full knowledge of G. Leader election algorithms: Trees that are not symmetric about any edge admit a quiescently terminating leader election algorithm with topology knowledge, even in anonymous networks, using O(n²) messages, where n is the number of nodes. Moreover, even-diameter trees admit a terminating leader election given only the knowledge of the network diameter D = 2r, with message complexity O(nr). Necessity of topology knowledge: In the family of graphs 𝒢 = {P₃, P₅}, both the 3-path P₃ and the 5-path P₅ admit a quiescently terminating leader election if nodes know the topology exactly. However, if nodes only know that the underlying topology belongs to 𝒢, then terminating leader election is impossible.
Cite as

Yi-Jun Chang, Lyuting Chen, and Haoran Zhou. Beyond 2-Edge-Connectivity: Algorithms and Impossibility for Content-Oblivious Leader Election. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 36:1-36:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{chang_et_al:LIPIcs.ITCS.2026.36,
  author =	{Chang, Yi-Jun and Chen, Lyuting and Zhou, Haoran},
  title =	{{Beyond 2-Edge-Connectivity: Algorithms and Impossibility for Content-Oblivious Leader Election}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{36:1--36:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.36},
  URN =		{urn:nbn:de:0030-drops-253239},
  doi =		{10.4230/LIPIcs.ITCS.2026.36},
  annote =	{Keywords: Asynchronous model, fault tolerance, quiescent termination}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.102
Smoothed Analysis of Dynamic Graph Algorithms

Authors: Uri Meir and Ami Paz

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
Recent years have seen significant progress in the study of dynamic graph algorithms, and most notably, the introduction of strong lower bound techniques for them (e.g., Henzinger, Krinninger, Nanongkai and Saranurak, STOC 2015; Larsen and Yu, FOCS 2023). As worst-case analysis (adversarial inputs) may lead to the necessity of high running times, a natural question arises: in which cases are high running times really necessary, and in which cases these inputs merely manifest unique pathological cases? Early attempts to tackle this question were made by Nikoletseas, Reif, Spirakis and Yung (ICALP 1995) and by Alberts and Henzinger (Algorithmica 1998), who considered models with very little adversarial control over the inputs, and showed fast algorithms exist for them. The question was then overlooked for decades, until Henzinger, Lincoln and Saha (SODA 2022) recently addressed uniformly random inputs, and presented algorithms and impossibility results for several subgraph counting problems. To tackle the above question more thoroughly, we employ smoothed analysis, a celebrated framework introduced by Spielman and Teng (J. ACM, 2004). An input is proposed by an adversary but then a noisy version of it is processed by the algorithm instead. This model of inputs is parameterized by the amount of adversarial control, and fully interpolates between worst-case inputs and a uniformly random input. Doing so, we extend impossibility results for some problems to the smoothed model with only a minor quantitative loss. That is, we show that partially-adversarial inputs suffice to impose high running times for certain problems. In contrast, we show that other problems become easy even with the slightest amount of noise. In addition, we study the interplay between the adversary and the noise, leading to three natural models of smoothed inputs, for which we show a hierarchy of increasing difficulty stretching between the average-case and the worst-case complexities.
Cite as

Uri Meir and Ami Paz. Smoothed Analysis of Dynamic Graph Algorithms. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 102:1-102:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{meir_et_al:LIPIcs.ITCS.2026.102,
  author =	{Meir, Uri and Paz, Ami},
  title =	{{Smoothed Analysis of Dynamic Graph Algorithms}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{102:1--102:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.102},
  URN =		{urn:nbn:de:0030-drops-253896},
  doi =		{10.4230/LIPIcs.ITCS.2026.102},
  annote =	{Keywords: Dynamic graph algorithms, Smoothed analysis, Shortest paths}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2025.34
Uniform Deployment of Mobile Robots in Complete Bipartite Graphs

Authors: Masahiro Shibata, Naoki Kitamura, Ryota Eguchi, Yuichi Sudo, Junya Nakamura, Yonghwan Kim, Yoshiaki Katayama, Toshimitsu Masuzawa, Quentin Bramas, and Sébastien Tixeuil

Published in: LIPIcs, Volume 361, 29th International Conference on Principles of Distributed Systems (OPODIS 2025)

Abstract
In this paper, we address the problem of uniformly deploying mobile robots in complete bipartite graphs. Specifically, when n robots are positioned arbitrarily at distinct nodes in a complete bipartite graph K_{n,n}, which consists of two n-node sets V_L and V_R, the uniform deployment problem requires the robots to achieve one of the following configurations: (a) each node in V_L is occupied by exactly one robot, with no robots in V_R, or (b) each node in V_R is occupied by exactly one robot, with no robots in V_L. In either configuration, the distance between any two robots is 2, ensuring that the robots are uniformly deployed. In this paper, we explore the relationship between the visibility range of robots and the solvability of the uniform deployment problem. First, we characterize solvable and unsolvable initial configurations under the assumption that robots have an infinite visibility range. Next, we demonstrate that visibility range 1 (meaning robots can only observe nodes at a distance of 1 and the robots positioned on them) is insufficient, proving the impossibility of solving the problem under this constraint. Conversely, we show that visibility range Θ(log n) is sufficient by presenting an algorithm that solves the uniform deployment problem in O(1) rounds, starting from any solvable initial configuration. Finally, we briefly introduce an example showing that robots with a constant visibility range (which is 3 in this example) cannot solve the problem in a native way.
Cite as

Masahiro Shibata, Naoki Kitamura, Ryota Eguchi, Yuichi Sudo, Junya Nakamura, Yonghwan Kim, Yoshiaki Katayama, Toshimitsu Masuzawa, Quentin Bramas, and Sébastien Tixeuil. Uniform Deployment of Mobile Robots in Complete Bipartite Graphs. In 29th International Conference on Principles of Distributed Systems (OPODIS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 361, pp. 34:1-34:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{shibata_et_al:LIPIcs.OPODIS.2025.34,
  author =	{Shibata, Masahiro and Kitamura, Naoki and Eguchi, Ryota and Sudo, Yuichi and Nakamura, Junya and Kim, Yonghwan and Katayama, Yoshiaki and Masuzawa, Toshimitsu and Bramas, Quentin and Tixeuil, S\'{e}bastien},
  title =	{{Uniform Deployment of Mobile Robots in Complete Bipartite Graphs}},
  booktitle =	{29th International Conference on Principles of Distributed Systems (OPODIS 2025)},
  pages =	{34:1--34:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-409-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{361},
  editor =	{Arusoaie, Andrei and Onica, Emanuel and Spear, Michael and Tucci-Piergiovanni, Sara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2025.34},
  URN =		{urn:nbn:de:0030-drops-252075},
  doi =		{10.4230/LIPIcs.OPODIS.2025.34},
  annote =	{Keywords: mobile robots, uniform deployment, complete bipartite graphs}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2025.32
Recolorable Graph Exploration by an Oblivious Agent with Fewer Colors

Authors: Shota Takahashi, Haruki Kanaya, Shoma Hiraoka, Ryota Eguchi, and Yuichi Sudo

Published in: LIPIcs, Volume 361, 29th International Conference on Principles of Distributed Systems (OPODIS 2025)

Abstract
Recently, Böckenhauer, Frei, Unger, and Wehner (SIROCCO 2023) introduced a novel variant of the graph exploration problem in which a single memoryless agent must visit all nodes of an unknown, undirected, and connected graph before returning to its starting node. Unlike the standard model for mobile agents, edges are not labeled with port numbers. Instead, the agent can color its current node and observe the color of each neighboring node. To move, it specifies a target color and then moves to an adversarially chosen neighbor of that color. They analyzed the minimum number of colors required for successful exploration and proposed an elegant algorithm that enables the agent to explore an arbitrary graph using only eight colors. In this paper, we present a novel graph exploration algorithm that requires only six colors. Furthermore, we prove that five colors are sufficient if we consider only a restricted class of graphs, which we call the φ-free graphs, a class that includes every graph with maximum degree at most three and every cactus.
Cite as

Shota Takahashi, Haruki Kanaya, Shoma Hiraoka, Ryota Eguchi, and Yuichi Sudo. Recolorable Graph Exploration by an Oblivious Agent with Fewer Colors. In 29th International Conference on Principles of Distributed Systems (OPODIS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 361, pp. 32:1-32:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{takahashi_et_al:LIPIcs.OPODIS.2025.32,
  author =	{Takahashi, Shota and Kanaya, Haruki and Hiraoka, Shoma and Eguchi, Ryota and Sudo, Yuichi},
  title =	{{Recolorable Graph Exploration by an Oblivious Agent with Fewer Colors}},
  booktitle =	{29th International Conference on Principles of Distributed Systems (OPODIS 2025)},
  pages =	{32:1--32:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-409-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{361},
  editor =	{Arusoaie, Andrei and Onica, Emanuel and Spear, Michael and Tucci-Piergiovanni, Sara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2025.32},
  URN =		{urn:nbn:de:0030-drops-252052},
  doi =		{10.4230/LIPIcs.OPODIS.2025.32},
  annote =	{Keywords: mobile agents, recolorable graphs, graph exploration}
}
Document
DOI: 10.4230/LIPIcs.DISC.2025.21
Content-Oblivious Leader Election in 2-Edge-Connected Networks

Authors: Jérémie Chalopin, Yi-Jun Chang, Lyuting Chen, Giuseppe A. Di Luna, and Haoran Zhou

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
Censor-Hillel, Cohen, Gelles, and Sela (PODC 2022 & Distributed Computing 2023) studied fully-defective asynchronous networks, where communication channels may arbitrarily corrupt messages. The model is equivalent to content-oblivious computation, where nodes communicate solely via pulses. They showed that if the network is 2-edge-connected, then any algorithm for a noiseless setting can be simulated in the fully-defective setting; otherwise, no non-trivial computation is possible in the fully-defective setting. However, their simulation requires a predesignated leader, which they conjectured to be necessary for any non-trivial content-oblivious task. Recently, Frei, Gelles, Ghazy, and Nolin (DISC 2024) refuted this conjecture for the special case of oriented ring topology. They designed two asynchronous content-oblivious leader election algorithms with message complexity O(n ⋅ ID_{max}), where n is the number of nodes and ID_{max} is the maximum ID. The first algorithm stabilizes in unoriented rings without termination detection. The second algorithm quiescently terminates in oriented rings, thus enabling the execution of the simulation algorithm after leader election. In this work, we present two results: General 2-edge-connected topologies: First, we show an asynchronous content-oblivious leader election algorithm that quiescently terminates in any 2-edge-connected network with message complexity O(m ⋅ N ⋅ ID_{min}), where m is the number of edges, N is a known upper bound on the number of nodes, and ID_{min} is the smallest ID. Combined with the above simulation, this result shows that whenever a size bound N is known, any noiseless algorithm can be simulated in the fully-defective model without a preselected leader, fully refuting the conjecture. Unoriented rings: We then show that the knowledge of N can be dropped in unoriented ring topologies by presenting a quiescently terminating election algorithm with message complexity O(n ⋅ ID_{max}) that matches the previous bound. Consequently, this result constitutes a strict improvement over the previous state of the art and shows that, on rings, fully-defective and noiseless communication are computationally equivalent, with no additional assumptions.
Cite as

Jérémie Chalopin, Yi-Jun Chang, Lyuting Chen, Giuseppe A. Di Luna, and Haoran Zhou. Content-Oblivious Leader Election in 2-Edge-Connected Networks. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 21:1-21:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chalopin_et_al:LIPIcs.DISC.2025.21,
  author =	{Chalopin, J\'{e}r\'{e}mie and Chang, Yi-Jun and Chen, Lyuting and Di Luna, Giuseppe A. and Zhou, Haoran},
  title =	{{Content-Oblivious Leader Election in 2-Edge-Connected Networks}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{21:1--21:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.21},
  URN =		{urn:nbn:de:0030-drops-248385},
  doi =		{10.4230/LIPIcs.DISC.2025.21},
  annote =	{Keywords: Asynchronous model, fault tolerance, quiescent termination}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2025.63
Brief Announcement: Optimal Dispersion Under Asynchrony

Authors: Debasish Pattanayak, Ajay D. Kshemkalyani, Manish Kumar, Anisur Rahaman Molla, and Gokarna Sharma

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
We study the dispersion problem in anonymous port-labeled graphs: k ≤ n mobile agents, each with a unique ID and initially located arbitrarily on the nodes of an n-node graph with maximum degree Δ, must autonomously relocate so that no node hosts more than one agent. Dispersion serves as a fundamental task in the distributed computing of mobile agents, and its complexity stems from key challenges in local coordination under anonymity and limited memory. The goal is to minimize both the time to achieve dispersion and the memory required per agent. It is known that any algorithm requires Ω(k) time in the worst case, and Ω(log k) bits of memory per agent. A recent result [Kshemkalyani et al., 2025] gives an optimal O(k)-time algorithm in the synchronous setting and an O(k log k)-time algorithm in the asynchronous setting, both using O(log(k+Δ)) bits. We close the complexity gap in the asynchronous setting by presenting the first dispersion algorithm that runs in optimal O(k) time using O(log(k+Δ)) bits of memory per agent. Our solution relies on a novel technique for constructing a port-one tree in anonymous graphs, which may be of independent interest.
Cite as

Debasish Pattanayak, Ajay D. Kshemkalyani, Manish Kumar, Anisur Rahaman Molla, and Gokarna Sharma. Brief Announcement: Optimal Dispersion Under Asynchrony. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 63:1-63:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{pattanayak_et_al:LIPIcs.DISC.2025.63,
  author =	{Pattanayak, Debasish and Kshemkalyani, Ajay D. and Kumar, Manish and Molla, Anisur Rahaman and Sharma, Gokarna},
  title =	{{Brief Announcement: Optimal Dispersion Under Asynchrony}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{63:1--63:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.63},
  URN =		{urn:nbn:de:0030-drops-248795},
  doi =		{10.4230/LIPIcs.DISC.2025.63},
  annote =	{Keywords: Distributed algorithms, mobile agents, local communication, dispersion, asynchrony, port-one tree, time and memory complexity}
}
Document
DOI: 10.4230/LIPIcs.DISC.2025.41
Natural Calamities Demand More Rescuers: Exploring Connectivity Time Dynamic Graphs

Authors: Ashish Saxena and Kaushik Mondal

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
We study the exploration problem by mobile agents in Connectivity Time dynamic graphs. The Connectivity Time model was introduced by Michail et al. [JPDC 2014] and is arguably one of the weakest dynamic graph connectivity models. We prove that exploration is impossible in such graphs using ((n-1)(n-2))/2 mobile agents starting from an arbitrary initial configuration, even when agents have full knowledge of system parameters, global communication, full visibility, and infinite memory. We then present an exploration algorithm that uses ((n-1)(n-2))/2 + 1 agents equipped with global communication, 1-hop visibility and O(log n) memory.
Cite as

Ashish Saxena and Kaushik Mondal. Natural Calamities Demand More Rescuers: Exploring Connectivity Time Dynamic Graphs. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 41:1-41:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{saxena_et_al:LIPIcs.DISC.2025.41,
  author =	{Saxena, Ashish and Mondal, Kaushik},
  title =	{{Natural Calamities Demand More Rescuers: Exploring Connectivity Time Dynamic Graphs}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{41:1--41:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.41},
  URN =		{urn:nbn:de:0030-drops-248585},
  doi =		{10.4230/LIPIcs.DISC.2025.41},
  annote =	{Keywords: Mobile agents, Anonymous graphs, Exploration, Dynamic graphs, Deterministic algorithm}
}
Document
DOI: 10.4230/LIPIcs.SAND.2025.13
Self-Stabilizing Weakly Byzantine Perpetual Gathering of Mobile Agents

Authors: Jion Hirose, Ryota Eguchi, and Yuichi Sudo

Published in: LIPIcs, Volume 330, 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)

Abstract
We study the Byzantine gathering problem involving k mobile agents with unique identifiers (IDs), f of which are Byzantine. These agents start the execution of a common algorithm from (possibly different) nodes in an n-node network, potentially starting at different times. Once started, the agents operate in synchronous rounds. We focus on weakly Byzantine environments, where Byzantine agents can behave arbitrarily but cannot falsify their IDs. The goal is for all non-Byzantine agents to eventually terminate at a single node simultaneously. In this paper, we first prove two impossibility results: (1) for any number of non-Byzantine agents, no algorithm can solve this problem without global knowledge of the network size or the number of agents, and (2) no self-stabilizing algorithm exists if k ≤ 2f even with n, k, f, and the length Λ_g of the largest ID among IDs of non-Byzantine agents, where the self-stabilizing algorithm enables agents to gather starting from arbitrary (inconsistent) initial states. Next, based on these results, we introduce a perpetual gathering problem and propose a self-stabilizing algorithm for this problem. This problem requires that all non-Byzantine agents always be co-located from a certain time onwards. If the agents know Λ_g and upper bounds N, K, F on n, k, f, the proposed algorithm works in O(K⋅ F⋅ Λ_g⋅ X(N)) rounds, where X(n) is the time required to visit all nodes in a n-nodes network. Our results indicate that while no algorithm can solve the original self-stabilizing gathering problem for any k and f even with exact global knowledge of the network size and the number of agents, the self-stabilizing perpetual gathering problem can always be solved with just upper bounds on this knowledge.
Cite as

Jion Hirose, Ryota Eguchi, and Yuichi Sudo. Self-Stabilizing Weakly Byzantine Perpetual Gathering of Mobile Agents. In 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 330, pp. 13:1-13:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{hirose_et_al:LIPIcs.SAND.2025.13,
  author =	{Hirose, Jion and Eguchi, Ryota and Sudo, Yuichi},
  title =	{{Self-Stabilizing Weakly Byzantine Perpetual Gathering of Mobile Agents}},
  booktitle =	{4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)},
  pages =	{13:1--13:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-368-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{330},
  editor =	{Meeks, Kitty and Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2025.13},
  URN =		{urn:nbn:de:0030-drops-230662},
  doi =		{10.4230/LIPIcs.SAND.2025.13},
  annote =	{Keywords: Distributed algorithms, Byzantine environments, Gathering}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2024.37
Almost Time-Optimal Loosely-Stabilizing Leader Election on Arbitrary Graphs Without Identifiers in Population Protocols

Authors: Haruki Kanaya, Ryota Eguchi, Taisho Sasada, and Michiko Inoue

Published in: LIPIcs, Volume 324, 28th International Conference on Principles of Distributed Systems (OPODIS 2024)

Abstract
The population protocol model is a computational model for passive mobile agents. We address the leader election problem, which determines a unique leader on arbitrary communication graphs starting from any configuration. Unfortunately, self-stabilizing leader election is impossible to be solved without knowing the exact number of agents; thus, we consider loosely-stabilizing leader election, which converges to safe configurations in a relatively short time, and holds the specification (maintains a unique leader) for a relatively long time. When agents have unique identifiers, Sudo {et al. }(2019) proposed a protocol that, given an upper bound N for the number of agents n, converges in O(mNlog n) expected steps, where m is the number of edges. When unique identifiers are not required, they also proposed a protocol that, using random numbers and given N, converges in O(mN²log{N}) expected steps. Both protocols have a holding time of Ω(e^{2N}) expected steps and use O(log{N}) bits of memory. They also showed that the lower bound of the convergence time is Ω(mN) expected steps for protocols with a holding time of Ω(e^N) expected steps given N. In this paper, we propose protocols that do not require unique identifiers. These protocols achieve convergence times close to the lower bound with increasing memory usage. Specifically, given N and an upper bound Δ for the maximum degree, we propose two protocols whose convergence times are O(mNlog n) and O(mNlog N) both in expectation and with high probability. The former protocol uses random numbers, while the latter does not require them. Both protocols utilize O(Δ log N) bits of memory and hold the specification for Ω(e^{2N}) expected steps.
Cite as

Haruki Kanaya, Ryota Eguchi, Taisho Sasada, and Michiko Inoue. Almost Time-Optimal Loosely-Stabilizing Leader Election on Arbitrary Graphs Without Identifiers in Population Protocols. In 28th International Conference on Principles of Distributed Systems (OPODIS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 324, pp. 37:1-37:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{kanaya_et_al:LIPIcs.OPODIS.2024.37,
  author =	{Kanaya, Haruki and Eguchi, Ryota and Sasada, Taisho and Inoue, Michiko},
  title =	{{Almost Time-Optimal Loosely-Stabilizing Leader Election on Arbitrary Graphs Without Identifiers in Population Protocols}},
  booktitle =	{28th International Conference on Principles of Distributed Systems (OPODIS 2024)},
  pages =	{37:1--37:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-360-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{324},
  editor =	{Bonomi, Silvia and Galletta, Letterio and Rivi\`{e}re, Etienne and Schiavoni, Valerio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2024.37},
  URN =		{urn:nbn:de:0030-drops-225734},
  doi =		{10.4230/LIPIcs.OPODIS.2024.37},
  annote =	{Keywords: Population protocols, Leader election, Loose-stabilization, Self-stabilization}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2024.12
Crash-Tolerant Perpetual Exploration with Myopic Luminous Robots on Rings

Authors: Fukuhito Ooshita, Naoki Kitamura, Ryota Eguchi, Michiko Inoue, Hirotsugu Kakugawa, Sayaka Kamei, Masahiro Shibata, and Yuichi Sudo

Published in: LIPIcs, Volume 324, 28th International Conference on Principles of Distributed Systems (OPODIS 2024)

Abstract
We investigate crash-tolerant perpetual exploration algorithms by myopic luminous robots on ring networks. Myopic robots mean that they can observe nodes only within a certain fixed distance ϕ, and luminous robots mean that they have light devices that can emit a color from a set of colors. The goal of perpetual exploration is to ensure that robots, starting from specific initial positions and colors, move in such a way that every node is visited by at least one robot infinitely often. As a main contribution, we clarify the tight necessary and sufficient number of robots to realize perpetual exploration when at most f robots crash. In the fully synchronous model, we prove that f+2 robots are necessary and sufficient for any ϕ ≥ 1. In the semi-synchronous and asynchronous models, we prove that 3f+3 (resp., 2f+2) robots are necessary and sufficient if ϕ = 1 (resp., ϕ ≥ 2).
Cite as

Fukuhito Ooshita, Naoki Kitamura, Ryota Eguchi, Michiko Inoue, Hirotsugu Kakugawa, Sayaka Kamei, Masahiro Shibata, and Yuichi Sudo. Crash-Tolerant Perpetual Exploration with Myopic Luminous Robots on Rings. In 28th International Conference on Principles of Distributed Systems (OPODIS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 324, pp. 12:1-12:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{ooshita_et_al:LIPIcs.OPODIS.2024.12,
  author =	{Ooshita, Fukuhito and Kitamura, Naoki and Eguchi, Ryota and Inoue, Michiko and Kakugawa, Hirotsugu and Kamei, Sayaka and Shibata, Masahiro and Sudo, Yuichi},
  title =	{{Crash-Tolerant Perpetual Exploration with Myopic Luminous Robots on Rings}},
  booktitle =	{28th International Conference on Principles of Distributed Systems (OPODIS 2024)},
  pages =	{12:1--12:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-360-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{324},
  editor =	{Bonomi, Silvia and Galletta, Letterio and Rivi\`{e}re, Etienne and Schiavoni, Valerio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2024.12},
  URN =		{urn:nbn:de:0030-drops-225486},
  doi =		{10.4230/LIPIcs.OPODIS.2024.12},
  annote =	{Keywords: mobile robots, crash faults, LCM model, exploration}
}
Document
DOI: 10.4230/LIPIcs.DISC.2024.38
Near-Linear Time Dispersion of Mobile Agents

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

Published in: LIPIcs, Volume 319, 38th International Symposium on Distributed Computing (DISC 2024)

Abstract
Consider that there are k ≤ n agents in a simple, connected, and undirected graph G = (V,E) with n nodes and m edges. The goal of the dispersion problem is to move these k agents to mutually distinct nodes. Agents can communicate only when they are at the same node, and no other communication means, such as whiteboards, are available. We assume that the agents operate synchronously. We consider two scenarios: when all agents are initially located at a single node (rooted setting) and when they are initially distributed over one or more nodes (general setting). Kshemkalyani and Sharma presented a dispersion algorithm for the general setting, which uses O(m_k) time and log(k + Δ) bits of memory per agent [OPODIS 2021], where m_k is the maximum number of edges in any induced subgraph of G with k nodes, and Δ is the maximum degree of G. This algorithm is currently the fastest in the literature, as no o(m_k)-time algorithm has been discovered, even for the rooted setting. In this paper, we present significantly faster algorithms for both the rooted and the general settings. First, we present an algorithm for the rooted setting that solves the dispersion problem in O(klog min(k,Δ)) = O(klog k) time using O(log (k+Δ)) bits of memory per agent. Next, we propose an algorithm for the general setting that achieves dispersion in O(k log k ⋅ log min(k,Δ)) = O(k log² k) time using O(log (k+Δ)) bits. Finally, for the rooted setting, we give a time-optimal (i.e., O(k)-time) algorithm with O(Δ+log k) bits of space per agent. All algorithms presented in this paper work only in the synchronous setting, while several algorithms in the literature, including the one given by Kshemkalyani and Sharma at OPODIS 2021, work in the asynchronous setting.
Cite as

Yuichi Sudo, Masahiro Shibata, Junya Nakamura, Yonghwan Kim, and Toshimitsu Masuzawa. Near-Linear Time Dispersion of Mobile Agents. In 38th International Symposium on Distributed Computing (DISC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 319, pp. 38:1-38:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{sudo_et_al:LIPIcs.DISC.2024.38,
  author =	{Sudo, Yuichi and Shibata, Masahiro and Nakamura, Junya and Kim, Yonghwan and Masuzawa, Toshimitsu},
  title =	{{Near-Linear Time Dispersion of Mobile Agents}},
  booktitle =	{38th International Symposium on Distributed Computing (DISC 2024)},
  pages =	{38:1--38:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-352-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{319},
  editor =	{Alistarh, Dan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2024.38},
  URN =		{urn:nbn:de:0030-drops-212658},
  doi =		{10.4230/LIPIcs.DISC.2024.38},
  annote =	{Keywords: mobile agents, autonomous robots, dispersion}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2024.55
Brief Announcement: Self-Stabilizing Graph Exploration by a Single Agent

Authors: Yuichi Sudo, Fukuhito Ooshita, and Sayaka Kamei

Published in: LIPIcs, Volume 319, 38th International Symposium on Distributed Computing (DISC 2024)

Abstract
In this paper, we present two self-stabilizing algorithms that enable a single (mobile) agent to explore graphs. The agent visits all nodes starting from any configuration, i.e., regardless of the initial state of the agent, the initial states of all nodes, and the initial location of the agent. We evaluate the algorithms using two metrics: cover time, which is the number of moves required to visit all nodes, and memory usage, which includes the storage needed for the state of the agent and the state of each node. The first algorithm is randomized. Given an integer c = Ω(n), the cover time of this algorithm is optimal, i.e., O(m) in expectation, and the memory requirements for the agent and each node v are O(log c) and O(log (c+δ_v)) bits, respectively, where n and m are the numbers of nodes and edges, respectively, and δ_v is the degree of v. The second algorithm is deterministic. It requires an input integer k ≥ max(D,δ_max), where D and δ_max are the diameter and the maximum degree of the graph, respectively. The cover time of this algorithm is O(m + nD), and it uses O(log k) bits both for agent memory and each node.
Cite as

Yuichi Sudo, Fukuhito Ooshita, and Sayaka Kamei. Brief Announcement: Self-Stabilizing Graph Exploration by a Single Agent. In 38th International Symposium on Distributed Computing (DISC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 319, pp. 55:1-55:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{sudo_et_al:LIPIcs.DISC.2024.55,
  author =	{Sudo, Yuichi and Ooshita, Fukuhito and Kamei, Sayaka},
  title =	{{Brief Announcement: Self-Stabilizing Graph Exploration by a Single Agent}},
  booktitle =	{38th International Symposium on Distributed Computing (DISC 2024)},
  pages =	{55:1--55:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-352-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{319},
  editor =	{Alistarh, Dan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2024.55},
  URN =		{urn:nbn:de:0030-drops-212832},
  doi =		{10.4230/LIPIcs.DISC.2024.55},
  annote =	{Keywords: mobile agents, self-stabilization, graph exploration}
}
Document
DOI: 10.4230/LIPIcs.ESA.2024.98
Local Max-Cut on Sparse Graphs

Authors: Gregory Schwartzman

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
We bound the smoothed running time of the FLIP algorithm for local Max-Cut as a function of α, the arboricity of the input graph. We show that, with high probability and in expectation, the following holds (where n is the number of nodes and ϕ is the smoothing parameter): 1) When α = O(log^{1-δ} n) FLIP terminates in ϕ poly(n) iterations, where δ ∈ (0,1] is an arbitrarily small constant. Previous to our results the only graph families for which FLIP was known to achieve a smoothed polynomial running time were complete graphs and graphs with logarithmic maximum degree. 2) For arbitrary values of α we get a running time of ϕ n^{O(α/(log n) + log α)}. This improves over the best known running time for general graphs of ϕ n^{O(√{log n})} for α = o(log^{1.5} n). Specifically, when α = O(log n) we get a significantly faster running time of ϕ n^{O(log log n)}.
Cite as

Gregory Schwartzman. Local Max-Cut on Sparse Graphs. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 98:1-98:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{schwartzman:LIPIcs.ESA.2024.98,
  author =	{Schwartzman, Gregory},
  title =	{{Local Max-Cut on Sparse Graphs}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{98:1--98:6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.98},
  URN =		{urn:nbn:de:0030-drops-211694},
  doi =		{10.4230/LIPIcs.ESA.2024.98},
  annote =	{Keywords: Algorithms, smoothed analysis}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2023.28
On Asynchrony, Memory, and Communication: Separations and Landscapes

Authors: Paola Flocchini, Nicola Santoro, Yuichi Sudo, and Koichi Wada

Published in: LIPIcs, Volume 286, 27th International Conference on Principles of Distributed Systems (OPODIS 2023)

Abstract
Research on distributed computing by a team of identical mobile computational entities, called robots, operating in a Euclidean space in Look-Compute-Move (LCM) cycles, has recently focused on better understanding how the computational power of robots depends on the interplay between their internal capabilities (i.e., persistent memory, communication), captured by the four standard computational models (OBLOT, LUMI, FSTA, and FCOM) and the conditions imposed by the external environment, controlling the activation of the robots and their synchronization of their activities, perceived and modeled as an adversarial scheduler. We consider a set of adversarial asynchronous schedulers ranging from the classical semi-synchronous (Ssynch) and fully asynchronous (Asynch) settings, including schedulers (emerging when studying the atomicity of the combination of operations in the LCM cycles) whose adversarial power is in between those two. We ask the question: what is the computational relationship between a model M₁ under adversarial scheduler K₁ (M₁(K₁)) and a model M₂ under scheduler K₂ (M₂(K₂))? For example, are the robots in M₁(K₁) more powerful (i.e., they can solve more problems) than those in M₂(K₂)? We answer all these questions by providing, through cross-model analysis, a complete characterization of the computational relationship between the power of the four models of robots under the considered asynchronous schedulers. In this process, we also provide qualified answers to several open questions, including the outstanding one on the proper dominance of Ssynch over Asynch in the case of unrestricted visibility.
Cite as

Paola Flocchini, Nicola Santoro, Yuichi Sudo, and Koichi Wada. On Asynchrony, Memory, and Communication: Separations and Landscapes. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 28:1-28:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{flocchini_et_al:LIPIcs.OPODIS.2023.28,
  author =	{Flocchini, Paola and Santoro, Nicola and Sudo, Yuichi and Wada, Koichi},
  title =	{{On Asynchrony, Memory, and Communication: Separations and Landscapes}},
  booktitle =	{27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
  pages =	{28:1--28:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-308-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{286},
  editor =	{Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.28},
  URN =		{urn:nbn:de:0030-drops-195188},
  doi =		{10.4230/LIPIcs.OPODIS.2023.28},
  annote =	{Keywords: Look-Compute-Move, Oblivious mobile robots, Robots with lights, Memory versus Communication, Moving and Computing, Asynchrony}
}
Document
DOI: 10.4230/LIPIcs.SAND.2023.2
Partial Gathering of Mobile Agents in Dynamic Tori

Authors: Masahiro Shibata, Naoki Kitamura, Ryota Eguchi, Yuichi Sudo, Junya Nakamura, and Yonghwan Kim

Published in: LIPIcs, Volume 257, 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)

Abstract
In this paper, we consider the partial gathering problem of mobile agents in synchronous dynamic tori. The partial gathering problem is a generalization of the (well-investigated) total gathering problem, which requires that all k agents distributed in the network terminate at a non-predetermined single node. The partial gathering problem requires, for a given positive integer g (< k), that agents terminate in a configuration such that either at least g agents or no agent exists at each node. So far, in almost cases, the partial gathering problem has been considered in static graphs. As only one exception, it is considered in a kind of dynamic rings called 1-interval connected rings, that is, one of the links in the ring may be missing at each time step. In this paper, we consider partial gathering in another dynamic topology. Concretely, we consider it in n× n dynamic tori such that each of row rings and column rings is represented as a 1-interval connected ring. In such networks, when k = O(gn), focusing on the relationship between the values of k, n, and g, we aim to characterize the solvability of the partial gathering problem and analyze the move complexity of the proposed algorithms when the problem can be solved. First, we show that agents cannot solve the problem when k = o(gn), which means that Ω (gn) agents are necessary to solve the problem. Second, we show that the problem can be solved with the total number of O(gn³) moves when 2gn+2n-1 ≤ k ≤ 2gn + 6n +16g -12. Finally, we show that the problem can be solved with the total number of O(gn²) moves when k ≥ 2gn + 6n +16g -11. From these results, we show that our algorithms can solve the partial gathering problem in dynamic tori with the asymptotically optimal number Θ (gn) of agents. In addition, we show that agents require a total number of Ω(gn²) moves to solve the partial gathering problem in dynamic tori when k = Θ(gn). Thus, when k ≥ 2gn+6n+16g -11, our algorithm can solve the problem with asymptotically optimal number O(gn²) of agent moves.
Cite as

Masahiro Shibata, Naoki Kitamura, Ryota Eguchi, Yuichi Sudo, Junya Nakamura, and Yonghwan Kim. Partial Gathering of Mobile Agents in Dynamic Tori. In 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 257, pp. 2:1-2:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{shibata_et_al:LIPIcs.SAND.2023.2,
  author =	{Shibata, Masahiro and Kitamura, Naoki and Eguchi, Ryota and Sudo, Yuichi and Nakamura, Junya and Kim, Yonghwan},
  title =	{{Partial Gathering of Mobile Agents in Dynamic Tori}},
  booktitle =	{2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)},
  pages =	{2:1--2:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-275-4},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{257},
  editor =	{Doty, David and Spirakis, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2023.2},
  URN =		{urn:nbn:de:0030-drops-179387},
  doi =		{10.4230/LIPIcs.SAND.2023.2},
  annote =	{Keywords: distributed system, mobile agents, partial gathering, dynamic tori}
}
  • Refine by Type
  • 23 Document/PDF
  • 10 Document/HTML

  • Refine by Publication Year
  • 4 2026
  • 6 2025
  • 4 2024
  • 2 2023
  • 1 2022
  • Show More...

  • Refine by Author
  • 16 Sudo, Yuichi
  • 9 Masuzawa, Toshimitsu
  • 7 Eguchi, Ryota
  • 6 Shibata, Masahiro
  • 5 Kim, Yonghwan
  • Show More...

  • Refine by Series/Journal
  • 23 LIPIcs

  • Refine by Classification
  • 12 Theory of computation → Distributed algorithms
  • 6 Theory of computation → Self-organization
  • 2 Theory of computation → Dynamic graph algorithms
  • 1 Computing methodologies → Self-organization
  • 1 Theory of computation → Distributed computing models
  • Show More...

  • Refine by Keyword
  • 5 Population protocols
  • 5 mobile agents
  • 4 Loose-stabilization
  • 3 Leader election
  • 3 self-stabilization
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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