Rendezvous

Further reading

Papers on this problem that are not yet placed in a setting.

• Kammer et al. 2026 Temporal Exploration and Rendezvous via Weisfeiler-Leman Colorings. Temporal rendezvous: two synchronous agents know the whole always-connected temporal graph but share no labelling of its nodes and cannot communicate; the adversary picks the starting nodes and the labellings. They meet within \(O(n\log^3 n)\) steps using polynomial computation, for a long enough lifetime (Theorem 1.4), against an \(\Omega(n\log n)\) lower bound from the paper that posed the problem (Dogeas et al., ICALP 2024, not in the catalogue), as reported. Preprint; read.
• Das 2026 Universal Rendezvous of Anonymous Agents with Footprints. Footprints: every node an agent visits keeps a permanent mark, the same for both agents, which an agent sees when it is at the node. For two anonymous agents with simultaneous start, Das gives a universal algorithm, which meets in every feasible instance (a graph and two start nodes), in every connected graph, finite or countably infinite with finite degrees (Theorem 2.1, Corollary 2.1); this answers an open question of Das and Pelc (SPAA 2026, not in the bibliography). By their Proposition 2.1, recalled here, an instance is feasible only if the views from the two start nodes differ or the footprints seen along some path differ. No bound on time is given. The problem has no axis for marking nodes yet. Preprint; read.
• Das & Pelc 2026 Rendezvous of Mobile Deterministic Automata in Graphs. Two anonymous agents modelled as copies of one deterministic finite automaton, synchronous, with arbitrary delay, in finite graphs whose degrees are bounded by a constant known to the designer; the automaton must meet in every feasible instance of a class. Without marking no such automaton exists even for paths (Proposition 2.1); with any finite number of pebbles that can be picked up again, none exists for all graphs (Proposition 2.2, through the graphs of Rollik 1980); with finitely many pebbles that cannot be picked up, none exists even for paths (Theorem 3.1, Corollary 3.1); with one pebble per agent that can be picked up, one automaton meets in every feasible instance on trees, within \(O(n^2)\) rounds from the start of the earlier agent (Theorem 4.1, Corollary 4.1). Without pebbles, \(\Theta(\log n)\) bits are needed in trees with delay Fraigniaud & Pelc 2013, so one pebble replaces them by constant memory. The problem has no axis for marking nodes yet. Preprint; read.
• Baaziz & Pelc 2026a Asynchronous Rendezvous of Anonymous Deterministic Mobile Automata in the Plane. Rendezvous in the plane rather than in a graph. Two anonymous agents, copies of one deterministic finite automaton with a compass, see the disc of radius 1 around them before each move, move asynchronously (the adversary sets the speed during each move), and carry pebbles that they can pick up again and that the other agent can tell apart from its own. With at most 8 pebbles each they always meet, at cost (total length of both trajectories) \(O(d^2)\) when the start points are at distance at most \(d\) (their \(D\)) (Theorem 2); the authors argue in Section 5 that \(\Omega(d^2)\) is necessary, since the adversary can hold one agent back until the other finds it. The same algorithm elects a leader between the two agents. Read (LIPIcs version).
• Gao & Pelc 2026 Gathering teams of bounded memory agents on a line. Two labelled agents that are finite automata (states depending only on \(L\)), started in the same round on distinct nodes of the infinite oriented path, can be placed so that they never meet (Theorem 3.1, for any set of such agents); teams of two or more agents per starting node gather (Theorems 4.1–6.2). Read (arXiv v1).
• Yamada et al. 2026 Rendezvous and merging for two metamorphic robotic systems without global compass. A different model: two metamorphic robotic systems (connected oblivious modules on the square grid) without a common compass meet until every module sees all the others, then merge into one connected system; five modules per system suffice (Theorems 1 and 2) and are necessary for rendezvous (Theorem 3). Read (arXiv v1).
• Bampas et al. 2019a On asynchronous rendezvous in general graphs. Characterises, in polynomial time, the pairs of walks that force rendezvous against an asynchronous adversary within a given number of edge traversals, with a certificate of why. Abstract read.
• Bouchard et al. 2018 On deterministic rendezvous at a node of agents with arbitrary velocities. Rendezvous at a node (not inside an edge) of labelled agents whose speed the adversary fixes per agent and per edge: polynomial in \(n\), the smaller label and the largest traversal time. Abstract read.
• Chalopin et al. 2016a Rendezvous in networks in spite of delay faults. Labelled agents with delay faults, measured by cost: polynomial cost with random faults; impossible with unbounded adversarial faults even on rings (cost \(O(n\lambda)\) on trees, \(\Omega(\lambda)\) needed); polynomial with faults bounded by an unknown \(c\). Abstract read.
• Dereniowski et al. 2015b Rendezvous of heterogeneous mobile agents in edge-weighted networks. Agents that know the map but traverse edges at different, private speeds: \(O(n\,T_{\mathrm{OPT}})\) in general, \(\Theta(T_{\mathrm{OPT}})\) if they exchange \(\Theta(n)\) bits at the start, with \(T_{\mathrm{OPT}}\) the offline meeting time. Abstract read.
• Miller & Pelc 2016 Time versus cost tradeoffs for deterministic rendezvous in networks. Trade-off between time and cost (edge traversals) for labelled agents, as functions of an exploration bound \(E\): cost \(O(E)\) with time \(O(EL)\), or both \(O(E\log L)\), with lower bounds on the trade-off. Abstract and introduction read.
• Miller & Pelc 2015a Fast rendezvous with advice. How much advice gives rendezvous in time \(O(d)\): \(\Theta(d\log(n/d)+\log\log L)\) bits. Abstract and introduction read.
• Eguchi et al. 2022 Fast Neighborhood Rendezvous. Neighbourhood rendezvous (agents start at adjacent nodes) in \(o(\Delta)\) rounds, with randomisation, node identifiers, neighbourhood identifiers and bounded minimum degree. Abstract read.
• Cosson 2024a Ariadne and Theseus: Exploration and Rendezvous with Two Mobile Agents in an Unknown Graph. Two agents with whiteboards: exploration in \(m\) steps from a common start and rendezvous in at most \(\lceil 3m/2\rceil\) steps, also against an asynchronous adversary, with matching lower bounds there. A preprint; abstract and main results read.
• Gao & Pelc 2025 Sniffing helps to meet: Deterministic rendezvous of anonymous agents in the grid. Identical agents in the infinite oriented grid that mark the nodes they visit: time \(O(D)\) if they know the distance bound \(D\) or start together, and \(O(D^2)\) with neither, where a superlinear lower bound separates the cases. Abstract read.
• Das et al. 2015a Mobile Agents Rendezvous in Spite of a Malicious Agent. Rendezvous of several asynchronous anonymous finite-state agents despite a fast malicious agent that blocks nodes: necessary conditions, solved on rings except for even numbers of agents on unoriented rings, and on oriented meshes iff agents see two hops. Abstract read.
• Dogeas et al. 2024 Exploiting Automorphisms of Temporal Graphs for Fast Exploration and Rendezvous. Temporal graphs with \(r\) automorphism orbits are explored in \(O(rn^{1+\varepsilon})\) steps, with lower bounds; the paper also poses rendezvous in temporal graphs. Abstract read.
• Mironowicz 2023 Entangled rendezvous: a possible application of Bell non-locality for mobile agents on networks. Location-aware agents on small networks that share entangled quantum states: optimal strategies with a limited number of steps, with an advantage over classical agents on cubic graphs and cycles. Introduction read.
• Pelc & Yadav 2020 Latecomers Help to Meet: Deterministic Anonymous Gathering in the Plane. Gathering of anonymous agents in the plane with compasses and clocks, where delays can break symmetry: characterisation of gatherable configurations, no common algorithm for the 'bad' ones, and the knowledge of the team size needed for the others. Abstract read.
• Dieudonné et al. 2023 Almost Universal Anonymous Rendezvous in the Plane. Rendezvous of two anonymous agents in the plane whose attributes (coordinates, clock rate, speed, wake-up) may differ: exact characterisation of feasible instances, no single algorithm for two small sets of them, and one algorithm for all others. Abstract read.
• Elouasbi & Pelc 2018 Deterministic Meeting of Sniffing Agents in the Plane. Labelled disc agents in the plane that sense their distance but not the direction to each other: deterministic rendezvous under two models of distance estimation. Abstract read.
• Czyzowicz et al. 2018b Linear Rendezvous with Asymmetric Clocks. Two anonymous robots on the line whose speeds or clock units may differ: a universal algorithm meets whenever at least one parameter differs. Abstract read.
• Georgiou et al. 2018 Symmetric Rendezvous with Advice: How to Rendezvous in a Disk. Randomised symmetric rendezvous of two robots at distance 2 with a common reference point (in a disk): expected time below the 4.25 of the line. Abstract read.
• Chuangpishit et al. 2017 Rendezvous on a Line by Location-Aware Robots Despite the Presence of Byzantine Faults. Location-aware robots on a line, some of them Byzantine: a central authority plans trajectories with bounded competitive ratio, better when the number of faulty robots is bounded. Abstract read.
• Ozsoyeller et al. 2021 Symmetric Rendezvous in Planar Environments With and Without Obstacles. Symmetric rendezvous of two robots in planar environments with and without obstacles. Abstract read.