Scheduling with Bounded Information: Correctness, Progress, and Near-Optimal Performance in DTA

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 {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ₘₐₓ(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/N²), 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δₕₒₚ/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 ηᵤₜᵢₗ, 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-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 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.