Distributed Algorithms

In Dependable System Laboratory, we study algorithms for distributed systems. Distributed systems are composed of many computing entities (such as computers and processes) and communication capabilities among them (See Fig. 1). For example, the Internet, which contains approximately a thousand million computers, can be regarded as one large-scale distributed system.

Fig. 1: An example of distributed systems

Fig. 1: An example of distributed systems

In large-scale distributed systems, it is impossible to manage all processes in the centralized manner. Hence, we have to design distributed algorithms that specify the behavior of each process that operates autonomously. The aim of distributed algorithms is to make multiple processes cooperate efficiently. In our laboratory, we develop efficient distributed algorithms for many types of distributed systems.

However, designing distributed algorithms is challenging. Each process cannot obtain global information of all processes because the distributed system usually contains huge number of processes. Consequently, each process should operate based on only local information such as states of nearby processes. In addition, processing speeds and communication speeds are different for processes, and even worse they may change depnding on load of processes and communication links. This means processes in distributed systems are asynchronous. Therefore, we must develop distributed algorithms that work correctly based on local information for any execution speed of each process and communication link. To propose such algorithms, we usually consider “What approach solves our problem?” and “What situation is the worst for our developed algorithm?”. Although it is difficult to develop an algorithm and prove its correctness, we can get a great sense of achievement when we solve the problem.