Introduction

Peterson's algorithm works only because its shared-memory writes happen in a specific logical order. If you reorder those commands, the proof of mutual exclusion breaks. In the classic bad reordering, both threads can believe it is safe to enter the critical section at the same time.

The Standard Form of Peterson's Algorithm

For two threads i and j, the entry section is usually written like this:

1flag[i] = true;
2turn = j;
3while (flag[j] && turn == j) {
4    // wait
5}

Meaning:

• 'flag[i] = true announces "I want to enter"'
• 'turn = j yields priority to the other thread if both compete'
• the while loop waits only when the other thread also wants in and it is their turn

The order matters because other threads must see your intent before the tie-break rule is evaluated.

The Common Reordering That Breaks It

Suppose you swap the first two commands:

1turn = j;
2flag[i] = true;
3while (flag[j] && turn == j) {
4    // wait
5}

That looks harmless, but it changes the observable state seen by the other thread during the critical race window.

Counterexample: Both Threads Enter

Let thread 0 and thread 1 both try to enter, using the reordered version.

Thread 0:

turn = 1;

Before it sets flag[0] = true, it is preempted.

Thread 1 runs:

turn = 0;
flag[1] = true;
while (flag[0] && turn == 0) { }

At this moment flag[0] is still false, so thread 1 does not wait and enters the critical section.

Now thread 0 resumes:

flag[0] = true;
while (flag[1] && turn == 1) { }

flag[1] is true, but turn is now 0, because thread 1 changed it. So the condition is false, and thread 0 also enters the critical section.

Now both are inside. Mutual exclusion is violated.

Why the Original Order Prevents That Case

In the correct version, each thread sets its flag before handing over the turn.

That means if a competing thread checks your state, it can already see that you intend to enter. The turn assignment then acts as a tie-breaker between two visible contenders.

In the broken version, one thread can momentarily give away the turn before it has published its interest, which opens the door to the interleaving above.

A Small Simulation in Python

The exact CPU memory semantics are not modeled here, but this sketch helps visualize the logical problem.

1flag = [False, False]
2turn = None
3
4# Thread 0 starts and gets interrupted early
5turn = 1
6
7# Thread 1 runs the reordered version
8turn = 0
9flag[1] = True
10t1_waits = flag[0] and (turn == 0)  # False
11
12# Thread 0 resumes
13flag[0] = True
14t0_waits = flag[1] and (turn == 1)  # False
15
16print("Thread 1 waits:", t1_waits)
17print("Thread 0 waits:", t0_waits)

Both conditions are false, which matches the violation scenario.

The Broader Lesson

Peterson's algorithm is not just a set of statements with the right variables. It is a carefully ordered protocol. The proof depends on:

• each thread announcing intent
• one shared tie-break variable
• a specific ordering of those writes

Changing the order changes the algorithm, not just the implementation style.

This is a recurring lesson in concurrent programming: if an algorithm is proven correct under a particular ordering, "small" reorderings are not small at all.

Memory Model Note

Even the standard Peterson algorithm assumes a strong enough memory model or explicit barriers so that other threads observe the writes as intended. On modern real hardware and languages, the naive textbook version may need memory-ordering support to be correct in practice.

That means there are two separate issues:

• the logical order in the algorithm
• the hardware or language memory ordering needed to preserve that logic

Reordering the commands is a correctness bug even before you get to low-level memory-model details.

What Properties Break

The most obvious property that breaks is mutual exclusion. But reorderings can also affect:

• progress
• bounded waiting
• fairness assumptions

Once the original reasoning is invalidated, you no longer have the original guarantees.

Common Pitfalls

One common mistake is thinking the two assignments are independent and can be swapped for style or micro-optimization reasons. They are not independent.

Another mistake is reading Peterson's algorithm as if it were ordinary sequential code rather than a protocol observed by another concurrent actor.

Developers also test only with light contention and conclude the reordered version "works." Concurrency bugs often survive casual testing.

Finally, some discussions mix algorithmic ordering bugs with hardware memory-reordering issues. Both matter, but they are different problems.

Summary

• Reordering Peterson's entry-section commands can break mutual exclusion.
• The classic bad swap is writing turn before publishing flag[i] = true.
• That allows an interleaving where both threads skip the wait loop and enter the critical section.
• Peterson's algorithm depends on the exact order of its shared-state updates.
• In concurrent algorithms, a reordered statement sequence is often a different algorithm altogether.