Skip to main content

Bounded Retransmission Protocol

A sender retries a packet if no acknowledgement arrives. The bounded retransmission protocol gives each packet a limited number of transmission attempts [Helmink et al. 1994]. If all attempts for one packet fail, the sender abandons the remaining packets.

How likely is success, and how many attempts are made on average? We first bound message failure and failed attempts in a complete retry loop, then examine the probability and cost of retrying an individual packet. The optional final section studies packet sequences that summarize each packet attempt by one probabilistic step.

A Complete Message in One Loop​

The following model sends packets packets, allowing at most maxTries transmission attempts per packet [Schröer et al. 2026, Figure 1]. Each attempt independently succeeds with probability 0.990.99. Success means that the packet arrives and its acknowledgement returns.

Probability of Abandoning the Message​

For maxTries > 0, we bound the probability of exhausting a packet's retry limit.

Complete message: failure probability
Expected: Verified
@wp
coproc brp(packets: UInt, maxTries: UInt)
-> (sent: UInt, fail: UInt, totalFail: UInt)
pre !?(maxTries > 0)
pre 1 - pow(1 - pow(0.01, maxTries), packets)
post [fail == maxTries]
{
sent = 0
fail = 0
totalFail = 0

// Failure is certain at the retry limit; otherwise combine this packet and the later packets.
@invariant(
!?(sent <= packets && fail <= maxTries)
⊔ [fail == maxTries]
⊔ (?(sent < packets && fail < maxTries)
⊓ (1 - (1 - pow(0.01, maxTries - fail))
* pow(1 - pow(0.01, maxTries), (packets - sent) - 1)))
)
while sent < packets && fail < maxTries {
var transmit: Bool = flip(0.99)
if transmit {
sent = sent + 1
fail = 0
} else {
fail = fail + 1
totalFail = totalFail + 1
}
}
}

After each successful transmission, sent increases and fail resets to zero, giving the next packet its full retry allowance. The counter totalFail keeps failures across all packets. At exit, fail == maxTries means that the sender abandoned the message. The loop makes at most packets * maxTries transmissions, so it always terminates.

One packet fails all m=maxTriesm=\mathtt{maxTries} attempts with probability 0.01m0.01^m. Successfully sending all n=packetsn=\mathtt{packets} packets therefore has probability (1−0.01m)n(1-0.01^m)^n. The coproc specification verifies the complementary upper bound

Pr⁡(fail=m)≤1−(1−0.01m)n.\Pr(\mathtt{fail}=m)\le 1-\bigl(1-0.01^m\bigr)^n.

For packets == 0, no transmission is made and the bound is zero.

The invariant uses probability one when the current packet has exhausted its attempts and zero when all packets have been sent. While transmission continues, the factor 1 - pow(0.01, maxTries - fail) is the current packet's success probability within its remaining attempts. The factor pow(1 - pow(0.01, maxTries), (packets - sent) - 1) covers all later packets. Their product gives the success probability for the whole message. Subtracting it from one gives the remaining failure probability.

Expected Number of Failed Attempts​

The next procedure bounds the expected number of failed attempts across the whole message. The excerpt shows its specification and invariant for the same transmission loop.

