Documentation

Crn.ExactMajorityDynamic

Dynamic exact majority with ties (CRN-5, [GHMSS16, Section 3]) #

The protocol P₂ of [GHMSS16, Section 3]. Every agent a carries a colour c_a ∈ {-1, 0, 1}, which an external force may change, and a state among the strong states [-2], …, [2] and the weak states ⟨-1⟩, ⟨0⟩, ⟨1⟩, with weight w([z]) = z, w(⟨x⟩) = 0 (Fig. 3). Interactions (the rules of the text of Section 3): [1], [-1] and [2], [-2] annihilate into [0], [0]; [2], [-1] become [1], [0] and [-2], [1] become [-1], [0]; a strong state of positive (negative) weight turns weak states and [0] into ⟨1⟩ (⟨-1⟩); [0] turns weak states into ⟨0⟩. The interaction table does not read the colours. When the force changes c_a to c_a + Δ, the state becomes [w(s_a) + Δ] (DynState.recolour, Fig. 3).

The colours are therefore kept outside the protocol: a configuration of P₂ is c : Fin n → DynState, and the colours col : Fin n → SignType are linked to it by the two invariants of Section 3 (DynInv). For the relative majority protocol of Section 5, P₂ runs separately in groups of agents (agents with the same label prefix); GStep grp is a step between two agents of the same group, and DynInv grp holds group by group. With one group, GStep is Step.

Main statements:

The table of Fig. 4 differs from the text in five entries. Four are harmless ([±2] meeting [∓1] gives ⟨±1⟩ instead of [0], of the same weight). The entry for [1] meeting [0], (⟨1⟩, [1]), needs a minor correction: it moves the weight to the [0] agent and breaks Invariant 2 (an agent of colour -1 in state [0] would get [1], and a later change of its colour to 1 would require the state [3]); the text's ([1], ⟨1⟩) is used.

inductive Crn.DynState :

The eight states of the dynamic majority protocol [GHMSS16, Fig. 3]: strong [-2], …, [2] and weak ⟨x⟩, x ∈ {-1, 0, 1}.

