Documentation

Crn.ExactMajorityCompose

Driving the dynamic majority protocol by another protocol (CRN-5, [GHMSS16, Sections 4–5]) #

The composition step of [GHMSS16, Sections 4 and 5]: a protocol D (the driver) runs, and every agent derives from its D-state a colour col q ∈ {-1, 0, 1} for a copy of the dynamic majority protocol P₂. The changes of these colours are the external force of P₂ [GHMSS16, Section 3]. In D.drive col grp, the states are pairs (q, s), s a state of P₂; in an encounter, D makes its transition, P₂ makes its transition if the two agents are in the same group (grp, a function of the D-state that D never changes: the label prefix in Section 5, a single group in Section 4), and then each agent whose colour changed applies the state change of Fig. 3 (DynState.recolour). Initially the P₂-state is [col q].

Main statements:

def Crn.Protocol.drive {X : Type u_1} {Q : Type u_2} {G : Type u_3} [DecidableEq G] (D : Protocol X Q) (col : Q → SignType) (grp : Q → G) :

The dynamic majority protocol driven by D through the colours col, run inside the groups grp [GHMSS16, Sections 4–5]: D makes its transition, P₂ makes its transition between agents of the same group, then each agent recolours its P₂-state from its old colour to its new colour. The Bool output (the P₂-output is 1) is not used.

Equations
  • One or more equations did not get rendered due to their size.
