Scheduling with Bounded Information: Correctness, Progress, and Near-Optimal Performance in DTA
Abstract
Every practical distributed scheduler makes placement decisions with an incomplete, purely local view of system state: no worker can afford to observe every peer's queue before deciding where to route a task, so observed information is inherently bounded and stale. This paper studies how much can be guaranteed --- correctness, progress, and near-optimal makespan --- from a scheduler that deliberately restricts itself to such bounded information, and quantifies the price of that restriction against schedulers (e.g.\ work-stealing) that acquire more information per decision. We use the \textsc{DTA} distributed task scheduler (N workers, SPSC mailboxes, Vyukov MPMC warehouse, hop-bounded deflection) as the concrete vehicle for this study: DTA routes tasks using only local queue occupancy and a bounded-hop deflection rule, never a global or neighbourhood queue scan.
Using a second-quantisation Fock-space algebra and kinetic theory, we establish six main results. (I) Four correctness theorems (task conservation, deadlock and livelock freedom, linearizability), generalized to a continuity law that accounts for task creation and cancellation as explicit source and sink terms rather than assuming a fixed task population. (II) Bounded waiting time with an explicit, distribution-free ceiling Wmax(N,L,CW,K,δ) and k-bounded fairness. (III) Quantitative performance bounds including mean-field load balance (O(1/√N) imbalance), an explicit BBGKY Level-2 pair- and triplet-correlator closure (O(1/N) and O(1/N2), in closed form rather than order alone), a three-line makespan bound (deterministic, Gumbel fluctuation, and a Cram\'er-type exponential tail sharper than either), a four-level stability ladder, fork-join DAG bounds via a sequential-nucleation kinetic equation with an analogous exact finite-size correlator, and a closed-form extension of the load-balance analysis to Markov-modulated (bursty) arrivals.
With correctness and progress established and performance characterised, we turn to how the restriction compares against alternatives and what it costs to lift. (IV) Competitive analysis with an adversarial BoT bound ρcDTA,worst ≤ 1 + N⌊ N/2⌋δhop/W → 1. (V) Empirical validation against the real, unmodified scheduler (not a simulation): the bounded-wait, k-fairness, and batch-makespan bounds hold at the paper's own published parameters, while the fork-join and information-acquisition-cost predictions are directionally but not quantitatively confirmed, a gap discussed openly rather than fitted away. (VI) An information-theoretic cost framework that decomposes the achieved-to-oracle makespan ratio into an information gap ηinfo and a utilisation ratio ηutil, proves both tend to $1$ for DTA as total work W → ∞ (so DTA is heavy-traffic information-optimal, matching the fully-informed offline oracle to leading order), and shows that at any fixed, moderate system scale DTA's information-\emph{acquisition} cost is Ω(log N) lower than work-stealing's on NUMA topologies, with a concrete crossover analysis for dual-socket systems.
Taken together, these results show that bounded-information scheduling is not merely a practical compromise but can be made \emph{provably near-optimal}: DTA loses essentially nothing to schedulers with a wider information window in the heavy-traffic limit, while paying a strictly lower and asymptotically smaller acquisition cost at any fixed scale.
Related
- Selective Replay Under Incomplete Dependency Information: An exploratory benchmark of correctness and audit cost
- Convergence is not correctness: context-dependent performance of enhanced-sampling methods across biological complexity
- Prediction-Driven Non-Preemptive Scheduling with Bounded Overtaking: A Per-Job Wait Guarantee
- Twin Prime Progress: Bounded Gaps, Unproven Conjecture, and a Flawed Claim — E8 Intelligence Research
- Twin Prime Progress: Bounded Gaps, Sieve Claims, and Unverified Construction — E8 Intelligence Research
BibTeX
@misc{yang2026scheduling,
title = {{Scheduling with Bounded Information: Correctness, Progress, and Near-Optimal Performance in DTA}},
author = {Xinyu Yang},
howpublished = {Zenodo},
year = {2026},
month = oct,
doi = {10.5281/zenodo.23450266},
url = {https://zenodo.org/records/23450266},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Scheduling with Bounded Information: Correctness, Progress, and Near-Optimal Performance in DTA
AU - Xinyu Yang
PY - 2026
DA - 2026/10/18
PB - Zenodo
DO - 10.5281/zenodo.23450266
UR - https://zenodo.org/records/23450266
AB - Every practical distributed scheduler makes placement decisions with an incomplete, purely local view of system state: no worker can afford to observe every peer's queue before deciding where to route a task, so observed information is inherently bounded and stale. This paper studies how much can be guaranteed --- correctness, progress, and near-optimal makespan --- from a scheduler that deliberately restricts itself to such bounded information, and quantifies the price of that restriction against schedulers (e.g.\ work-stealing) that acquire more information per decision. We use the \textsc{DTA} distributed task scheduler (N workers, SPSC mailboxes, Vyukov MPMC warehouse, hop-bounded deflection) as the concrete vehicle for this study: DTA routes tasks using only local queue occupancy and a bounded-hop deflection rule, never a global or neighbourhood queue scan. Using a second-quantisation Fock-space algebra and kinetic theory, we establish six main results. (I) Four correctness theorems (task conservation, deadlock and livelock freedom, linearizability), generalized to a continuity law that accounts for task creation and cancellation as explicit source and sink terms rather than assuming a fixed task population. (II) Bounded waiting time with an explicit, distribution-free ceiling W_max(N,L,C_W,K,δ) and k-bounded fairness. (III) Quantitative performance bounds including mean-field load balance (O(1/√N) imbalance), an explicit BBGKY Level-2 pair- and triplet-correlator closure (O(1/N) and O(1/N^2), in closed form rather than order alone), a three-line makespan bound (deterministic, Gumbel fluctuation, and a Cram\'er-type exponential tail sharper than either), a four-level stability ladder, fork-join DAG bounds via a sequential-nucleation kinetic equation with an analogous exact finite-size correlator, and a closed-form extension of the load-balance analysis to Markov-modulated (bursty) arrivals. With correctness and progress established and performance characterised, we turn to how the restriction compares against alternatives and what it costs to lift. (IV) Competitive analysis with an adversarial BoT bound ρ_c^DTA,worst ≤ 1 + N⌊ N/2⌋δ_hop/W → 1. (V) Empirical validation against the real, unmodified scheduler (not a simulation): the bounded-wait, k-fairness, and batch-makespan bounds hold at the paper's own published parameters, while the fork-join and information-acquisition-cost predictions are directionally but not quantitatively confirmed, a gap discussed openly rather than fitted away. (VI) An information-theoretic cost framework that decomposes the achieved-to-oracle makespan ratio into an information gap η_info and a utilisation ratio η_util, proves both tend to $1$ for DTA as total work W → ∞ (so DTA is heavy-traffic information-optimal, matching the fully-informed offline oracle to leading order), and shows that at any fixed, moderate system scale DTA's information-\emph{acquisition} cost is Ω(log N) lower than work-stealing's on NUMA topologies, with a concrete crossover analysis for dual-socket systems. Taken together, these results show that bounded-information scheduling is not merely a practical compromise but can be made \emph{provably near-optimal}: DTA loses essentially nothing to schedulers with a wider information window in the heavy-traffic limit, while paying a strictly lower and asymptotically smaller acquisition cost at any fixed scale.
ER -