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
verifiedA lone agent can decide only what its view of the graph determines; deciding is then the same as verifying both yes and no answers.
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: no knowledge
- The agents know nothing about \(G\).
What is known
- 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)
- Fraigniaud and Pelc state the same for whether \(G\) is a tree and whether \(G\) has a given number of nodes
- configurations with a single agent; holds whatever the agents' memory
Results, in order of publication
No result recorded yet.
Open questions
Give a combinatorial characterisation of the problems that a lone agent decides. Posed in Fraigniaud & Pelc 2017.
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.
Notes
The quotient graph of \(G\) merges nodes with the same view (the infinite tree of port-labelled walks from a node) and is the most a lone agent can learn about \(G\) (Lemma 3.1 of Fraigniaud & Pelc 2017, after Yamashita and Kameda). For one agent, the decidable problems are exactly those verifiable both for yes and for no answers (Theorem 4.1); they are strictly fewer than those verifiable for yes or for no answers, which are strictly fewer than those decidable when the agent is given its quotient graph (Theorem 4.2: the product of 'G is a consistently labelled cycle' and 'G is a sun' is decidable with the quotient graph but verifiable neither for yes nor for no answers). Bampas and Ilcinkas note that under this promise most of their classes coincide, and name the inability to tell one agent from several as the main source of difficulty Bampas & Ilcinkas 2018. Checked against the full texts.
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
Branches from here
One agent that knows \(n\)
One agent with a map
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.