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 measuresexpand
\(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.
Any number of agents
standard settingverifiedNot every decidable property can be decided: agents that may be alone cannot tell a long path from a cycle.
Assumed (added on the last edge are outlined)
Not assumed
Formal definitions of this setting
- Graph dynamics: static graph
- \(G_t=G\) for all \(t\): the edge set never changes.
- Edge direction: undirected
- \(G=(V,E)\) with \(E\subseteq\binom V2\); every edge can be traversed in both directions.
- Node identifiers: anonymous 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.
- Identifiers: distinct IDs (eponymous)
- 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.
- Communication: local communication
- 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.
- Timing: synchronous
- Time proceeds in rounds \(t=1,2,\dots\); in every round every agent communicates, computes and moves (at most one edge) simultaneously.
- Node memory: no whiteboards
- Nodes have no storage: no information can be left at a node except by an agent staying there.
- Number of agents: any \(k\)
- Any number \(k \ge 1\) of agents; no agent knows \(k\), so an agent cannot tell whether it is alone.
- Certificates: decide
- The agents receive only their identifiers and inputs.
- Knowledge of the graph: no knowledge
- The agents know nothing about \(G\).
What is known
- inherited from the single-agent setting: a configuration with one agent is a configuration of this setting
- the problem whether \(G\) is a path, which a centralised algorithm decides: a lone agent that decides after \(t\) rounds behaves alike at the centre of a path of \(2t+3\) nodes and on a cycle, both with ports \(1\) in one direction and \(2\) in the other (Section 2.2)
Results, in order of publication
No result recorded yet.
Open questions
What is the least information about the number of agents that lets several agents reconstruct the whole configuration? Posed in Fraigniaud & Pelc 2017.
Notes
Fraigniaud and Pelc call the decidable problems of this setting \(\mathsf{MAD}\) (mobile agent decidable) and show that it is strictly contained in \(\mathsf{MAV}\), the problems that can be verified with a certificate Fraigniaud & Pelc 2017. Some global properties are decidable: whether \(G\) is a tree with a given number \(x\) of nodes, by a depth-first search of \(2(x-1)\) steps that draws a map. Bampas and Ilcinkas refine the picture Bampas & Ilcinkas 2018. Requiring every agent to be right also in no-instances gives a class equal to the problems in both \(\mathsf{MAD}\) and \(\text{co-}\mathsf{MAD}\) (Theorem 1); \(\mathsf{MAD}\) and \(\text{co-}\mathsf{MAD}\) differ (Proposition 4, with the problem whether all inputs are empty). Theorem 5 shows that every problem of \(\mathsf{MAD}\) also has certificates for its no-instances, which makes \(\mathsf{MAD}\) a part of \(\text{co-}\mathsf{MAV}\). If only one agent must answer correctly, the class becomes too large: for every \(j \ge 1\) it contains a problem complete for the \(j\)-th level \(\Sigma^0_j\) of the arithmetic hierarchy (Theorem 6). Their main tool is a meta-protocol that runs infinitely many protocols in parallel, the mobile-agent analogue of dovetailing. Checked against the full texts (Fraigniaud & Pelc 2017 in arXiv v1, Bampas & Ilcinkas 2018 in its HAL version).
What carries over from neighbouring settings
Read off the order of assumptions, not checked case by case: results may carry extra assumptions (shown on their pages), and asynchronous time is measured in epochs.
Algorithms from weaker settings work here
No catalogued weaker setting.
Lower bounds from stronger settings hold here
Branches from here
One agent
Any number of agents, with certificates
Two or more agents that know their number
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.