Population protocols on an interaction graph (CRN-4) #
Mertzios, Nikoletseas, Raptopoulos and Spirakis [MNRS14, §2] run population protocols on an
arbitrary connected interaction graph G: two agents may interact only if they share an edge.
On an undirected graph an interaction is an oriented edge (a SimpleGraph.Dart): the tail is
the initiator, the head the responder. This file generalizes the reachability form of stable
computation of Crn.Protocol.StablyComputes (StableBasic, complete interaction graph) to
interactions along the edges of G : SimpleGraph (Fin n), without changing the existing
definitions:
Protocol.GraphStep,Protocol.GraphReaches,Protocol.GraphOutputStable: one encounter along an edge ofG, reachability, and output stability onG;Protocol.StablyComputesOnGraph P G D φ: on the graphG, from every input whose count vector lies in the domainD, every reachable configuration can reach an output-stable configuration with outputφ. The domain is needed because majority is a partial function [MNRS14, §2: "a (possibly partial) function"]: the paper only asks for the correct output "if there exists initially a majority" (Theorem 2);Protocol.GraphStablyComputes P D φ: stable computation on every connected graph.
On the complete graph ⊤ these notions are the existing ones (graphStep_top,
graphReaches_top, graphOutputStable_top, stablyComputesOnGraph_top_iff), so
GraphStablyComputes P (fun _ => True) φ implies P.StablyComputes φ
(GraphStablyComputes.stablyComputes).
The majority problem has the input alphabet Bool (true is the paper's red r, false its
green g), majority x = decide (x false < x true) (output true for a red majority) and the
domain HasMajority x : x true ≠ x false (no tie).
References #
- [MNRS14] G. B. Mertzios, S. E. Nikoletseas, C. L. Raptopoulos, P. G. Spirakis, Determining majority in networks with local interactions and very small local memory, ICALP 2014; arXiv:1404.7671 (numbering of the arXiv version); Distributed Computing 30 (2017).
The ordered pair (initiator, responder) of distinct agents of an oriented edge d of G
[MNRS14, §2: the tail of d is the initiator, the head the responder].
Equations
- Crn.dartPair d = ⟨d.toProd, ⋯⟩
Instances For
One step c → c' on the interaction graph G [MNRS14, §2.2, "directly reachable"]: c'
results from c by the encounter of the two endpoints of an oriented edge of G.
Instances For
Reachability on the interaction graph G: the reflexive-transitive closure of
GraphStep.
Equations
- P.GraphReaches G = Relation.ReflTransGen (P.GraphStep G)
Instances For
c is output-stable with output b on G [MNRS14, §2, property (b)]: in every
configuration reachable from c on G, every agent outputs b.
Equations
- P.GraphOutputStable G b c = ∀ (c' : Fin n → Q), P.GraphReaches G c c' → ∀ (v : Fin n), P.output (c' v) = b
Instances For
P stably computes the partial predicate φ with domain D on the interaction graph G
[MNRS14, §2], in the reachability form of Protocol.StablyComputes: for every input
assignment ι whose count vector lies in D, every configuration reachable on G from the
initial configuration I ∘ ι can reach on G an output-stable configuration whose common
output is φ of the input counts.
Equations
- One or more equations did not get rendered due to their size.
Instances For
P stably computes the partial predicate φ with domain D on every connected
interaction graph [MNRS14, §2: "an arbitrary connected network"].
Equations
- P.GraphStablyComputes D φ = ∀ (n : ℕ) (G : SimpleGraph (Fin n)), G.Connected → P.StablyComputesOnGraph G D φ
Instances For
The domain of the majority function [MNRS14, Theorem 2: "if there exists initially a majority"]: the two input counts differ.
Equations
- Crn.HasMajority x = (x true ≠ x false)
Instances For
The complete graph: agreement with Protocol.StablyComputes #
On the complete graph, reachability is reachability in the standard population.
Agreement with Protocol.StablyComputes. Stable computation on the complete graphs of
all nonempty populations, with the trivial domain, is the existing notion
Protocol.StablyComputes of CRN-3.
Stable computation on every connected graph implies stable computation in the standard population (complete interaction graph).
Stable computation on every connected graph gives stable computation on the complete graph of every nonempty population, for any domain.
Embedding a population into a larger one #
Embedding lemma (used in the proof of [MNRS14, Theorem 1]: "ignoring agents v and u
during these steps"). If c reaches d on G and f embeds the agents of G into those of
G', mapping edges to edges, then any configuration of G' that agrees with c on the image of
f reaches, on G', the configuration that agrees with d on the image of f and is unchanged
elsewhere.