Documentation

Crn.ExactMajorityRelative

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

Algorithm Relative-Majority [GHMSS16, Section 5.1]. Colours are k-bit labels; the winner is the most frequent label, ties broken in favour of the lexicographically largest label (bit 0 first, -1 < 1, i.e. false < true: IsPlurality). Stages i = k-1, …, 0: in stage i, the agents whose labels share the prefix l[0..i-1] form a group, and a copy P₂(i) of the dynamic majority protocol runs inside each group, with colour c[i] = l[i] (as ±1) for the agents whose label won all stages > i (the winner of the group of prefix l[0..i]) and c[i] = 0 for the others. An agent wins stage i if c[i] = -1 and P₂(i) outputs -1, or c[i] = 1 and P₂(i) outputs 0 or 1 (a tie goes to the larger label, wins).

Formalization: the protocol is the k-fold iteration of Protocol.drive (ExactMajorityCompose.lean). Level 0 keeps the label; level m + 1 drives P₂(k-1-m) by level m through the colour stageColour (computed from the label and from whether the agent won the stages k-1, …, k-m), in the groups of the prefixes of length k-1-m. The colours c[i] are derived from the states rather than stored, so a change propagates through all lower stages within the same encounter, as described in [GHMSS16, Section 5.1, Stabilisation Stage 2]. At the end (level k), every agent knows whether its own colour is the winner (RelState.won): the protocol marks the agents of the winning colour [GHMSS16, Section 5].

Main statements:

def Crn.RelState (k : ℕ) :
ℕ → Type

The states of level m of Relative-Majority: the label and the states of P₂ at the stages k-1, …, k-m (the last one outermost).

