Corollary 2 — the expected time in the limiting supermarket system converges to
ProvedPowerTwoChoices.Limit.corollary_2differential-equationsload-balancingmean-fieldp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1queueing
Let and , and let
which is finite. For a trajectory of the limiting supermarket system (1), the expected time a customer arriving at time spends in the system is .
- If for some (the condition of Theorem 2), then as .
- If the system is initially empty, then for all .
For the corresponding quantity is the M/M/1 value ; for is exponentially smaller as , which is the "power of two choices".
Formalization Note. and are computed in ; the finiteness of is part of the conclusion, so the convergence is to a real number. Convergence is along real time .
Preamble
import Mathlib import Definitions.Def_PowerTwoChoices_Limit_SupermarketSystem open scoped ENNReal open Filter Topology
Formal statement
namespace PowerTwoChoices.Limit
/-- Corollary 2 (Mitzenmacher 2001, p. 1099). Let `d ≥ 2` and `0 < λ < 1`. The number
`T_d(λ) = ∑_{i ≥ 1} λ^{(d^i-d)/(d-1)}` is finite; for every trajectory of the limiting
supermarket system with `s_j(0) = 0` for some `j` (the condition of Theorem 2), the expected
time `E(t) = ∑_{i ≥ 1} i (s_{i-1}(t)^d - s_i(t)^d)` a customer arriving at time `t` spends in
the system converges to `T_d(λ)` as `t → ∞`; and for the trajectory started from the empty
system, `E(t) ≤ T_d(λ)` for all `t ≥ 0`. -/
theorem corollary_2 (lam : ℝ) (d : ℕ) (hd : 2 ≤ d) (hlam0 : 0 < lam) (hlam1 : lam < 1) :
Td lam d ≠ ⊤ ∧
(∀ s : ℝ → ℕ → ℝ, IsTrajectory lam d s → (∃ j : ℕ, s 0 j = 0) →
Tendsto (fun t => expectedTime d (s t)) atTop (𝓝 (Td lam d))) ∧
(∀ s : ℝ → ℕ → ℝ, IsTrajectory lam d s → s 0 = emptyState →
∀ t : ℝ, 0 ≤ t → expectedTime d (s t) ≤ Td 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. 1099, Corollary 2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.