4 papers
Almost Time-Optimal Loosely-Stabilizing Leader Election on Arbitrary Graphs Without Identifiers in Population Protocols
Haruki Kanaya, Ryota Eguchi, Taisho Sasada +1
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 communicatio…
Time- and Space-Optimal Silent Self-Stabilizing Exact Majority in Population Protocols
Haruki Kanaya, Ryota Eguchi, Taisho Sasada +2
We address the self-stabilizing exact majority problem in the population protocol model, introduced by Angluin, Aspnes, Diamadi, Fischer, and Peralta (2004). In this model, there a…
Recolorable Graph Exploration by an Oblivious Agent with Fewer Colors
Shota Takahashi, Haruki Kanaya, Shoma Hiraoka +2
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 o…
Complete Graph Identification in Population Protocols
Haruki Kanaya, Yuichi Sudo
We consider the population protocol model where indistinguishable state machines, referred to as agents, communicate in pairs. The communication graph specifies potential interacti…