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:
drive_dynInv: along every execution, the colours derived from theD-states and theP₂-states satisfy the invariants of Section 3 (Lemma 4 for the composition).drive_stablyMarks: ifDstably marks every agent with its eventual colour (and possibly further outputs), thenD.drive col grpstably marks every agent with the sign of the eventual colour sum of its group, i.e.P₂tolerates the dynamic changes of its inputs whileDstabilizes [GHMSS16, proofs of Theorems 6 and 7].
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
The transition of the driven protocol, unfolded.
A path of D lifts to the driven protocol (same encounters).
If D never changes groups, the group of every agent is constant along paths of the driven
protocol.
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.
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.
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).
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.
[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.
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.