The median dynamics: definitions #
Doerr, Goldberg, Minder, Sauerwald and Scheideler, Stabilizing consensus with the power of two choices (SPAA 2011): every node holds a value from a linearly ordered set; in each round it samples two nodes uniformly at random (independently, with replacement) and adopts the median of its own value and the two sampled values. With two values this is the 2-Choices dynamics.
Median of three elements of a linear order.
Instances For
@[reducible, inline]
Configurations of n nodes with values in α.
Equations
- Median.Config n α = (Fin n → α)
Instances For
@[reducible, inline]
A round: the two nodes sampled by every node.
Instances For
One synchronous round of the median rule.
Equations
- Median.step x r v = Median.med3 (x v) (x (r v).1) (x (r v).2)
Instances For
def
Median.run
{n : ℕ}
{α : Type u_1}
[LinearOrder α]
(x : Config n α)
(l : List (Round n))
:
Config n α
The configuration after a list of rounds (the first round first).
Equations
- Median.run x l = List.foldl Median.step x l
Instances For
All nodes hold the same value.
Equations
- Median.Consensus x = ∃ (c : α), ∀ (v : Fin n), x v = c
Instances For
Indicator of not yet being in consensus.
Equations
- Median.notConsensus x = if Median.Consensus x then 0 else 1
Instances For
noncomputable def
Median.kernel
(n : ℕ)
[NeZero n]
(α : Type u_2)
[LinearOrder α]
[Fintype α]
:
Dynamics.Kernel (Config n α)
The median dynamics as a Markov kernel (uniform i.i.d. rounds).