Lemma 2 — the unique fixed point of the limiting system with finite mass is
ProvedPowerTwoChoices.Limit.lemma_2differential-equationsload-balancingmean-fieldp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1queueing
Let and , and consider the limiting supermarket system
whose states are sequences with , and nonincreasing in . A fixed point is a state at which for every .
The sequence is a state, is a fixed point, and satisfies ; and every fixed point with
equals .
The summability condition cannot be dropped: is also a fixed point. Lemma 2 identifies the point to which the system is later shown to converge, and its doubly exponential decay is the source of the paper's main results.
Preamble
import Mathlib import Definitions.Def_PowerTwoChoices_Limit_SupermarketSystem open scoped ENNReal open Filter Topology
Formal statement
namespace PowerTwoChoices.Limit
/-- Lemma 2 (Mitzenmacher 2001, p. 1097). For `d ≥ 2` and `0 < λ < 1`, the limiting system (1)
has a unique fixed point with `∑_{i ≥ 1} s_i < ∞`, namely `π_i = λ^{(d^i-1)/(d-1)}`:
`π` is a state at which every drift `ds_i/dt` (`i ≥ 1`) vanishes and whose tails are summable,
and every state with these two properties equals `π`. -/
theorem lemma_2 (lam : ℝ) (d : ℕ) (hd : 2 ≤ d) (hlam0 : 0 < lam) (hlam1 : lam < 1) :
IsState (fixedPoint lam d) ∧
(∀ i : ℕ, 1 ≤ i → drift lam d (fixedPoint lam d) i = 0) ∧
Summable (fixedPoint lam d) ∧
∀ x : ℕ → ℝ, IsState x → (∀ i : ℕ, 1 ≤ i → drift lam d x i = 0) → Summable x →
x = fixedPoint lam d := by sorry
end PowerTwoChoices.Limit
Source
Mitzenmacher, The Power of Two Choices in Randomized Load Balancing, IEEE Trans. Parallel Distrib. Syst. 12(10), 2001, p. 1097, Lemma 2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.