Rabin’s Mutual-Exclusion Algorithm
Mutual exclusion allows only one processor at a time to enter a shared critical section. We study a sequential model of the voting stage in Rabin’s mutual-exclusion algorithm [Kushilevitz and Rabin 1992]. In each voting round, every contender flips a fair coin to decide whether to withdraw [Hurd et al. 2004]. One survivor wins, several survivors vote again, and no survivors means that the election has failed. How likely is voting to end with no survivors?
The Program
The outer loop runs the voting rounds.
The inner loop makes one withdrawal decision for each contender present at the start of the round.
The variable i counts contenders who have not withdrawn, and n counts decisions still to be made in the round.
Verified@wlp
proc rabin(init_i: UInt) -> (i: UInt)
pre [init_i == 1] + [init_i > 1] * (2/3)
post [i == 1]
{
i = init_i
// One survivor contributes 1, no survivors contribute 0, and another round contributes 2/3.
@invariant([i == 1] + [i > 1] * (2/3))
while i > 1 {
// Each contender present at the start of this round flips exactly once.
var n: UInt = i
// Evaluate the outer annotation after the remaining n flips.
@invariant(
[n <= i] * (
// More than one eventual survivor contributes 2/3.
(2/3) * (1 - ([i == n] * (n + 1) + [i == n + 1]) * rec_pown_2(n))
// Exactly one eventual survivor contributes 1.
+ ([i == n] * n + [i == n + 1]) * rec_pown_2(n)
)
)
while n > 0 {
var withdraw: Bool = flip(0.5)
if withdraw {
i = i - 1
} else {}
n = n - 1
}
}
}
Verification
For init_i > 1, the probability of terminating with no survivors is at most .
The @wlp annotation verifies the complementary lower bound of , counting both one survivor and nontermination.
It does not establish that voting terminates.
The outer @invariant annotation uses .
A round starting with contenders leaves zero or one survivors with probabilities and , respectively. Its expected invariant value is therefore
For n <= i, the inner invariant uses rec_pown_2(n) for .
- gives the probability that the round ends with one survivor.
With
i == n, one remaining contender must stay, whereas withi == n + 1, all must withdraw. - accounts for rounds with at least two survivors.
[n <= i]restricts the calculation to states with enough contenders for the remaining flips.
See Also
- Two-Sided Random Walks shows how almost-sure termination is proved separately.
- Zeroconf Address Allocation verifies a probability bound using specifications for recursive procedures.
References
-
Kushilevitz and Rabin (1992). Randomized Mutual Exclusion Algorithms Revisited.
Develops the mutual-exclusion algorithm underlying this voting model.
-
Hurd et al. (2004). Probabilistic Guarded Commands Mechanized in HOL.
Verifies the voting stage using nested-loop invariants.
(Section 4) -
Schröer et al. (2023). A Deductive Verification Infrastructure for Probabilistic Programs. OOPSLA.
Presents the HeyVL encoding and its liberal bound.
(Example 1.1 and Figure 2)