Equations
Instances For
    @[implicit_reducible]

    Finitely many states.

    Equations
    def Crn.bitAt {k : ℕ} (L : Label k) (i : ℕ) :

    The bit i of a label (false for i ≥ k).

    Equations
    Instances For
      def Crn.prefixMask {k : ℕ} (L : Label k) (j : ℕ) :

      The prefix L[0..j-1] of a label, padded with false: two labels have the same prefix of length j iff their prefixMasks agree.

      Equations
      Instances For
        def Crn.wins (c o : SignType) :

        Whether an agent with colour c for a stage, whose P₂ reports o, wins the stage [GHMSS16, Section 5.1, Stabilisation Stage 2]: c = -1 and o = -1, or c = 1 and o ∈ {0, 1} (a tie goes to the lexicographically larger label).

        Equations
        Instances For
          def Crn.RelState.label {k m : ℕ} :
          RelState k m → Label k

          The label of an agent.

          Equations
          Instances For
            def Crn.RelState.won {k m : ℕ} :
            RelState k m → Bool

            Whether the agent's label won all stages so far (true at level 0; at level m + 1, it won the stages before and wins stage k-1-m against the report of its P₂(k-1-m)).

            Equations
            Instances For
              def Crn.stageColour {k m : ℕ} (q : RelState k m) :

              The colour c[k-1-m] of an agent at level m [GHMSS16, Section 5, memory organisation (2)]: its bit l[k-1-m] as ±1 if it won all stages so far, 0 otherwise.

              Equations
              Instances For

                Level m of Relative-Majority: the label alone at level 0; at level m + 1, the dynamic majority protocol P₂(k-1-m) driven by level m through stageColour, inside the groups of the prefixes of length k-1-m [GHMSS16, Section 5.1].

                Equations
                Instances For

                  Algorithm Relative-Majority [GHMSS16, Section 5.1]: all k stages.

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

                    L wins its group of prefix length j: among the labels with the same prefix L[0..j-1], L is the most frequent, ties broken by the lexicographic order.

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

                      L is the relative majority (plurality) colour [GHMSS16, Section 5]: the most frequent colour, the lexicographically largest one among several most frequent colours.

                      Equations
                      Instances For
                        @[implicit_reducible]
                        noncomputable instance Crn.instDecidablePredLabelIsGroupWinner {k : ℕ} (x : Label k → ℕ) (j : ℕ) :
                        Equations
                        noncomputable def Crn.duelColour {k : ℕ} (x : Label k → ℕ) (i : ℕ) (L : Label k) :

                        The colour at stage i of an agent with label L once the stages > i are stable: L[i] as ±1 if L won its group of prefix length i + 1, 0 otherwise.

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

                          The ranking key of a label: its count first, then the label itself in lex order.

                          Equations
                          Instances For
                            theorem Crn.beats_iff_winKey {k : ℕ} (x : Label k → ℕ) (L' L : Label k) :
                            x L' < x L ∨ x L' = x L ∧ toLex L' ≤ toLex L ↔ winKey x L' ≤ winKey x L
                            theorem Crn.isGroupWinner_iff {k : ℕ} (x : Label k → ℕ) (j : ℕ) (L : Label k) :
                            IsGroupWinner x j L ↔ ∀ (L' : Label k), prefixMask L' j = prefixMask L j → winKey x L' ≤ winKey x L
                            theorem Crn.prefixMask_mono {k : ℕ} {A B : Label k} {j j' : ℕ} (hjj : j ≤ j') (h : prefixMask A j' = prefixMask B j') :
                            theorem Crn.prefixMask_succ_iff {k i : ℕ} (hi : i < k) (A B : Label k) :
                            prefixMask A (i + 1) = prefixMask B (i + 1) ↔ prefixMask A i = prefixMask B i ∧ A ⟨i, hi⟩ = B ⟨i, hi⟩
                            theorem Crn.prefixMask_update {k i : ℕ} (hi : i < k) (L : Label k) (b : Bool) :
                            theorem Crn.exists_groupWinner {k : ℕ} (x : Label k → ℕ) (j : ℕ) (L₀ : Label k) :
                            ∃ (W : Label k), prefixMask W j = prefixMask L₀ j ∧ IsGroupWinner x j W
                            theorem Crn.exists_groupWinner_bit {k : ℕ} (x : Label k → ℕ) {i : ℕ} (hi : i < k) (L : Label k) (b : Bool) :
                            ∃ (W : Label k), prefixMask W i = prefixMask L i ∧ W ⟨i, hi⟩ = b ∧ IsGroupWinner x (i + 1) W
                            theorem Crn.groupWinner_unique {k : ℕ} (x : Label k → ℕ) {j : ℕ} {W W' : Label k} (h : IsGroupWinner x j W) (h' : IsGroupWinner x j W') (hp : prefixMask W j = prefixMask W' j) :
                            W = W'
                            theorem Crn.isGroupWinner_succ {k : ℕ} (x : Label k → ℕ) {i : ℕ} {L : Label k} (h : IsGroupWinner x i L) :
                            IsGroupWinner x (i + 1) L
                            theorem Crn.toLex_lt_of_bit {k i : ℕ} (hi : i < k) {A B : Label k} (hp : prefixMask A i = prefixMask B i) (hA : A ⟨i, hi⟩ = false) (hB : B ⟨i, hi⟩ = true) :
                            theorem Crn.duelColour_of_winner {k : ℕ} (x : Label k → ℕ) {i : ℕ} (hi : i < k) {W : Label k} (hW : IsGroupWinner x (i + 1) W) :
                            duelColour x i W = bitSign (W ⟨i, hi⟩)
                            theorem Crn.wins_one (o : SignType) :
                            wins 1 o = decide (o ≠ -1)
                            theorem Crn.wins_neg_one (o : SignType) :
                            wins (-1) o = decide (o = -1)
                            theorem Crn.duel_sum_eq {k : ℕ} (x : Label k → ℕ) {i : ℕ} (hi : i < k) {Wp Wm L : Label k} (hp : IsGroupWinner x (i + 1) Wp) (hm : IsGroupWinner x (i + 1) Wm) (hpb : Wp ⟨i, hi⟩ = true) (hmb : Wm ⟨i, hi⟩ = false) (hpL : prefixMask Wp i = prefixMask L i) (hmL : prefixMask Wm i = prefixMask L i) :
                            ∑ j : Label k with prefixMask j i = prefixMask L i, ↑(x j) * ↑(duelColour x i j) = ↑(x Wp) - ↑(x Wm)
                            theorem Crn.duel_wins_iff {k : ℕ} (x : Label k → ℕ) {i : ℕ} (hi : i < k) (L : Label k) :
                            wins (duelColour x i L) (SignType.sign (∑ j : Label k with prefixMask j i = prefixMask L i, ↑(x j) * ↑(duelColour x i j))) = decide (IsGroupWinner x i L)

                            [GHMSS16, proof of Theorem 7], one stage. In the group of the prefix L[0..i-1], the sum of the stage-i colours is #W₁ - #W₋₁, W_{±1} the winners of the subgroups of prefixes L[0..i-1]·(±1); the agent with label L wins the duel iff L wins its group of prefix length i.

                            theorem Crn.isGroupWinner_zero_iff {k : ℕ} (x : Label k → ℕ) (L : Label k) :

                            The winner of the group of prefix length 0 is the plurality colour.

                            The transitions of every level keep the labels.

                            The initial state of every level carries the input label.

                            theorem Crn.relativeMajorityLevel_zero_reaches {k n : ℕ} {c d : Fin n → RelState k 0} (h : (relativeMajorityLevel k 0).Reaches c d) :
                            d = c

                            Level 0 never changes a configuration.

                            theorem Crn.prefixMask_self {k : ℕ} (L : Label k) :

                            The prefix of length k is the whole label.

                            theorem Crn.isGroupWinner_self {k : ℕ} (x : Label k → ℕ) (L : Label k) :

                            Every label wins its group of prefix length k (the group of the label alone).

                            theorem Crn.relativeMajority_level_stablyMarks {k m : ℕ} (hm : m ≤ k) :
                            (relativeMajorityLevel k m).StablyMarks (fun (q : RelState k m) => (q.label, q.won)) fun (x : Label k → ℕ) (L : Label k) => (L, decide (IsGroupWinner x (k - m) L))

                            [GHMSS16, proof of Theorem 7], the induction on stages. For m ≤ k, level m stably marks every agent with its label and with whether its label wins its group of prefix length k - m (i.e. the stages k-1, …, k-m have stabilized).

                            [GHMSS16, Theorem 7] Algorithm Relative-Majority stably marks the agents of the relative majority colour: eventually and forever, an agent outputs true iff its colour is the most frequent one (the lexicographically largest among several most frequent ones).

                            theorem Crn.card_relState_level {k : ℕ} (m : ℕ) :
                            Fintype.card (RelState k m) = 2 ^ k * 8 ^ m

                            Level m has 2^k · 8^m states.

                            theorem Crn.card_relState {k : ℕ} :
                            Fintype.card (RelState k k) = 2 ^ k * 8 ^ k ∧ 2 ^ k * 8 ^ k = 2 ^ (4 * k)

                            [GHMSS16, Theorem 7, space] Relative-Majority has 2^k · 8^k = 2^(4k) states (label and k states of P₂): 4k bits.