Home›Notation

Notation and assumptions

Each model uses the symbols of its own literature, so that a bound reads the same here as in the papers it comes from. Inside one model a symbol has exactly one meaning. The same letter may mean different things in different models (for example \(n\) counts nodes on graphs and robots in the plane); essays that cross models say which model a symbol belongs to. Where a paper writes a different symbol for the same quantity, the table says so under papers write. Symbols that a single paper defines for its own result are defined where they are used and listed under that problem.

General conventions · Mobile agents on graphs · Mobile robots in the plane · Search in geometric domains · Programmable matter · Index of assumptions

General conventions

Symbol	Meaning	Papers write
\(O, \Omega, \Theta, o, \omega\)	asymptotic notation, as \(n\) (or the stated parameter) grows; \(\tilde O\) hides polylogarithmic factors
\(\log\)	logarithm to base 2 unless stated
\(\varepsilon\)	an arbitrarily small positive real (a constant unless stated)
\(\kappa\)	a positive constant whose value does not matter for the statement
\(t\)	time: a round, or a point of time in an asynchronous execution
\(\text{round}\)	in synchronous settings (FSYNC, SSYNC, synchronous agents), one step in which every activated entity performs one full cycle
\(\text{epoch}\)	in asynchronous settings, an interval of time in which every entity completes at least one full cycle; it need not be the shortest such interval. The execution is divided into consecutive epochs, and a bound of \(X\) epochs holds for every such division. Programmable matter calls the same notion an asynchronous round

Symbols: Mobile agents on graphs

