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]