When agents fail

The papers give two kinds of reasons. The first is hardware and environment. For robots in the plane, faults "can occur due to the unreliable components in the system, which are custom made or manually built", from manufacturing defects, or from "some external factor in the field of deployment" Pattanayak et al. 2019; since swarms "are envisioned for applications such as rescue, exploration, and surveillance in hazardous environments, it is natural that robots may experience faults" Pramanick et al. 2025. The second is scale: "When the number of robots in a swarm increases, the possibility of having one robot crash unpredictably becomes important to tackle" Bramas et al. 2023, and on graphs "The scale-up when considering numerous agents is inevitably tied to the occurrence of faults among them" Bouchard et al. 2022.

The fault models are borrowed from classical distributed computing. A crash fault stops an entity for ever; a Byzantine fault lets it behave arbitrarily, and "the Byzantine fault subsumes the crash fault" Molla et al. 2020. On graphs a further distinction matters: a weakly Byzantine agent cannot fake its identifier, a strongly Byzantine one can Molla et al. 2021. Bouzid, Das and Tixeuil import wait-freedom: "an arbitrary and unexpected delay observed at one robot may not prevent other robots from making progress toward the solution", even if \(n-1\) of the \(n\) robots are delayed or crashed Bouzid et al. 2013.

Black hole search puts the fault in the network instead of the agents. Di Luna et al. motivate it by host attacks on mobile code: a black hole is a site "that disposes of visiting agents upon their arrival, leaving no observable trace of such a destruction", which can be a virus that trashes incoming messages or "the undetectable crash failure of a site" Di Luna et al. 2025. Kaur et al. add a node in a cloud that loses essential data Kaur et al. 2026. The task is to locate it with at least one agent surviving, so the primary measure is the team size: how many agents the adversary may destroy.

The answers depend on what agents know and how they communicate. Asynchronous agents with whiteboards and no map need \(\Delta+1\) agents and \(\Theta(n^2)\) moves; with a map two agents suffice and \(\Theta(n\log n)\) moves Dobrev et al. 2006. Tokens can replace whiteboards: \(\Delta+2\) agents without a map Balamohan et al. 2016, two with a map at the same cost Flocchini et al. 2012. When the adversary may also remove one edge per round of a ring, three agents are necessary and sufficient, with \(\Theta(n^{1.5})\) moves using pebbles Di Luna et al. 2025; in arbitrary dynamic graphs with one missing edge per round, six co-located agents with whiteboards suffice Kaur et al. 2026.

A crash is the mildest fault, and in the plane it is often harmless for feasibility. In SSYNC, the correct robots gather despite up to \(n-1\) crashes, wait-free, with only weak multiplicity detection and no agreement on coordinates Pattanayak et al. 2019; the first crash-tolerant algorithm, for one crash, is in Agmon & Peleg 2006. The subtlety is what "gathering" means: in the weak version only correct robots must meet, in the strong version all robots must meet at the crash site; Bramas, Lamani and Tixeuil describe the strong one as one "where correct robots are requested to rescue failed ones", and show that two robots with lights cannot solve it in SSYNC Bramas et al. 2023. For mutual visibility with lights one crash fault is tolerated Aljohani & Sharma 2018.

On graphs a crashed agent "loses all its information immediately, as if the robot has vanished from the network" Chand et al. 2023. For dispersion this costs time rather than feasibility: the best crash-tolerant algorithm for \(k\) agents runs in \(O(\min(m,k\Delta))\) rounds on a graph with \(m\) edges and maximum degree \(\Delta\) Pattanayak et al. 2023 against the fault-free \(O(k)\) Kshemkalyani et al. 2025, while on oriented grids crash-tolerant dispersion takes \(O(\sqrt n)\) rounds on \(n\) nodes, optimal when \(k = \Omega(n)\) Banerjee et al. 2025. In search, a crashed robot is silent: it visits the target without reporting it Kupavskii & Welzl 2018. On the line the optimal ratio with \(f\) crash faults among \(k\) robots is known exactly Czyzowicz et al. 2016 Kupavskii & Welzl 2018; with one crash among three wireless robots in a disk, evacuation takes between about \(5.082\) and \(6.309\) Czyzowicz et al. 2017.

Byzantine faults are "considered as the worst faults that can occur", and a Byzantine agent "may also convey arbitrary information to the other agents, impersonate the identity of another agent, and so on" Bouchard et al. 2022. In the plane one Byzantine robot among three already prevents gathering, and even convergence, in SSYNC, while in FSYNC \(n \ge 3f+1\) robots tolerate \(f\) Byzantine ones Agmon & Peleg 2006; for mutual visibility with lights one Byzantine robot among three is likewise fatal Aljohani & Sharma 2018. On graphs, gathering with \(f\) strongly Byzantine agents needs at least \(f+1\) good agents when the number \(n\) of nodes is known and \(f+2\) otherwise, as Dieudonné, Pelc and Peleg proved when they posed the problem Dieudonné et al. 2014, and these team sizes suffice Bouchard et al. 2016; the algorithms are exponential, and polynomial time is known only for larger teams Bouchard et al. 2022.

Dispersion was taken to Byzantine agents because "in the real world, where systems must be fault tolerant and errors are the norm instead of the exception, more work must be done" Molla et al. 2021. On rings it costs \(\Theta(n)\) rounds under the assumptions of Molla et al. 2020; on general graphs the best bound is \(\tilde O(n^9)\) against \(\Omega(n)\), because the algorithms go through Byzantine gathering Molla et al. 2021; with strong Byzantine agents an arbitrary start becomes polynomial only with a trusted shepherd Moses Jr. & Redlich 2024. Black hole search with weakly Byzantine companions that survive the black hole needs \(2f+2\) agents with a map Di Luna et al. 2025.

In search a Byzantine robot can claim a target that is not there, so "a reliable robot cannot necessarily trust an announcement that the target has been found" Czyzowicz et al. 2021. On the line the optimal ratio is known only for some densities \(f/k\) Czyzowicz et al. 2021; with three robots and one Byzantine, disk evacuation takes between about \(5.948\) and \(6.921\) Czyzowicz et al. 2017.

Each model in the atlas orders faults from most hostile (level 0) to none: strong Byzantine, weak Byzantine, crash, none for agents on graphs; Byzantine, crash, none for robots in the plane and for search. An algorithm proved against Byzantine entities therefore carries over to crashes, and an impossibility for crashes carries over to Byzantine entities. The black hole is not a value on this axis: it is part of the statement of black hole search, whose faults axis concerns the agents (the Byzantine-companion variants sit at weak Byzantine).

The measure that a fault changes differs by model, and that is the clearest lesson of the comparison. Losing agents in a black hole changes the team size. Crashes in the plane rarely change feasibility, but Byzantine robots often do. Crashes on graphs change time by a factor that is not yet understood, and Byzantine agents change it from linear to a high polynomial. In search every fault changes an exact constant, and the gaps between the constants are the open problems.