Mobile agents on graphs

Graphs that change all the time entered distributed computing as models of mobile, wireless and peer-to-peer networks. Kuhn, Lynch and Oshman introduced \(T\)-interval connectivity in a worst-case model where an adversary picks the edges of each round; "for \(T = 1\) this means that the graph is connected in every round, but changes arbitrarily between rounds" Kuhn et al. 2010. Casteigts, Flocchini, Quattrociocchi and Santoro unified the many models of time-varying graphs into a hierarchy of classes: the always-connected class, used earlier by O'Dell and Wattenhofer (as reported there), and recurrent connectivity, in which journeys exist from every time onward, which is level 0 here Casteigts et al. 2012. They put the reason for the scale in one sentence: in these systems "changes are not anomalies but rather integral part of the nature of the system" Casteigts et al. 2012. Kuhn et al. show the adversary's strength with a token that must keep moving: in a 1-interval connected graph the adversary can keep it between two nodes forever Kuhn et al. 2010, which is in effect a single agent that cannot explore. Mobile agents entered the setting with live exploration of 1-interval connected rings Di Luna et al. 2020 and dispersion in dynamic rings Agarwalla et al. 2018; offline exploration of temporal graphs is the centralised counterpart Erlebach et al. 2021.

Most of the mobile-agent literature uses undirected graphs because this "captures the ability of the agents to move in both directions along each link" Pelc 2019. Directed graphs come from the exploration literature. The earliest paper in the atlas on exploring an unknown directed graph is Deng and Papadimitriou's Deng & Papadimitriou 1999, continued by Albers and Henzinger Albers & Henzinger 2000. Bender, Fernández, Ron, Sahai and Vadhan asked what a robot needs to map an unlabelled strongly connected digraph, and showed that one pebble suffices when a bound on \(n\) is known Bender et al. 2002; Fraigniaud and Ilcinkas studied how little memory digraph exploration needs Fraigniaud & Ilcinkas 2004. Direction removes backtracking: a static undirected graph is explored by depth-first search in fewer than \(2|V|\) steps, while some static directed graphs need \(\Theta(|V|^2)\) steps Erlebach et al. 2021. Italiano, Pattanayak and Sharma posed dispersion on directed anonymous graphs because "the existing approaches for undirected graphs rely substantially on visiting a graph edge in both directions", and showed that without strong connectivity dispersion may be unsolvable Italiano et al. 2022.

Most tasks in this model are posed for a team of any size: gathering an unknown team of anonymous agents Dieudonné & Pelc 2016, black hole search, where the size of the team is the main measure Dobrev et al. 2006, and collective exploration by \(k\) agents Fraigniaud et al. 2006. The cap \(k \le n\) comes from dispersion, where every agent needs a node of its own. Augustine and Moses Jr. posed dispersion with \(k = n\), motivated by electric cars that should not queue at one charging station Augustine & Moses Jr. 2018, and Kshemkalyani and Ali relaxed it to \(k \le n\) Kshemkalyani & Ali 2019. Molla and Moses Jr. extended dispersion to any \(k\), asking for at most \(\lceil k/n \rceil\) agents per node Molla & Moses Jr. 2019. The extension is not free: with \(k > n\) Byzantine dispersion is impossible deterministically whenever \(\lceil k/n \rceil > \lceil (k-f)/n \rceil\) Molla et al. 2021. The axis thus separates tasks where the team must fit into the graph from tasks where the team size is unconstrained.

Pelc's survey names anonymous versus labelled agents as one of the two main pairs of assumptions in rendezvous, and gives the reason: two identical agents running the same deterministic algorithm in an oriented ring, starting together, keep the same distance forever Pelc 2019. Distinct labels break this symmetry: in the work of Dessmark, Fraigniaud, Kowalski and Pelc each agent knows only its own label and uses it as a parameter of the common algorithm, and rendezvous becomes feasible in every graph at cost polynomial in \(n\), the delay and \(\log\lambda\), \(\lambda\) the smaller label; without labels it fails already on two nodes joined by an edge, since both agents always stay or always move together Dessmark et al. 2006. Without labels the only asymmetry comes from the graph and the starting positions; Dieudonné and Pelc characterised the configurations of anonymous agents that can be gathered Dieudonné & Pelc 2016. Homonyms, several agents sharing a label, come from Byzantine agreement with homonyms Delporte-Gallet et al. 2013 and were taken to robots in the plane Bouzid & Lamani 2011. In graphs, Devismes, Dieudonné and Labourel motivate them by the cost of "generating and maintaining globally unique labels" and by privacy, and ask how many distinct labels gathering really needs Devismes et al. 2026.

