Large-system response-time conjecture for speculative queueing networks

Let $R_{N,n}(\tau)$ be the overall time spent by the $n$-th arriving job in a symmetric speculative queueing network of $N$ FCFS queues, and define the average response time

$$R_N(\tau):=\limsup_{m\to\infty}\frac{1}{m}\sum_{n=1}^m\mathbb{E}[R_{N,n}].$$

For a fixed speculation threshold $\tau$, let $\rho(\tau)$ be the corresponding load, let $\hat{\eta}_2$ have the distribution of $\eta_2\mid\eta_1>\tau$, and define

$$W:=\frac{\lambda}{2}\bigl(1+\mathbb{P}(\eta_1\geq\tau)\bigr)\frac{M}{1-\rho(\tau)},$$

where

$$M:=\frac{\mathbb{E}[(\eta_1\wedge\tau)^2]+\mathbb{E}[\hat{\eta}_2^2]\mathbb{P}(\eta_1>\tau)}{1+\mathbb{P}(\eta_1>\tau)}.$$

Large-system response-time conjecture. Provided that $\rho(\tau)<1$,

$$\lim_{N\to\infty}R_N(\tau)=(1+\mathbb{P}(\eta_1>\tau))W+\frac{\rho(\tau)}{\lambda}.$$

The conjecture gives an approximation for response time in the large-system regime, where $N\to\infty$ with $\rho(\tau)$ fixed. Its justification relies on asymptotic independence of queues and a Palm–Khintchine approximation for the superposition of sparse feedback processes; the source does not establish the limit rigorously.