What forces the bounds

Each lower bound in the atlas carries a bottleneck: two or three words for what the adversary uses. Across all problems the commonest names are distance, symmetry breaking and symmetry, then memory (colours of lights), unknown exit, adversarial edge changes and unknown distance; a long tail of names (trap graphs, port addressing, indistinguishable Byzantine agents, timing is the only channel) covers single arguments. This essay groups them into four kinds and ends with what is left open.

The grouping matters because results move along the assumption axes in opposite directions: an algorithm for a weak setting holds in every stronger one, a lower bound for a strong setting holds in every weaker one. A bound whose bottleneck survives every strengthening (distance, for instance) is inherited by a whole subtree of settings; a bound that depends on an assumption (asynchrony, an unknown exit) disappears as soon as that assumption is lifted.

The plainest argument is that an entity must cover a distance. Kshemkalyani et al. state it for dispersion in one sentence: "Suppose two nodes of a graph are at a distance of \(\Omega(k)\), then to disperse from one node to the furthest node takes \(\Omega(k)\) time (e.g., line graph)" Kshemkalyani et al. 2025. The bound is from Kshemkalyani & Ali 2019, and after several rounds of algorithms it is matched by \(O(k)\) rounds, synchronous and asynchronous Kshemkalyani et al. 2025 Pattanayak et al. 2025. On grids the distance is \(\sqrt k\) Kshemkalyani et al. 2020. For collaborative exploration the offline cost \(\Theta(n/k+D)\) is the distance part Disser et al. 2020.

Programmable matter has the same argument, counted in moves: \(n\) particles reshaping a compact configuration into a line need \(\Omega(n^2)\) moves in total Derakhshandeh et al. 2015, as do deterministic shape formation Di Luna et al. 2020, universal coating Derakhshandeh et al. 2017 and centralised transformations by sliding Michail et al. 2019; universal shape formation needs \(\Omega(\sqrt n)\) rounds Derakhshandeh et al. 2016. Distance bounds are usually the easy half of a tight result. What took years in dispersion was the algorithm, not the bound.

The second kind of argument is about possibility rather than cost. Identical entities that the adversary keeps in symmetric positions cannot be separated by a deterministic rule: two oblivious robots in SSYNC Suzuki & Yamashita 1999 Flocchini et al. 2016, anonymous agents whose views coincide Dieudonné & Pelc 2016, leader election among disoriented robots in symmetric positions Dieudonné et al. 2013, arbitrary patterns in ASYNC without a common orientation Flocchini et al. 2008, and silent particles that share only chirality Navarra & Piselli 2023. Identical points that the robots cannot count produce the same effect: without multiplicity detection gathering is impossible Prencipe 2007.

Even when identifiers break symmetry, carrying them costs memory. For dispersion of \(k\) agents the \(\Omega(\log k)\) bits bound holds "since at least one agent needs \(\Omega(\log k)\) bits to store its unique ID" Kshemkalyani et al. 2025 Augustine & Moses Jr. 2018. Anonymous rendezvous in graphs of \(n\) nodes needs \(\Theta(\log n)\) bits Czyzowicz et al. 2012, and labelled rendezvous on a ring with simultaneous start takes \(\Theta(d\log\lambda)\) rounds, where \(d\) is the initial distance between the agents and \(\lambda\) the smaller label: the price of reading a label of \(\log\lambda\) bits bit by bit Dessmark et al. 2006. When agents cannot talk at all, time is the only channel: silent dispersion needs \(\Omega(k+\log L)\) rounds Das et al. 2025 and \(\Omega(\log L+\log\Delta)\) bits Gorain et al. 2022, with identifiers at most \(L\) and maximum degree \(\Delta\). In the plane the same economy appears as colours: two robots with lights need two Viglietta 2013, with only internal or only external lights three Otaka et al. 2026.

Search problems are bounded by what the searcher does not know. Beck already showed that, without knowing the distribution of the target, the distance travelled cannot be below 9 times the expected distance (as reported by Kupavskii & Welzl 2018), and the cow-path ratio 9 is the competitive form of the same fact Baeza-Yates et al. 1993; randomization lowers it to about \(4.5911\) Kao et al. 1996. Kupavskii and Welzl's bound for \(m\) rays, specialised to robots without faults, settled the question of parallel search on \(m\) rays "posed by three groups of scientists some 15 to 30 years ago" Kupavskii & Welzl 2018. An unknown exit gives every evacuation bound on the disk Czyzowicz et al. 2014, and one-way communication gives the line its exact ratio \(3+2\sqrt2\) Czyzowicz et al. 2021.

