Japanese

Mobile Agents

Mobile agents are software programs that can move autonomously from a node to a node in a distributed system. In mobile agent systems, agents execute tasks while moving around in the system. As an example, Fig. 8 shows an electronic commerce system with mobile agents. In the system, agents with budget and a shopping list move around the system to efficiently buy the products. To realize tasks more efficiently, agents often cooperate with other agents.

Fig. 8: An example of mobile agent systems.

Fig. 8: An example of mobile agent systems.

Mobile agents have the following advantages.

In Dependable System Laboratory, we develop algorithms to efficiently operate mobile agents. Such algorithms can be used in a system library. For example, we develop algorithms to realize the following functions.

However, it is not easy to design algorithms for mobile agents. Agents do not get information of other agents immediately, and so in the initial configuration they do not know where other agents exist. From such a configuration, agents must move in the network and achieve the goal.

A gathering algorithm tolerant to Byzantine agents

We briefly explain the recent result of our laboratory, gathering algorithms tolerant to Byzantine agents.

Fig. 9: Byzantine environments

Fig. 9: Byzantine environments

Fig. 10: Gathering in Byzantine environments

Fig. 10: Gathering in Byzantine environments

In large-scale distributed systems, some agents may become faulty (Fig. 9). In this work, we proposed an algorithm that can achieve gathering even when agents with Byzantine faults exist. We refer to such agents as Byzantine agents. Byzantine agents do not obey an algorithm and behave arbitrarily. That is, they can stop, move randomly, or behave in a malicious way. For example, Byzantine agents may inform agents of different gathering nodes. We can model agents controlled by crackers or corruptted by software errors as Byzantine agents. We consider algorithms that make correct agents meet at a single node even when some Byzantine agents exist (Fig. 17).

In the following paper, we propose an algorithm that achieves gathering in O(fm) time under the assumption that agents can use an authenticated whiteboard on each node, where f is the upper bound of the number of Byzantine agents and m is the number of edges. We omit the definition of an authenticated whiteboard here. The previous algorithm achieves gathering in about O(n9) time without an authenticated whiteboard. So, our algorithm shows an authenticated whiteboard can significantly reduce the time to achieve gathering in Byzantine environments.

Masashi Tsuchida, Fukuhito Ooshita, and Michiko Inoue, Byzantine gathering in networks with authenticated whiteboards, Proceedings of the 11th International Workshop on Algorithms and Computation (WALCOM), Mar. 2017.