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

Stéphane Devismes, Yoann Dieudonné, Arnaud Labourel · 2025

Read Can Like Attract Like? A Study of Homonymous Gathering in Networks by Stéphane Devismes, Yoann Dieudonné, Arnaud Labourel (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-25451.txt.

Introduction

Stephane Devismes, Yoann Dieudonne, and Arnaud Labourel study agent gathering. Their 2025 paper asks whether identical labels can gather. Mobile agents start from distinct network nodes. They must meet at one node and declare success. Agents run the same method when activated. Activation comes from an adversary or visiting agent. Perception and contact are strictly local here.

The gathering task is central in distributed systems. Prior work mostly minimized time hardness of gathering. Deterministic answers usually assume pairwise distinct agent labels. Labels are known only to the agents themselves. The authors consider agents sharing the same label. A team is gatherable if some method always succeeds. They give a full characterization of gatherable teams. Their method gathers all such teams quickly. Time is polynomial in graph order and label size. Little common knowledge is needed initially. They show that dependency is almost optimal. Termination finding techniques may interest other scholars.

Catalog record

CREATORStéphane Devismes, Yoann Dieudonné, Arnaud Labourel
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE159 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-25451

Browse the full library · About the Tower of Babel