Documentation

Crn.ExactMajorityAbsolute

Absolute majority with O(k)-bit states (CRN-5, [GHMSS16, Section 4]) #

Colours are k-bit labels L : Fin k → Bool (Label k; [GHMSS16] reads the bits as ±1, bitSign); a population with C ≤ 2^k colours uses C of the labels. Algorithm Absolute-Majority [GHMSS16, Section 4.1]: every agent keeps its label l, runs k independent copies P₁(i) of the static majority protocol on the bits l[i] (bitsProtocol), and a copy of the dynamic majority protocol P₂ whose colour is 1 if the agent's label agrees with all the majority bits currently reported by its P₁(i), and -1 otherwise (absColour); P₂ decides whether the label of the reported majority bits is held by more than half of the agents. An agent outputs some L*, L* the reported majority bits, if its P₂ outputs 1, and none otherwise (absOutput).

Main statements:

@[reducible, inline]
abbrev Crn.Label (k : ℕ) :

k-bit colour labels [GHMSS16, Section 4].

Equations
Instances For

    A bit read as ±1 [GHMSS16, Section 4]: true ↦ 1, false ↦ -1.

    Equations
    Instances For

      The k independent copies P₁(0), …, P₁(k-1) of the static majority protocol on the bits of the labels, the label being kept [GHMSS16, Section 4, memory organisation (1)–(2)]. The Bool output is not used.

      Equations
      • One or more equations did not get rendered due to their size.
      Instances For
        noncomputable def Crn.majBit {k : ℕ} (x : Label k → ℕ) (i : Fin k) :

        The majority bit i of the input counts x: the sign of #(bit i = 1) - #(bit i = 0), the output of P₁(i).

        Equations
        Instances For
          theorem Crn.bitsProtocol_interact_snd {k n : ℕ} (c : Fin n → Label k × (Fin k → StaticState)) (e : AgentPair n) (i : Fin k) :
          (fun (w : Fin n) => ((bitsProtocol k).interact c e w).2 i) = staticMajority.interact (fun (w : Fin n) => (c w).2 i) e

          Component i of an encounter of bitsProtocol is an encounter of P₁.

          theorem Crn.bitsProtocol_interact_fst {k n : ℕ} (c : Fin n → Label k × (Fin k → StaticState)) (e : AgentPair n) :
          (fun (w : Fin n) => ((bitsProtocol k).interact c e w).1) = fun (w : Fin n) => (c w).1

          Encounters of bitsProtocol keep the labels.

          theorem Crn.bitsProtocol_reaches_snd {k n : ℕ} {c d : Fin n → Label k × (Fin k → StaticState)} (h : (bitsProtocol k).Reaches c d) (i : Fin k) :
          staticMajority.Reaches (fun (w : Fin n) => (c w).2 i) fun (w : Fin n) => (d w).2 i

          Paths of bitsProtocol project to paths of P₁ in every component.

          theorem Crn.bitsProtocol_reaches_fst {k n : ℕ} {c d : Fin n → Label k × (Fin k → StaticState)} (h : (bitsProtocol k).Reaches c d) :
          (fun (w : Fin n) => (d w).1) = fun (w : Fin n) => (c w).1

          Paths of bitsProtocol keep the labels.

          theorem Crn.bitsProtocol_lift {k n : ℕ} (i : Fin k) {c₁ d₁ : Fin n → StaticState} (h : staticMajority.Reaches c₁ d₁) (c : Fin n → Label k × (Fin k → StaticState)) (hc : (fun (w : Fin n) => (c w).2 i) = c₁) :
          ∃ (d : Fin n → Label k × (Fin k → StaticState)), (bitsProtocol k).Reaches c d ∧ (fun (w : Fin n) => (d w).2 i) = d₁

          A path of P₁ in component i lifts to bitsProtocol (same encounters).

          theorem Crn.sign_counts_bit_eq_majBit {k n : ℕ} (ι : Fin n → Label k) (i : Fin k) :
          SignType.sign (↑(↑(counts fun (v : Fin n) => bitSign (ι v i)) 1) - ↑(↑(counts fun (v : Fin n) => bitSign (ι v i)) (-1))) = majBit (↑(counts ι)) i

          The output of P₁(i) is the majority bit i: #(bit i = 1) - #(bit i = 0) is ∑_L x_L · bitSign (L i).

          theorem Crn.bitsProtocol_stablyMarks {k : ℕ} :
          (bitsProtocol k).StablyMarks (fun (q : Label k × (Fin k → StaticState)) => (fun (i : Fin k) => (q.2 i).out, q.1)) fun (x : Label k → ℕ) (L : Label k) => (majBit x, L)

          [GHMSS16, Section 4] The k copies of P₁ stably compute the k majority bits, and every agent keeps its label.

          def Crn.absColour {k : ℕ} (q : Label k × (Fin k → StaticState)) :

          The colour of an agent for P₂ [GHMSS16, Section 4.1, Initialisation Stage 2]: 1 if every P₁(i) currently reports the agent's own bit l[i] as the majority bit, -1 otherwise.

          Equations
          Instances For

            Algorithm Absolute-Majority [GHMSS16, Section 4.1]: P₂ driven by the k copies of P₁ through absColour, in a single group.

            Equations
            Instances For
              def Crn.absOutput {k : ℕ} (p : (Label k × (Fin k → StaticState)) × DynState) :

              The output of Absolute-Majority: some L*, L* the majority bits reported by the copies of P₁, if P₂ reports colour 1 in the majority; none (no absolute majority) otherwise.

              Equations
              Instances For
                def Crn.IsAbsMajority {k : ℕ} (x : Label k → ℕ) (L : Label k) :

                L is an absolute majority colour: more than half of the agents have colour L.

                Equations
                Instances For
                  noncomputable def Crn.absMajority {k : ℕ} (x : Label k → ℕ) :

                  The absolute majority colour of the counts x, or none if there is none.

                  Equations
                  Instances For
                    theorem Crn.absMajority_eq_some_iff {k : ℕ} (x : Label k → ℕ) (L : Label k) :

                    There is at most one absolute majority colour, and absMajority returns it.

                    noncomputable def Crn.absTarget {k : ℕ} (x : Label k → ℕ) (L : Label k) :

                    The eventual colour for P₂ of an agent with label L: 1 if L agrees with all majority bits, -1 otherwise.

                    Equations
                    Instances For
                      theorem Crn.bitSign_mul_mul_bitSign (b : Bool) (a : ℤ) :
                      ↑(bitSign b) * (a * ↑(bitSign b)) = a

                      A sign ±1 squared is 1.

                      theorem Crn.neg_le_bitSign_mul (b c : Bool) {a : ℤ} (ha : 0 ≤ a) :
                      -a ≤ ↑(bitSign b) * (a * ↑(bitSign c))

                      A product of two signs ±1 with a ≥ 0 is at least -a.

                      theorem Crn.sign_eq_bitSign_of_pos (b : Bool) {S : ℤ} (h : 0 < ↑(bitSign b) * S) :

                      If s * S > 0 for a sign s = ±1, then sign S = s.

                      theorem Crn.majBit_eq_bitSign_of_isAbsMajority {k : ℕ} {x : Label k → ℕ} {L : Label k} (h : IsAbsMajority x L) (i : Fin k) :
                      majBit x i = bitSign (L i)

                      The majority bits of an absolute majority colour are its bits (the proof of majBit_eq_of_isAbsMajority).

                      theorem Crn.sum_mul_absTarget_of {k : ℕ} {x : Label k → ℕ} {L : Label k} (hL : ∀ (i : Fin k), majBit x i = bitSign (L i)) :
                      ∑ L' : Label k, ↑(x L') * ↑(absTarget x L') = 2 * ↑(x L) - ∑ L' : Label k, ↑(x L')

                      If L matches every majority bit, the absTarget-weighted sum is 2 x L - n.

                      theorem Crn.absTarget_sum_sign_eq_one_iff {k : ℕ} (x : Label k → ℕ) :
                      SignType.sign (∑ L : Label k, ↑(x L) * ↑(absTarget x L)) = 1 ↔ ∃ (L : Label k), IsAbsMajority x L

                      [GHMSS16, proof of Theorem 6] The final test of P₂: the eventual colour sum #(L = L*) - #(L ≠ L*) is positive iff some colour is an absolute majority (it is then L*).

                      theorem Crn.majBit_eq_of_isAbsMajority {k : ℕ} {x : Label k → ℕ} {L : Label k} (h : IsAbsMajority x L) (i : Fin k) :
                      majBit x i = bitSign (L i)

                      [GHMSS16, proof of Theorem 6] The majority bits of an absolute majority colour are its bits.

                      [GHMSS16, Theorem 6] Algorithm Absolute-Majority stably computes the absolute majority: all agents eventually and forever output some L if more than half of the agents have colour L, and none if there is no such colour.

                      theorem Crn.card_absState {k : ℕ} :
                      Fintype.card ((Label k × (Fin k → StaticState)) × DynState) = 2 ^ k * 6 ^ k * 8 ∧ 2 ^ k * 6 ^ k * 8 ≤ 2 ^ (4 * k + 3)

                      [GHMSS16, Theorem 6, space] Absolute-Majority has 2^k · 6^k · 8 states (label, k states of P₁, one state of P₂), at most 2^(4k+3): O(k) bits.