Can Like Attract Like? A Study of Homonymous Gathering in Networks

A team of mobile agents, starting from distinct nodes of a network modeled as an undirected graph, have to meet at the same node and simultaneously declare that they all met. Agents execute the same algorithm, which they start when activated by an adversary or when an agent enter their initial node. While executing their algorithm, agents move from node to node by traversing edges of the network in synchronous rounds. Their perceptions and interactions are always strictly local: they have no visibility beyond their current node and can communicate only with agents occupying the same node. This task, known as gathering, is one of the most fundamental problems in distributed mobile systems. Over the past decades, numerous gathering algorithms have been designed, with a particular focus on minimizing their time complexity, i.e., the worst-case number of rounds between the start of the earliest agent and the completion of the task. To solve gathering deterministically, a common widespread assumption is that each agent initially has an integer ID, called label, only known to itself and that is distinct from those of all other agents. Labels play a crucial role in breaking possible symmetries, which, when left unresolved, may make gathering impossible. But must all labels be pairwise distinct to guarantee deterministic gathering?

In this paper, we conduct a deep investigation of this question by considering a context in which each agent applies a deterministic algorithm and has a label that may be shared with one or more other agents called homonyms. A team L of mobile agents, represented as the multiset of its labels, is said to be gatherable if, for every possible initial setting of L, there exists an algorithm, even dedicated to that setting, that solves gathering. Our contribution is threefold. First, we give a full characterization of the gatherable teams. Second, we design an algorithm that gathers all of them in poly(n, log λ) time, where n (resp. λ) is the order of the graph (resp. the smallest label in the team). This algorithm requires the agents to initially share only O(log log log µ) bits of common knowledge, where µ is the multiplicity index of the team, i.e., the largest label multiplicity in L. Lastly, we show this dependency is almost optimal in the precise sense that no algorithm can gather every gatherable team in poly(n, log λ) time, with initially o(log log log µ) bits of common knowledge.

As a by-product, we get the first deterministic poly(n, log λ)-time algorithm that requires no common knowledge to gather any team in the classical case where all agent labels are pairwise distinct. While this was known to be achievable for teams of exactly two agents, extending it to teams of arbitrary size-under the same time and knowledge constraints-faced a major obstacle inherently absent in the two-agent scenario: that of termination detection. The synchronization techniques that enable us to overcome this obstacle may be of independent interest, as termination detection is a key issue in distributed systems.