Complete message: count failed attempts
Expected: Verified
@wp
coproc brp_failed_transmissions(packets: UInt, maxTries: UInt)
-> (sent: UInt, fail: UInt, totalFail: UInt)
pre 0.01 * maxTries * packets
post totalFail
{
sent = 0
fail = 0
totalFail = 0

// Each unused transmission slot contributes at most its failure probability.
// Delivery can discard several remaining slots, while a failure consumes one.
@invariant(
!?(sent <= packets && fail <= maxTries)
⊔ (totalFail + 0.01 * (maxTries * (packets - sent) - fail))
)

Caesar verifies

E[totalFail]≤0.01⋅m⋅n.\mathbb{E}[\mathtt{totalFail}]\le 0.01\cdot m\cdot n.

The counter includes failed attempts before a later success. The bound allows all n⋅mn\cdot m transmission slots, although successful delivery or abandoning the message can leave some unused. It also applies when either input is zero.

The invariant retains totalFail and adds an allowance of 0.010.01 for each remaining transmission slot. The term maxTries * (packets - sent) - fail removes slots already consumed on the current packet. A failed transmission consumes one slot and increments the counter; a success can discard the unused slots of that packet. The expected counter increase is therefore covered by the decrease in the allowance.

Packet-Level Retry Proofs​

The following variants isolate the retry loop for one packet, then combine these retries in a nested message loop. The transmission probability p() and retry limit MAX() are symbolic [van Jaarsveld 2025, §4.1].

Each transmission succeeds independently with probability p(), where 0≤p()≤10\le\mathtt{p}()\le1. The procedure sendPacket stops after the first success or after MAX() failures, with MAX() a nonnegative integer. With MAX() == 0, it makes no attempt and returns success == false.

Packet retries with three allowed attemptsAn incoming arrow marks the initial state with zero failures. The sender receives an acknowledgement with probability p or adds one failure with probability 1−p, and the third failure exhausts the attempt limit.012give upsuccess1 − p1 − p1 − ppppfailedMAX = 3

Success Probability for One Packet​

Caesar verifies a success probability of at least packet_success(), defined as 1 - pow(1 - p(), MAX()).

Send one packet: success probability
Expected: Verified
@wlp
proc sendPacket() -> (success: Bool)
pre packet_success()
post [success]
{
var failed: UInt = 0
success = false

// Use probability 1 after delivery, or the delivery probability within the remaining attempts.
@invariant(
ite(success, 1, 1 - pow(1 - p(), MAX() - failed))
)
while failed < MAX() && !success {
// Either this attempt succeeds, or a failure leaves one fewer attempt.
success = flip(p())
if !success {
failed = failed + 1
} else {}
}
}

The loop makes at most MAX() attempts, so the @wlp annotation gives a bound on success probability without requiring a separate termination proof. The @invariant annotation uses probability one after success and 1 - pow(1 - p(), MAX() - failed) for success within the remaining attempts. With m>0m>0 attempts remaining and p=p()p=\mathtt{p}(), its preservation follows from

p+(1−p)⋅(1−(1−p)m−1)=1−(1−p)m.p+(1-p)\cdot\bigl(1-(1-p)^{m-1}\bigr)=1-(1-p)^m.

If all attempts fail, the bound is zero.

Success Probability for All Packets​

The procedure BRP applies the retry loop to each of NN packets, stopping when all succeed or one uses all its attempts without success. Caesar verifies a probability of at least packet_success()N\mathtt{packet\_success}()^N for successfully sending the whole sequence.

Send all packets: nested retry annotations
Expected: Verified
@wlp
proc BRP(N: UInt) -> (success: Bool)
pre pow(packet_success(), N)
post [success]
{
var sent: UInt = 0
success = true

// Each remaining packet contributes a factor packet_success() to sequence delivery.
@invariant(
ite(success, pow(packet_success(), N - sent), 0)
)
while sent < N && success {
var failed: UInt = 0
success = false
// Multiply this packet's delivery probability by the factor for all later packets.
@invariant(
ite(success, 1, 1 - pow(1 - p(), MAX() - failed))
* pow(packet_success(), (N - sent) - 1)
)
// Initially this agrees with the outer annotation for all packets still to send.
while failed < MAX() && !success {
// Either this attempt succeeds, or a failure leaves one fewer attempt.
success = flip(p())
if !success {
failed = failed + 1
} else {}
}
if success {
sent = sent + 1
} else {}
}
}

The outer invariant uses pow(packet_success(), N - sent) for all unsent packets and becomes zero after a packet fails. The inner invariant multiplies the current packet's success bound by pow(packet_success(), (N - sent) - 1) for all later packets.

There are at most NN packet attempts, each with at most MAX() transmissions, so the loop terminates. For N=0N=0, no packet is attempted and success remains true.

For p() == 0.99, MAX() == maxTries, and N == packets, this success bound is the complement of the failure bound in the single-loop model.

Expected Number of Transmission Attempts​

When p() > 0, Caesar verifies that the expected number of transmission attempts for one packet is at most MAX() ⊓ (1 / p()).

sendPacket: expected number of transmission attempts
Expected: Verified
@ert
coproc sendPacket() -> ()
pre MAX() ⊓ (1 / p())
post 0
{
var failed: UInt = 0
var success: Bool = false

// Remaining attempts are bounded by both the retry limit and the geometric waiting time.
@invariant(?(!success) ⊓ ((MAX() - failed) ⊓ (1 / p())))
while failed < MAX() && !success {
// Each transmission attempt costs one reward unit, and failure leaves further attempts possible.
success = flip(p())
if !success {
failed = failed + 1
} else {}
reward 1
}
}

With the @ert annotation, one reward 1 per transmission makes the expected cost count transmission attempts. At most MAX() - failed further attempts are possible. Writing p=p()p=\mathtt{p}(), the expected number of attempts until success without a retry limit is 1/p1/p, since

1+(1−p)⋅1p=1p.1+(1-p)\cdot\frac{1}{p}=\frac{1}{p}.

The invariant bounds the remaining attempts by both quantities, and success ends the wait. With MAX() == 0, the bound is zero.

Expected Number of Failed Attempts​

Caesar verifies that the expected number of unsuccessful transmission attempts, recorded by failed, is at most MAX() * (1 - p()).

sendPacket: specification and invariant for failed transmissions
Expected: Verified
@wp
coproc sendPacket() -> (failed: UInt)
pre MAX() * (1 - p())
post failed
{
failed = 0
var success: Bool = false

// At exit, use failed itself; while retrying, add (1-p()) per remaining possible attempt.
@invariant(
failed + (?(!success) ⊓ ((1 - p()) * (MAX() - failed)))
)
while failed < MAX() && !success {
success = flip(p())
if !success {
// This failed attempt is now included in failed, with one fewer attempt available.
failed = failed + 1
} else {}
}
}

While retrying, (1 - p()) * (MAX() - failed) bounds further failures by allowing every remaining transmission, even though success can stop the loop earlier. At exit, the invariant equals failed.

Optional: Abstract Packet Sequences​

The remaining BRP procedures summarize each packet attempt by one flip(s()), without tracking individual retries [van Jaarsveld 2025, §§2.4, 4.1]. The packet success probability satisfies 0≤s()≤10\le\mathtt{s}()\le1 and is not related to p() or MAX() in these files.

These procedures stop after NN successful packet attempts or the first failure. Thus, they make at most NN packet attempts, with no attempt when N=0N=0.

Expected Number of Packet Attempts​

When s() < 1, Caesar verifies that the expected number of packet attempts is at most N ⊓ (1 / (1 - s())).

Abstract sequence: expected packet attempts
Expected: Verified
@ert
coproc BRP(N: UInt) -> ()
pre N ⊓ (1 / (1 - s()))
post 0
{
var sent: UInt = 0
var success: Bool = true

// Remaining attempts are bounded by both the unsent packets and the wait for failed delivery.
@invariant(?(success) ⊓ ((N - sent) ⊓ (1 / (1 - s()))))
while sent < N && success {
// Each packet attempt costs one reward unit and permits another attempt after successful delivery.
success = flip(s())
if success {
sent = sent + 1
} else {}
reward 1
}
}

Here one reward 1 counts a whole packet attempt, including an unsuccessful final attempt. At most N - sent further packets can be attempted. Writing s=s()s=\mathtt{s}(), waiting for the first failed packet attempt with no packet limit has expected cost 1/(1−s)1/(1-s). One attempt adds one reward unit and continues with probability s(), so preservation uses 1+s/(1−s)=1/(1−s)1+s/(1-s)=1/(1-s). Completing all packets can stop the sequence sooner. In particular, the bound is zero for N=0N=0.

Expected Number of Sent Packets​

Caesar verifies that the expected number of successfully sent packets, recorded by sent, is at most N * s().

BRP: specification and invariant for sent packets
Expected: Verified
@wp
coproc BRP(N: UInt) -> (sent: UInt)
pre s() * N
post sent
{
sent = 0
var success: Bool = true

// Keep the delivered packets, adding s() for each of at most N-sent further packet attempts.
@invariant(
sent + (?(success) ⊓ (s() * (N - sent)))
)
while sent < N && success {
// With probability s(), this attempt delivers one packet and reduces the number still to send.
// Otherwise the loop exits with sent unchanged, matching the postexpectation.
success = flip(s())
if success {
sent = sent + 1
} else {}
}
}

The term s() * (N - sent) bounds further successes by allowing all remaining packet attempts, even though the first failure stops the sequence.

Fixed Cost per Packet Attempt​

In failed.heyvl, each packet attempt adds the fixed nonnegative integer f() to totalFailed, including an unsuccessful attempt. The file does not relate f() to individual transmission failures. Caesar verifies that the expected value of this counter is at most N * f().

Abstract sequence: accumulate f() per packet attempt
Expected: Verified
@wp
coproc BRP(N: UInt) -> (totalFailed: UInt)
pre f() * N
post totalFailed
{
var sent: UInt = 0
var success: Bool = true
totalFailed = 0

// At most N-sent packet attempts remain, each adding exactly f() to totalFailed.
@invariant(
totalFailed + (?(success) ⊓ (f() * (N - sent)))
)
while sent < N && success {
success = flip(s())
// Charge f() for this attempt, including an attempt that fails to deliver a packet.
totalFailed = totalFailed + f()
if success {
// The increment reduces the remaining allowance f()*(N-sent) by the amount just charged.
sent = sent + 1
} else {}
}
}

Every packet attempt either increments sent or stops the sequence, so f() * (N - sent) covers all remaining cost.

See Also​

References​