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.
Two or more agents that know their number
verifiedAgents that know their number \(k \ge 2\) gather, draw a map and decide 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: known \(k \ge 2\)
- \(k \ge 2\) agents, and every agent knows \(k\).
- 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
Results, in order of publication
Introductory and current best (proof of Theorem 3.2 and Section 4): the agents gather by rendezvous with growing guesses of \(n\) and of the length of identifiers (Claim 3.3), the agent with the largest identifier draws a map of \(G\) using the others as a movable token (Claim 3.4), and every agent then knows the whole configuration. The rendezvous runs DFS walks of up to \(2n^n\) rounds each, so the time is finite but exponential.
Open questions
None recorded for this variant.
Notes
Fraigniaud and Pelc conclude that knowing the number of agents is very powerful when it is larger than 1, which points to gathering as the key task in mobile agent computing Fraigniaud & Pelc 2017. Bampas and Ilcinkas remark that the promise of two or more agents already suffices, the agents learning the configuration by rendezvous with growing guesses of \(n\) Bampas & Ilcinkas 2018; they state this in their discussion without a proof. Checked against the full text of Fraigniaud & Pelc 2017 (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.