Search

Two mobile agents starting at different nodes of an unknown network have to meet. This task is known in the literature as rendezvous. Each agent has a different label which is a positive integer known to it but unknown to the other agent. Agents move in an asynchronous way: the speed of agents may vary and is controlled by an adversary. The cost of a rendezvous algorithm is the total number of edge traversals by both agents until their meeting. The only previous deterministic algorithm solving this problem has cost exponential in the size of the graph and in the larger label. In this paper we present a deterministic rendezvous algorithm with cost polynomial in the size of the graph and in the length of the smaller label. Hence, we decrease the cost exponentially in the size of the graph and doubly exponentially in the labels of agents. As an application of our rendezvous algorithm we solve several fundamental problems involving teams of unknown size larger than 1 of labeled agents moving asynchronously in unknown networks. Among them are the following problems: team size, in which every agent has to find the total number of agents; leader election, in which all agents have to output the label of a single agent; perfect renaming, in which all agents have to adopt new and different labels from the set {1,...,k}, where k is the number of agents; and gossiping, in which each agent has initially a piece of information (value) and all agents have to output all the values. Using our rendezvous algorithm, we solve all of these problems at cost polynomial in the size of the graph and in the smallest length of all labels of participating agents. [ABSTRACT FROM AUTHOR]

Abstract: We consider a fixed, undirected, known network and a number of “mobile agents” which can traverse the network in synchronised steps. Some nodes in the network may be faulty and the agents are to find the faults and repair them. The agents could be software agents, if the underlying network represents a computer network, or robots, if the underlying network represents some potentially hazardous physical terrain. Assuming that the first agent encountering a faulty node can immediately repair it, it is easy to see that the number of steps necessary and sufficient to complete this task is , where is the number of nodes in the network, is the diameter of the network, and is the number of agents. We consider the case where one agent can repair only one faulty node. After repairing the fault, the agent dies. We show that a simple deterministic algorithm for this problem terminates within steps, where , assuming that the number of faulty nodes is at most . We also demonstrate the worst-case asymptotic optimality of this algorithm by showing a network such that for any deterministic algorithm, there is a placement of faults forcing the algorithm to work for steps. [Copyright &y& Elsevier]

We have been proposing the automatic human tracking system to overcome limitations of existing video surveillance systems. This paper proposes two bypass methods to keep tracking a targeted person by the system constructed by using mobile agent technologies even if unexpected problems are occurred. The proposed methods are called as "Recalculation Bypass Method" and "Additional Calculation Bypass Method". These bypass methods utilize the algorithm which is elaborated in the paper, "An Algorithm to Determine Neighbor Nodes" [7]. The mobile agents are operating in automatic human tracking system and the bypass methods are utilized by the mobile agents. It is a very important ability for the mobile agent not to lose tracking in automatic human tracking systems. The bypass methods contribute to the realization of robust system and resolve two classifications of problem to ensure the tracking ability of mobile agents. The two classifications of problem are logical and physical problems. In the case of logical problems, they occur inside the system and they are called as "broken server". While in the case of physical problems, they occur outside the system and they are called as "pathway being modified". This system is able to track the targeted person continuously by utilizing the methods even if unexpected problems are occurred. We confirmed the effectiveness of the proposed bypass methods by the experiments that used more than one broken servers and pathway being modified. [ABSTRACT FROM AUTHOR]

A black hole is a highly harmful stationary process residing in a node of a network and destroying all mobile agents visiting the node without leaving any trace. The Black Hole Search is the task of locating all black holes in a network by exploring it with mobile agents. We consider the problem of designing the fastest Black Hole Search, given the map of the network and the starting node. We study the version of this problem that assumes that there is at most one black hole in the network and there are two agents, which move in synchronized steps. We prove that this problem is NP-hard in arbitrary graphs (even in planar graphs), solving an open problem stated in [J. Czyzowicz, D. Kowalski, E. Markou, A. Pelc, Searching for a black hole in tree networks, in: Proc. 8th Int. Conf. on Principles of Distributed Systems, OPODIS 2004, 2004, pp. 34–35. Also: Springer LNCS, vol. 3544, pp. 67–80]. We also give a -approximation algorithm, showing the first non-trivial approximation ratio upper bound for this problem. Our algorithm follows a natural approach of exploring networks via spanning trees. We prove that this approach cannot lead to an approximation ratio bound better than 3/2. [Copyright &y& Elsevier]

In this paper we consider a network where an intruder is moving "contaminating" the nodes it passes by, and we focus on the problem of decontaminating such a network by a team of mobile agents. The contamination/decontamination process has the following asynchronous dynamics: when the team is deployed all nodes are assumed to be contaminated, when an agent transits on a node, it will clean the node, when the node is left with no agent, the node will be recontaminated as soon as at least one of its neighbours is contaminated. We study the problem in asynchronous chordal ring networks and in tori. We consider two variations of the model: one where agents have only local knowledge, the other in which they have "visibility", i.e., they can "see" the state of their neighbouring nodes. We first derive lower bounds on the minimum number of agents necessary for the decontamination. In the case of chordal rings we show that the number of agents necessary to perform the cleaning does not depend on the size of the network; in fact it is linear in the length of the longest chord (provided that it is not too long). In the case of a torus, the minimum number of agents is equal to 2 · h, where h is the smallest dimension. We then propose optimal strategies for decontamination and we analyse the number of moves and the time complexity of the decontamination algorithms, showing that the visibility assumption allows us to decrease substantially both complexity measures. Another advantage of the "visibility model" is that agents move independently and autonomously without requiring any coordination. [ABSTRACT FROM AUTHOR]

Abstract: A wide range of algorithms have been developed for various types of negotiating agents. In developing such algorithms the main focus has been on their efficiency and their effectiveness. However, this is only a part of the picture. Typically, agents negotiate on behalf of their owners and for this to be effective the agents must be able to adequately represent their owners’ strategies and preferences for negotiation. However, the process by which such knowledge is acquired is typically left unspecified. To address this problem, we undertook a study of how user information about negotiation tradeoff strategies and preferences can be captured. Specifically, we devised a novel default-then-adjust acquisition technique. In this, the system firstly does a structured interview with the user to suggest the attributes that the tradeoff could be made between, then it asks the user to adjust the suggested default tradeoff strategy by improving some attribute to see how much worse the attribute being traded off can be made while still being acceptable, and, finally, it asks the user to adjust the default preference on the tradeoff alternatives. This method is consistent with the principles of standard negotiation theory and to demonstrate its effectiveness we implemented a prototype system and performed an empirical evaluation in an accommodation renting scenario. The result of this evaluation indicates the proposed technique is helpful and efficient in accurately acquiring the users’ tradeoff strategies and preferences. [Copyright &y& Elsevier]

Mobile agent technology has been applied to develop the solutions for various kinds of parallel and distributed computing problems. However, performance evaluation of mobile agent algorithms remains a difficult task, mainly due to the characteristics of mobile agents such as distributed and asynchronous execution, autonomy and mobility. This paper proposes a general approach based on direct execution simulation for evaluating the performance of mobile agent algorithms by collecting and analyzing the information about the agents during their execution. We describe the proposed generic simulation model, named MADES, the architecture of a software environment based on MADES, and a prototype implementation. A mobile agent-based distributed load balancing algorithm has been used for experiments with the prototype. [ABSTRACT FROM AUTHOR]