Documentation

ThreeMajority.AnyStartModel

3-Majority and Voter with any number of colours (roadmap MAJ-6, part (b)) #

Model of Berenbrink, Clementi, Elsässer, Kling, Mallmann-Trenn, Natale, Ignore or Comply? On breaking symmetry in consensus, PODC 2017, arXiv:1702.04921 (v1), Section 2.1. Each of n agents holds a colour of an arbitrary type σ; the paper's colours [k] ⊆ [n] are σ = Fin n.

def ThreeMajority.voterStep {n : ℕ} {σ : Type u_1} (c : Fin n → σ) (y : Fin n → Fin n) :
Fin n → σ

One round of the Voter process (BCEKMN17, Section 2.2, Equation (1)): agent v adopts the colour of agent y v.

Equations
Instances For
    def ThreeMajority.voterRun {n : ℕ} {σ : Type u_1} (c : Fin n → σ) :
    List (Fin n → Fin n) → Fin n → σ

    The configuration of the Voter process after consuming a list of rounds.

    Equations
    Instances For
      @[simp]
      theorem ThreeMajority.voterRun_cons {n : ℕ} {σ : Type u_1} (c : Fin n → σ) (y : Fin n → Fin n) (l : List (Fin n → Fin n)) :
      voterRun c (y :: l) = voterRun (voterStep c y) l
      theorem ThreeMajority.voterRun_eq_foldl {n : ℕ} {σ : Type u_1} (c : Fin n → σ) (l : List (Fin n → Fin n)) :
      def ThreeMajority.majColour {n : ℕ} {σ : Type u_1} [DecidableEq σ] (c : Fin n → σ) (s : Fin n × Fin n × Fin n) :
      σ

      The 3-Majority update rule on a sample triple s = (s₁, s₂, s₃) (BCEKMN17, Section 2.2): if the second and third samples agree, adopt their colour (a majority); otherwise the first sample's colour is a majority or all three colours differ, and the first sample's colour is adopted.

      Equations
      Instances For
        def ThreeMajority.stepCol {n : ℕ} {σ : Type u_1} [DecidableEq σ] (c : Fin n → σ) (r : Tgt3 n) :
        Fin n → σ

        One round of 3-Majority with any number of colours (BCEKMN17, Section 2.2).

        Equations
        Instances For
          def ThreeMajority.runCol {n : ℕ} {σ : Type u_1} [DecidableEq σ] (c : Fin n → σ) :
          List (Tgt3 n) → Fin n → σ

          The configuration of 3-Majority after consuming a list of rounds.

          Equations
          Instances For
            def ThreeMajority.colourCount {n : ℕ} {σ : Type u_1} [DecidableEq σ] (c : Fin n → σ) (a : σ) :

            The number c_a of agents of colour a: the configuration vector of BCEKMN17, Section 2.1.

            Equations
            Instances For
              def ThreeMajority.numColours {n : ℕ} {σ : Type u_1} [DecidableEq σ] (c : Fin n → σ) :

              The number of remaining colours of a configuration. Consensus is numColours c ≤ 1.

              Equations
              Instances For
                @[simp]
                theorem ThreeMajority.runCol_nil {n : ℕ} {σ : Type u_1} [DecidableEq σ] (c : Fin n → σ) :
                runCol c [] = c
                @[simp]
                theorem ThreeMajority.runCol_cons {n : ℕ} {σ : Type u_1} [DecidableEq σ] (c : Fin n → σ) (r : Tgt3 n) (l : List (Tgt3 n)) :
                runCol c (r :: l) = runCol (stepCol c r) l
                theorem ThreeMajority.runCol_eq_foldl {n : ℕ} {σ : Type u_1} [DecidableEq σ] (c : Fin n → σ) (l : List (Tgt3 n)) :
                theorem ThreeMajority.runCol_append {n : ℕ} {σ : Type u_1} [DecidableEq σ] (c : Fin n → σ) (l₁ l₂ : List (Tgt3 n)) :
                runCol c (l₁ ++ l₂) = runCol (runCol c l₁) l₂
                theorem ThreeMajority.stepCol_bool {n : ℕ} (c : Fin n → Bool) (r : Tgt3 n) :
                {v : Fin n | stepCol c r v = true} = step {v : Fin n | c v = true} r

                Bridge to the two-opinion model. With colours Bool, the agents of colour true after one round of stepCol are the opinion-1 set after one round of the two-opinion step.

                theorem ThreeMajority.stepCol_comp {n : ℕ} {σ : Type u_1} [DecidableEq σ] {τ : Type u_2} [DecidableEq τ] {g : σ → τ} (hg : Function.Injective g) (c : Fin n → σ) (r : Tgt3 n) :
                stepCol (g ∘ c) r = g ∘ stepCol c r

                Renaming the colours by an injective map commutes with a round: the rule only compares colours.

                theorem ThreeMajority.image_stepCol_subset {n : ℕ} {σ : Type u_1} [DecidableEq σ] (c : Fin n → σ) (r : Tgt3 n) :

                3-Majority never creates a colour: the colours after a round are among the current ones.

                theorem ThreeMajority.numColours_stepCol_le {n : ℕ} {σ : Type u_1} [DecidableEq σ] (c : Fin n → σ) (r : Tgt3 n) :
                theorem ThreeMajority.numColours_runCol_append_le {n : ℕ} {σ : Type u_1} [DecidableEq σ] (c : Fin n → σ) (l₁ l₂ : List (Tgt3 n)) :
                numColours (runCol c (l₁ ++ l₂)) ≤ numColours (runCol c l₁)

                The number of colours of 3-Majority never increases along a trajectory; hence the event "at most κ colours at time T" is the event "at most κ colours by time T", and fixed-time bounds are bounds on the hitting times T^κ of the paper.

                theorem ThreeMajority.numColours_voterStep_le {n : ℕ} {σ : Type u_1} [DecidableEq σ] (c : Fin n → σ) (y : Fin n → Fin n) :