Japanese

# 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. Fig. 11: A nano-scale distributed system.

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. Fig. 12: The population protocol model.

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. 