A set of identical, mobile agents is deployed in a weighted network. Each agent has a battery--a power source allowing it to move along network edges. An agent uses its battery proportionally to the distance traveled. We consider two tasks: convergecast, in which at the beginning, each agent has some initial piece of information, and information of all agents has to be collected by some agent; and broadcast in which information of one specified agent has to be made available to all other agents. In both tasks, the agents exchange the currently possessed information when they meet. The objective of this paper is to investigate what is the minimal value of power, initially available to all agents, so that convergecast or broadcast can be achieved. We study this question in the centralized and the distributed settings. In the centralized setting, there is a central monitor that schedules the moves of all agents. In the distributed setting every agent has to perform an algorithm being unaware of the network. In the centralized setting, we give a linear-time algorithm to compute the optimal battery power and the strategy using it, both for convergecast and for broadcast, when agents are on the line. We also show that finding the optimal battery power for convergecast or for broadcast is NP-hard for the class of trees. On the other hand, we give a polynomial algorithm that finds a 2-approximation for convergecast and a 4-approximation for broadcast, for arbitrary graphs.In the distributed setting, we give a 2-competitive algorithm for convergecast in trees and a 4-competitive algorithm for broadcast in trees. The competitive ratio of 2 is proved to be the best for the problem of convergecast, even if we only consider line networks. Indeed, we show that there is no ( @math 2-∈)-competitive algorithm for convergecast or for broadcast in the class of lines, for any @math ∈>0.
Assumptions similar to our paper have been made in @cite_19 @cite_0 @cite_29 where the mobile agents are constrained to travel a fixed distance to explore an unknown graph @cite_19 @cite_0 , or tree @cite_29 . In @cite_19 @cite_0 a mobile agent has to return to its home base to refuel (or recharge its battery) so that the same maximal distance may repeatedly be traversed. @cite_29 gives an 8-competitive distributed algorithm for a set of agents with the same amount of power exploring the tree starting at the same node.
@cite_0 @cite_19 @cite_29
2100580556 2137561762 1972775782 2128634904
Two mobile agents (robots) with distinct labels have to meet in an arbitrary, possibly infinite, unknown connected graph or in an unknown connected terrain in the plane. Agents are modeled as points, and the route of each of them only depends on its label and on the unknown environment. The actual walk of each agent also depends on an asynchronous adversary that may arbitrarily vary the speed of the agent, stop it, or even move it back and forth, as long as the walk of the agent in each segment of its route is continuous, does not leave it and covers all of it. Meeting in a graph means that both agents must be at the same time in some node or in some point inside an edge of the graph, while meeting in a terrain means that both agents must be at the same time in some point of the terrain. Does there exist a deterministic algorithm that allows any two agents to meet in any unknown environment in spite of this very powerful adversary? We give deterministic rendezvous algorithms for agents starting at arbitrary nodes of any anonymous connected graph (finite or infinite) and for agents starting at any interior points with rational coordinates in any closed region of the plane with path-connected interior. While our algorithms work in a very general setting - agents can, indeed, meet almost everywhere - we show that none of the above few limitations imposed on the environment can be removed. On the other hand, our algorithm also guarantees the following approximate rendezvous for agents starting at arbitrary interior points of a terrain as above: agents will eventually get at an arbitrarily small positive distance from each other. An n-node tree has to be explored by k mobile agents (robots), starting in its root. Every edge of the tree must be traversed by at least one robot, and exploration must be completed as fast as possible. Even when the tree is known in advance, scheduling optimal collective exploration turns out to be NP-hard. We investigate the problem of distributed collective exploration of unknown trees. Not surprisingly, communication between robots influences the time of exploration. Our main communication scenario is the following: robots can communicate by writing at the currently visited node previously acquired information, and reading information available at this node. We construct an exploration algorithm whose running time for any tree is only O(k log k) larger than optimal exploration time with full knowledge of the tree. (We say that the algorithm has overheadO(k log k)). On the other hand we show that, in order to get overhead sublinear in the number of robots, some communication is necessary. Indeed, we prove that if robots cannot communicate at all, then every distributed exploration algorithm works in time Ω (k) larger than optimal exploration time with full knowledge, for some trees. Two identical (anonymous) mobile agents start from arbitrary nodes in an a priori unknown graph and move synchronously from node to node with the goal of meeting. This rendezvous problem has been thoroughly studied, both for anonymous and for labeled agents, along with another basic task, that of exploring graphs by mobile agents. The rendezvous problem is known to be not easier than graph exploration. A well-known recent result on exploration, due to Reingold, states that deterministic exploration of arbitrary graphs can be performed in log-space, i.e., using an agent equipped with O(log n) bits of memory, where n is the size of the graph. In this paper we study the size of memory of mobile agents that permits us to solve the rendezvous problem deterministically. Our main result establishes the minimum size of the memory of anonymous agents that guarantees deterministic rendezvous when it is feasible. We show that this minimum size is Θ(log n), where n is the size of the graph, regardless of the delay between the starting times of the agents. More precisely, we construct identical agents equipped with Θ(log n) memory bits that solve the rendezvous problem in all graphs with at most n nodes, if they start with any delay τ, and we prove a matching lower bound Ω(log n) on the number of memory bits needed to accomplish rendezvous, even for simultaneous start. In fact, this lower bound is achieved already on the class of rings. This shows a significant contrast between rendezvous and exploration: e.g., while exploration of rings (without stopping) can be done using constant memory, rendezvous, even with simultaneous start, requires logarithmic memory. As a by-product of our techniques introduced to obtain log-space rendezvous we get the first algorithm to find a quotient graph of a given unlabeled graph in polynomial time, by means of a mobile agent moving around the graph. A team consisting of an unknown number of mobile agents, starting from different nodes of an unknown network, have to meet at the same node. Agents move in synchronous rounds. Each agent has a different label. Up to f of the agents are Byzantine. We consider two levels of Byzantine behavior. A strongly Byzantine agent can choose an arbitrary port when it moves and it can convey arbitrary information to other agents, while a weakly Byzantine agent can do the same, except changing its label. What is the minimum number of good agents that guarantees deterministic gathering of all of them, with terminationq We solve exactly this Byzantine gathering problem in arbitrary networks for weakly Byzantine agents and give approximate solutions for strongly Byzantine agents, both when the size of the network is known and when it is unknown. It turns out that both the strength versus the weakness of Byzantine behavior and the knowledge of network size significantly impact the results. For weakly Byzantine agents, we show that any number of good agents permits solving the problem for networks of known size. If the size is unknown, then this minimum number is fp2. More precisely, we show a deterministic polynomial algorithm that gathers all good agents in an arbitrary network, provided that there are at least fp2 of them. We also provide a matching lower bound: we prove that if the number of good agents is at most fp1, then they are not able to gather deterministically with termination in some networks. For strongly Byzantine agents, we give a lower bound of fp1, even when the graph is known: we show that f good agents cannot gather deterministically in the presence of f Byzantine agents even in a ring of known size. On the positive side, we give deterministic gathering algorithms for at least 2fp1 good agents when the size of the network is known and for at least 4fp2 good agents when it is unknown.