Universal Rendezvous of Anonymous Agents with Footprints
2026-08-10 • Distributed, Parallel, and Cluster Computing
Distributed, Parallel, and Cluster Computing
AI summaryⓘ
The authors study a problem where two identical agents start at different places in a network and try to meet by moving around in steps. They work with a setting where agents can leave permanent marks (footprints) on nodes they visit, and these marks look the same to both agents. The authors address a previously unsolved question by showing there is a single method (a universal algorithm) that guarantees the agents will eventually meet in any connected graph, whether it is finite or infinite. This means their method works for all instances in this settings and solves the open problem posed by earlier researchers.
deterministic rendezvousanonymous agentsanonymous graphuniversal algorithmfootprintsconnected graphsynchronous navigationalgorithm feasibilityinfinite graphmobile agents
Authors
Bibhuti Das
Abstract
Deterministic rendezvous for two anonymous mobile agents starting simultaneously from two distinct nodes of an anonymous connected graph and navigating synchronously in the graph requires that they meet at some node. An instance of the rendezvous problem is the underlying graph, together with two distinct nodes that are the initial positions of the agents. Such an instance is said to be feasible if there is a deterministic algorithm guaranteeing rendezvous, possibly valid only for this instance. A rendezvous algorithm is said to be universal for a class of instances if it guarantees rendezvous for all feasible instances from this class. We consider the model with footprints: whenever an agent visits an unmarked node, it leaves a permanent footprint on it, and all footprints are identical. This paper aims at answering the open problem from the paper by Das and Pelc (SPAA 2026), asking whether there exists a universal rendezvous algorithm for the class of all instances in the model with footprints. We propose a universal rendezvous algorithm for the class of all instances where the underlying graph is connected (finite or countably infinite) in the model with footprints. This shows the existence of a universal algorithm for the class of all instances in the model with footprints, which is an affirmative answer to the open problem.