Distributed systems, which are composed of multiple computers (nodes) that can communicate with each other, have become larger in scale recently. This makes it complicated to design distributed systems. In order to address this challenge, we focus on (mobile) agents as a design method for distributed systems. Agents are software programs that can autonomously move and execute various tasks in distributed systems and they can take charge of communication on the network. However, agents and nodes may be modified to perform malicious behaviors due to cracking. We call a fault that behaves maliciously a Byzantine fault. To counter this Byzantine fault, we consider fault-tolerant algorithms for agents to construct highly reliable distributed systems.
In this presentation, we focus on agents with faults. We call an agent that has a Byzantine fault a Byzantine agent, and we consider a gathering problem with Byzantine agents. The gathering problem is a problem of collecting correct agents into one node. By gathering, it is possible to exchange information directly among agents and facilitate cooperative operations. We porpose three algorithms to solve gathering problem in various environments.
Second, we consider that nodes and agents have faults. We solve a black hole search problem with Byzantine agents. This is a problem to detect a failed node by correct agents. By detecting the failed node, it becomes easier to operate other agent algorithms. We propose an algorithm to solve Black hole search problem and we show that our algorithm is optimal in terms of the number of tolerable faulty agents.
Third, we consider an algorithm that solves the maximal distance-$k$ independent set problem as a clustering algorithm. This is because, if the number of nodes increases, the number of movements of agents also increases. So, we can reduce the number of nodes that the agent needs to move by moving on only the representative nodes of clusters. We aim to realize a self-stabilizing algorithm that solve maximal distance-$k$ independent set problem. Then, we propose an algrithm that satisfies the closure property among the properties that the self-stabilizing algorithm should satisfy.
We consider that these our algorithms will make it easy to construct highly reliable distributed systems. In this presentation, we introduce each algorithm.