Documentation

Crn.ExactMajorityOutput

Stable computation with general outputs (CRN-5) #

Protocol.StablyComputes (CRN-3) computes predicates: every agent outputs a Bool through the output field of the protocol, and all agents agree. The exact majority and plurality protocols of [GHMSS16] need two generalizations, which only change the output convention (the transitions, Protocol.Reaches and the fair-execution semantics in reachability form are those of StableBasic.lean):

StablyComputesWith P O f is the uniform case, and StablyComputesWith P P.output φ is exactly P.StablyComputes φ (stablyComputesWith_output_iff).

References #

def Crn.Protocol.OutputStableAt {X : Type u_1} {Q : Type u_2} {Y : Type u_3} {n : ℕ} (P : Protocol X Q) (O : Q → Y) (y : Fin n → Y) (c : Fin n → Q) :

c is output-stable for the output map O with the target outputs y (one per agent): in every configuration reachable from c, every agent v outputs y v.

Equations
Instances For
    def Crn.Protocol.StablyMarks {X : Type u_1} {Q : Type u_2} {Y : Type u_3} [Fintype X] [DecidableEq X] (P : Protocol X Q) (O : Q → Y) (g : (X → ℕ) → X → Y) :

    P stably marks the agents with g through the output map O: for every nonempty population and input assignment ι, every configuration reachable from I ∘ ι reaches a configuration that is output-stable with the output g x (ι v) at each agent v, where x is the input count vector. This is StablyComputes with outputs in Y that may depend on the agent's own input symbol.

    Equations
    • One or more equations did not get rendered due to their size.
    Instances For
      def Crn.Protocol.StablyComputesWith {X : Type u_1} {Q : Type u_2} {Y : Type u_3} [Fintype X] [DecidableEq X] (P : Protocol X Q) (O : Q → Y) (f : (X → ℕ) → Y) :

      P stably computes f : (X → ℕ) → Y through the output map O: all agents eventually and forever output f of the input counts (StablyMarks with a target independent of the agent).

      Equations
      Instances For
        theorem Crn.Protocol.stablyComputesWith_output_iff {X : Type u_1} {Q : Type u_2} [Fintype X] [DecidableEq X] (P : Protocol X Q) (φ : (X → ℕ) → Bool) :

        With the protocol's own Bool output, StablyComputesWith is StablyComputes (CRN-3).

        theorem Crn.Protocol.StablyMarks.map {X : Type u_1} {Q : Type u_2} {Y : Type u_3} {Z : Type u_4} [Fintype X] [DecidableEq X] {P : Protocol X Q} {O : Q → Y} {g : (X → ℕ) → X → Y} (h : P.StablyMarks O g) (F : Y → Z) :
        P.StablyMarks (fun (q : Q) => F (O q)) fun (x : X → ℕ) (i : X) => F (g x i)

        Post-composing the outputs: if P stably marks with g through O, it stably marks with F ∘ g through F ∘ O.

        theorem Crn.Protocol.StablyMarks.congr {X : Type u_1} {Q : Type u_2} {Y : Type u_3} [Fintype X] [DecidableEq X] {P : Protocol X Q} {O O' : Q → Y} {g g' : (X → ℕ) → X → Y} (h : P.StablyMarks O g) (hO : ∀ (q : Q), O q = O' q) (hg : ∀ (x : X → ℕ) (i : X), g x i = g' x i) :
        P.StablyMarks O' g'

        StablyMarks only evaluates the output map and the targets.

        Tools for the proofs of CRN-5 #

        theorem Crn.Protocol.outputStableAt_of_invariant {X : Type u_1} {Q : Type u_2} {Y : Type u_3} {n : ℕ} {P : Protocol X Q} {O : Q → Y} {y : Fin n → Y} {I : (Fin n → Q) → Prop} (hI : ∀ (c d : Fin n → Q), I c → P.Step c d → I d) (hO : ∀ (c : Fin n → Q), I c → ∀ (v : Fin n), O (c v) = y v) {c : Fin n → Q} (hc : I c) :

        A property preserved by every step, under which every agent v outputs y v, gives output-stability with the targets y.

        theorem Crn.Protocol.sum_interact {X : Type u_1} {Q : Type u_2} {n : ℕ} {M : Type u_5} [AddCommMonoid M] (P : Protocol X Q) (F : Q → M) (c : Fin n → Q) (e : AgentPair n) :
        ∑ w : Fin n, F (P.interact c e w) + (F (c (↑e).1) + F (c (↑e).2)) = ∑ w : Fin n, F (c w) + (F (P.δ (c (↑e).1, c (↑e).2)).1 + F (P.δ (c (↑e).1, c (↑e).2)).2)

        Sums over agents across an encounter: only the initiator and the responder change.

        theorem Crn.Protocol.forall_step {X : Type u_1} {Q : Type u_2} {n : ℕ} {P : Protocol X Q} {p : Q → Prop} (hp : ∀ (a b : Q), p a → p b → p (P.δ (a, b)).1 ∧ p (P.δ (a, b)).2) {c d : Fin n → Q} (h : P.Step c d) (hc : ∀ (v : Fin n), p (c v)) (v : Fin n) :
        p (d v)

        If every state of an encounter satisfies p whenever both states before it do, then "every agent satisfies p" is preserved by steps.

        theorem Crn.Protocol.exists_step {X : Type u_1} {Q : Type u_2} {n : ℕ} {P : Protocol X Q} {p : Q → Prop} (hp : ∀ (a b : Q), p a ∨ p b → p (P.δ (a, b)).1 ∨ p (P.δ (a, b)).2) {c d : Fin n → Q} (h : P.Step c d) (hc : ∃ (v : Fin n), p (c v)) :
        ∃ (v : Fin n), p (d v)

        If some state after an encounter satisfies p whenever some state before it does, then "some agent satisfies p" is preserved by steps.

        theorem Crn.exists_reflTransGen_of_measure {α : Type u_5} {r : α → α → Prop} (I G : α → Prop) (μ : α → ℕ) (h : ∀ (a : α), I a → G a ∨ ∃ (b : α), r a b ∧ I b ∧ μ b < μ a) {a : α} (ha : I a) :
        ∃ (b : α), Relation.ReflTransGen r a b ∧ I b ∧ G b

        Strong induction on a potential μ: if from every a satisfying I either G a holds or a step leads to some b satisfying I with a smaller potential, then from every a satisfying I a configuration satisfying I and G is reachable.

        theorem Crn.exists_recruit {Q : Type u_2} {n : ℕ} {r : (Fin n → Q) → (Fin n → Q) → Prop} (I : (Fin n → Q) → Prop) (T : Fin n → Q → Prop) (h : ∀ (c : Fin n → Q), I c → ∀ (v : Fin n), ¬T v (c v) → ∃ (c' : Fin n → Q), r c c' ∧ I c' ∧ T v (c' v) ∧ ∀ (w : Fin n), T w (c w) → T w (c' w)) {c : Fin n → Q} (hc : I c) :
        ∃ (d : Fin n → Q), Relation.ReflTransGen r c d ∧ I d ∧ ∀ (v : Fin n), T v (d v)

        Recruitment: if every agent v outside its target set T v can be moved into it by a step that keeps I and moves no other agent out of its target set, then a configuration satisfying I with every agent in its target set is reachable (a strong induction on the number of agents outside their target sets).