Mobility Matters
Home›Mobile agents on graphs›Computing with agents›Deciding graph properties by mobile agents

Deciding graph properties by mobile agents

Agents in an anonymous graph must decide together whether their starting configuration has a property, such as "the graph is a tree": which properties can they decide, with what help, and with how little memory?

Problem statement and measurescollapse
12121212121212121212121212pathcycleit sees: a node with 2 edges, ports 1 and 2entered by port 2; this node has 2 edges, ports 1 and 2entered by port 2; this node has 2 edges, ports 1 and 2entered by port 1; this node has 2 edges, ports 1 and 2answers yes: rightanswers yes: wrongaaaStart: the same agent at the middle of a path of 2t + 3 = 9 nodes, or on a cycleRound 1: port 1 in both graphs; it sees the sameRound 2: port 1 again; the ends of the path are still out of reachFinal, round t = 3: same view in both, so the same answer, wrong in one
Why agents cannot decide whether the graph is a path Fraigniaud & Pelc 2017: a lone agent, which cannot know that it is alone, must answer after some number \(t\) of rounds (here \(t = 3\); the ports it takes stand for any algorithm). Placed at the middle of a path of \(2t+3\) nodes with port 1 to the right and port 2 to the left, or on a cycle with port 1 clockwise and port 2 counter-clockwise, it sees exactly the same in every round, since the ends of the path are \(t + 1\) edges away. So it gives the same answer on both graphs, and that answer is wrong on one of them. A certificate stating the number of nodes would let it check the answer.

\(k \ge 1\) agents start at nodes of a connected undirected graph \(G\) with \(n\) nodes; the nodes are anonymous, and at each node the edges carry distinct port numbers. Each agent has a distinct identifier and an input string, and several agents may start at the same node. The agents move in synchronous rounds, crossing at most one edge per round, cannot mark nodes unless a setting gives whiteboards, and exchange everything they know when they are at the same node; no agent knows anything else in advance. A configuration is the graph with the agents' start nodes and inputs. A decision problem \(\Pi\) is a set of configurations, closed under automorphisms of \(G\) that preserve ports, whose membership a centralised algorithm that sees the whole configuration can decide. The agents decide \(\Pi\) if every agent eventually outputs yes or no, all agents output yes when the configuration is in \(\Pi\), and at least one outputs no when it is not Fraigniaud & Pelc 2017. In verification every agent also receives a certificate: for every configuration in \(\Pi\) some certificate makes all agents output yes, and for every other configuration no certificate does. The question is which decision problems the agents can decide, in particular whether all of them, and with how much memory. Time is in rounds; memory in bits per agent.

Measures: Time, rounds until every agent has decided; Memory, bits per agent.

A first look

the basic problem, a simple algorithm and why some things cannot be done, for a newcomer

Imagine a few explorers lowered into a cave system they cannot see. Each must eventually answer yes or no to a question about the caves and the explorers in them, such as "do the caves form a single corridor?" The caves are a graph: chambers are nodes and tunnels are edges. The nodes have no names, but at each node the edges carry distinct port numbers, so an explorer can tell the exits apart. The explorers are agents, each with a distinct identifier and an input string; several may start on the same node. They move in synchronous rounds, crossing at most one edge per round. They cannot mark nodes, unless a setting gives every node a whiteboard, a small memory that agents there can read and write. They tell each other everything when they meet. The configuration is the graph with the agents' start nodes and inputs. A decision problem is a property of configurations that a computer seeing the whole configuration could check, such as "the graph is a tree". The agents decide it if every agent eventually answers, all agents answer yes when the configuration has the property, and at least one answers no when it does not. In verification every agent also receives a certificate, a string that can make all agents answer yes only when the true answer is yes. In the standard version the agents know nothing in advance, not even how many they are, and receive no certificate. The question is which decision problems they can decide, and with how much memory.

1ImpossibilityA lone agent cannot tell a long path from a cycle Any number of agents → Fraigniaud & Pelc 2017

Take the decision problem "is the graph a path?", a path being nodes in a row. A computer that sees the graph answers it at once.

  1. Put a single agent on an endless path whose edges carry port 1 to the right and port 2 to the left at every node. Every algorithm must make the agent answer after some number of rounds \(t\).
  2. Now place the agent at the middle node of a path of \(2t+3\) nodes numbered the same way, or on a cycle with port 1 clockwise and port 2 counter-clockwise.
  3. The ends of the path are \(t+1\) edges away, so in \(t\) rounds the agent never reaches them. On both graphs it sees, round after round, a node with two edges numbered 1 and 2, exactly as on the endless path.
  4. It cannot wait for help either, since it cannot know whether other agents exist.
Why it holds. So the agent gives the same answer, after the same \(t\) rounds, on both graphs, and that answer is wrong on one of them Fraigniaud & Pelc 2017. The same holds for "is the graph a tree?" and "does the graph have exactly \(x\) nodes?". Not every problem that a computer can decide can be decided by agents; Fraigniaud and Pelc call those that can be decided \(\mathsf{MAD}\). A certificate helps here: given the number of nodes as certificate, the agents can check that the graph is a path, so this problem can be verified though not decided.

