Search

This paper investigates an open problem introduced in Dieudonné et al. (ACM Trans Algorithms 11(1):1, 2014). Two or more mobile agents start from nodes of a network and have to accomplish the task of gathering which consists in getting all together at the same node at the same time. An adversary chooses the initial nodes of the agents and assigns a different positive integer (called label) to each of them. Initially, each agent knows its label but does not know the labels of the other agents or their positions relative to its own. Agents move in synchronous rounds and can communicate with each other only when located at the same node. Up to f of the agents are Byzantine. A Byzantine agent can choose an arbitrary port when it moves, can convey arbitrary information to other agents and can change its label in every round, in particular by forging the label of another agent or by creating a completely new one. What is the minimum number $${\mathcal {M}}$$ of good agents that guarantees deterministic gathering of all of them, with termination? We provide exact answers to this open problem by considering the case when the agents initially know the size of the network and the case when they do not. In the former case, we prove $${\mathcal {M}}=f+1$$ while in the latter, we prove $${\mathcal {M}}=f+2$$ . More precisely, for networks of known size, we design a deterministic algorithm gathering all good agents in any network provided that the number of good agents is at least $$f+1$$ . For networks of unknown size, we also design a deterministic algorithm ensuring the gathering of all good agents in any network but provided that the number of good agents is at least $$f+2$$ . Both of our algorithms are optimal in terms of required number of good agents, as each of them perfectly matches the respective lower bound on $${\mathcal {M}}$$ shown in Dieudonné et al. (2014), which is of $$f+1$$ when the size of the network is known and of $$f+2$$ when it is unknown. Perhaps surprisingly, our results highlight an interesting feature when put in perspective with known results concerning a relaxed variant of this problem in which the Byzantine agents cannot change their initial labels. Indeed under this variant $${\mathcal {M}}=1$$ for networks of known size and $${\mathcal {M}}=f+2$$ for networks of unknown size. Following this perspective, it turns out that when the size of the network is known, the ability for the Byzantine agents to change their labels significantly impacts the value of $${\mathcal {M}}$$ . However, the relevance for $${\mathcal {M}}$$ of such an ability completely disappears in the most general case where the size of the network is unknown, as $${\mathcal {M}}=f+2$$ regardless of whether Byzantine agents can change their labels or not. [ABSTRACT FROM AUTHOR]

Two mobile agents, starting from different nodes of a network at possibly different times, have to meet at the same node. This problem is known as rendezvous. Agents move in synchronous rounds. Each agent has a distinct integer label from the set $$\{1,\ldots ,L\}$$ . Two main efficiency measures of rendezvous are its time (the number of rounds until the meeting) and its cost (the total number of edge traversals). We investigate tradeoffs between these two measures. A natural benchmark for both time and cost of rendezvous in a network is the number of edge traversals needed for visiting all nodes of the network, called the exploration time. Hence we express the time and cost of rendezvous as functions of an upper bound E on the time of exploration (where E and a corresponding exploration procedure are known to both agents) and of the size L of the label space. We present two natural rendezvous algorithms. Algorithm Cheap has cost O( E) (and, in fact, a version of this algorithm for the model where the agents start simultaneously has cost exactly E) and time O( EL). Algorithm Fast has both time and cost $$O(E\log L)$$ . Our main contributions are lower bounds showing that, perhaps surprisingly, these two algorithms capture the tradeoffs between time and cost of rendezvous almost tightly. We show that any deterministic rendezvous algorithm of cost asymptotically E (i.e., of cost $$E+o(E)$$ ) must have time $$\varOmega (EL)$$ . On the other hand, we show that any deterministic rendezvous algorithm with time complexity $$O(E\log L)$$ must have cost $$\varOmega (E\log L)$$ . [ABSTRACT FROM AUTHOR]

Two mobile agents with range of vision 1 start at arbitrary points in the plane and have to accomplish the task of approach, which consists in getting at distance at most one from each other, i.e., in getting within each other's range of vision. An adversary chooses the initial positions of the agents, their possibly different starting times, and assigns a different positive integer label and a possibly different speed to each of them. Each agent is equipped with a compass showing the cardinal directions, with a measure of length and a clock. Each agent knows its label and speed but not those of the other agent and it does not know the initial position of the other agent relative to its own. Agents do not have any global system of coordinates and they cannot communicate. Our main result is a deterministic algorithm to accomplish the task of approach, working in time polynomial in the unknown initial distance between the agents, in the length of the smaller label and in the inverse of the larger speed. The distance travelled by each agent until approach is polynomial in the first two parameters and does not depend on the third. The problem of approach in the plane reduces to a network problem: that of rendezvous in an infinite grid. [ABSTRACT FROM AUTHOR]