Pelc counts determinism versus randomisation among the two assumptions that most shape the methods for rendezvous: a deterministic algorithm faces adversarial starting positions and is judged by its worst-case cost, while randomised algorithms often use random walks and are judged by expected cost Pelc 2019. The random-walk view of graph traversal goes back to Aleliunas et al., who connected random walks with universal traversal sequences Aleliunas et al. 1979. In this model randomness serves mainly to break symmetry: Molla and Moses Jr. let co-located anonymous agents elect a local leader by coin flips, so that dispersion needs \(O(\log\Delta)\) bits per agent instead of the \(\Omega(\log n)\) bits of deterministic algorithms Molla & Moses Jr. 2019. Deterministic algorithms are level 0 because they promise a bound for every execution; Devismes, Dieudonné and Labourel note that probabilistic approaches "typically fail to provide absolute guarantees in terms of complexity and/or accuracy" Devismes et al. 2026. Hence a deterministic algorithm also counts in the randomized setting, and a lower bound against randomized algorithms holds for deterministic ones.

The first faults studied for mobile agents sat in the network: Dobrev, Flocchini, Prencipe and Santoro introduced the black hole, a node that destroys every agent that enters it, in rings and then in arbitrary networks Dobrev et al. 2007 Dobrev et al. 2006; it models a host that trashes incoming code or crashes without notice Di Luna et al. 2025. Faults in the agents, which this axis records, came later. Dieudonné, Pelc and Peleg started the study of gathering with Byzantine agents and defined the two levels used here: a strongly Byzantine agent "can choose an arbitrary port when it moves and it can convey arbitrary information to other agents, while a weakly Byzantine agent can do the same, except changing its label" Dieudonné et al. 2014. The distinction is about identity and it changes the answer: with known \(n\) a single good agent gathers despite \(f\) weakly Byzantine agents, but \(f+1\) good agents are needed against strongly Byzantine ones, even in a ring of known size, while with unknown \(n\) both cases need \(f+2\) Dieudonné et al. 2014; Dieudonné, Pelc and Peleg left the strongly Byzantine upper bounds at \(2f+1\) (known \(n\)) and \(4f+2\) (unknown \(n\)), and Bouchard, Dieudonné and Ducourthial closed them Bouchard et al. 2016 Pelc 2019. Crash faults are the mildest level; Pelc showed that with fully asynchronous agents gathering with crashes is impossible, since a waiting agent cannot tell a slow agent from a crashed one, and solved it when each agent has a fixed speed Pelc 2018. Dispersion adopted both Byzantine levels Molla et al. 2021 and crash faults Chand et al. 2023.

Communication between co-located agents is the classical assumption of rendezvous and gathering, where agents that meet "can exchange all information they currently have" Pelc 2019. Augustine and Moses Jr. kept it for dispersion, assuming robots "can only communicate with other robots present on their own node", in line with their picture of cars that interact only car to car Augustine & Moses Jr. 2018. Di Luna, Dobrev, Flocchini and Santoro list the forms used in exploration: face-to-face, wireless (agents on different nodes), and whiteboards Di Luna et al. 2020. Kshemkalyani, Molla and Sharma introduced global communication to dispersion to measure "how much global communication helps", and observed that it does not tell two agents on neighbouring nodes which edge joins them, so the graph must still be walked Kshemkalyani et al. 2020. For collective tree exploration Fraigniaud, Gąsieniec, Kowalski and Pelc showed that without communication \(k\) agents gain nothing over one Fraigniaud et al. 2006. Between the two, Italiano, Pattanayak and Sharma studied a 1-hop model, in which "a robot may also communicate with robots positioned on its 1-hop neighbors", and used it to disperse on directed graphs in \(O(kD)\) rounds by broadcasting and gathering information along the graph Italiano et al. 2022. Saxena, Kaur and Mondal generalised it to ℓ-hop communication (\(h\)-hop here), "a spectrum between f-2-f (\(l = 0\)) and global communication (\(l = D\))", and showed that for balanced dispersion on 1-bounded 1-interval connected graphs agents need 1-hop visibility and 1-hop communication Saxena et al. 2025; the axis writes \(h\) for their \(\ell\), which the atlas uses for occupied nodes. At level 0, Gorain, Mandal, Mondal and Pandit asked whether talking is needed at all, and dispersed agents that only learn whether they are alone and whether the number of agents at their node changed Gorain et al. 2022.

Pelc names synchronous versus asynchronous movement as the second main pair of assumptions for rendezvous: synchronous agents can alternate measured periods of activity and waiting, "a powerful tool", while asynchronous agents move at speeds the adversary varies, so algorithms must force trajectories to overlap Pelc 2019. The asynchronous model for agents in graphs was introduced by De Marco, Gargano, Kranakis, Krizanc, Pelc and Vaccaro for rendezvous; since a meeting at a node cannot be guaranteed even in the two-node graph, agents may also meet inside an edge De Marco et al. 2006 (as described in Pelc 2019). Black hole search was posed for asynchronous agents with whiteboards Dobrev et al. 2006, while dispersion started synchronous and Kshemkalyani and Ali gave its first asynchronous algorithms Kshemkalyani & Ali 2019. Intermediate schedulers exist: Di Luna et al. brought the semi-synchronous model, "common in the context of mobile agents in continuous spaces", to agents in graphs Di Luna et al. 2020. Asynchrony interacts with other axes: it makes gathering with crash faults impossible Pelc 2018, and dynamic graphs are synchronous by definition Di Luna et al. 2025.

