Documentation

Plurality.Rules

3-input rules that solve plurality consensus (Section 4.2) #

A 3-input rule f : Fin k → Fin k → Fin k → Fin k is applied by every node to the colors of its three samples (stepWith f). The paper characterizes the rules that solve plurality consensus by two properties:

This file contains the definitions and the tools shared by the two parts of Theorem 4.8: the counts Δ and δ, the solver predicate, and the fact that consensus on a color is impossible once that color has disappeared (mono_le_alive).

@[reducible, inline]
abbrev Plurality.Rule (k : ℕ) :

A 3-input rule.

Equations
Instances For
    def Plurality.Conservative {k : ℕ} (f : Rule k) :

    A rule is a 3-dynamics in the sense of Definition 4.3: it returns one of the colors it sees.

    Equations
    Instances For

      Clear-majority property (Definition 4.4).

      Equations
      Instances For
        def Plurality.majCount {k : ℕ} (f : Rule k) (r b : Fin k) :

        Δ_r for the pair (r, b): on how many of the three orderings of (r, r, b) the rule returns r.

        Equations
        Instances For
          def Plurality.deltaCount {k : ℕ} (f : Rule k) (r g b c : Fin k) :

          δ_c for the triple (r, g, b): on how many of the six orderings of (r, g, b) the rule returns c.

          Equations
          • One or more equations did not get rendered due to their size.
          Instances For
            def Plurality.UniformRule {k : ℕ} (f : Rule k) :

            Uniform property (Definition 4.5).

            Equations
            Instances For
              def Plurality.Solver {k : ℕ} (f : Rule k) (n : ℕ) (s ε : ℝ) :

              (s, ε)-solver (Definition 4.7): from every coloring in which m is the unique plurality color with bias at least s, the probability that all nodes eventually support m is at least 1 - ε. Consensus is absorbing, so "eventually" is the supremum over the horizon T.

              Equations
              • One or more equations did not get rendered due to their size.
              Instances For
                theorem Plurality.deltaCount_sum {k : ℕ} {f : Rule k} (hf : Conservative f) {r g b : Fin k} (hrg : r ≠ g) (hgb : g ≠ b) (hrb : r ≠ b) :
                deltaCount f r g b r + deltaCount f r g b g + deltaCount f r g b b = 6

                The counts of the three distinct colors sum to 6.

                theorem Plurality.deltaCount_swap12 {k : ℕ} (f : Rule k) (r g b c : Fin k) :
                deltaCount f g r b c = deltaCount f r g b c

                δ does not depend on the order in which the triple is listed.

                theorem Plurality.deltaCount_swap13 {k : ℕ} (f : Rule k) (r g b c : Fin k) :
                deltaCount f b g r c = deltaCount f r g b c

                Absorption for conservative rules #

                theorem Plurality.count_stepWith_eq_zero {n k : ℕ} {f : Rule k} (hf : Conservative f) (x : Config n k) {j : Fin k} (hj : count x j = 0) (r : ThreeMajority.Tgt3 n) :
                count (stepWith f x r) j = 0
                theorem Plurality.count_runWith_eq_zero {n k : ℕ} {f : Rule k} (hf : Conservative f) (x : Config n k) {j : Fin k} (hj : count x j = 0) (l : List (ThreeMajority.Tgt3 n)) :
                count (runWith f x l) j = 0
                theorem Plurality.mono_le_alive {n k : ℕ} (hn : 1 ≤ n) {f : Rule k} (hf : Conservative f) (x : Config n k) (m : Fin k) (T T₀ : ℕ) :

                Consensus needs survival. For every horizon T, the probability of consensus on m at time T is at most the probability that m still has a node at any fixed time T₀.

                Sums over the sampled colors #

                theorem Plurality.sum_triple_factor {k : ℕ} (w P Q R : Fin k → ℝ) :
                ∑ a : Fin k, ∑ b : Fin k, ∑ c : Fin k, w a * w b * w c * (P a * Q b * R c) = ((∑ a : Fin k, w a * P a) * ∑ b : Fin k, w b * Q b) * ∑ c : Fin k, w c * R c

                A triple sum of weights against a product of functions factorizes.

                theorem Plurality.sum_weight_ind {k : ℕ} (w : Fin k → ℝ) (c : Fin k) :
                (∑ a : Fin k, w a * if a = c then 1 else 0) = w c