Why it matters. It is the basic limit of agents in anonymous graphs: what they cannot reach they cannot see, and a lone agent cannot know when it has seen enough.

2AlgorithmKnowing the number of agents: gather, draw a map, decide Two or more agents that know their number → Fraigniaud & Pelc 2017

Suppose every agent knows the number \(k \ge 2\) of agents.

  1. The agents gather on one node. They try ever larger guesses of \(n\) and of the length of the identifiers, and for each guess run a procedure that makes agents meet. Since they know \(k\), they know when all of them are together.
  2. The agent with the largest identifier draws a map of the graph, using another agent as a movable token, so that it recognises a node it has already seen.
  3. Now every agent knows the whole configuration and answers as the computer that sees it would.
Why it works and what it costs. So agents that know \(k \ge 2\) decide every decision problem (proof of Theorem 3.2) Fraigniaud & Pelc 2017. The time is finite but huge, because the meeting procedure uses walks of up to \(2n^n\) rounds. A lone agent has no partner to use as a token, which is exactly why it fails above. A lone agent given a map of the graph, without its start node marked, also decides everything, but one that knows only \(n\) does not. Fraigniaud and Pelc conclude that knowing the number of agents is very powerful once it is larger than 1, which points to gathering as the key task.

Why it matters. It shows that gathering is not just one task among many: once agents can meet and count themselves, they can compute anything about where they are.

3AlgorithmOne bit of memory is enough with whiteboards One agent with whiteboards and little memory → Izumi et al. 2022

Now a single agent has very little memory, but every node has a whiteboard of a constant number of bits.

  1. The agent runs a depth-first search in port order that needs only a constant number of bits in its own memory and on each whiteboard (Theorem 3). This puts the nodes in a fixed order.
  2. Along that order, the whiteboards serve as the tape of a Turing machine, a model computer that reads and writes a long tape one cell at a time. So the agent can simulate an agent with \(O(n)\) bits of memory.
  3. The constant number of bits the agent still carries is reduced to one. It keeps them on the whiteboard of its node and moves them to the next node one bit at a time, with one round trip per bit.
Why it works and what it costs. So an agent with one bit of memory decides everything that an agent with \(O(n)\) bits decides in polynomial time, with a polynomial slowdown (Theorem 1) Izumi et al. 2022. Planarity, being bipartite and bounds on the diameter are examples. Zero bits are not enough. Such an agent cannot explore every graph, so on some graph it answers without visiting a node, and adding a leaf there changes the answer to "is \(n\) odd?" (Theorem 2).

Why it matters. It shows that the agent's own memory hardly matters once the graph can store information: the whiteboards together act as its memory.

What is known

The best upper bound against the best lower bound in each catalogued setting. Open a setting for its results, proofs and notes, or see the progress map with the branch points.

tight near-optimal polynomial gap unknown impossible· one row per catalogued setting, in tree order; each cell: best upper bound vs lower bound, and what forces the lower bound
Setting
Time
Memory
Any number of agents standard
Not every decidable property can be decided: agents that may be alone cannot tell a long path from a cycle.
impossible — vs \(\text{impossible}\) locality
impossible — vs —
One agent
A lone agent can decide only what its view of the graph determines; deciding is then the same as verifying both yes and no answers.
impossible — vs \(\text{impossible}\) locality
impossible — vs —
One agent that knows \(n\)
Knowing \(n\) lets a lone agent learn its quotient graph, but not \(G\) itself.
impossible — vs \(\text{impossible}\) symmetry breaking
impossible — vs —
One agent with a map
With a map of the graph, a lone agent decides every decidable property.
unknown \(\text{finite}\) vs —
unknown — vs —
Any number of agents, with certificates
Certificates verify strictly more problems than can be decided, and one problem is complete for them, but some decidable problems still cannot be verified.
impossible — vs \(\text{impossible}\) locality
impossible — vs —
Two or more agents that know their number
Agents that know their number \(k \ge 2\) gather, draw a map and decide every decidable property.
unknown \(\text{finite}\) vs —
unknown — vs —
One agent with whiteboards and little memory
One bit of agent memory, with constant-size whiteboards, decides everything that \(O(n)\) bits decide in polynomial time; zero bits do not.
unknown \(\text{poly}(n)\) vs —
tight \(1\) vs \(1\) memory

Open questions 6

Any number of agents

  1. What is the least information about the number of agents that lets several agents reconstruct the whole configuration? Posed in Fraigniaud & Pelc 2017.

One agent

  1. Give a combinatorial characterisation of the problems that a lone agent decides. Posed in Fraigniaud & Pelc 2017.
  2. Is it decidable whether a lone agent can decide a given problem: is there a Turing machine that, given a Turing machine deciding membership in \(\Pi\), decides whether a lone agent can decide \(\Pi\)? Posed in Fraigniaud & Pelc 2017.

