Conditioning on Queue Completion
A server processes a queue while new jobs arrive, and it can fail before the queue empties. For initial jobs, we prove at most 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 ; 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].
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 be the final round count and the input initial.
Encode Conditional Expected Valuesβ
For and a program with observations but no nondeterministic choices, use [Olmedo et al. 2018]:
Verify the same inputs, program body, and observations against two specifications:
- :
@wp coprocwithpre U,post f. - :
@wlp procwithpre 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 by the following recursive function:
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:
@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,
where is observed_queue.
Each round fails with probability , so nontermination has probability zero.
Thus .
Bound the Numeratorβ
Next, bound the rounds contributed by successful runs:
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 .
The invariant is zero after failure and equals rounds at successful exit.
The procedure proves
Dividing by the positive denominator bound gives
For three initial jobs, this is at most five rounds on average among successful runs.
Referencesβ
-
Paz and Yechiali (2014). An M/M/1 Queue in Random Environment with Disasters. Asia-Pacific Journal of Operational Research.Queueing context; our program stops at the first failure or empty queue and counts discrete rounds. (Section 2)
-
Olmedo et al. (2018). Conditioning in Probabilistic Programming. TOPLAS.Conditioning as a ratio of weakest preexpectations.