Skip to main content

Conditioning on Queue Completion

A server processes a queue while new jobs arrive, and it can fail before the queue empties. For nn initial jobs, we prove at most 5β‹…n/35\cdot n/3 rounds on average, conditioned on completing before failure. For any positive initial size, successful runs can still reach arbitrarily large queues and take arbitrarily many rounds.

Queue Example​

Each round fails with probability 1/51/5; otherwise, an arrival or service completion occurs with equal probability. We stop at failure or an empty queue, using a discrete version of a queue with disasters [Paz and Yechiali 2014].

Queue conditioned on completing before failure
proc observed_queue(initial: UInt) -> (pending: UInt, rounds: UInt, healthy: Bool) {
pending = initial
rounds = 0
healthy = true
while pending > 0 && healthy {
rounds = rounds + 1
healthy = flip(4/5)
if healthy {
var arrival: Bool = flip(1/2)
if arrival { pending = pending + 1 }
else { pending = pending - 1 }
}
}
assert ?(healthy)
}

The final assert gives failed runs zero contribution. Call emptying the queue before failure success, and let RR be the final round count and nn the input initial.

Encode Conditional Expected Values​

For fβ‰₯0f\ge0 and a program CC with observations but no nondeterministic choices, use [Olmedo et al. 2018]:

cwp⁑⟦C⟧(f)=wp⁑⟦C⟧(f)wlp⁑⟦C⟧(1)≀UL.\operatorname{cwp}\llbracket C\rrbracket(f) =\frac{\operatorname{wp}\llbracket C\rrbracket(f)} {\operatorname{wlp}\llbracket C\rrbracket(1)} \le\frac UL.

Verify the same inputs, program body, and observations against two specifications:

  • wp⁑⟦C⟧(f)≀U\operatorname{wp}\llbracket C\rrbracket(f)\le U: @wp coproc with pre U, post f.
  • 0<L≀wlp⁑⟦C⟧(1)0<L\le\operatorname{wlp}\llbracket C\rrbracket(1): @wlp proc with pre L, post 1.

The @wlp denominator includes nonterminating runs that have not violated an observation. When nontermination has probability zero, the ratio is the ordinary conditional expectation.

Verify the Queue Bounds​

The source represents 2βˆ’n2^{-n} by the following recursive function:

Power of one half
domain QueueConditioning {
// The minimum exposes the bound <= 1 to the solver.
// It does not change the value 2^(-n).
func success_probability(n: UInt): UReal =
ite(n == 0, 1, (success_probability(n - 1)/2) βŠ“ (1/2))
}

Bound the Denominator​

The probability proof uses the queue updates from observed_queue with this specification and annotation:

Lower bound on the success probability
@wlp
proc evidence_lower(initial: UInt) -> (pending: UInt, rounds: UInt, healthy: Bool)
pre success_probability(initial)
post 1
{
pending = initial
rounds = 0
healthy = true
@invariant(ite(healthy, success_probability(pending), 0))
while pending > 0 && healthy {

The final assert ?(healthy) retains successful runs, and post 1 counts them. Consequently,

wlp⁑⟦C⟧(1)=Pr⁑(success)β‰₯2βˆ’n>0,\operatorname{wlp}\llbracket C\rrbracket(1) =\Pr(\text{success})\ge2^{-n}>0,

where CC is observed_queue. Each round fails with probability 1/51/5, so nontermination has probability zero. Thus L=2βˆ’nL=2^{-n}.

Bound the Numerator​

Next, bound the rounds contributed by successful runs:

Upper bound on the successful runs’ round count
Expected: Verified
@wp
coproc rounds_upper(initial: UInt) -> (pending: UInt, rounds: UInt, healthy: Bool)
pre success_probability(initial) * ((5*initial)/3)
post rounds
{
pending = initial
rounds = 0
healthy = true
@invariant(ite(healthy, success_probability(pending) * (rounds + (5*pending)/3), 0))
while pending > 0 && healthy {

With the observation, post rounds measures E[Rβ‹…[success]]\mathbb E[R\cdot[\text{success}]]. The invariant is zero after failure and equals rounds at successful exit. The procedure proves

E[Rβ‹…[success]]≀U=2βˆ’nβ‹…5β‹…n3.\mathbb E[R\cdot[\text{success}]] \le U=2^{-n}\cdot\frac{5\cdot n}{3}.

Dividing by the positive denominator bound gives

E[R∣success]≀2βˆ’nβ‹…(5β‹…n/3)2βˆ’n=5β‹…n3.\mathbb E[R\mid\text{success}] \le\frac{2^{-n}\cdot(5\cdot n/3)}{2^{-n}} =\frac{5\cdot n}{3}.

For three initial jobs, this is at most five rounds on average among successful runs.

References​