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 \\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. \\textbf{(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. \\textbf{(II)}~Bounded waiting time with an explicit, distribution-free ceiling $W_{\\max}(N,L,C_W,K,\\delta)$ and $k$-bounded fairness. \\textbf{(III)}~Quantitative performance bounds including mean-field load balance ($O(1/\\sqrt{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. \\textbf{(IV)}~Competitive analysis with an adversarial BoT bound $\\rho_c^{\\mathrm{DTA,worst}} \\leq 1 + N\\lfloor N/2\\rfloor\\delta_{\\mathrm{hop}}/W \\to 1$. \\textbf{(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. \\textbf{(VI)}~An information-theoretic cost framework that decomposes the achieved-to-oracle makespan ratio into an information gap $\\eta_{\\mathrm{info}}$ and a utilisation ratio $\\eta_{\\mathrm{util}}$, proves both tend to $1$ for DTA as total work $W \\to \\infty$ (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 $\\Omega(\\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.