Instances For
    def Crn.instDecidableEqDynState.decEq (x✝ x✝¹ : DynState) :
    Decidable (x✝ = x✝¹)
    Equations
    Instances For

      The weight [GHMSS16, Fig. 3]: w([z]) = z, w(⟨x⟩) = 0.

      Equations
      Instances For

        Weak states.

        Equations
        Instances For

          The output (the reported sign of the colour sum) [GHMSS16, Section 3]: the sign of z in [z], and x in ⟨x⟩.

          Equations
          Instances For

            The strong state of weight z, for -2 ≤ z ≤ 2 (clamped outside this range).

            Equations
            • One or more equations did not get rendered due to their size.
            Instances For

              The new state of an agent in state a meeting an agent in state b, outside annihilations [GHMSS16, Section 3]: a weak state, or [0] meeting a strong state of nonzero weight, becomes the weak state of the sign of the strong state b (its output); otherwise nothing changes.

              Equations
              Instances For

                The state change forced by a colour change c → c' [GHMSS16, Fig. 3]: s ↦ [w(s) + c' - c] if c ≠ c', nothing otherwise.

                Equations
                Instances For
                  theorem Crn.DynState.weight_ofWeight {z : ℤ} (h₁ : -2 ≤ z) (h₂ : z ≤ 2) :

                  ofWeight is the strong state of weight z on [-2, 2].

                  theorem Crn.DynState.δ_weight (a b : DynState) :
                  (δ (a, b)).1.weight + (δ (a, b)).2.weight = a.weight + b.weight

                  Interactions preserve the total weight of the two agents [GHMSS16, proof of Lemma 4].

                  The dynamic majority protocol P₂ [GHMSS16, Section 3] without the external force: input colour x ↦ [x]. Its Bool output (more 1s than -1s) is not used; the outputs are DynState.out.

                  Equations
                  Instances For
                    def Crn.Protocol.GStep {X : Type u_1} {Q : Type u_2} {G : Type u_3} {n : ℕ} (P : Protocol X Q) (grp : Fin n → G) (c d : Fin n → Q) :

                    A step between two agents of the same group (grp assigns a group to every agent).

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

                      Reachability by steps inside groups.

                      Equations
                      Instances For
                        theorem Crn.Protocol.gReaches_const_iff {X : Type u_1} {Q : Type u_2} {G : Type u_3} {n : ℕ} (P : Protocol X Q) (g : G) {c d : Fin n → Q} :
                        P.GReaches (fun (x : Fin n) => g) c d ↔ P.Reaches c d

                        With a single group, steps inside groups are all steps.

                        structure Crn.DynInv {G : Type u_1} [DecidableEq G] {n : ℕ} (grp : Fin n → G) (col : Fin n → SignType) (c : Fin n → DynState) :

                        The invariants of [GHMSS16, Section 3] for the colours col and the states c, group by group: (1) in every group the colour sum equals the weight sum; (2) |w(s_a) - c_a| ≤ 1 for every agent; and (3) every group contains a strong state. (3) is not stated in the paper but used in the tie case of its final argument (an agent in state [0] must remain); it holds initially and is preserved.

                        • sum_eq (v : Fin n) : ∑ u : Fin n with grp u = grp v, ↑(col u) = ∑ u : Fin n with grp u = grp v, (c u).weight

                          Invariant 1, in every group.

                        • close (v : Fin n) : |(c v).weight - ↑(col v)| ≤ 1

                          Invariant 2.

                        • strong (v : Fin n) : ∃ (u : Fin n), grp u = grp v ∧ (c u).isWeak = false

                          Every group contains a strong state.

                        Instances For
                          theorem Crn.DynInv.input {G : Type u_1} [DecidableEq G] {n : ℕ} (grp : Fin n → G) (col : Fin n → SignType) :
                          DynInv grp col fun (v : Fin n) => DynState.ofWeight ↑(col v)

                          The initial configuration [c_a] satisfies the invariants.

                          R = ∑ |w| does not increase in an encounter [GHMSS16, proof of Lemma 5].

                          R decreases in an encounter of opposite weights.

                          theorem Crn.DynState.close_δ_fst (x : SignType) (a b : DynState) (h : |a.weight - ↑x| ≤ 1) :
                          |(δ (a, b)).1.weight - ↑x| ≤ 1

                          Invariant 2 of the initiator is preserved by an encounter [GHMSS16, proof of Lemma 4]: its weight does not change sign and does not grow in absolute value.

                          theorem Crn.DynState.close_δ_snd (x : SignType) (a b : DynState) (h : |b.weight - ↑x| ≤ 1) :
                          |(δ (a, b)).2.weight - ↑x| ≤ 1

                          Invariant 2 of the responder is preserved by an encounter.

                          An encounter never removes the last strong state.

                          theorem Crn.DynState.δ_out (s : SignType) (a b : DynState) (ha : a.out = s) (hb : b.out = s) :
                          (δ (a, b)).1.out = s ∧ (δ (a, b)).2.out = s

                          The states reporting s are closed under encounters.

                          theorem Crn.DynState.δ_recruit (s : SignType) (a b : DynState) (ha : a.isWeak = false) (has : SignType.sign a.weight = s) (hb : b.weight = 0 ∨ SignType.sign b.weight = s) (hbs : b.out ≠ s) :
                          δ (a, b) = (a, weak s)

                          A strong state a of weight sign s recruits every state of weight 0 or of sign s that does not report s into ⟨s⟩, and keeps its state.

                          A strong state reports the sign of its weight.

                          A state of nonzero weight is strong.

                          The colour change is trivial if the colour does not change.

                          theorem Crn.sum_group_interact {G : Type u_1} [DecidableEq G] {n : ℕ} {X : Type u_2} {Q : Type u_3} {M : Type u_4} [AddCancelCommMonoid M] (P : Protocol X Q) (F : Q → M) (hF : ∀ (a b : Q), F (P.δ (a, b)).1 + F (P.δ (a, b)).2 = F a + F b) {grp : Fin n → G} (c : Fin n → Q) (e : AgentPair n) (he : grp (↑e).1 = grp (↑e).2) (g : G) :
                          ∑ u : Fin n with grp u = g, F (P.interact c e u) = ∑ u : Fin n with grp u = g, F (c u)

                          Sums over a group across an encounter inside a group: if the encounter preserves F a + F b, the sum of F over every group is preserved.

                          theorem Crn.sum_eq_add_of_eq_off {n : ℕ} {M : Type u_2} [AddCommGroup M] (s : Finset (Fin n)) {F F' : Fin n → M} (v : Fin n) (h : ∀ (u : Fin n), u ≠ v → F' u = F u) :
                          ∑ u ∈ s, F' u = ∑ u ∈ s, F u + if v ∈ s then F' v - F v else 0

                          A sum of a function that differs from another one only at v.

                          theorem Crn.DynInv.gstep {G : Type u_1} [DecidableEq G] {n : ℕ} {grp : Fin n → G} {col : Fin n → SignType} {c d : Fin n → DynState} (hc : DynInv grp col c) (h : dynamicMajority.GStep grp c d) :
                          DynInv grp col d

                          [GHMSS16, Lemma 4], interactions. Steps inside groups preserve the invariants (the colours do not change).

                          theorem Crn.DynInv.recolour {G : Type u_1} [DecidableEq G] {n : ℕ} {grp : Fin n → G} {col : Fin n → SignType} {c : Fin n → DynState} (hc : DynInv grp col c) (v : Fin n) (x : SignType) :
                          DynInv grp (Function.update col v x) (Function.update c v (DynState.recolour (col v) x (c v)))

                          [GHMSS16, Lemma 4], the external force. Changing the colour of agent v to x and its state by DynState.recolour preserves the invariants.

                          theorem Crn.DynState.absWeight_sum_gstep_le {G : Type u_1} {n : ℕ} {grp : Fin n → G} {c d : Fin n → DynState} (h : dynamicMajority.GStep grp c d) :
                          ∑ v : Fin n, |(d v).weight| ≤ ∑ v : Fin n, |(c v).weight|

                          [GHMSS16, Lemma 5], first part. R = ∑ |w| does not increase along interactions.

                          theorem Crn.DynState.exists_greaches_noOpposite {G : Type u_1} [DecidableEq G] {n : ℕ} (grp : Fin n → G) (c : Fin n → DynState) :
                          ∃ (d : Fin n → DynState), dynamicMajority.GReaches grp c d ∧ ∀ (u v : Fin n), grp u = grp v → 0 ≤ (d u).weight * (d v).weight

                          [GHMSS16, Lemma 5], second part. Interactions inside groups reach a configuration in which no two agents of the same group have weights of opposite signs.

                          theorem Crn.DynInv.greaches {G : Type u_1} [DecidableEq G] {n : ℕ} {grp : Fin n → G} {col : Fin n → SignType} {c d : Fin n → DynState} (hc : DynInv grp col c) (h : dynamicMajority.GReaches grp c d) :
                          DynInv grp col d

                          The invariants hold along every execution inside groups.

                          theorem Crn.DynInv.exists_stable {G : Type u_1} [DecidableEq G] {n : ℕ} {grp : Fin n → G} {col : Fin n → SignType} {c : Fin n → DynState} (hc : DynInv grp col c) :
                          ∃ (d : Fin n → DynState), dynamicMajority.GReaches grp c d ∧ ∀ (e : Fin n → DynState), dynamicMajority.GReaches grp d e → ∀ (v : Fin n), (e v).out = SignType.sign (∑ u : Fin n with grp u = grp v, ↑(col u))

                          [GHMSS16, Section 3, after Lemma 5] Stabilization of the dynamic majority protocol. From a configuration satisfying the invariants, interactions inside groups reach a configuration from which, along every further execution inside groups, every agent outputs the sign of the colour sum of its group (1: more 1s, -1: more -1s, 0: a tie).

                          def Crn.DynExtStep {n : ℕ} (p q : (Fin n → SignType) × (Fin n → DynState)) :

                          An interaction of P₂ (the colours are unchanged) or a colour change of one agent by the external force (with the state change of Fig. 3), on pairs (colours, states).

                          Equations
                          • One or more equations did not get rendered due to their size.
                          Instances For
                            theorem Crn.dynamicMajority_stabilizes {n : ℕ} (hn : 0 < n) {ι col : Fin n → SignType} {c : Fin n → DynState} (h : Relation.ReflTransGen DynExtStep (ι, dynamicMajority.input ∘ ι) (col, c)) :
                            ∃ (d : Fin n → DynState), dynamicMajority.Reaches c d ∧ dynamicMajority.OutputStableAt DynState.out (fun (x : Fin n) => SignType.sign (∑ v : Fin n, ↑(col v))) d

                            [GHMSS16, Section 3] The dynamic majority protocol with the external force. Start from the colours ι in the states [ι a], and let interactions and colour changes alternate arbitrarily, reaching the colours col and the states c. If the force stops there, the protocol reaches a configuration that is output-stable with the sign of the final colour sum at every agent.

                            Without the external force, the dynamic majority protocol stably computes the sign of #1 - #(-1), like the static one.