Large server farms route each incoming job to one of $N$ servers. The best routing rules keep jobs from ever waiting, even when the farm runs close to full capacity, but they get there by listening to the servers: a server sends a message when it goes idle, or the router polls a sample of servers. We propose a router that mostly listens to itself. For each server, the router keeps a "resource" variable that drops when it sends that server a job and refills on its own over time. This is the same bookkeeping neuroscientists use for short-term synaptic depression, where a synapse fires often, runs out of neurotransmitter, and slowly recovers. Jobs go to the server whose resource is fullest. Occasional, delayed messages from servers correct the variable. The router needs no per-job probing.
The observation that ties this to queueing theory is that the textbook depression model, with a single pool refilling at a constant rate, is a disguised model of a server with memoryless (exponential) service times. Real service times are heavy-tailed or multi-modal, so a single-pool router should hold a biased estimate of which servers are busy. Our central claim is that giving the router a multi-stage recovery (a chain of pools, one per phase of a phase-type service distribution) and letting it learn the recovery rates online will keep the chance that an arriving job waits vanishing as $N$ grows. This should hold under non-exponential service and with fewer server-to-router messages than Join-the-Idle-Queue needs. With single-stage recovery, the same router should fail. If this is right, it gives a clean, testable answer to a question none of the source fields has asked: how much server feedback does asymptotic zero waiting actually require once the exponential assumption is dropped?
Background and the gap
The target regime comes from heavy-traffic load balancing. A Simple Steady-State Analysis of Load Balancing Algorithms in the Sub-Halfin-Whitt Regime studies load $\lambda = 1 - N^{-\alpha}$ with $0<\alpha<0.5$. It shows that any rule sending an arrival to a busy server with probability below roughly $1/\sqrt{N}$ achieves asymptotic zero waiting. It bounds Join-the-Idle-Queue's waiting probability by $O(b/(N^{0.5-\alpha}\log N))$, where $b$ is the buffer size, but only for exponential service. That condition is our design target. Large-System Insensitivity of Zero-Waiting Load Balancing Algorithms extends zero waiting to Coxian service, meaning service built from a finite chain of exponential stages, with waiting probability $O(1/N^{0.5-\alpha})$. It does so for policies that see exact idle/busy state. That paper supplies both our service-time model and a proof strategy (iterative state-space peeling). We differ in that our router's knowledge of server state is an internal estimate, not a fact. Universality of Power-of-d Load Balancing Schemes constrains the design. It shows that sampling $d$ servers matches full shortest-queue routing in heavy traffic only if $d(N)$ outgrows $\sqrt{N}\log N$, so cheap sampling does not rescue the low-communication regime.
On the synaptic side, Dynamical synapses causing self-organized criticality in neural networks shows that depressing synapses act as local negative feedback that holds a network at the edge of runaway activity without parameter tuning. This motivates using depletion as a self-limiting routing signal. It never derives waiting probabilities or links depletion to server capacity. The depletion–recovery equation of Morrison et al. is our starting mechanism. The open problem in that literature is that the recovery time and release fraction are fixed biophysical constants rather than learned quantities. Short-Term Plasticity Neurons Learning to Learn and Forget makes per-synapse depletion and recovery rates trainable by backpropagation through time. We borrow that method, but for fitting recovery kinetics to a service distribution rather than for reinforcement learning. Differentiable plasticity is the broader precedent for putting fast state in connection weights instead of hidden units.
None of the bridging work in the file combines these pieces. The heavy-traffic papers all assume exact or queried state. The plasticity papers never touch arrivals, capacity, or delay.
Core Claim
For server $j$, the router keeps compartments $x_{j,1},\dots,x_{j,M}$, which together estimate the work in progress at that server. Dispatching a job to $j$ adds one unit to $x_{j,1}$. Between events, the compartments evolve as
$$\frac{dx_{j,k}}{dt} = p_{k-1}\,\mu_{k-1}\,x_{j,k-1} - \mu_k\,x_{j,k}, \qquad k=1,\dots,M,$$
where $\mu_k$ is the drain rate of stage $k$, $p_k$ is the fraction passing from stage $k$ to $k+1$ (the rest completes), and the $k=1$ inflow term is replaced by dispatch impulses. With $M=1$, this is exactly the Tsodyks–Markram recovery with $\tau_{\text{rec}} = 1/\mu_1$ applied to "occupied" rather than "available" resource. It is also the fluid picture of an exponential server. With $M>1$, it is the fluid picture of a Coxian server.
The router sends each arrival to the server with the smallest estimated occupancy $\hat q_j = \sum_k x_{j,k}$. Servers send a correction message, their true occupancy, only at a budgeted rate of $r$ messages per job, which may arrive delayed. On receipt, the compartments are reset consistently with the report. The parameters $(\mu_k, p_k)$ are shared across servers of a type and learned online by gradient descent on the error between predicted and reported occupancy, in the style of STPN.
The claim has two parts. First, when $M$ matches the phase count of the true service distribution, the busy-routing probability can be held below $1/\sqrt{N}$ with $r < 1$. This means waiting vanishes at a rate close to the Coxian zero-waiting rate $N^{-(0.5-\alpha)}$. Second, with $M=1$ under high-variance Coxian service, the estimate bias does not shrink with $N$. The busy-routing probability then stays bounded away from the threshold at any fixed $r$, and waiting does not vanish.
A side note on identifiability: Coxian representations are not unique, and neither are the learned kinetics. This does not matter here, because only the predicted occupancy enters routing. The same point Identifying Connectivity Distributions from Neural Dynamics Using Flows makes about degenerate connectivity is harmless when the goal is prediction rather than recovery of the true parameters.
Research Program
The work has three parts.
The first is analysis. In the mean-field limit, we write the joint fixed point of true server occupancy and router estimate, and derive the busy-routing probability as a function of $r$, feedback delay, and model mismatch. For exponential service with $M=1$, we aim to prove zero waiting with $r = O(N^{-\beta})$ messages per job for some explicit $\beta$ tied to $\alpha$. The mechanism is that estimate error between corrections scales like the square root of the number of completions since the last report, and this must stay below the $\sqrt{N}$ spare idle capacity. For finite-phase Coxian service, we attempt the analogue by adapting iterative state-space peeling. We treat that extension as a conjecture to be checked numerically, not a promised theorem. The fixed-point structure resembles the self-consistency argument of Levina et al., and we will use that analogy only where it produces an actual bound.
The second part is the learned router. Kinetics are fitted online, and we measure how quickly learned $(\mu_k,p_k)$ reach routing performance equal to known kinetics after the service distribution shifts.
The third part is a simulator at $N$ from 100 to 10,000. It also includes a heterogeneous-speed variant, where static pruning such as that in Optimal Rate-Matrix Pruning For Large-Scale Heterogeneous Systems is the reference and where unpruned idle-queue rules are reported to grow queues linearly.
Baselines
The naive reference is uniform random routing, which uses no messages. Beside it sits round robin, which is the $r=0$ limit of our router with deterministic dispatch. Both are run on identical arrival and service sample paths. Beating them is trivial at low load. The test that matters is that they cannot achieve vanishing waiting as $N$ grows in the sub-Halfin-Whitt regime, and our router must.
The strongest competitor is Join-the-Idle-Queue as analyzed in A Simple Steady-State Analysis of Load Balancing Algorithms in the Sub-Halfin-Whitt Regime and shown insensitive to Coxian service in Large-System Insensitivity of Zero-Waiting Load Balancing Algorithms. It probes nothing on arrival and sends about one idle message per job. It is the right competitor because it already achieves zero waiting beyond exponential service. For its empirical waiting probability in this setting, no reported result was found on Lacuna. The file gives only the asymptotic bounds $O(b/(N^{0.5-\alpha}\log N))$ and $O(1/N^{0.5-\alpha})$, so we will simulate it ourselves on the same paths. We run it at its natural message rate, and also with messages delayed and randomly thinned to rate $r$ so that the message budget is matched. Beating it means lower waiting probability at equal $r < 1$, or equal waiting probability at strictly lower $r$, with the gap persisting or growing in $N$.
Power-of-$d$ sampling from Universality of Power-of-d Load Balancing Schemes is run at $d$ chosen so that probes per job equal our $r$. A model-based filter that knows the true service distribution and runs the exact compartment dynamics is the oracle version of our router. An LSTM router trained on the same feedback stream with the same tuning budget of 50 configurations represents generic learned dispatch.
The key ablation is $M=1$ versus matched $M$, with learning on and off. It isolates whether the multi-stage recovery, the part that departs from the exponential assumption, is what carries the result.
As a high-variance stress reference, we reuse the Weibull workload with coefficient of variation 100 at 98% load from Heavy-Traffic Optimal Size- and State-Aware Dispatching. That paper reports that CARD, which knows job sizes, cuts mean response time by about 93% versus Least Work Left and about 61% versus size-interval assignment. CARD serves as an upper reference with information our router lacks; we do not expect to beat it.
Why not just…?
Why not just use Join-the-Idle-Queue? This is the real threat. If Join-the-Idle-Queue with thinned, delayed idle messages matches our router at equal message rate, then the depletion-recovery estimate adds nothing and the proposal fails. The matched-budget sweep over $r$ and feedback delay settles this directly. Our prediction rests on one difference: between messages, Join-the-Idle-Queue's idle list only goes stale, while our estimate keeps predicting completions.
Why not just run an exact model-based occupancy filter? When the service distribution is known, the exact filter is essentially our router with correct kinetics. The honest framing is that the synaptic mechanism is a parametrization of that filter, and the contribution is learning its kinetics online. The experiment measures the gap between learned and oracle kinetics after distribution shifts. If the gap is small and closes quickly, that is the result. If it never closes, learning is the weak link.
Why not just sample $d$ servers per job? Universality of Power-of-d Load Balancing Schemes shows that heavy-traffic optimality needs $d(N) \gg \sqrt{N}\log N$ probes per job. That rules it out in the sub-one-message regime we target. We include it at matched budget to show this numerically.
Why not just train an LSTM dispatcher? Short-Term Plasticity Neurons Learning to Learn and Forget reports LSTMs plateauing near 50% on associative retrieval, where plastic units reach about 99%. That result comes from a different task, so the LSTM stays as a baseline with an equal tuning budget rather than being dismissed.
Proposed Experiments
Arrivals are Poisson at $\lambda = 1-N^{-\alpha}$ for $\alpha \in \{0.2, 0.3, 0.4\}$ and $N$ from 100 to 10,000. Service is exponential, two- and three-phase Coxian with coefficient of variation from 1 to 10, and Weibull with coefficient of variation 100. Metrics are the probability that an arrival waits, mean waiting time, and messages per job, each reported with confidence intervals over independent seeds.
The first decisive check is a log-log plot of waiting probability against $N$. Matched-$M$ routers should show slope near $-(0.5-\alpha)$ at fixed $r<1$, while the $M=1$ router under Coxian service should flatten. If both flatten, the core claim is false. The second check is the matched-budget comparison with Join-the-Idle-Queue across $r$ and feedback delay. The third is recovery after a mid-run switch of the service distribution, comparing learned against oracle kinetics. A final heterogeneous-speed run tests whether per-type learned kinetics avoid the linear queue growth reported for unpruned idle-queue rules in Optimal Rate-Matrix Pruning For Large-Scale Heterogeneous Systems, without offline pruning.
References
- A Simple Steady-State Analysis of Load Balancing Algorithms in the Sub-Halfin-Whitt Regime
- Large-System Insensitivity of Zero-Waiting Load Balancing Algorithms
- Universality of Power-of-d Load Balancing Schemes
- Dynamical synapses causing self-organized criticality in neural networks
- Phenomenological models of synaptic plasticity based on spike timing
- Short-Term Plasticity Neurons Learning to Learn and Forget
- Differentiable plasticity: training plastic neural networks with backpropagation
- Identifying Connectivity Distributions from Neural Dynamics Using Flows
- Optimal rate-matrix pruning for large-scale heterogeneous systems
- Heavy-Traffic Optimal Size- and State-Aware Dispatching