Home›Mobile agents on graphs›Exploration›Graph exploration by a single agent›Rendezvous

Rendezvous

Two agents start at different nodes of an unknown graph and must meet; how long does it take, and how much memory or symmetry breaking does it need?

Problem statement and measuresexpand

Two mobile agents start at different nodes of an unknown connected port-labelled graph. In the synchronous model they must be at the same node in the same round; in the asynchronous model an adversary controls their speeds and they may also meet inside an edge. Agents are either labelled (distinct labels from \(\{1,\dots,L\}\); \(\lambda\) is the smaller label) or anonymous. They may start at different times; \(\tau\) is the delay. Time is the number of rounds from the start of the later agent (synchronous) or the total number of moves, that is edge traversals (asynchronous cost). Memory is bits per agent.

Measures: Time, rounds after the later agent starts (synchronous); edge traversals (asynchronous); Memory, bits per agent.

Progress map

tight near-optimal polynomial gap unknown impossible· rows follow the assumption tree; each cell: best upper bound vs lower bound, and what forces the lower bound

Setting

Time

Memory

No assumptions

—

Graph size + static graph, + undirected

—

Asynchronous anonymous agents + finite graph

0 open · 1 results

unknown \(\text{finite}\) vs —

unknown — vs —

Asynchronous labelled agents + distinct IDs (eponymous)

1 open · 3 results

unknown \(\text{poly}(n,\log \lambda)\) vs —

unknown — vs —

Labelled agents, arbitrary finite graphs + synchronous

1 open · 3 results

polynomial gap \(\tilde O(n^5\log \lambda)\) vs \(\Omega(n^2)\) exploration

unknown — vs —

Labelled agents in trees any delay, + tree

0 open · 1 results

tight \(O(n+\log \lambda)\) vs \(\Omega(n+\log \lambda)\) distance

unknown — vs —

Labelled agents in rings, simultaneous start + simultaneous start, + ring

0 open · 1 results

tight \(O(d\log \lambda)\) vs \(\Omega(d\log \lambda)\) symmetry breaking

unknown — vs —

Anonymous agents: memory anonymous, + synchronous

0 open · 1 results

unknown — vs —

tight \(O(\log n)\) vs \(\Omega(\log n)\) symmetry breaking

Anonymous agents in trees, simultaneous start + simultaneous start, + tree

0 open · 1 results

unknown — vs —

tight \(O(\log \nu+\log\log n)\) vs \(\Omega(\log \nu+\log\log n)\) symmetry breaking

Labelled agents, graphs with infinite degrees infinite degrees allowed, + distinct IDs (eponymous), + synchronous

1 open · 1 results

polynomial gap \(O((W\log L)^3)\) vs \(\Omega(\max(W,\log L))\) port addressing

unknown — vs —

Know a better result, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.