Documentation

Crn.GraphMajorityAmbassador

The 4-state ambassador protocol computes majority on every connected graph (CRN-4) #

The ambassador protocol of [MNRS14, §4] has the states (color, ambassador) : Bool × Bool (true is red r, false is green g; the second component says whether the vertex holds an ambassador). An input x starts in (x, true) and the output is the color. On an encounter:

The protocol is symmetric (ambassador_symm): it does not distinguish initiator and responder. Its transition table is Figure 1 of [MNRS14] (ambassador_table).

Theorem 2 of [MNRS14] (ambassador_graphStablyComputes): on every connected graph, if there is initially a majority, the ambassador protocol stably computes it. The proof pins:

The tie case is excluded exactly as in the paper (domain HasMajority); without it the protocol can get stuck in a configuration with both colors and no ambassadors (ambassador_tie_stuck).

References #

@[reducible, inline]

The states of the ambassador protocol [MNRS14, §4]: a color (true red, false green) and whether the vertex holds an ambassador.

Equations
Instances For

    The transition function of the ambassador protocol [MNRS14, §4, Figure 1], on the states of (initiator, responder).

    Equations
    Instances For

      The 4-state ambassador protocol [MNRS14, §4]: input x ↦ (x, true) (every vertex starts with an ambassador of its own color), output the color.

      Equations
      Instances For

        The ambassador protocol has 4 states.

        theorem Crn.ambassador_table_rest (p : AmbState × AmbState) :
        p.1.2 = false ∧ p.2.2 = false ∨ p.1 = p.2 → ambassadorδ p = p

        The entries "−" of [MNRS14, Figure 1]: the remaining six pairs are unchanged.

        The ambassador protocol is symmetric [MNRS14, §2 and §4].

        def Crn.ambCount {n : ℕ} (b : Bool) (c : Fin n → AmbState) :

        The number of ambassadors of color b in the configuration c (the indices k, ℓ of the classes 𝒞_{k,ℓ} in the proof of [MNRS14, Theorem 2]).

        Equations
        Instances For
          theorem Crn.ambCount_input {n : ℕ} (b : Bool) (ι : Fin n → Bool) :
          ambCount b (ambassador.input ∘ ι) = ↑(counts ι) b

          Initially every vertex holds an ambassador of its input color.

          def Crn.ambInd (b : Bool) (s : AmbState) :

          The indicator of an ambassador of color b in the state s.

          Equations
          Instances For
            theorem Crn.ambCount_eq_sum {n : ℕ} (b : Bool) (c : Fin n → AmbState) :
            ambCount b c = ∑ v : Fin n, ambInd b (c v)

            The number of ambassadors of color b is the sum of their indicators over the vertices.

            theorem Crn.ambCount_interact_add {n : ℕ} (b : Bool) (c : Fin n → AmbState) (e : AgentPair n) :
            ambCount b (ambassador.interact c e) + (ambInd b (c (↑e).1) + ambInd b (c (↑e).2)) = ambCount b c + (ambInd b (ambassadorδ (c (↑e).1, c (↑e).2)).1 + ambInd b (ambassadorδ (c (↑e).1, c (↑e).2)).2)

            Summing the indicators over an encounter e: only the two agents of e change.

            theorem Crn.ambInd_δ_le (b : Bool) (p q : AmbState) :

            No transition creates an ambassador of color b.

            Every transition removes as many red as green ambassadors.

            theorem Crn.ambCount_interact_le {n : ℕ} (b : Bool) (c : Fin n → AmbState) (e : AgentPair n) :

            Invariant [MNRS14, proof of Theorem 2]: no encounter creates an ambassador.

            Invariant [MNRS14, proof of Theorem 2: "whenever ambassadors disappear, they disappear in pairs, i.e. one from each color"]: the difference between the numbers of red and green ambassadors never changes.

            theorem Crn.card_filter_add_pair {n : ℕ} (p : AmbState → Prop) [DecidablePred p] {c c' : Fin n → AmbState} {u x : Fin n} (hux : u ≠ x) (h : ∀ (w : Fin n), w ≠ u → w ≠ x → c' w = c w) :
            {v : Fin n | p (c' v)}.card + ((if p (c u) then 1 else 0) + if p (c x) then 1 else 0) = {v : Fin n | p (c v)}.card + ((if p (c' u) then 1 else 0) + if p (c' x) then 1 else 0)

            Counting the agents whose state satisfies p when only the agents u ≠ x change.

            theorem Crn.ambCount_eq_zero_iff {n : ℕ} {b : Bool} {c : Fin n → AmbState} :
            ambCount b c = 0 ↔ ∀ (v : Fin n), c v ≠ (b, true)

            There are no ambassadors of color b iff no vertex is in the state (b, true).

            theorem Crn.interact_move {n : ℕ} {c : Fin n → AmbState} {e : AgentPair n} {b : Bool} (hu : c (↑e).1 = (b, true)) (hx : (c (↑e).2).2 = false) :
            ambassador.interact c e (↑e).1 = (b, false) ∧ ambassador.interact c e (↑e).2 = (b, true)

            Move [MNRS14, §4]: an ambassador of color b meeting a vertex without ambassador moves there and paints it with its color b.

            theorem Crn.ambCount_interact_move {n : ℕ} {c : Fin n → AmbState} {e : AgentPair n} {b : Bool} (hu : c (↑e).1 = (b, true)) (hx : (c (↑e).2).2 = false) (b' : Bool) :

            A move changes no ambassador count.

            theorem Crn.ambCount_interact_annihilate {n : ℕ} {c : Fin n → AmbState} {e : AgentPair n} (hu : c (↑e).1 = (true, true)) (hx : c (↑e).2 = (false, true)) :

            Annihilation [MNRS14, §4]: two ambassadors of different colors meet; both disappear.

            theorem Crn.exists_adj_dist_lt {n : ℕ} {G : SimpleGraph (Fin n)} (hG : G.Connected) {u w : Fin n} (h : u ≠ w) :
            ∃ (x : Fin n), G.Adj u x ∧ G.dist x w < G.dist u w

            On a connected graph, every vertex u ≠ w has a neighbour closer to w.

            theorem Crn.exists_reaches_annihilate_of_dist {n : ℕ} {G : SimpleGraph (Fin n)} (hG : G.Connected) {w : Fin n} (k : ℕ) (c : Fin n → AmbState) (u : Fin n) :
            G.dist u w = k → c u = (true, true) → c w = (false, true) → ∃ (c' : Fin n → AmbState), ambassador.GraphReaches G c c' ∧ ambCount true c' + 1 = ambCount true c ∧ ambCount false c' + 1 = ambCount false c

            Annihilation is reachable, by induction on the distance k from a red ambassador at u to a green ambassador at w: the red ambassador walks towards w along a shortest path (moving to free vertices, or handing over to a red ambassador it meets) until it meets a green one.

            theorem Crn.exists_reaches_spread_of_dist {n : ℕ} {G : SimpleGraph (Fin n)} (hG : G.Connected) {b : Bool} {w : Fin n} (k : ℕ) (c : Fin n → AmbState) (u : Fin n) :
            G.dist u w = k → c u = (b, true) → ambCount (!b) c = 0 → (c w).1 = !b → ∃ (c' : Fin n → AmbState), ambassador.GraphReaches G c c' ∧ ambCount (!b) c' = 0 ∧ 0 < ambCount b c' ∧ {v : Fin n | (c' v).1 = !b}.card < {v : Fin n | (c v).1 = !b}.card

            Spreading the color b by one vertex, by induction on the distance k from an ambassador of color b at u to a vertex w of color !b, in the absence of ambassadors of color !b: the ambassador walks towards w along a shortest path (handing over to the ambassadors of color b it meets) until it paints a vertex of color !b.

            theorem Crn.exists_reaches_annihilate {n : ℕ} {G : SimpleGraph (Fin n)} (hG : G.Connected) {c : Fin n → AmbState} (hr : 0 < ambCount true c) (hg : 0 < ambCount false c) :

            Annihilation is reachable [MNRS14, proof of Theorem 2: every configuration of 𝒞_{k,ℓ} with k, ℓ ≥ 1 can lead to 𝒞_{k−1,ℓ−1}]: on a connected graph, while both colors have an ambassador, a configuration with one ambassador fewer of each color is reachable.

            theorem Crn.exists_reaches_allColor {n : ℕ} {G : SimpleGraph (Fin n)} (hG : G.Connected) {c : Fin n → AmbState} {b : Bool} (hb : 0 < ambCount b c) (hnb : ambCount (!b) c = 0) :
            ∃ (c' : Fin n → AmbState), ambassador.GraphReaches G c c' ∧ ∀ (v : Fin n), (c' v).1 = b

            Spreading is reachable [MNRS14, proof of Theorem 2: from 𝒞_{k−ℓ,0} "there exists a chain of transitions that lead to a configuration where all vertices are colored with the color of the initial majority"]: on a connected graph, if there is an ambassador of color b and none of the other color, the configuration in which every vertex has color b is reachable.

            theorem Crn.ambassadorδ_color (b : Bool) (p q : AmbState) (hp : p.1 = b) (hq : q.1 = b) :
            (ambassadorδ (p, q)).1.1 = b ∧ (ambassadorδ (p, q)).2.1 = b

            An encounter of two vertices of color b keeps both of color b.

            theorem Crn.graphOutputStable_of_allColor {n : ℕ} (G : SimpleGraph (Fin n)) {c : Fin n → AmbState} {b : Bool} (h : ∀ (v : Fin n), (c v).1 = b) :

            A configuration in which every vertex has color b is output-stable with output b, on every interaction graph: encounters of two vertices of color b keep color b.

            theorem Crn.ambCount_sub_reaches {n : ℕ} {G : SimpleGraph (Fin n)} {c c' : Fin n → AmbState} (h : ambassador.GraphReaches G c c') :
            ↑(ambCount true c') - ↑(ambCount false c') = ↑(ambCount true c) - ↑(ambCount false c)

            The difference between the numbers of red and green ambassadors is invariant along reachability on any interaction graph (ambCount_sub_interact).

            theorem Crn.exists_reaches_ambCount_eq_zero {n : ℕ} {G : SimpleGraph (Fin n)} (hG : G.Connected) (c : Fin n → AmbState) :
            ∃ (c' : Fin n → AmbState), ambassador.GraphReaches G c c' ∧ (ambCount true c' = 0 ∨ ambCount false c' = 0)

            Iterated annihilation [MNRS14, proof of Theorem 2: 𝒞_{k,ℓ} → ⋯ → 𝒞_{k−ℓ,0}]: on a connected graph, a configuration in which some color has no ambassador is reachable.

            [MNRS14, Theorem 2]. Given any connected graph, if there exists initially a majority, the 4-state ambassador protocol stably computes the initial majority value.

            [MNRS14, Theorem 2] on the complete graph of every nonempty population (the standard population of Protocol.StablyComputes).

            theorem Crn.graphReaches_eq_of_noAmb {n : ℕ} {G : SimpleGraph (Fin n)} {c d : Fin n → AmbState} (hc : ∀ (v : Fin n), (c v).2 = false) (h : ambassador.GraphReaches G c d) :
            d = c

            A configuration without ambassadors is a fixed point on every interaction graph: every encounter of two vertices without ambassador leaves both unchanged (ambassador_table_rest).

            theorem Crn.ambassador_tie_stuck :
            ∃ (ι : Fin 2 → Bool), ↑(counts ι) true = ↑(counts ι) false ∧ ∃ (c : Fin 2 → AmbState), ambassador.GraphReaches ⊤ (ambassador.input ∘ ι) c ∧ ∀ (d : Fin 2 → AmbState), ambassador.GraphReaches ⊤ c d → ∀ (b : Bool), ¬ambassador.GraphOutputStable ⊤ b d

            The tie case is excluded (as in [MNRS14, Theorem 2]): on the complete graph of two agents with one red and one green input, the protocol reaches a configuration (both ambassadors annihilated, both colors present) from which no output-stable configuration is reachable.