Symmetry is the adversary

Pelc's survey of deterministic rendezvous names the obstacle directly: "The main problem that has to be solved in order to make deterministic rendezvous possible, both in networks and in the plane, is breaking symmetry" Pelc 2019. His example is an oriented ring, port 0 clockwise at every node, with two identical agents that start at the same time: whatever one does, the other does too, so the distance between them never changes. The same holds in the empty plane for agents with the same compass, unit and speed Pelc 2019. Ta-Shma and Zwick make the same point when they give their rendezvous agents labels: without them "the rendezvous problem cannot be solved deterministically" Ta-Shma & Zwick 2014.

The argument travels to every model in the catalogue. For dispersion, Das, Bose and Sau spell it out: anonymous agents that start on one node are in the same state and run the same algorithm, so "they will always mirror each other's move" and never separate; the same reasoning gives the \(\Omega(\log k)\) bits per agent, for \(k\) agents, that every deterministic dispersion algorithm needs Das et al. 2021 Augustine & Moses Jr. 2018. In the plane, two oblivious robots cannot gather under a semi-synchronous scheduler Flocchini et al. 2016 (first shown by Suzuki and Yamashita Suzuki & Yamashita 1999, as the catalogue records it), and scattering robots that may start on a common point has no deterministic solution Dieudonné & Petit 2009. Clement, Défago, Potop-Butucaru, Izumi and Messika put it generally: because robots are anonymous, "the impossibility results proved in classical distributed computing also hold in robot networks", and flocking, gathering or scattering are impossible without additional assumptions Clement et al. 2010.

Each model has its own notion of symmetry, and the strongest results characterise it exactly. In port-labelled graphs the notion is the view of a node, the infinite tree of port sequences seen from it (introduced by Yamashita and Kameda, as recounted by Pelc 2019). Two anonymous agents can meet if and only if their starting nodes have different views Czyzowicz et al. 2012, as stated in Pelc 2019. For larger anonymous teams the asymmetry may come from the agents' positions relative to each other rather than from the graph, which Pelc singles out as the main difficulty solved by Dieudonné and Pelc Dieudonné & Pelc 2016 Pelc 2019.

In the plane the notion is geometric. Dieudonné, Levé, Petit and Villain characterise the positions from which disoriented robots can deterministically elect a leader, with and without a common handedness, for every \(n > 1\); both characterisations rest on Lyndon words built from the positions Dieudonné et al. 2013. For fat robots, Gan Chaudhuri and Mukhopadhyaya show that a leader can be elected exactly from asymmetric configurations Chaudhuri & Mukhopadhyaya 2015.

Dieudonné, Levé, Petit and Villain open their paper with the reason leader election matters: "many problems that are hard to solve become easier to solve with a leader to coordinate the system" Dieudonné et al. 2013. For robots in the plane the link is an equivalence. Flocchini, Prencipe, Santoro and Widmayer showed that \(n \ge 3\) robots that cannot elect a leader cannot form arbitrary patterns (as reported by Dieudonné et al. 2013). Dieudonné, Petit and Villain proved the converse in asynchronous systems for \(n \ge 4\) with chirality and \(n \ge 5\) without Dieudonné et al. 2010. Cicerone, Di Stefano and Navarra later gave a full characterisation without chirality, arbitrary pattern formation being solvable exactly from leader configurations, and reported that several earlier proofs, including the arXiv version of Dieudonné et al. 2010, are not correct Cicerone et al. 2019.

Programmable matter repeats the pattern. Derakhshandeh et al. motivate leader election by observing that consensus "can easily be solved once the leader election problem can be solved" and that most shape-formation algorithms depend on a seed Derakhshandeh et al. 2015. Emek, Kutten, Lavi and Moses Jr. call it "an important primitive ... that subsequently breaks symmetry and coordinates the remaining amoebots", and their deterministic algorithm without chirality also makes the particles agree on a handedness Emek et al. 2019. In the agent-based model on graphs, Kshemkalyani, Kumar, Molla and Sharma note that leader election "can also be seen as a form of symmetry breaking" and build minimum spanning trees, independent sets and dominating sets on the elected leader Kshemkalyani et al. 2024.

