Das and Pelc prove single movable pebble enables universal rendezvous on trees

Das and Pelc's new paper tackles the classic rendezvous problem: two identical mobile agents (modeled as deterministic finite automata) start at unknown, adversarially chosen nodes in an unlabeled graph and must meet. Agents operate in synchronous rounds and may begin in different rounds. The authors ask whether a single "universal" automaton can guarantee rendezvous for an entire class of graphs, regardless of the starting positions or the delay between agent activations.

Their results are sharply contrasting. First, they show that without any ability to mark nodes, no universal DFA exists—even for simple line graphs. If agents may drop stationary pebbles (which cannot be picked up), universality still fails for trees, regardless of how many pebbles are available. However, the picture changes dramatically when pebbles are movable: the authors construct a universal DFA where each agent carries just one movable pebble, and they prove this is sufficient for rendezvous on any tree. This stark asymmetry highlights that the ability to retrieve and reposition a marker is computationally far more powerful than merely leaving a permanent trace.

The paper is significant for distributed computing theory: it precisely characterizes the resource boundary (one movable pebble) needed to solve rendezvous in tree-shaped, unlabeled environments. Practically, the result suggests minimal hardware requirements for swarm robotics or networked agents that must coordinate without GPS, beacons, or shared memory. The constructed automaton provides an explicit (though theoretical) strategy that could inspire efficient local protocols for real-world agents navigating unknown tree-like terrains.