Whiteboards are the shared memory of the mobile-agent model: each node keeps a little storage that visiting agents read and write in mutual exclusion, "where the agents communicate by writing on and reading from whiteboards present in each node" Di Luna et al. 2020. They are the standard tool in black hole search, posed for asynchronous agents with whiteboards Dobrev et al. 2006, and in map construction, where identical agents with whiteboards build a map exactly when symmetry can be broken Das et al. 2007. Their purpose is marking: an agent that can leave information at a node can recognise it later, which is what node labels would otherwise provide Bender et al. 2002. The cheaper markers are pebbles or tokens, and black hole search showed that whiteboards can be replaced by them Dobrev et al. 2013 Flocchini et al. 2012; for digraphs, whiteboards of \(O(\log\Delta_{out})\) bits let an agent with constant memory explore Fraigniaud & Ilcinkas 2004. Pelc counts the ability to see marks among the assumptions that most change methods, since it "significantly facilitates" rendezvous Pelc 2019. Level 0 has no node memory, as in dispersion, where settled agents serve as markers instead Kshemkalyani & Ali 2019.

Anonymous nodes with locally labelled ports are the standard network of this model, and Pelc gives the reasons. Practically, nodes may withhold their labels "for privacy or security reasons", or the agents' sensors may be too weak to read them; methodologically, readable labels would let agents meet at the smallest label, reducing rendezvous to exploration Pelc 2019. Port numbers are kept because without them an agent may be unable to visit all neighbours of a node of degree at least 3, and because reading a port needs far less than reading a name Pelc 2019. The same convention underlies memory-bounded exploration, where a finite automaton explores a graph "whose nodes are unlabeled and whose edge ports are locally labeled" Fraigniaud et al. 2005. Labelled nodes belong to the online-exploration tradition, in which the agent recognises nodes and builds a map Deng & Papadimitriou 1999 Albers & Henzinger 2000, and to collective exploration, where nodes are typically labelled Augustine & Moses Jr. 2018 Fraigniaud et al. 2006. With labelled nodes many symmetry questions disappear, which is why the axis separates navigation from symmetry breaking.

Special topologies enter for two reasons: they are the simplest graphs with a given feature, and they are networks that are used. Trees can be explored with termination by a single agent and have a central node or edge that acts as a focal point, so rendezvous was first solved there; rings are "the simplest class" of graphs with cycles Pelc 2019 Dessmark et al. 2006. The oriented ring is also the most symmetric instance, where identical agents cannot meet Pelc 2019. The ring, oriented or not, was the first topology for black hole search Dobrev et al. 2007, and the oriented ring was the first for live exploration of dynamic graphs Di Luna et al. 2020 and, as reported by Molla et al. 2021, for Byzantine dispersion. Grids model discretised space: the infinite grid is a tool for rendezvous in the plane Pelc 2019, and dispersion on grids is studied for its own sake Kshemkalyani et al. 2020. Hypercubes are interconnection networks on which decontamination was solved before unknown graphs Flocchini et al. 2008; the complete graph \(K_3\) is the witness in Pelc's crash impossibility Pelc 2018; bipartite graphs appear with butterfly counting by agents Chand et al. 2025. Level 0 is an arbitrary connected graph, unknown to the agents.

The starting configuration is the adversary's last choice. Rooted starts come from exploration, where the team leaves a common home: collective tree exploration places all \(k\) agents at the root Fraigniaud et al. 2006, black hole search starts from a safe home base Dobrev et al. 2006, and Molla and Moses Jr. call this a rooted graph Molla & Moses Jr. 2019. Dispersed starts come from rendezvous and gathering, where agents start at distinct nodes Pelc 2019 Dieudonné & Pelc 2016, and from black hole search with scattered agents Di Luna et al. 2025. A dispersed configuration is also the output of dispersion, so tasks computed by agents after dispersing, such as leader election, start from it Kshemkalyani et al. 2026 Sudo et al. 2024. Dispersion itself was posed from arbitrary configurations, robots "placed in an n node graph arbitrarily" Augustine & Moses Jr. 2018, and rooted dispersion became a separate variant Molla & Moses Jr. 2019. The two special starts expose different symmetries: co-located agents are indistinguishable by position, so labels or coins must decide who moves Molla & Moses Jr. 2019; scattered agents have distinct positions that may still look alike in a symmetric graph Pelc 2019.