The first way out is to give agents labels. Pelc lists it first: distinct labels, each known to its owner, make deterministic rendezvous possible in every connected graph, at a cost that grows with the length of the labels Pelc 2019 Dessmark et al. 2006. In dispersion the identifiers are what the memory pays for: the \(\Omega(\log k)\) lower bound is the cost of storing a distinct identifier Kshemkalyani et al. 2025.

Between anonymous and fully labelled lies homonymy, which Delporte-Gallet et al. introduced for Byzantine agreement Delporte-Gallet et al. 2013. Bouzid and Lamani brought it to robots, recalling that sequences of patterns are formable by labelled robots almost without restriction but by anonymous robots only when all patterns have the same symmetricity Das et al. 2015; this gap, they write, "illustrates how much anonymity can be a limiting factor" Bouzid & Lamani 2011. Asahiro and Yamashita treat the number of distinct programs (target functions) as a resource: gathering needs two, and three once a robot may crash Asahiro & Yamashita 2025. On graphs, Devismes, Dieudonné and Labourel argue that unique labels can be costly to maintain or undesirable for privacy, and that randomised alternatives give no absolute guarantees; they characterise the teams with repeated labels that can gather and gather all of them in time polynomial in the number \(n\) of nodes and in \(\log\lambda\), where \(\lambda\) is the smallest label Devismes et al. 2026.

The second way out is randomness. Clement et al. remark that work on robot impossibilities had focused on extra assumptions rather than on randomisation Clement et al. 2010. Scattering is the clean case: no deterministic algorithm exists Dieudonné & Petit 2009, and Bramas and Tixeuil show that, to scatter \(n\) robots, \(n\log n\) random bits are necessary in total, give a scattering algorithm that uses that many bits and runs in \(O(\log\log n)\) rounds without strong multiplicity detection, and prove that no algorithm without strong multiplicity detection runs in constant expected time Bramas & Tixeuil 2017. For dispersion, coin flips replace identifiers: anonymous randomised agents disperse with \(O(\log\Delta)\) bits on graphs of maximum degree \(\Delta\) Das et al. 2021, matching the \(\Omega(\log\Delta)\) bound of Molla and Moses Jr. Molla & Moses Jr. 2019. The randomised amoebot algorithm of Derakhshandeh et al. elects a leader in expected time linear in the longest boundary Derakhshandeh et al. 2015.

The third way out lives in the scheduler. Under a sequential scheduler, which activates one robot per round, robots can break symmetry and elect a leader. Flocchini, Navarra, Pattanayak, Piselli and Santoro show that this power is "much stronger than the obvious capacity these schedulers offer of breaking symmetry": every pattern except a point becomes formable from every start, which is impossible under the fully synchronous scheduler even for robots with a leader Flocchini et al. 2026.

The cost of breaking symmetry is not settled even in the problems that are otherwise solved. Deterministic dispersion runs in optimal \(O(k)\) rounds, but with \(O(\log(k+\Delta))\) bits; whether \(O(\log k)\) bits, the price of an identifier, suffice is open Kshemkalyani et al. 2025. Anonymous randomised agents disperse with optimal memory, but in \(\Theta(k^2)\) rounds against an \(\Omega(k)\) lower bound Das et al. 2021. Whether anonymous randomised agents can disperse from an arbitrary configuration and then stop, rather than stay active forever, is open Molla & Moses Jr. 2019 Das et al. 2021. And faults bring indistinguishability back: weak Byzantine agents can behave exactly like honest ones and occupy nodes, which makes balanced dispersion impossible whenever \(\lceil k/n\rceil > \lceil (k-f)/n\rceil\) Molla et al. 2021.