One agent that knows \(n\)

  1. Is it decidable whether a lone agent that knows \(n\) can decide a given problem? Posed in Fraigniaud & Pelc 2017.

Any number of agents, with certificates

  1. Do certificates that may depend on the agents' identifiers verify more problems? Raised in Bampas & Ilcinkas 2018.
  2. Which problems become verifiable under the promise that there are at most two agents? Raised in Bampas & Ilcinkas 2018.

What the community started looking at

Fraigniaud and Pelc asked which properties of their starting configuration agents can decide in an anonymous graph, with the acceptance rule of distributed decision (all accept, or someone rejects), and set decision against verification with a certificate, by analogy with P and NP Fraigniaud & Pelc 2017. They found a complete problem for verification, built from the number of agents and the quotient graph, and showed that knowing the number of agents decides everything once there are at least two, while a lone agent depends on what it is told about the graph. Bampas and Ilcinkas refined the classes with unanimity and with certificates for no answers, using a mobile-agent analogue of dovetailing Bampas & Ilcinkas 2018. Izumi, Kakizawa, Kawabata, Kitamura and Masuzawa turned to a single agent with little memory and constant-size whiteboards, where one bit of agent memory decides as much as \(O(n)\) bits in polynomial time Izumi et al. 2022.

Related problems

Map construction: Two or more agents that know their number decide every property by gathering and drawing a map, one agent using the others as a token; a lone agent with a map decides every property Fraigniaud & Pelc 2017.

Gathering in graphs: Gathering is what makes a known number of agents decisive: after it, the agents learn the whole configuration Fraigniaud & Pelc 2017.

Graph exploration by a single agent: A lone agent with constant memory and constant-size whiteboards explores by a depth-first search in port order Izumi et al. 2022; without memory it cannot explore every graph Cohen et al. 2008, which is why it cannot decide whether \(n\) is odd.

Further reading

Papers on this problem that are not yet placed in a setting.

  • Pattanayak & Pelc 2023 Computing Functions by Teams of Deterministic Finite Automata. Which functions \(f : \mathbb{N}^k \to \mathbb{N}\) teams of deterministic finite automata compute on the half-line, starting in groups at the arguments. A preprint; abstract read.

All settings

The assumption tree (7 settings, 2 branch points)

The root assumes nothing. Going down, each edge adds the assumptions on its chips (+blue); a grey chip names the branch that leaves that axis unassumed while a sibling assumes something. Solid nodes are catalogued variants with their status per measure (Time, Memory); dashed nodes are branch points with no catalogued variant, named after the axis on which their branches differ. Axis order: Graph dynamics › Edge direction › Node identifiers › Identifiers › Communication › Timing › Node memory › Number of agents › Certificates › Knowledge of the graph.

tight near-optimal polynomial gap unknown impossible no variant

Assumptions specific to this problem

Number of agents

0any number of agents, unknown to them1a single agent1two or more agents that know their number

Fraigniaud and Pelc allow any number of agents, unknown to them, and show that knowing it is very powerful when it is larger than 1 but useless for a single agent Fraigniaud & Pelc 2017; they then study the single agent separately. Bampas and Ilcinkas name the inability to tell one agent from several as the main source of difficulty Bampas & Ilcinkas 2018. Izumi et al. study a single agent Izumi et al. 2022.

Formal definitions
0any \(k\)
Any number \(k \ge 1\) of agents; no agent knows \(k\), so an agent cannot tell whether it is alone.
1one agent
Exactly one agent, \(k = 1\): configurations with more agents are excluded.
1known \(k \ge 2\)
\(k \ge 2\) agents, and every agent knows \(k\).

Certificates

0no certificate (decision)1a certificate for yes answers (verification)

Fraigniaud and Pelc separate deciding from verifying, as P from NP, and motivate certificates by agents that repeatedly check a property Fraigniaud & Pelc 2017; Bampas and Ilcinkas add certificates for no answers and argue that verification lets agents check the assumptions of another algorithm, or its output, before relying on it Bampas & Ilcinkas 2018.

Formal definitions
0decide
The agents receive only their identifiers and inputs.
1verify
Each agent also receives a certificate string. For every configuration in \(\Pi\) some certificate makes all agents output yes; for every other configuration, whatever the certificate, some agent outputs no.

Knowledge of the graph

0nothing known1\(n\) known2a map of \(G\)

Fraigniaud and Pelc compare, for a single agent, three kinds of information given as oracles: the quotient graph, the number of nodes and a map; they note that the size of the graph and its topology are often given to agents in network tasks, while the quotient graph matters because it is all an agent can learn Fraigniaud & Pelc 2017.

Formal definitions
0no knowledge
The agents know nothing about \(G\).
1knows \(n\)
The agents know \(n\) (an oracle for the number of nodes in Fraigniaud & Pelc 2017).
2map
The agents have a copy of \(G\) with its ports, without their start nodes marked on it.

Know a better result, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.