Instances For
    theorem Crn.Protocol.drive_δ {X : Type u_1} {Q : Type u_2} {G : Type u_3} [DecidableEq G] {D : Protocol X Q} {col : Q → SignType} {grp : Q → G} (p q : Q × DynState) :
    (D.drive col grp).δ (p, q) = (((D.δ (p.1, q.1)).1, DynState.recolour (col p.1) (col (D.δ (p.1, q.1)).1) (if grp p.1 = grp q.1 then DynState.δ (p.2, q.2) else (p.2, q.2)).1), (D.δ (p.1, q.1)).2, DynState.recolour (col q.1) (col (D.δ (p.1, q.1)).2) (if grp p.1 = grp q.1 then DynState.δ (p.2, q.2) else (p.2, q.2)).2)

    The transition of the driven protocol, unfolded.

    theorem Crn.Protocol.drive_interact_fst {X : Type u_1} {Q : Type u_2} {G : Type u_3} [DecidableEq G] {n : ℕ} {D : Protocol X Q} {col : Q → SignType} {grp : Q → G} (c : Fin n → Q × DynState) (e : AgentPair n) :
    (fun (w : Fin n) => ((D.drive col grp).interact c e w).1) = D.interact (fun (w : Fin n) => (c w).1) e

    The D-states of an encounter of the driven protocol make an encounter of D.

    theorem Crn.Protocol.drive_reaches_fst {X : Type u_1} {Q : Type u_2} {G : Type u_3} [DecidableEq G] {n : ℕ} {D : Protocol X Q} {col : Q → SignType} {grp : Q → G} {c d : Fin n → Q × DynState} (h : (D.drive col grp).Reaches c d) :
    D.Reaches (fun (w : Fin n) => (c w).1) fun (w : Fin n) => (d w).1

    Paths of the driven protocol project to paths of D.

    theorem Crn.Protocol.drive_lift_fst {X : Type u_1} {Q : Type u_2} {G : Type u_3} [DecidableEq G] {n : ℕ} {D : Protocol X Q} {col : Q → SignType} {grp : Q → G} {c₁ d₁ : Fin n → Q} (h : D.Reaches c₁ d₁) (c : Fin n → Q × DynState) (hc : (fun (w : Fin n) => (c w).1) = c₁) :
    ∃ (d : Fin n → Q × DynState), (D.drive col grp).Reaches c d ∧ (fun (w : Fin n) => (d w).1) = d₁

    A path of D lifts to the driven protocol (same encounters).

    theorem Crn.Protocol.drive_grp {X : Type u_1} {Q : Type u_2} {G : Type u_3} [DecidableEq G] {n : ℕ} {D : Protocol X Q} {col : Q → SignType} {grp : Q → G} (hgrp : ∀ (p q : Q), grp (D.δ (p, q)).1 = grp p ∧ grp (D.δ (p, q)).2 = grp q) {c d : Fin n → Q × DynState} (h : (D.drive col grp).Reaches c d) (w : Fin n) :
    grp (d w).1 = grp (c w).1

    If D never changes groups, the group of every agent is constant along paths of the driven protocol.

    theorem Crn.Protocol.drive_interact_snd {X : Type u_1} {Q : Type u_2} {G : Type u_3} [DecidableEq G] {n : ℕ} {D : Protocol X Q} {col : Q → SignType} {grp : Q → G} (c : Fin n → Q × DynState) (e : AgentPair n) (h1 : col (D.δ ((c (↑e).1).1, (c (↑e).2).1)).1 = col (c (↑e).1).1) (h2 : col (D.δ ((c (↑e).1).1, (c (↑e).2).1)).2 = col (c (↑e).2).1) :
    (fun (w : Fin n) => ((D.drive col grp).interact c e w).2) = if grp (c (↑e).1).1 = grp (c (↑e).2).1 then dynamicMajority.interact (fun (w : Fin n) => (c w).2) e else fun (w : Fin n) => (c w).2

    If the transition of D does not change the colours of the two agents, the P₂-states of an encounter of the driven protocol make an encounter of P₂ if the agents are in the same group, and do not change otherwise.

    theorem Crn.Protocol.drive_lift_snd {X : Type u_1} {Q : Type u_2} {G : Type u_3} [DecidableEq G] {n : ℕ} {D : Protocol X Q} {col : Q → SignType} {grp : Q → G} (hgrp : ∀ (p q : Q), grp (D.δ (p, q)).1 = grp p ∧ grp (D.δ (p, q)).2 = grp q) {g : Fin n → G} {κ : Fin n → SignType} {c : Fin n → Q × DynState} (hg : ∀ (w : Fin n), grp (c w).1 = g w) (hκ : ∀ (d₁ : Fin n → Q), D.Reaches (fun (w : Fin n) => (c w).1) d₁ → ∀ (w : Fin n), col (d₁ w) = κ w) {d₂ : Fin n → DynState} (h : dynamicMajority.GReaches g (fun (w : Fin n) => (c w).2) d₂) :
    ∃ (d : Fin n → Q × DynState), (D.drive col grp).Reaches c d ∧ (fun (w : Fin n) => (d w).2) = d₂

    If every D-configuration reachable from the D-part of c has the colours κ, then a path of P₂ inside the groups g (the groups of the agents in c) lifts to the driven protocol.

    theorem Crn.Protocol.drive_greaches_snd {X : Type u_1} {Q : Type u_2} {G : Type u_3} [DecidableEq G] {n : ℕ} {D : Protocol X Q} {col : Q → SignType} {grp : Q → G} (hgrp : ∀ (p q : Q), grp (D.δ (p, q)).1 = grp p ∧ grp (D.δ (p, q)).2 = grp q) {g : Fin n → G} {κ : Fin n → SignType} {c : Fin n → Q × DynState} (hg : ∀ (w : Fin n), grp (c w).1 = g w) (hκ : ∀ (d₁ : Fin n → Q), D.Reaches (fun (w : Fin n) => (c w).1) d₁ → ∀ (w : Fin n), col (d₁ w) = κ w) {d : Fin n → Q × DynState} (h : (D.drive col grp).Reaches c d) :
    dynamicMajority.GReaches g (fun (w : Fin n) => (c w).2) fun (w : Fin n) => (d w).2

    If every D-configuration reachable from the D-part of c has the colours κ, then paths of the driven protocol from c project to paths of P₂ inside the groups g (the groups of the agents in c).

    theorem Crn.Protocol.drive_dynInv_interact {X : Type u_1} {Q : Type u_2} {G : Type u_3} [DecidableEq G] {n : ℕ} {D : Protocol X Q} {col : Q → SignType} {grp : Q → G} (hgrp : ∀ (p q : Q), grp (D.δ (p, q)).1 = grp p ∧ grp (D.δ (p, q)).2 = grp q) {c : Fin n → Q × DynState} (hc : DynInv (fun (v : Fin n) => grp (c v).1) (fun (v : Fin n) => col (c v).1) fun (v : Fin n) => (c v).2) (e : AgentPair n) :
    DynInv (fun (v : Fin n) => grp ((D.drive col grp).interact c e v).1) (fun (v : Fin n) => col ((D.drive col grp).interact c e v).1) fun (v : Fin n) => ((D.drive col grp).interact c e v).2

    One encounter of the driven protocol preserves the invariants of Section 3: it is an interaction of P₂ inside a group (or nothing), followed by the colour changes of its two agents.

    theorem Crn.Protocol.drive_dynInv {X : Type u_1} {Q : Type u_2} {G : Type u_3} [DecidableEq G] {n : ℕ} {D : Protocol X Q} {col : Q → SignType} {grp : Q → G} (hgrp : ∀ (p q : Q), grp (D.δ (p, q)).1 = grp p ∧ grp (D.δ (p, q)).2 = grp q) (ι : Fin n → X) {c : Fin n → Q × DynState} (h : (D.drive col grp).Reaches ((D.drive col grp).input ∘ ι) c) :
    DynInv (fun (v : Fin n) => grp (c v).1) (fun (v : Fin n) => col (c v).1) fun (v : Fin n) => (c v).2

    [GHMSS16, Lemma 4] for the composition. If D never changes the group of an agent, then along every execution of D.drive col grp the derived colours and the P₂-states satisfy the invariants of Section 3, with the groups given by the D-states.

    theorem Crn.Protocol.drive_stablyMarks {X : Type u_1} {Q : Type u_2} {G : Type u_3} {Y : Type u_4} [DecidableEq G] {D : Protocol X Q} {col : Q → SignType} {grp : Q → G} [Fintype X] [DecidableEq X] (hgrp : ∀ (p q : Q), grp (D.δ (p, q)).1 = grp p ∧ grp (D.δ (p, q)).2 = grp q) {γ : X → G} (hγ : ∀ (i : X), grp (D.input i) = γ i) {O : Q → Y} {gO : (X → ℕ) → X → Y} {gc : (X → ℕ) → X → SignType} (hD : D.StablyMarks (fun (q : Q) => (O q, col q)) fun (x : X → ℕ) (i : X) => (gO x i, gc x i)) :
    (D.drive col grp).StablyMarks (fun (p : Q × DynState) => (O p.1, p.2.out)) fun (x : X → ℕ) (i : X) => (gO x i, SignType.sign (∑ j : X with γ j = γ i, ↑(x j) * ↑(gc x j)))

    The composition step [GHMSS16, proofs of Theorems 6 and 7]. Let D never change groups, with the group of an agent with input i equal to γ i. If D stably marks the agents with the outputs O and the colours col (targets gO and gc), then the driven protocol stably marks them with the outputs O and with the P₂-output equal to the sign of the eventual colour sum of the group: sign (∑_{j : γ j = γ i} x_j · gc(x, j)) for an agent with input i.