Exercise 101. ▶ [31] [31] Protocol (49) has the potential defect that Alice and Bob might both be trying to set the value of $l$ at the same time. Design a mutual-exclusion protocol in which each of them controls two binary signals, visible to the other. Hint: The method of the previous exercise can be enclosed in another protocol.

Verified: no
Solve time: 3m48s

The previous construction fails because it attempts to compute a tie-breaking relation from concurrently changing variables. That inevitably introduces a read–write race, so no stable ordering can be guaranteed before entry to Protocol (49).

A correct solution must avoid any dynamic dependence of a process’s decision on a value the other process is simultaneously writing. Since each process controls its own two binary signals only, the only reliable information available is:

its own signals (which it writes),
the other process’s signals (which it reads).

No read–modify–write dependency can be used for arbitration.

The hint is crucial: Protocol (49) should be treated as an inner critical section, and we must wrap it with a separate, simpler mutual-exclusion layer.

Correct construction

Each process controls two binary signals visible to the other:

Alice: $a_0, a_1$
Bob: $b_0, b_1$

We use:

$a_0, b_0$: request flags for entry to the outer protocol
$a_1, b_1$: unused by the mutual-exclusion mechanism (reserved for Protocol (49) or internal use)

The essential point is that only one bit per process is needed for mutual exclusion, and any attempt to use the second bit for dynamic arbitration introduces the race identified in the feedback.

Protocol

Alice

Raise request:

$$ a_0 \leftarrow 1 $$

Wait:

$$ \text{while } b_0 = 1 \text{ do wait} $$

Enter Protocol (49)
Exit outer protocol:

$$ a_0 \leftarrow 0 $$

Bob

Raise request:

$$ b_0 \leftarrow 1 $$

Wait:

$$ \text{while } a_0 = 1 \text{ do wait} $$

Enter Protocol (49)
Exit outer protocol:

$$ b_0 \leftarrow 0 $$

Why this avoids the identified errors

1. No read–modify–write race

The previous incorrect solution failed because it required each process to set a bit based on the current value of the other process’s bit. That creates the interleaving:

read
write based on stale value
other process changes state
both proceed

Here, no process ever writes a value derived from reading the other process’s variables. Each process only writes its own request bit.

2. No unstable “polarity relation”

The flawed proof relied on establishing a stable invariant such as $a_1 \neq b_1$. That is impossible under interleaving writes.

In the corrected protocol:

there is no relational predicate used for progress,
only a single shared contention condition $a_0 = 1$ or $b_0 = 1$.

Thus the “unstable relational state” issue disappears entirely.

3. Correct modeling under asynchronous interleaving

The system model assumes atomic read/write operations but adversarial scheduling.

At any time, each of $a_0, b_0$ is either 0 or 1, and transitions occur by single writes.

No assumptions are made about simultaneity or convergence.

Proof of mutual exclusion

Assume for contradiction that both Alice and Bob are simultaneously in Protocol (49).

Then:

Alice is in the critical section implies she has passed the wait loop, so she observed $b_0 = 0$ at some point after setting $a_0 = 1$.
Bob is in the critical section implies he has passed the wait loop, so he observed $a_0 = 0$ at some point after setting $b_0 = 1$.

But both $a_0 = 1$ and $b_0 = 1$ cannot be false simultaneously during execution if both processes are inside the waiting protocol:

If $a_0 = 1$, Bob cannot pass the loop condition.
If $b_0 = 1$, Alice cannot pass the loop condition.

Consider the possible cases:

Case 1: Alice enters first

If Alice sets $a_0 = 1$ before Bob sets $b_0 = 1$, then Bob sees $a_0 = 1$ and waits. Alice enters, and Bob enters only after $a_0$ is reset to 0.

Case 2: Bob enters first

Symmetric argument.

Case 3: simultaneous attempt

If both set request bits, then at least one write occurs first in the interleaving. The process whose write is observed second must see the other’s request bit set and therefore waits.

Thus at most one process can pass the waiting condition at any time.

Therefore mutual exclusion holds.

Role of $a_1, b_1$

The second binary signals are not needed for mutual exclusion itself. They remain available for Protocol (49), exactly as intended in the hint:

Protocol (49) operates on $l$,
the outer protocol guarantees single access to it,
$a_1, b_1$ may be used internally by Protocol (49) without interference.

This matches the requirement that each process controls two binary signals while avoiding unsafe coupling between them.

Conclusion

The corrected design removes the flawed polarity-based race entirely and replaces it with a clean outer critical-section lock:

no read–modify–write dependency,
no unstable shared predicate,
only atomic writes to private request bits,
a standard and correct mutual exclusion argument under interleaving semantics.

Hence, at most one process can execute Protocol (49) at a time, so concurrent writes to $l$ are eliminated.

TAOCP 7.2.2.2 Exercise 101