Suppose we want to patrol a fence (line segment) using $$k$$ mobile agents with given speeds $$v _1$$ , ..., $$v _k$$ so that every point on the fence is visited by an agent at least once in every unit time period. Czyzowicz et al. conjectured that the maximum length of the fence that can be patrolled is $$(v _1 + \cdots + v _k)/2$$ , which is achieved by the simple strategy where each agent $$i$$ moves back and forth in a segment of length $$v _i / 2$$ . We disprove this conjecture by a counterexample involving $$k = 6$$ agents. We also show that the conjecture is true for $$k \le 3$$ . [ABSTRACT FROM AUTHOR]

Two identical (anonymous) mobile agents start from arbitrary nodes of an unknown tree and have to meet at some node. Agents move in synchronous rounds: in each round an agent can either stay at the current node or move to one of its neighbors. We consider deterministic algorithms for this rendezvous task. The main result of this paper is a tight trade-off between the optimal time of completing rendezvous and the size of memory of the agents. For agents with $$k$$ memory bits, we show that optimal rendezvous time is $$\Theta (n+n^2/k)$$ in $$n$$ -node trees. More precisely, if $$k \ge c\log n$$ , for some constant $$c$$ , we design agents accomplishing rendezvous in arbitrary trees of size $$n$$ (unknown to the agents) in time $$O(n+n^2/k)$$ , starting with arbitrary delay. We also show that no pair of agents can accomplish rendezvous in time $$o(n+n^2/k)$$ , even in the class of lines of known length and even with simultaneous start. Finally, we prove that at least logarithmic memory is necessary for rendezvous, even for agents starting simultaneously in a $$n$$ -node line. [ABSTRACT FROM AUTHOR]

We consider the problem of leader election among mobile agents operating in an arbitrary network modeled as an undirected graph. Nodes of the network are unlabeled and all agents are identical. Hence the only way to elect a leader among agents is by exploiting asymmetries in their initial positions in the graph. Agents do not know the graph or their positions in it, hence they must gain this knowledge by navigating in the graph and share it with other agents to accomplish leader election. This can be done using meetings of agents, which is difficult because of their asynchronous nature: an adversary has total control over the speed of agents. When can a leader be elected in this adversarial scenario and how to do it? We give a complete answer to this question by characterizing all initial configurations for which leader election is possible and by constructing an algorithm that accomplishes leader election for all configurations for which this can be done. [ABSTRACT FROM AUTHOR]

Chatzigiannakis et al. (Lect Notes Comput Sci 5734:56-76, ) extended the Population Protocol (PP) of Angluin et al. (2004) and introduced the Mediated Population Protocol (MPP) by introducing an extra memory on every agent-to-agent communication link (i.e., edge), in order to model more powerful networks of mobile agents with limited resources. For a general distributed system of autonomous agents, Leader Election (LE) plays a key role in their efficient coordination. A Self-Stabilizing (SS) protocol has ideal properties required for distributed systems of huge numbers of not highly reliable agents typically modeled by PP or MPP; it does not require any initialization and tolerates a finite number of transient failures. Cai et al. (2009) showed that for a system of $$n$$ agents, any PP for SS-LE requires at least $$n$$ agent-states, and gave a PP with $$n$$ agent-states for SS-LE. In this paper, we show, for a system of $$n$$ agents, any MPP for SS-LE with 2 edge-states (i.e., 1 bit memory) on every edge requires at least $$(1/2) \lg {n}$$ agent-states, and give an MPP for SS-LE with $$(2/3)n$$ agent-states and 2 edge-states on every edge. Furthermore, we show that a constant number of edge-states on every edge do not help in designing an MPP for SS-LE with a constant number of agent-states, and that there is no MPP for SS-LE with 2 agent-states, regardless of the number of edge-states; the edge-state is not a complete alternative of the agent-state, although it can help in reducing the number of agent-states, when solving SS-LE. [ABSTRACT FROM AUTHOR]

Consider a networked environment, supporting mobile agents, where there is a black hole: a harmful host that disposes of visiting agents upon their arrival, leaving no observable trace of such a destruction. The black hole search problem is the one of assembling a team of asynchronous mobile agents, executing the same protocol and communicating by means of whiteboards, to successfully identify the location of the black hole; we are concerned with solutions that are generic (i.e., topology-independent). We establish tight bounds on the size of the team (i.e., the number of agents), and the cost (i.e., the number of moves) of a size-optimal solution protocol. These bounds depend on the a priori knowledge the agents have about the network, and on the consistency of the local labelings. In particular, we prove that: with topological ignorance Δ+1 agents are needed and suffice, and the cost is Θ( n 2), where Δ is the maximal degree of a node and n is the number of nodes in the network; with topological ignorance but in presence of sense of direction only two agents suffice and the cost is Θ( n 2); and with complete topological knowledge only two agents suffice and the cost is Θ( n log n). All the upper-bound proofs are constructive. [ABSTRACT FROM AUTHOR]