← All problems

The delay-information duality conjecture for lookahead queues

13 years old · documented by

Let pp be fixed in (0,1)(0,1), let w(λ)w(\lambda) denote the size of the lookahead window, and let CΠw(λ)∗(p,λ)C^*_{\Pi_{w(\lambda)}}(p,\lambda) be the best achievable delay under policies with lookahead window w(λ)w(\lambda). Delay-information duality conjecture. If

w(λ)≪log⁡11−λas λ→1,w(\lambda)\ll\log\frac{1}{1-\lambda}\quad\text{as }\lambda\to1,

then

lim sup⁡λ→1CΠw(λ)∗(p,λ)=∞.\limsup_{\lambda\to1}C^*_{\Pi_{w(\lambda)}}(p,\lambda)=\infty.

Equivalently, delay collapse can occur only if w(λ)=Θ ⁣(log⁡11−λ)w(\lambda)=\Theta\!\left(\log\frac{1}{1-\lambda}\right). The preceding theorem shows that a window of order log⁡11−λ\log\frac{1}{1-\lambda} achieves the optimal heavy-traffic delay limit, while this conjecture asserts that asymptotically smaller windows cannot keep the delay bounded.

References
  1. Joel Spencer, Madhu Sudan and Kuang Xu, “Queuing with future information”, arXiv:1211.0618 (2014).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.