TAOCP 7.2.2.2 Exercise 98

Exercise 98. ▶ [M23] This exercise is about proving the nonexistence of starvation cycles (47).

a) A cycle of states is called "pure" if one of the players is never bumped, and "simple" if no state is repeated. Prove that every starvation cycle, if any, is either simple or consists of two simple pure cycles that share a common state.

b) If Alice is starved by some cycle with protocol (49), we know that she is never in states A0 or A5 within the cycle. Show that she can't be in A1, A2, or A6 either.

c) Construct clauses to test whether there exist states $X_0 \to X_1 \to \cdots \to X_r$, with $X_0$ arbitrary, such that $(X_0 X_1 \ldots X_{k-1})$ is a starvation cycle for some $k \le r$.

d) Use (c) to conclude that (49) is starvation-free without much extra work.

Verified: no
Solve time: 3m42s

Solution

In the direct encoding, each variable $x_i$ is represented by Boolean variables indicating its possible values. Write

$$ x_{i,j}=1\iff x_i=j, $$

where $0\le i<p$ and $1\le j\le d$ if the domain has size $d$. The direct encoding already contains the clauses forcing each $x_i$ to have exactly one value. The all-different constraint adds the requirement that two different variables cannot choose the same value.

For two distinct variables $x_i$ and $x_k$, and for any value $j$, the assignment

$$ x_{i,j}=x_{k,j}=1 $$

must be forbidden. The corresponding clause is

$$ \bar{x}{i,j}\vee \bar{x}{k,j}. $$

Taking all pairs of variables and all possible values gives the complete encoding:

$$ \bigwedge_{0\le i<k<p}\ \bigwedge_{1\le j\le d} (\bar{x}{i,j}\vee\bar{x}{k,j}). $$

These clauses are sufficient. Suppose the direct variables represent an assignment satisfying the clauses. If two variables $x_i$ and $x_k$ had the same value $j$, then the direct encoding would require

$$ x_{i,j}=1,\qquad x_{k,j}=1. $$

The clause

$$ \bar{x}{i,j}\vee\bar{x}{k,j} $$

would then be false, contradicting satisfiability. Hence no two variables receive the same value.

They are also necessary. Given any assignment satisfying the all-different constraint, no pair of variables $x_i,x_k$ has the same value. Therefore, for every $j$, at least one of $x_{i,j}$ and $x_{k,j}$ is false, so every clause

$$ \bar{x}{i,j}\vee\bar{x}{k,j} $$

is satisfied.

Thus the all-different constraint in the direct encoding is enforced by adding one binary clause for every pair of variables and every possible value:

$$ \boxed{\bar{x}{i,j}\vee\bar{x}{k,j}\qquad (0\le i<k<p,\ 1\le j\le d).} $$

This completes the proof. ∎