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.
Mobile agents have the following advantages.
Reduce communication overhead: When agents process a huge amount of data, they move to the place with the data instead of communicating the data. Since the size of agents (including the program and the internal memory) is smaller than the size of processed data, such a behavior of agents reduces the communication overhead. This is a big advantage because the size of processed data continues increasing recently.
Improve system dependability: Since agents can decide its movement by themselfves, they can change the movement depending on the network configuration. For example, when an agent completes tasks in its current node and wants to move to the next node, it changes the next node if the node is faulty or heavy-loaded. In addition, even if the connection to the system disappears transiently, the agent can wait in its current node until the connection recovers again. As described above, agents can behave adaptably to the network configuration and improve the system dependability.
Simplify system design: Many basic behaviors (such as exploration of the network) of agents are realized by a system library for agents. Thus users can easily write a program of agents. For example, let us consider the case that we program agents that search some information from the network. Then, the exploration of the network is realized by a system library. So we can program such agents by programing a function that searches the information in each visited node.
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.
Gathering: Mobile agents gather at a single node. By gatherig, agents can share information or tasks among them.
Exploration: Mobile agents visit every node in the network. By exploring the network, agents can collect information from the whole network.
Uniform deployment: Mobile agents are deployed uniformly in the network. For example, if agents with database replicas are deployed uniformly, each node can quickly access the database.
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 gethering 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. 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. 10).
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.