10 papers · 1 filter
Asynchronous Gathering Algorithms for Autonomous Mobile Robots with Lights
R. Nakai, Y. Sudo, K. Wada
We consider a Gathering problem for n autonomous mobile robots with persistent memory called light in an asynchronous scheduler (ASYNC). It is well known that Gathering is impossib…
Smoothed Analysis of Population Protocols
Gregory Schwartzman, Yuichi Sudo
In this work, we initiate the study of \emph{smoothed analysis} of population protocols. We consider a population protocol model where an adaptive adversary dictates the interactio…
Self-Stabilizing Construction of a Minimal Weakly -Reachable Directed Acyclic Graph
Junya Nakamura, Masahiro Shibata, Yuichi Sudo +1
We propose a self-stabilizing algorithm to construct a minimal weakly -reachable directed acyclic graph (DAG), which is suited for routing messages on wireless networ…
Efficient Dispersion of Mobile Agents without Global Knowledge
Takahiro Shintaku, Yuichi Sudo, Hirotsugu Kakugawa +1
We consider the dispersion problem for mobile agents. Initially, k agents are located at arbitrary nodes in an undirected graph. Agents can migrate from node to node via an edge in…
Time-optimal Loosely-stabilizing Leader Election in Population Protocols
Yuichi Sudo, Ryota Eguchi, Taisuke Izumi +1
We consider the leader election problem in population protocol models. In pragmatic settings of population protocols, self-stabilization is a highly desired feature owing to its fa…
The Power of Global Knowledge on Self-stabilizing Population Protocols
Yuichi Sudo, Masahiro Shibata, Junya Nakamura +2
In the population protocol model, many problems cannot be solved in a self-stabilizing way. However, global knowledge, such as the number of nodes in a network, sometimes allows us…