On graphs the missing information is which port to take. Remembering one port among \(\Delta\) costs \(\lceil\log\Delta\rceil\) bits for perpetual tree exploration Diks et al. 2002 and \(\Omega(\log\Delta)\) bits for dispersion by anonymous randomized agents Molla & Moses Jr. 2019; treasure hunt with pebbles needs \(\Omega(D\log\Delta)\) rounds Gorain et al. 2022. Stronger memory bounds come from trap graphs, built so that an agent with too little memory (or too few pebbles) misses part of them: \(\Omega(D\log\Delta)\) bits for perpetual exploration Fraigniaud et al. 2005 and \(\Theta(\log\log n)\) pebbles for a constant-memory agent Disser et al. 2019. Fraigniaud et al. recall why these bounds were pursued: exploration by finite automata was tied to the complexity of undirected connectivity Fraigniaud et al. 2006.

Some bounds need an adversary that does more than choose the input. An adversary that removes edges forces three agents and \(\Omega(n^{1.5})\) moves for black hole search in a dynamic ring Di Luna et al. 2025, makes dispersion with local communication impossible in 1-interval-connected graphs Kshemkalyani et al. 2020, and forces \(\Omega(n^2)\) steps to explore some temporal graphs even offline, whereas static undirected graphs need fewer than \(2n\) Erlebach et al. 2021. An adversary that delays agents forces \(\Theta(n^2)\) moves in black hole search without a map Dobrev et al. 2006 and an \(\Omega(\log^2 k)\) factor in asynchronous collaborative tree exploration Cosson & Massoulié 2025; one that reveals a tree online forces a competitive ratio of \(\Omega(\log k/\log\log k)\) for collaborative exploration Disser et al. 2020.

Byzantine entities act from inside. Because they are indistinguishable from good ones, gathering on graphs with \(f\) Byzantine agents needs \(f+1\) good agents Bouchard et al. 2016, three robots with one Byzantine cannot gather in SSYNC Agmon & Peleg 2006, dispersion of \(k > n\) agents on \(n\) nodes into a balanced configuration is impossible whenever \(\lceil k/n\rceil > \lceil (k-f)/n\rceil\), because Byzantine agents can occupy nodes exactly like honest ones Molla et al. 2021, and the best lower bound for search on the line with Byzantine robots, about \(5.23\), comes from the argument for crash faults Kupavskii & Welzl 2018. The black hole is the extreme case of an adversary inside the network: an asynchronous team without a map needs \(\Delta+1\) agents, \(\Delta\) the maximum degree, and it cannot succeed at all if \(n\) is unknown or the graph is not 2-connected Dobrev et al. 2006.

At the time of writing, the atlas judges optimality per measure for every variant, and more than two in five of these judgements are unknown: no non-trivial lower bound, or no analysis of that measure. Most of them come from two habits of the literature. In the plane, time is often not analysed because the question was feasibility. On graphs, rendezvous and exploration algorithms often leave memory unbounded. Both are open questions that nobody has asked yet rather than hard ones.

The polynomial gaps cluster where the only lower bound is distance. Dispersion on trees with \(n\) nodes has \(O(n)\) for \(k=n\) agents against an \(\Omega(D^2)\) bound proved only for trees of height about \(\sqrt{\log n}\) Disser et al. 2020; crash-tolerant dispersion is a factor \(\Delta\) (the maximum degree) from \(\Omega(k)\) Pattanayak et al. 2023; Byzantine dispersion is \(\tilde O(n^9)\) against \(\Omega(n)\) Molla et al. 2021. Black hole search with tokens is \(O(mn)\), for \(m\) edges, against \(\Omega(n^2/\Delta)\) Balamohan et al. 2016. Stopping tree exploration without knowing \(n\) uses \(O(\log n)\) bits against an \(\Omega(\log\log\log n)\) bound Ambühl et al. 2011 Diks et al. 2002, and leader election in programmable matter has no proven lower bound, only an informal \(\Omega(D)\) remark, \(D\) being the diameter of the particle configuration Dufoulon et al. 2021. Where the bottleneck is symmetry or missing information, results tend to be tight or exact; the gaps that remain in search are between two constants, as in two-robot face-to-face evacuation, about \(5.255\) against \(5.6234\) Czyzowicz et al. 2020 Disser & Schmitt 2019. The progress map of each problem shows the bottleneck next to every bound, so these patterns can be checked directly.