Skip to main content

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.

Specification and voting rounds
Expected: 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 1/31/3.

The @wlp annotation verifies the complementary lower bound of 2/32/3, counting both one survivor and nontermination. It does not establish that voting terminates.

The outer @invariant annotation uses I=[i=1]+23⋅[i>1]I=[i=1]+\tfrac23\cdot[i>1].

A round starting with k≥2k\ge2 contenders leaves zero or one survivors with probabilities 2−k2^{-k} and k⋅2−kk\cdot2^{-k}, respectively. Its expected invariant value is therefore

k⋅2−k+23⋅(1−(k+1)⋅2−k)=23+k−23⋅2k≥23.k\cdot2^{-k} +\frac23\cdot\left(1-(k+1)\cdot2^{-k}\right) =\frac23+\frac{k-2}{3\cdot2^k} \ge\frac23.

For n <= i, the inner invariant uses rec_pown_2(n) for 2−n2^{-n}.

  • ([i=n]⋅n+[i=n+1])⋅2−n([i=n]\cdot n+[i=n+1])\cdot2^{-n} gives the probability that the round ends with one survivor. With i == n, one remaining contender must stay, whereas with i == n + 1, all must withdraw.
  • 23⋅(1−([i=n]⋅(n+1)+[i=n+1])⋅2−n)\tfrac23\cdot(1-([i=n]\cdot(n+1)+[i=n+1])\cdot2^{-n}) accounts for rounds with at least two survivors.
  • [n <= i] restricts the calculation to states with enough contenders for the remaining flips.

See Also​

References​