Showing 2019Show all
3 papers · 1 filter
cs.DC2019
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…
cs.DC2019
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…
cs.DC2019
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…