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):
- outputs in an arbitrary type
Y, read through a separate mapO : Q → Y(the sign of a majority vote in [GHMSS16, Theorem 3], the absolute majority colour or none in [GHMSS16, Theorem 6]); this is the function-computation convention of Chen, Doty and Soloveichik (2014); - outputs that depend on the agent's own input symbol (
StablyMarks): in the relative majority protocol [GHMSS16, Theorem 7] the agents end up marked, each one knowing whether its own colour is the winner, not the winner's label.
StablyComputesWith P O f is the uniform case, and StablyComputesWith P P.output φ is exactly
P.StablyComputes φ (stablyComputesWith_output_iff).
References #
- [GHMSS16] L. Gąsieniec, D. Hamilton, R. Martin, P. G. Spirakis, G. Stachowiak, Deterministic population protocols for exact majority and plurality, OPODIS 2016, LIPIcs 70, Article 14.
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
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
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
- P.StablyComputesWith O f = P.StablyMarks O fun (x : X → ℕ) (x_1 : X) => f x
Instances For
With the protocol's own Bool output, StablyComputesWith is StablyComputes (CRN-3).
Post-composing the outputs: if P stably marks with g through O, it stably marks with
F ∘ g through F ∘ O.
StablyMarks only evaluates the output map and the targets.
Tools for the proofs of CRN-5 #
A property preserved by every step, under which every agent v outputs y v, gives
output-stability with the targets y.
Sums over agents across an encounter: only the initiator and the responder change.
If every state of an encounter satisfies p whenever both states before it do, then
"every agent satisfies p" is preserved by steps.
If some state after an encounter satisfies p whenever some state before it does, then
"some agent satisfies p" is preserved by steps.
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.
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).