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.
One agent with a map
verifiedWith a map of the graph, a lone agent decides every decidable property.
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: one agent
- Exactly one agent, \(k = 1\): configurations with more agents are excluded.
- Certificates: decide
- The agents receive only their identifiers and inputs.
- Knowledge of the graph: map
- The agents have a copy of \(G\) with its ports, without their start nodes marked on it.
What is known
Results, in order of publication
Introductory and current best (Theorem 4.3): with the map the agent finds its start node up to a port-preserving automorphism and so knows the whole configuration.
Open questions
None recorded for this variant.
Notes
The chain of Theorem 4.3 of Fraigniaud & Pelc 2017: a lone agent given its quotient graph decides strictly less than one that knows \(n\), which decides strictly less than one with a map. Checked against the full text (arXiv v1).
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
Lower bounds from stronger settings hold here
No catalogued stronger setting.
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.