Documentation

Median.Defs

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.

def Median.med3 {α : Type u_1} [LinearOrder α] (a b c : α) :
α

Median of three elements of a linear order.

Equations
Instances For
    @[reducible, inline]
    abbrev Median.Config (n : ℕ) (α : Type u_1) :
    Type u_1

    Configurations of n nodes with values in α.

    Equations
    Instances For
      @[reducible, inline]
      abbrev Median.Round (n : ℕ) :

      A round: the two nodes sampled by every node.

      Equations
      Instances For
        def Median.step {n : ℕ} {α : Type u_1} [LinearOrder α] (x : Config n α) (r : Round n) :
        Config n α

        One synchronous round of the median rule.

        Equations
        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
          Instances For
            def Median.ones {n : ℕ} (x : Config n Bool) :

            Number of nodes holding true (binary case, false < true).

            Equations
            Instances For
              def Median.Consensus {n : ℕ} {α : Type u_1} (x : Config n α) :

              All nodes hold the same value.

              Equations
              Instances For
                noncomputable def Median.notConsensus {n : ℕ} {α : Type u_1} (x : Config n α) :

                Indicator of not yet being in consensus.

                Equations
                Instances For
                  noncomputable def Median.kernel (n : ℕ) [NeZero n] (α : Type u_2) [LinearOrder α] [Fintype α] :

                  The median dynamics as a Markov kernel (uniform i.i.d. rounds).

                  Equations
                  Instances For