Nano-scale Distributed Algorithms

With the development of nanotechnologies, nano-scale or molecular-scale distributed systems will be developped (Fig. 11). Actually, sensors, actuators, and operation circuits have been realized by DNAs, and molecular robots composed of the nano devices are in development. Such molecular robots will construct a network in our body. By using the network, we will collect information of our body or deliver a specific medicine directly to a cancer cell.

In nano-scale distributed systems, each device is very weak and so we cannot assume correct computation, reliable communication, or a large amount of memory that are common in computer networks. This means we cannot use distributed algorithms for computer networks in nano-scale distributed systems. So we are developping algorithms for very weak nano-scale devices.

Algorithms for population protocol models

Toward nano-scale distributed systems, we are developing algorithms for population protocol (PP) models. As in Fig. 12, the PP model represents a system such that multiple agents are passively moved. When two agents come sufficiently close, they make an interaction and change their states. For example, the PP model can represent molecules that float in liquid solutions and change their states at the time of collision. We aim to clarify which function we can realize in such simple systems.

Let us consider a simple example. In the initial configuration, every agent is in a red state (we simply say every agent is red). From this initial configuration, we want to make exactly one agent remain red and all other agents become blue. In this case, the solution is very simple. We can achieve the task by a simple algorithm: If two red agents make an interaction, one of them becomes blue. As in Fig. 11, after repeating interactions, eventually exactly one agent remains red. This task is well-known as a leader election problem, which elects a single leader (i.e., a single red agent) from all agents. The leader election problem is a fundamental task of the population protocol model and leader election algorithms are used as building blocks of many other algorithms.

Now we consider more practical setting. In the above example, we assumed every agent is red in the initial configuration. However, in nano-scale distributed systems, such initialization is usually difficult. In addition, agents in nano-scale distributed systems are not stable because they are easily affected by environmental noises. By such noises, agents may change their states arbitrarily or even worse may be corrupted. For example, some blue agent may accidentally become red and hence multiple leaders appear, or the single leader may accidentally disappear and hence leaders disappear. So, it is desirable that one leader is automatically elected again even in this case. Does the previous algorithm satisfy this property? In the case that multiple red agents appear, they can reduce the number of red agents to one by repeating interactions between them. How about the case that red agents disappear? Since the algorithm does not make red agents, red agents never appear.

So we should design an algorithm that can make red agents. However, as a matter of fact, this is very difficult. It is proven that, to elect a single leader from any initial configuration and keep it forever, each agent must know the exact number of agents in the system. As described above, agents in nano-scale distributed systems can be corrupted. This means it is almost impossible to know the exact number of agents in practice. For this reason, in our research group, we consider a relaxed version of this problem. In the following paper, we proposed an algorithm that can elect a single leader quickly from any initial configuration and keep it for a sufficiently long time.