When we design a distributed algorithm, the algorithm usually guarantees a correct result only when it is started from an ideal condition (e.g., the condition where all nodes are initialized or that where all nodes know the network topology). In the real system, the algorithm rarely starts from these ideal conditions due to the participation and defection of nodes, continually-changing network topology, or the crash of some nodes.
The self-stabilizing algorithm is an distributed algorithm that guarantees a correct result even if it starts from any conditions. From this property, the self-stabilizing algorithm tolerate network changes described above without any human intervention. Therefore, it is self-adaptive and fault-tolerance.
Up to now, a lot of self-stabilizing algorithms are concidered for some basic demands in the distributed system. For example, constructing a spanning tree, token circulation problem and dining philosophers problem are made to be self-stabilizing. We also study the algorithm which is adaptable for specific failure of a node or change of the network topology. We present a self-stabilizing algorithm which works even if a malicious user, which resides in a node, lets the system destroyed. We present another type of algorithm. In this algorithm, when a failure is ocurred in a system, the influence of that failure is localized as much as possible.
Mobile Agent Algorithm
A user wants to work in a distributed system, he needs to communicate with a lot of computers in the system. As the system becomes larger and larger, he becomes more strained to communicate with computers. In order to reduce his strain, the system using mobile agents is designed. Mobile agent is a software which, as a delegate of a user, outputs the result for a user's request. It can autonomously compute at each node and can move to the neighboring node in the network.
We study the algorithm of the agent to exercise autonomia and cooperativeness of each agent. We present the way to maintain an adequate number of agents in the system (mobile agent population control problem). We also study how each agent can exchange its information with all the agents in the system (mobile agent gossip problem).
Algorithm for Sensor Network
Sensor network is the distributed system which consists of a lot of small nodes (sensor nodes). A sensor node has computational circuits, radio communication circuits, and the battery. Each sensor node wirelessly communicates with other one and gets sensing results in a coordinated way. Such sensor network is useful for the automated control of air conditioning or lighting in the building or biology observation in the nature.
Sensor network has the new characters compared with the traditional distributed system. Computation capacity and the battery equipped on it is limited and the network is consist of enormous numbers of nodes. We present where to set each sensor node to cover the observation area and experiment by implementing theoretical distributed algorithms in a real sensor network.