7 papers
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…
A Self-Stabilizing Minimal k-Grouping Algorithm
Ajoy K. Datta, Lawrence L. Larmore, Toshimitsu Masuzawa +1
We consider the minimal k-grouping problem: given a graph G=(V,E) and a constant k, partition G into subgraphs of diameter no greater than k, such that the union of any two subgrap…
Leader Election Requires Logarithmic Time in Population Protocols
Yuichi Sudo, Toshimitsu Masuzawa
This paper shows that every leader election protocol requires logarithmic stabilization time both in expectation and with high probability in the population protocol model. This lo…
Atomic Cross-Chain Swaps with Improved Space and Local Time Complexity
Soichiro Imoto, Yuichi Sudo, Hirotsugu Kakugawa +1
An effective atomic cross-chain swap protocol is introduced by Herlihy [Herlihy, 2018] as a distributed coordination protocol in order to exchange assets across multiple blockchain…