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, with certificates
verifiedCertificates verify strictly more problems than can be decided, and one problem is complete for them, but some decidable problems still cannot be verified.
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: verify
- 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: no knowledge
- The agents know nothing about \(G\).
What is known
- the problem whether every agent's input equals the number of agents: a lone agent on a ring accepts with some certificate; two such agents, placed at the roots of their truncated views joined by an edge, run as if alone, so both accept although there are two of them (Proposition 7)
- the same argument shows that this problem cannot be verified for no-instances either
Results, in order of publication
No result recorded yet.
Open questions
Do certificates that may depend on the agents' identifiers verify more problems? Raised in Bampas & Ilcinkas 2018.
Which problems become verifiable under the promise that there are at most two agents? Raised in Bampas & Ilcinkas 2018.
Notes
Whether \(G\) is a path is verifiable with the number of nodes as certificate, so \(\mathsf{MAV}\) is strictly larger than \(\mathsf{MAD}\); the problems 'some node has degree \(d\)', one for each \(d\), form an infinite family of which none reduces to another Fraigniaud & Pelc 2017. Fraigniaud and Pelc's main result is a complete problem for \(\mathsf{MAV}\): the product of teamsize (are there more than a given number of agents?) and quotient (is the quotient graph of \(G\), which merges nodes with the same view, different from a given graph?) (Theorem 3.2). Every verifiable problem reduces to it: with two or more agents, knowing their number lets them gather and draw a map; a lone agent learns the quotient graph, which is all it can ever learn. Bampas and Ilcinkas add certificates for no-instances and unanimous acceptance, and place the nine resulting classes in a complete diagram of inclusions (Table 1 and Figures 2–3 of Bampas & Ilcinkas 2018); for example, whether some node has degree equal to an agent's input is verifiable, but not with unanimous rejection and not for no-instances (Proposition 6).
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.