Symbol	Meaning	Papers write	Used in
\(G=(V,E)\)	the graph; for a directed graph \(E\) is a set of arcs, written \(G=(V,A)\) where both appear		whole model
\(n\)	number of nodes, \(n = \|V\|\)		whole model
\(m\)	number of edges (arcs)		whole model
\(\Delta\)	maximum degree		whole model
\(\Delta_{out}\)	maximum out-degree of a directed graph	\(d\) in some exploration papers	whole model
\(\deg(v),\ \deg_{out}(v)\)	degree and out-degree of node \(v\)	\(\delta(v)\), \(\delta_{out}(v)\)	whole model
\(D\)	diameter of the graph (for a tree explored from a root: its height)		whole model
\(u, v, w\)	nodes (local names)		whole model
\(s\)	the starting node of a single agent, the root of a rooted team, or the home base of black hole search and decontamination	\(h\) (home base), \(r\) (root)	whole model
\(k\)	number of agents		whole model
\(\ell\)	number of initially occupied nodes; \(\ell=1\) is a rooted start, \(\ell=k\) a dispersed start		Dispersion
\(f\)	maximum number of faulty agents (crashed or Byzantine)		whole model
\(N\)	a known upper bound on \(n\)	\(\hat n\)	whole model
\(\mathcal L\)	the set of agent labels in use; \(\|\mathcal L\|\) distinct labels, \(\|\mathcal L\|=1\) anonymous, \(\|\mathcal L\|=k\) distinct identifiers	\(\ell\) (homonyms)	whole model
\(L\)	the largest possible label: labels are integers in \(\{1,\dots,L\}\)	\(\lambda\) (largest identifier), \(\mu\) (largest label)	whole model
\(\lambda\)	the smallest label among the agents (for two agents: the smaller label)	\(l\) Pelc 2019	whole model
\(\tau\)	delay between the starting times of two agents		whole model
\(d\)	distance from the starting node to the target (the treasure), or between the starting nodes of two agents in rendezvous	\(D\) for the distance between starting positions Pelc 2019	whole model
\(v^*\)	the node of the treasure	\(t\)	whole model
\(e(d)\)	number of edges with an endpoint at distance less than \(d\) from the start		Treasure hunt
\(w(\cdot),\ W\)	weight of the cheapest path type to the treasure (treasure hunt); \(W\) its maximum over the two directions (rendezvous)		Treasure hunt, Rendezvous
\(h\)	communication range in hops (\(h\)-hop communication)	\(\ell\) Saxena et al. 2025	whole model
\(T\)	window length in \(T\)-interval and \(T\)-path connectivity of dynamic graphs		whole model
\(\mu\)	maximum number of edges missing in a round (\(\mu\)-bounded 1-interval connected graphs)	\(\ell\)-bounded Saxena et al. 2025	whole model
\(\eta\)	number of transient edges of a temporally connected graph		Exploration of dynamic graphs by teams
\(\delta\)	longest time an edge of a dynamic ring may be absent		Graph exploration by a single agent
\(p\)	number of pebbles		whole model
\(b\)	number of bits of an agent's memory, when it is a parameter		whole model
\(\beta\)	number of bits of a label written at a node in advance		Graph exploration by a single agent
\(\phi\)	deficiency of a directed graph: the number of arcs whose addition makes it Eulerian	\(d\) Italiano et al. 2022	Dispersion, Graph exploration by a single agent
\(\nu\)	number of leaves of a tree	\(\lambda\)	Rendezvous
\(\mathrm{CR}(k)\)	competitive ratio of a collaborative exploration algorithm with \(k\) agents		Collaborative exploration
\(X(n)\)	time to explore any \(n\)-node graph		Dispersion
\(\mathrm{port}_v\)	port numbering at node \(v\)	\(\lambda_v\)	Graph exploration by a single agent
\(R\)	running time, in rounds, of a message-passing algorithm simulated by agents		Leader election by agents, Maximal independent set by agents, Minimal dominating set by agents, Minimum spanning tree by agents, BFS tree by agents, Triangle and butterfly counting by agents
\(K\)	number of states of a finite-automaton agent		Graph exploration by a single agent, Exploration of recolourable graphs
\(\gamma\)	exponent of the team size in large-team collaborative exploration, \(k = Dn^{\gamma}\)		Collaborative exploration
\(\theta\)	the exponent of Reingold's universal exploration sequences		Treasure hunt
\((q,\rho)\)	type of a path: its largest port \(q\) and its length \(\rho\)		Treasure hunt
\(z\)	number of nodes of non-zero capacity		Dispersion
\(r\)	radius of a ball of the grid		Dispersion
\(c\)	number of colours (of a robot's light, or of the colours a node can hold)	\(\kappa\), \(\ell\)	Exploration by luminous robots, Exploration of recolourable graphs
\(\varphi\)	visibility range of a myopic robot, in hops		Exploration by luminous robots
\(a\times b\)	size of a grid or torus with \(a\) rows and \(b\) columns		Exploration by luminous robots
\(\psi(v)\)	current colour of node \(v\)	\(c(v)\)	Exploration of recolourable graphs
\(c_0\)	initial colour of the nodes		Exploration of recolourable graphs
\(\pi_v\)	rotor pointer at node \(v\): the port the next departing agent takes		Exploration of recolourable graphs
\(N(v)\)	the neighbours of node \(v\)		Exploration of recolourable graphs
\(\mathrm{circ}(G)\)	circumference of \(G\): the length of its longest cycle	\(k\)	Exploration of recolourable graphs
\(g\)	a known upper bound on the circumference		Exploration of recolourable graphs

Symbols: Mobile robots in the plane

Symbol	Meaning	Papers write	Used in
\(n\)	number of robots	\(N\) in some mutual visibility papers	whole model
\(f\)	maximum number of faulty robots (crashed or Byzantine)		whole model
\(\ell\)	number of distinct labels of homonymous robots; \(\ell=1\) anonymous, \(\ell=n\) distinct identifiers	\(h\)	whole model
\(c\)	number of colours of a light		whole model
\(V\)	visibility radius (limited visibility)		whole model
\(\delta\)	minimum distance a robot travels in a non-rigid move before the adversary may stop it		whole model
\(\Delta_0\)	diameter of the initial configuration	\(D_E\)	whole model
\(k\)	number of groups (\(k\)-grouping; in partitioning the number of fixed points, each receiving \(n/k\) robots)	Bhagat et al. 2021 write \(k\) for the group size of partitioning, which is \(n/k\) here	k-grouping, Partitioning, Separation
\(L\)	length (circumference) of the ring or circle	\(\ell\)	Uniform deployment on a ring
\(d\)	the target spacing \(L/n\) in uniform deployment		Uniform deployment on a ring
\(m\)	number of patterns in a sequence		Pattern sequences
\(\lambda\)	contraction factor of a \(\lambda\)-contracting gathering protocol		Gathering, Near-gathering
\(r, s\)	robots (local names)		whole model
\(g\)	hop diameter of the initial visibility graph	\(D_G\), \(D\)	Gathering, Scattering
\(\phi\)	expected running time function of scattering algorithm \(SA_\phi\)	\(f\)	Scattering

Symbols: Search in geometric domains

Symbol	Meaning	Papers write	Used in
\(k\)	number of robots	\(n\)	whole model
\(f\)	maximum number of faulty robots (crash or Byzantine)		whole model
\(m\)	number of rays sharing an endpoint		whole model
\(e\)	number of exits on the boundary		Chauffeuring a crashed robot
\(d\)	distance from the origin to the target on a line or on rays		whole model
\(x\)	position of the target on the line		whole model
\(R\)	radius of the disk (results are usually stated for \(R=1\))		whole model
\(v,\ v_i\)	speeds of robots (robot \(i\) moves at speed at most \(v_i\))	\(s\), \(s_i\)	whole model
\(\alpha\)	known arc distance along the boundary (between two exits, or between the treasure and the exit)	\(d\)	whole model
\(r\)	communication range of wireless robots		whole model
\(\ell\)	length of the fence (segment or circle)		Patrolling
\(L\)	known distance between the starting points of two robots		Evacuation
\(p\)	index of an \(\ell_p\) norm		Evacuation
\(w\)	weight of the second robot's arrival time in weighted group search		Evacuation
\(\sigma\)	number of servants in priority evacuation (the queen and \(\sigma\) servants, \(k=\sigma+1\) robots)	\(n\)	Evacuation

Symbols: Programmable matter

Symbol	Meaning	Used in
\(n\)	number of particles (modules, tiles)	whole model
\(D\)	diameter of the configuration (largest lattice distance between two particles)	whole model
\(L_{out},\ L_{max}\)	length of the outer boundary and of the longest boundary of the configuration	Leader election in programmable matter
\(\lambda\)	bias towards having more neighbours (stochastic approach)	whole model
\(\gamma\)	bias towards neighbours of the same colour (separation)	Separation of coloured particles
\(\alpha\)	compression factor: perimeter at most \(\alpha\) times the minimum	Compression
\(q\)	number of orientations (alignment)	Alignment
\(s\)	number of energy sources	Energy distribution
\(k\)	symmetricity of a configuration (a \(k\)-symmetric configuration admits up to \(k\) leaders)	Leader election in programmable matter

Index of assumptions

Every assumption the atlas uses, with its formal definition: the axes of each model, then the assumptions specific to single problems. Level 0 assumes nothing; each higher level is a stronger assumption. Where the assumptions come from is told on each model page.

Mobile agents on graphs

Graph dynamics Mobile agents on graphs

0any dynamics: A temporal graph is a sequence \(\mathcal G=(G_t)_{t\ge 0}\) with \(G_t=(V,E_t)\) on a fixed node set. It is temporally connected if for all \(u,v\in V\) and every time \(t\) there is a journey (a path whose edges appear at non-decreasing times \(\ge t\)) from \(u\) to \(v\). No \(G_t\) need be connected.
1connected every round explore →: \(\mathcal G=(G_t)_{t\ge0}\) is 1-interval connected if every snapshot \(G_t=(V,E_t)\) is connected. More generally it is \(T\)-interval connected if for every \(t\) the graph \(\bigl(V,\bigcap_{i=t}^{t+T-1}E_i\bigr)\) is connected.
2static graph explore →: \(G_t=G\) for all \(t\): the edge set never changes.

Edge direction Mobile agents on graphs

0directed: \(G=(V,A)\) with \(A\subseteq V\times V\); an agent at \(u\) may move along \((u,v)\in A\) only, never back along it unless \((v,u)\in A\). \(G\) is strongly connected.
1undirected explore →: \(G=(V,E)\) with \(E\subseteq\binom V2\); every edge can be traversed in both directions.

Number of agents Mobile agents on graphs

0any \(k\): The number of agents \(k\ge1\) is arbitrary; \(k>n\) is allowed.
1\(k \le n\) explore →: The number of agents satisfies \(1\le k\le n\).

Identifiers Mobile agents on graphs

0anonymous: All agents run the same deterministic algorithm on the same input; no agent has a label. Formally the label function is constant: \(\mathrm{id}(a)=\mathrm{id}(b)\) for all agents \(a,b\).
1homonymous explore →: Each agent \(a\) has a label \(\mathrm{id}(a)\in\mathcal L\) known to itself (and revealed on meeting), but the labelling need not be injective: \(1\le|\{\mathrm{id}(a)\}|\le k\). With \(|\mathcal L|\) distinct labels, \(|\mathcal L|=1\) is the anonymous case and \(|\mathcal L|=k\) the eponymous one Delporte-Gallet et al. 2013.
2distinct IDs (eponymous) explore →: Distinct identifiers (eponymous agents): the label function \(\mathrm{id}:\{1,\dots,k\}\to\{1,\dots,L\}\) is injective; usually \(L=k^{O(1)}\), so a label takes \(O(\log k)\) bits.

Randomness Mobile agents on graphs

0deterministic: The next state and move of an agent are a function of its current state and what it observes.
1private coins explore →: Each agent additionally has access to independent fair coin flips; guarantees hold with probability 1, in expectation, or with high probability, as stated per result.

Faults Mobile agents on graphs

0any faults: Up to \(f\) agents behave arbitrarily (adversarially) and may forge identifiers, i.e. report any label in \(\mathcal L\).
1at most weak Byzantine faults explore →: Up to \(f\) agents behave arbitrarily but always report their own true identifier.
2at most crash faults explore →: Up to \(f\) agents may stop forever at an adversarially chosen time; a crashed agent stays at its node (or vanishes, as stated per result) and never acts again.
3no faults explore →: All agents follow the algorithm forever.

Communication Mobile agents on graphs

0no communication: Agents exchange no messages; an agent at \(v\) observes only the number of agents at \(v\) (and, where stated, whether that number changed).
1local communication explore →: Agents at the same node at the same time can read each other's entire memory (face-to-face communication). Agents crossing on an edge do not meet.
2\(h\)-hop communication explore →: For a fixed \(h \ge 1\), stated with each result: at every round an agent at \(v\) can read the memory of every agent at a node \(u\) with \(\mathrm{dist}(v,u) \le h\) (in the current snapshot \(G_t\) for a dynamic graph), in addition to the co-located agents. \(h = 1\) is 1-hop communication (agents at neighbouring nodes communicate); local communication is the case \(h = 0\), and global communication the case \(h \ge D\). Reading another agent's memory does not tell an agent which port leads to it.
3global communication explore →: At every round every agent can read the memory of every other agent, wherever it is.

Timing Mobile agents on graphs

0asynchronous: Each agent's Communicate–Compute–Move steps take finite but unbounded, adversarially chosen time. Time is measured in epochs. An epoch is an interval of time in which every agent completes at least one full Communicate–Compute–Move step; it need not be the shortest such interval. Time is counted by dividing the execution into consecutive epochs, and a bound of \(X\) epochs holds for every such division.
1synchronous explore →: Time proceeds in rounds \(t=1,2,\dots\); in every round every agent communicates, computes and moves (at most one edge) simultaneously.

Node memory Mobile agents on graphs

0no whiteboards: Nodes have no storage: no information can be left at a node except by an agent staying there.
1whiteboards explore →: Each node \(v\) has a whiteboard of bounded size that agents at \(v\) can read and write, with mutual exclusion.

Node identifiers Mobile agents on graphs

0anonymous nodes: Nodes have no identifiers; an agent at \(v\) sees only \(\deg(v)\) and the port numbers \(1,\dots,\deg(v)\), which are assigned locally and independently at each endpoint of an edge.
1labelled nodes explore →: Each node \(v\) carries a distinct identifier that agents at \(v\) can read; hence an agent can recognise a node it has visited.

Topology Mobile agents on graphs

0any topology: \(G\) is any connected graph in the class allowed by the other axes.
1ring explore →: \(G\) is a cycle \(C_n\) (every node of degree 2), or a path when stated.
1tree explore →: \(G\) is connected and acyclic: \(|E|=n-1\).
1grid explore →: \(G\) is a \(\sqrt n\times\sqrt n\) grid graph; whether ports are globally consistent (oriented) is stated per result.
1complete graph explore →: \(G=K_n\): every pair of nodes is adjacent.
1hypercube explore →: \(G=Q_j\): nodes are the \(n=2^j\) binary strings of length \(j\), adjacent when they differ in one bit.
1bipartite explore →: \(V = V_1 \cup V_2\) with \(V_1 \cap V_2 = \emptyset\) and every edge joining \(V_1\) to \(V_2\); trees are a special case.

Initial configuration Mobile agents on graphs

0any start: Agents start at arbitrary nodes; \(\ell\le k\) nodes are initially occupied, possibly with several agents each.
1rooted start explore →: All \(k\) agents start at the same node (\(\ell=1\)). Also called co-located (black hole search: all agents at the home base) or a rooted graph Molla & Moses Jr. 2019.
1dispersed start explore →: Every initially occupied node holds exactly one agent (\(\ell=k\)). Also called a scattered start, notably in black hole search.

Specific to Graph exploration by a single agent

Knowledge Graph exploration by a single agent

0nothing known: The agent knows nothing about \(G\): not \(n\), \(m\), \(\Delta\) or \(D\).
1knows a bound on \(n\) explore →: The agent is given an integer \(N\ge n\) (an upper bound on the number of nodes) as input.
2knows the map explore →: The agent is given a graph isomorphic to \(G\), with port numbers, and (where stated) its own position on it; for a dynamic graph, the whole sequence \((G_t)\).

Markers Graph exploration by a single agent

0no markers: The agent cannot mark nodes.
1one pebble explore →: The agent carries one pebble that it can drop at its current node and later pick up; it sees whether a pebble is at its node.
2pebbles explore →: The agent carries \(p\) pebbles (identical or distinguishable, as stated); \(p\) is a resource reported with the memory.

Preprocessing Graph exploration by a single agent

0adversarial ports: Port numbers (and any node labels) are chosen by an adversary.
1designer ports explore →: Before the agent starts, the designer may choose the port numbering \(\mathrm{port}_v:\{\text{edges at }v\}\to\{1,\dots,\deg(v)\}\) at every node. Ilcinkas calls a designer's port numbering a local orientation Ilcinkas 2008.
1designer labels explore →: Before the agent starts, the designer may write a label of \(b\) bits (a constant) at every node, which the agent reads on arrival.

Termination requirement Graph exploration by a single agent

0with return: The agent visits every node and then halts at its start node \(s\).
1with stop explore →: The agent visits every node and then halts, at any node. Also called terminating exploration.
2perpetual explore →: Every node is visited at least once (and, for periodic exploration, infinitely often); the agent never needs to halt.

Specific to Collaborative exploration

Team size Collaborative exploration

0any \(k\): Any number \(k\ge 2\) of agents.
1\(k = n\) explore →: Exactly \(k=n\) agents.
1\(k \ge Dn^{1+\varepsilon}\) explore →: \(k\ge D\,n^{1+\varepsilon}\) agents for a constant \(\varepsilon>0\) (written \(k=Dn^\gamma\), \(\gamma>1\)).

Specific to Treasure hunt

Graph size Treasure hunt

0infinite degrees allowed: \(G\) is finite or countably infinite; a node may have countably infinite degree (ports \(1,2,3,\dots\)).
1locally finite explore →: \(G\) is finite or countably infinite, and every node has finite degree.
2finite graph explore →: \(G\) has finitely many nodes.

External help Treasure hunt

0no help: No information beyond the agent's own observations.
1advice explore →: An oracle that knows the whole instance gives the agent a binary string before it starts; its length (in bits) is the measure.
1oracle pebbles explore →: An oracle that knows the instance places pebbles on nodes (at most one per node) before the agent starts; their number is the measure.

Specific to Rendezvous

Graph size Rendezvous

0infinite degrees allowed: \(G\) is finite or countably infinite; degrees may be infinite.
1locally finite explore →: \(G\) is finite or countably infinite with finite degrees.
2finite graph explore →: \(G\) has finitely many nodes.

Start Rendezvous

0any delay: An adversary wakes the agents at times \(t_1\) and \(t_2\); the delay \(\tau=|t_1-t_2|\) is unknown.
1simultaneous start explore →: Both agents start in the same round (\(\tau=0\)).

Specific to Black hole search

Knowledge of the graph Black hole search

0topology unknown: Agents know \(n\) but not the topology of \(G\).
1sense of direction explore →: Agents have a consistent sense of direction: a globally consistent labelling of edges from which they can tell whether two walks lead to the same node.
2map explore →: Agents have a map of \(G\) and know their starting position on it.

Marking nodes Black hole search

0no marking: Agents cannot leave information at nodes.
1tokens explore →: Agents carry tokens (pebbles) they can place at nodes or on ports; tokens are identical and carry no other information.
2whiteboards explore →: Every node has a whiteboard that agents read and write under mutual exclusion.

Specific to Map construction

Agents Map construction

0one agent: A single agent.
1several agents explore →: \(k\ge2\) identical agents.

Knowledge Map construction

0nothing known: Nothing is known about \(G\).
1bound on \(n\) explore →: An upper bound \(N\ge n\) is known.

Markers Map construction

0no markers: No markers.
1markers explore →: The agent carries markers it can drop and pick up.

Whiteboards Map construction

0no whiteboards: No whiteboards.
1whiteboards explore →: Each node has a whiteboard.

Specific to Leader election by agents

Knowledge Leader election by agents

0no knowledge: Agents know no graph parameter (\(n\), \(m\), \(\Delta\), \(D\)).
1knows \(n\), \(\Delta\) explore →: Every agent knows \(n\) and \(\Delta\) (upper bounds suffice where stated).

Specific to Maximal independent set by agents

Knowledge Maximal independent set by agents

0no knowledge: Agents know no graph parameter (\(n\), \(m\), \(\Delta\), \(D\)).
1knows \(n\), \(\Delta\) explore →: Every agent knows \(n\) and \(\Delta\) (upper bounds suffice where stated).

Specific to Minimal dominating set by agents

Knowledge Minimal dominating set by agents

0no knowledge: Agents know no graph parameter (\(n\), \(m\), \(\Delta\), \(D\)).
1knows \(n\), \(\Delta\) explore →: Every agent knows \(n\) and \(\Delta\) (upper bounds suffice where stated).

Specific to Triangle and butterfly counting by agents

Knowledge Triangle and butterfly counting by agents

0no knowledge: Agents know no graph parameter (\(n\), \(m\), \(\Delta\), \(D\)).
1knows \(n\), \(\Delta\) explore →: Every agent knows \(n\) and \(\Delta\) (upper bounds suffice where stated).

Specific to Minimum spanning tree by agents

Knowledge Minimum spanning tree by agents

0no knowledge: Agents know no graph parameter (\(n\), \(m\), \(\Delta\), \(D\)).
1knows \(n\), \(\Delta\) explore →: Every agent knows \(n\) and \(\Delta\) (upper bounds suffice where stated).

Specific to BFS tree by agents

Knowledge BFS tree by agents

0no knowledge: Agents know no graph parameter (\(n\), \(m\), \(\Delta\), \(D\)).
1knows \(n\), \(\Delta\) explore →: Every agent knows \(n\) and \(\Delta\) (upper bounds suffice where stated).

Specific to Network decontamination

Knowledge Network decontamination

0unknown graph: Agents know nothing about \(G\).
1known graph explore →: The topology is known to the agents (or to a coordinator).

Specific to Exploration by luminous robots

Scheduler Exploration by luminous robots

0ASYNC: ASYNC: each robot's Look, Compute and Move phases take finite but unbounded, adversarially chosen time; a robot may Look while others are between phases, so it may move on an outdated snapshot. A robot is always seen on a node (an edge traversal is instantaneous), and its new colour is visible from the end of its Compute phase. The scheduler is fair: every robot is activated infinitely often. Called CORDA in Datta et al. 2013.
1SSYNC explore →: SSYNC: time is divided into rounds; in each round a fair adversary chooses a non-empty subset of robots, which execute one atomic Look–Compute–Move cycle together. Called ATOM in Datta et al. 2013.
2FSYNC explore →: FSYNC: in every round every robot executes one atomic Look–Compute–Move cycle.

Lights (memory and messages) Exploration by luminous robots

0oblivious: OBLOT: a robot's Compute phase depends only on the current snapshot; nothing persists across cycles and robots communicate only by moving. Equivalent to a light with \(c = 1\) colour.
1FSTA explore →: FSTA (finite-state): each robot has a light with \(c\) colours that only it can see. The colour is set at the end of Compute and persists until the robot changes it: \(\log_2 c\) bits of persistent memory, no communication Flocchini et al. 2016.
1FCOM explore →: FCOM (finite-communication): each robot has a light with \(c\) colours that the other robots within distance \(\varphi\) can see but the robot itself cannot; the robot stays oblivious, but every robot that looks reads its last colour: \(\log_2 c\) bits broadcast to the neighbourhood, no memory Flocchini et al. 2016.
2luminous explore →: LUMI (luminous robots): each robot has a light with \(c\) colours, set at the end of Compute, persistent across cycles, and visible to the robot itself and to every robot within distance \(\varphi\) Das et al. 2016. It is both memory and message. A Look returns, for every node within distance \(\varphi\), the multiset of colours of the robots on it.

Visibility range Exploration by luminous robots

0\(\varphi=1\): In a Look phase a robot at node \(v\) sees every node at distance at most \(\varphi = 1\) from \(v\) (in the graph metric), with the robots on it, their colours, and how many robots each node holds. It sees no node identifiers and, without chirality, no orientation.
1\(\varphi=2\) explore →: As for \(\varphi = 1\), but the robot sees every node at distance at most \(\varphi = 2\). An algorithm for \(\varphi = 2\) works for every larger \(\varphi\), since a robot can ignore what lies further away.
2\(\varphi=3\) explore →: As for \(\varphi = 1\), but the robot sees every node at distance at most \(\varphi = 3\).

Chirality Exploration by luminous robots

0no chirality: Robots share no orientation: on a ring a robot cannot tell its two directions apart; on a grid or torus its snapshot is known only up to rotation and reflection, and the adversary may choose a different transformation in every cycle (self-inconsistent robots, as in Darwich et al. 2023 and Bramas et al. 2026).
1chirality explore →: All robots agree on the clockwise direction: a snapshot is known up to rotation only (no reflection), so a robot on an axis of symmetry of its view can still tell its two sides apart. Robots still share no North.

Exploration goal Exploration by luminous robots

0both goals: Solve both terminating and perpetual exploration with the stated resources (possibly with two algorithms). A lower bound for either goal holds here, and a result here gives both. No variant is catalogued here; the value exists because the two goals do not imply each other.
1terminating explore →: Every node is visited by at least one robot, and from some time on no robot is enabled (no robot changes its position or colour again).
1perpetual explore →: Every node is visited by at least one robot infinitely often; robots never stop.

Network Exploration by luminous robots

0any graph: A finite, connected, anonymous graph \(G=(V,E)\) with \(n\) nodes and no port numbers visible to the robots.
1ring explore →: An anonymous, unoriented ring of \(n\) nodes; \(n\) is unknown to the robots.
1grid explore →: An \(a \times b\) grid (\(n = ab\) nodes; nodes \((i,j)\), edges between nodes at Manhattan distance one); anonymous, with \(a\) and \(b\) unknown. A robot sees the border of the grid when it is within range, since nodes beyond the border are missing from its snapshot.
1torus explore →: An \(a \times b\) torus: the grid with wrap-around edges in both dimensions, so every node has degree four and there is no border.

Specific to Exploration of recolourable graphs

Port numbers Exploration of recolourable graphs

0no ports: Edges carry no port numbers. To move, the agent at \(v\) names a colour \(x\); the adversary moves it to any neighbour \(u\) of \(v\) with \(\psi(u) = x\) (if the agent sees no neighbour colours, to any neighbour). The agent never learns by which edge it arrived.
1ports, no entry port explore →: The edges at \(v\) carry port numbers \(1,\dots,\deg(v)\), assigned by an adversary independently at each endpoint (\(\mathrm{port}_v\)). The agent chooses the port by which it leaves, but on arrival it is not told the port by which it entered (unknown inport).
2ports + entry port explore →: As for port numbers, and on arrival at \(v\) the agent also reads the port \(\mathrm{port}_v(e)\) of the edge \(e\) by which it entered. This is the standard convention of single-agent exploration.

View Exploration of recolourable graphs

0own node: At node \(v\) the agent observes \(\psi(v)\), \(\deg(v)\) and nothing about its neighbours (and, where ports exist, what the port axis grants).
1neighbour colours explore →: At node \(v\) the agent observes \(\psi(v)\) and the multiset \(\{\!\{\psi(u) : u \in N(v)\}\!\}\) of its neighbours' colours (hence also \(\deg(v)\)), without knowing which edge leads to which colour unless ports say so.

Agent memory Exploration of recolourable graphs

0oblivious: The agent has no internal state: its action (new colour of \(v\), then a move, stay or stop) is a function of its current observation only. Called zero-memory, memoryless or a 1-state robot.
1finite automaton explore →: The agent is a deterministic automaton with \(K\) states, \(K\) independent of the graph; its action and next state depend on its state and its observation.
2\(O(\log n)\) bits explore →: The agent has \(b = O(\log n)\) bits of memory, enough to hold a counter up to a polynomial in \(n\). No variant is catalogued here yet.

Recolouring Exploration of recolourable graphs

0fixed colours: The colouring \(\psi : V \to \{1,\dots,c\}\) never changes; the agent reads \(\psi(v)\) (and, with neighbour view, its neighbours' colours) but cannot write.
1colour once explore →: Every node starts with the initial colour \(c_0\). The agent at \(v\) may change \(\psi(v)\) only while \(\psi(v) = c_0\); once \(v\) has a colour other than \(c_0\) it keeps it forever. This is the main model of Böckenhauer et al. 2023.
2recolourable explore →: At every step the agent at \(v\) may set \(\psi(v)\) to any colour of the palette, including back to \(c_0\), any number of times (the convention of Takahashi et al. 2026 and Hiraoka et al. 2026).

Initial colouring Exploration of recolourable graphs

0arbitrary colours: The initial colouring \(\psi_0 : V \to \{1,\dots,c\}\) is chosen by the adversary; an algorithm must work from every \(\psi_0\) (as with a rotor-router whose pointers are set arbitrarily).
1uniform \(c_0\) explore →: Initially \(\psi(v) = c_0\) for every node \(v\) (clean node memory). The colour \(c_0\) counts as one of the \(c\) colours.
2designer's colours explore →: Before the agent starts, a designer who knows \(G\) (and the start node) chooses \(\psi_0\). Used with fixed colours this is label-guided exploration Cohen et al. 2008.

Knowledge Exploration of recolourable graphs

0nothing known: The algorithm is the same for all graphs: it knows neither \(n\) nor \(\Delta\) nor any other parameter (a uniform algorithm in Böckenhauer et al. 2023).
1\(n\) known explore →: The algorithm may depend on \(n\): it must explore every graph with exactly \(n\) nodes (a non-uniform algorithm).

Termination requirement Exploration of recolourable graphs

0return: The agent visits every node and then halts at its start node \(s\) (exploration with return).
1stop explore →: The agent visits every node and then halts, at any node.
2perpetual explore →: Every node is visited at least once (for the rotor-router: infinitely often); the agent never needs to halt.

Network Exploration of recolourable graphs

0any graph: A finite, simple, connected, undirected, anonymous graph \(G = (V,E)\) with \(n\) nodes.
1cactus explore →: \(G\) is a cactus: every edge lies on at most one cycle (equivalently, every block is a cycle or a single edge).
2tree explore →: \(G\) is a tree (a cactus without cycles).

Mobile robots in the plane

Body Mobile robots in the plane

0fat: Each robot is a closed disc of radius 1 (unit disc). Discs may not overlap, so robots cannot share a point and must avoid collisions; a disc hides what lies behind it from other robots. Gathering then asks for a configuration whose union of discs is connected and in which every robot sees all others Czyzowicz et al. 2009.
1point explore →: Each robot is a point of the plane: several robots may share a point (multiplicity), and a robot hides only what lies exactly behind it on a line of sight.

Scheduler Mobile robots in the plane

0ASYNC: ASYNC: each robot's Look, Compute and Move phases take finite but unbounded, adversarially chosen time; a robot may look while others move, and compute on an outdated snapshot. Time is counted in epochs: an epoch is an interval of time in which every robot completes at least one full Look–Compute–Move cycle; it need not be the shortest such interval. The execution is divided into consecutive epochs, and a bound of \(X\) epochs holds for every such division. In FSYNC and SSYNC time is counted in rounds. Called Corda by Prencipe Prencipe 2007. Intermediate variants restrict interleavings: LC-atomic (no Look by another robot between a robot's Look and its Compute), Move-atomic (no Look during another robot's Move) and CM-atomic Flocchini et al. 2023.
1SSYNC explore →: SSYNC: time is divided into rounds; in each round a non-empty subset of robots, chosen by a fair adversary, executes one atomic Look–Compute–Move cycle. Called Atom by Prencipe Prencipe 2007.
2sequential explore →: Sequential: an SSYNC scheduler that activates exactly one robot per round (fairly). Also called a centralized scheduler Terai et al. 2023; a round-robin scheduler is a fair special case.
2FSYNC explore →: FSYNC: every robot executes one atomic cycle in every round.

Lights (persistent memory) Mobile robots in the plane

0oblivious: OBLOT: a robot's computation depends only on the current snapshot; nothing persists across cycles.
1internal light (FSTA) explore →: FSTA: each robot has a light with \(c\) colours that only it can see; it persists between cycles (constant persistent memory, no communication). Also called an internal light.
1external light (FCOM) explore →: FCOM: each robot has a light with \(c\) colours that only the others can see (constant communication, no persistent memory of its own). Also called an external light.
2lights (LUMI) explore →: LUMI: each robot has a light with \(c\) colours, set at the end of Compute, visible to all robots including itself; it is both memory and communication. Also called luminous robots, or a full light.

Agreement on coordinates Mobile robots in the plane

0disoriented: Each robot \(r\) observes in its own coordinate system, obtained from the global one by an unknown similarity (translation, rotation, uniform scaling, and possibly reflection); systems may differ between robots and, in some models, between cycles. Papers that call robots disoriented do not always mean this: Défago and Souissi use the word while assuming chirality Défago & Souissi 2008. Some papers also let the adversary change a robot's rotation, reflection and unit at every Look (variable disorientation) Flocchini et al. 2023 Masuzawa et al. 2026.
1chirality explore →: All local coordinate systems have the same handedness (clockwise orientation): no reflection. Also called handedness. Prencipe uses chirality for agreement on North and East, i.e. a compass Prencipe 2007.
1one axis explore →: All robots agree on the direction and orientation of one axis (e.g. North), but not necessarily on handedness: two robots may disagree on which side is East. This is how the papers use one axis agreement (e.g. robots "agree on only 'left' and 'right'" Bose et al. 2021; robots "do not necessarily have the same handedness" Pagli et al. 2015). One axis and chirality are alternatives on this axis; together they amount to a common compass.
2compass explore →: All robots agree on the directions and orientations of both axes (a common compass); they may still disagree on origin and unit. Called full compass by Efrima and Peleg, who also use half compass (both axis directions, the positive sense of one axis, no chirality), direction-only and axes-only Efrima & Peleg 2009. Agreement on one axis together with common chirality is equivalent: the orientation of the second axis then follows from handedness.

Movement Mobile robots in the plane

0non-rigid: In a Move phase the adversary may stop a robot before its destination, but only after it has travelled at least \(\delta>0\) (a constant unknown to the robots) or reached the destination.
1rigid explore →: Every Move phase ends at the computed destination.

Multiplicity detection Mobile robots in the plane

0no multiplicity detection: A snapshot is a set of points: a point occupied by several robots looks like a single robot.
1weak multiplicity explore →: A snapshot marks each occupied point as holding one robot or more than one.
2strong multiplicity explore →: A snapshot is a multiset: each occupied point comes with the exact number of robots on it.

Visibility Mobile robots in the plane

0limited visibility: A robot sees exactly the robots within Euclidean distance \(V\) of its position, for a fixed radius \(V>0\).
1unlimited visibility explore →: A robot sees all robots (subject to opacity).

Opacity Mobile robots in the plane

0opaque: Robots are points that obstruct sight: \(r\) sees \(s\) iff no third robot lies on the open segment \(\overline{rs}\).
1transparent explore →: Robots do not obstruct each other's view.

Faults Mobile robots in the plane

0Byzantine: Up to \(f\) robots move arbitrarily (adversarially); with lights, they may also set arbitrary colours.
1crash faults explore →: Up to \(f\) robots stop forever at adversarial times and remain visible at their last position.
2no faults explore →: All robots follow the algorithm forever.

Randomness Mobile robots in the plane

0deterministic: The destination computed in a cycle is a function of the snapshot (and the light, if any).
1randomized explore →: Robots may use random bits in Compute; guarantees hold with probability 1 or in expectation, as stated per result.

Identifiers Mobile robots in the plane

0anonymous: Robots are indistinguishable and run the same algorithm.
1homonymous explore →: Robots carry labels from a set of size \(\ell\), \(1\le\ell\le n\), which may repeat; equivalently, robots may run one of \(\ell\) algorithms. The minimum \(\ell\) that solves a problem is its minimum algorithm size Asahiro & Yamashita 2025.
2distinct IDs (eponymous) explore →: Distinct identifiers (eponymous robots): labels are pairwise distinct (\(\ell=n\)); whether others can see a robot's label is stated per result.

Specific to Gathering

Number of robots Gathering

0any \(n\): Any number \(n\ge 2\) of robots.
1\(n = 2\) explore →: Exactly two robots (rendezvous).
1\(n \ge 3\) explore →: \(n\ge 3\) robots.

Search in geometric domains

Communication Search in geometric domains

0face-to-face: Face-to-face: two robots exchange information only when they are at the same point at the same time.
1sender/receiver explore →: Sender/receiver: one robot can only transmit and the other only receive, instantly at any distance.
2wireless explore →: Wireless: every robot can send messages to every other robot instantly at any distance.

Faults Search in geometric domains

0Byzantine: Up to \(f\) robots may lie: stay silent when they find the target, or claim to have found it where it is not.
1crash faults explore →: Up to \(f\) robots may fail to detect or to report the target when they pass over it.
2no faults explore →: Every robot detects and reports the target.

Speeds Search in geometric domains

0distinct speeds: Each robot \(i\) has its own maximum speed \(v_i\), known to all.
1equal speeds explore →: All robots move at most at unit speed.

Randomness Search in geometric domains

0deterministic: Trajectories are fixed functions of the information received.
1randomized explore →: Trajectories may depend on random choices; the measure is the expected competitive ratio against an oblivious adversary.

Specific to Linear search (cow path)

Domain Linear search (cow path)

0\(m\) rays: \(m\ge2\) half-lines sharing their endpoint, the origin, where the robots start.
1line explore →: The real line, robots start at \(0\); the target is at an unknown \(x\) with \(|x|\ge1\).

Number of robots Linear search (cow path)

0any \(k\): \(k\ge1\) robots.
1one robot explore →: A single robot.
1two robots explore →: Two robots.

Goal Linear search (cow path)

0evacuation: The task ends when every robot has reached the target.
1search explore →: The task ends when the first robot reaches the target (and, with faults, the others can be sure of it).

Specific to Evacuation

Domain Evacuation

0any domain: A bounded convex domain, robots start at an interior point.
1disk explore →: The unit disk; robots start at its centre; the exit is a point of the boundary circle.
1triangle explore →: The equilateral triangle of unit side; robots start at its centroid; the exit is a point of the boundary.
1square explore →: The unit square; robots start at its centroid; the exit is a point of the boundary.
1line explore →: The robots start at the origin of the real line; the exit is at an unknown point at distance at least \(1\); the measure is the competitive ratio, the evacuation time divided by that distance.
1rays explore →: \(m \ge 2\) half-lines share an endpoint, the junction; the exit lies on one ray at distance at least \(1\) from the start; the measure is the competitive ratio.

Number of robots Evacuation

0any \(k\): \(k\ge1\) robots.
1two robots explore →: Two robots.
1three robots explore →: Three robots.

Goal Evacuation

0all robots: The task ends when the last robot reaches the exit.
1priority (queen) explore →: One designated robot (the queen) must reach the exit; the others (servants) only help; the task ends when the queen exits.
1search-and-fetch explore →: A treasure lies at an unknown point of the boundary, and the exit at a known arc distance \(\alpha\) from it; the task ends when some robot has carried the treasure to the exit.

Exits Evacuation

0one exit: One exit, at an unknown point of the boundary.
1two exits explore →: Two exits at unknown points of the boundary; the task ends when every robot has reached one of them.

Specific to Patrolling

Fence Patrolling

0graph: Every point of every edge of a graph \(G\) must be visited; robots move along edges.
1segment explore →: An open fence: the segment \([0,\ell]\); robots may reverse direction anywhere.
1circle explore →: A closed fence: a circle of length \(\ell\).

Specific to Chauffeuring a crashed robot

Exits Chauffeuring a crashed robot

0\(e\) exits: \(e\ge1\) exits at unknown boundary points.
1one exit explore →: Exactly one exit.
1two exits explore →: Exactly two exits.

Programmable matter

Orientation Programmable matter

0no orientation: Each particle labels its six incident directions in its own clockwise or counter-clockwise order, starting anywhere.
1chirality explore →: All particles agree on clockwise order, not on a common direction.
1common direction explore →: All particles agree on one lattice direction, not on handedness. Chalopin, Das and Kokkou call this a common direction Chalopin et al. 2026, but the same words mean agreement on all six directions in other papers Chalopin et al. 2026 Navarra & Piselli 2023.
2common compass explore →: All particles agree on all six directions.

Scheduler Programmable matter

0weak scheduler: An activation's look, compute and move need not be atomic; concurrent activations may interfere. The scheduler of Bazzi and Briones is described as weak sequential, as non-atomic, and as fair asynchronous by different later papers Briones et al. 2023 Dufoulon et al. 2021 Chalopin et al. 2026.
1strong scheduler explore →: Each activation is executed atomically; the adversary chooses the order, fairly.
2sequential explore →: At most one particle is active at any time.

Memory Programmable matter

0oblivious: No persistent state and no messages; a particle decides from its view only.
1constant memory explore →: Each particle has \(O(1)\) bits of persistent memory and reads or writes neighbours' memory.

Randomness Programmable matter

0deterministic: No random choices.
1randomized explore →: Particles flip fair coins; guarantees hold with high probability or in expectation.

Initial shape Programmable matter

0holes allowed: The initial set of occupied nodes induces a connected subgraph; it may enclose empty regions.
1no holes explore →: The initial configuration is connected and encloses no empty node. Also called contractible Briones et al. 2023 or hole-free Gastineau et al. 2019.

Connectivity during execution Programmable matter

0stays connected: At every time the occupied nodes induce a connected subgraph.
1may disconnect explore →: Connectivity is required only initially and at the end.

Specific to Leader election in programmable matter

Movement Leader election in programmable matter

0stationary: No particle ever expands or contracts; the configuration is fixed and only states change.
1may move explore →: Particles may expand and contract during the election.

Specific to Shape formation by hybrid programmable matter

Space Shape formation by hybrid programmable matter

03D: Tiles occupy nodes of the face-centred cubic lattice; planar structures are a special case.
12D explore →: Tiles occupy nodes of the triangular lattice.

Specific to Centralised transformations of modular robots

Mechanism Centralised transformations of modular robots

0rotation: A module may rotate \(90°\) around an adjacent module, if the cells it sweeps are empty.
1rotation + sliding explore →: In addition, a module may slide one cell along a line of modules.