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 across seven parts: (I) four correctness theorems (task conservation, deadlock and livelock freedom, linearizability); (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), BBGKY Level-1 pair-correlator correction (O(1/N )), a two-line makespan bound (deterministic + Gumbel fluctuation), a four-level stability ladder, and fork-join DAG bounds via a sequential-nucleation kinetic equation; (IV) competitive analysis with an adversarial BoT bound ρ^(DTA, worst)_c ≤ 1 + N N/2 δ_hop/W → 1; (V) empirical validation against public Criterion CI benchmarks, with variance and moment analysis confirming all predictions; (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-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.