Most systems that support modern society, including the Internet, are distributed systems in which many autonomous devices, such as computers and robots, operate cooperatively. Our research focuses on the theoretical study of highly efficient and highly reliable distributed algorithms for a wide range of distributed systems, including computer networks, a swarm of mobile robots, blockchain systems, sensor networks, and nano-scale networks. In particular, we are interested in designing distributed algorithms that enable a system to continue operating correctly as a whole, even when some devices fail, stop functioning, or exhibit abnormal behavior due to malicious attacks such as cracking.
Many of the information systems that support modern society—such as the Internet, the Internet of Things (IoT), sensor networks, and systems where multiple robots cooperate—are distributed systems in which numerous computing entities (processes, agents, robots) work together through communication. In this laboratory, we study the theories and technologies required to realize distributed systems that users can rely on with confidence. In particular, our primary focus is the design and analysis of distributed algorithms where individual elements operate autonomously based only on limited local information to achieve sophisticated global functions.
The key point of research in distributed algorithms is to balance high efficiency with high reliability in environments where computational resources and communication capabilities are limited. In real-world, large-scale distributed systems, it is impossible to centrally manage all components, and each element operates at different timings. Furthermore, communication delays, computer failures, and even malicious attacks (Byzantine faults) can occur. Our major research challenges involve determining how to complete tasks with minimal time, cost, and memory under such uncertain environments, and how to achieve fault tolerance against severe failures.
Our specific research subjects are diverse. Regarding mobile robots and agents moving through physical space or networks, we deal with exploration by robots with limited visibility and gathering problems in environments containing malicious agents. In population protocols, which assume nanoscale molecular robots or networks of low-performance devices, we study methods for leader election and group partitioning using minimal memory. Furthermore, in the study of self-stabilizing algorithms—where a system autonomously returns to a normal state from any abnormal state—we investigate methods that are faster and more memory-efficient than conventional ones, as well as implementation methods for "Loose-stabilization," a new concept of stability.
Most of our research is supported by theoretically proving the correctness and complexity (time, space, number of moves, etc.) of algorithms using abstract theoretical models of distributed systems. By clarifying theoretical limits (lower bounds) and constructing optimal or semi-optimal algorithms that challenge those limits, we are building various fundamental theories that serve as the foundation for distributed systems.