Documentation

Crn.GraphMajorityBasic

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:

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 #

def Crn.dartPair {n : ℕ} {G : SimpleGraph (Fin n)} (d : G.Dart) :

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
Instances For
    def Crn.Protocol.GraphStep {X : Type u_1} {Q : Type u_2} {n : ℕ} (P : Protocol X Q) (G : SimpleGraph (Fin n)) (c c' : Fin n → Q) :

    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.

    Equations
    Instances For
      def Crn.Protocol.GraphReaches {X : Type u_1} {Q : Type u_2} {n : ℕ} (P : Protocol X Q) (G : SimpleGraph (Fin n)) :
      (Fin n → Q) → (Fin n → Q) → Prop

      Reachability on the interaction graph G: the reflexive-transitive closure of GraphStep.

      Equations
      Instances For
        def Crn.Protocol.GraphOutputStable {X : Type u_1} {Q : Type u_2} {n : ℕ} (P : Protocol X Q) (G : SimpleGraph (Fin n)) (b : Bool) (c : Fin n → Q) :

        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
        Instances For
          def Crn.Protocol.StablyComputesOnGraph {X : Type u_1} {Q : Type u_2} {n : ℕ} [Fintype X] [DecidableEq X] (P : Protocol X Q) (G : SimpleGraph (Fin n)) (D : (X → ℕ) → Prop) (φ : (X → ℕ) → Bool) :

          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
            def Crn.Protocol.GraphStablyComputes {X : Type u_1} {Q : Type u_2} [Fintype X] [DecidableEq X] (P : Protocol X Q) (D : (X → ℕ) → Prop) (φ : (X → ℕ) → Bool) :

            P stably computes the partial predicate φ with domain D on every connected interaction graph [MNRS14, §2: "an arbitrary connected network"].

            Equations
            Instances For
              def Crn.majority (x : Bool → ℕ) :

              The majority predicate on two input types [MNRS14, §3]: true (red) is the majority.

              Equations
              Instances For
                def Crn.HasMajority (x : Bool → ℕ) :

                The domain of the majority function [MNRS14, Theorem 2: "if there exists initially a majority"]: the two input counts differ.

                Equations
                Instances For

                  The complete graph: agreement with Protocol.StablyComputes #

                  theorem Crn.Protocol.graphStep_top {X : Type u_1} {Q : Type u_2} {n : ℕ} (P : Protocol X Q) :

                  On the complete graph, a graph step is a step of the standard population.

                  theorem Crn.Protocol.graphReaches_top {X : Type u_1} {Q : Type u_2} {n : ℕ} (P : Protocol X Q) :

                  On the complete graph, reachability is reachability in the standard population.

                  theorem Crn.Protocol.graphOutputStable_top {X : Type u_1} {Q : Type u_2} {n : ℕ} (P : Protocol X Q) (b : Bool) (c : Fin n → Q) :

                  On the complete graph, output stability is output stability in the standard population.

                  theorem Crn.Protocol.stablyComputesOnGraph_top_iff {X : Type u_1} {Q : Type u_2} (P : Protocol X Q) [Fintype X] [DecidableEq X] (φ : (X → ℕ) → Bool) :
                  (∀ (n : ℕ), 0 < n → P.StablyComputesOnGraph ⊤ (fun (x : X → ℕ) => True) φ) ↔ P.StablyComputes φ

                  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.

                  theorem Crn.Protocol.GraphStablyComputes.stablyComputes {X : Type u_1} {Q : Type u_2} {P : Protocol X Q} [Fintype X] [DecidableEq X] {φ : (X → ℕ) → Bool} (h : P.GraphStablyComputes (fun (x : X → ℕ) => True) φ) :

                  Stable computation on every connected graph implies stable computation in the standard population (complete interaction graph).

                  theorem Crn.Protocol.GraphStablyComputes.top {X : Type u_1} {Q : Type u_2} {P : Protocol X Q} [Fintype X] [DecidableEq X] {D : (X → ℕ) → Prop} {φ : (X → ℕ) → Bool} (h : P.GraphStablyComputes D φ) (n : ℕ) (hn : 0 < n) :

                  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 #

                  theorem Crn.Protocol.GraphReaches.extend {X : Type u_1} {Q : Type u_2} {n : ℕ} (P : Protocol X Q) {m : ℕ} {G : SimpleGraph (Fin m)} {G' : SimpleGraph (Fin n)} {f : Fin m → Fin n} (hf : Function.Injective f) (hG : ∀ (u v : Fin m), G.Adj u v → G'.Adj (f u) (f v)) {c d : Fin m → Q} (h : P.GraphReaches G c d) (e : Fin n → Q) :

                  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.