The Complexity Firewall (or, Why Peterson's Algorithm Failed on the Sega 32X)

I was browsing Hacker News recently and saw this absolutely bugnuts crazy post: someone ported Linux to the 1994 Sega 32X. The original blog post by Cakehonolulu details the wild technical hurdles involved in waking up a thirty-year-old dual-core console, but one specific detail stood out. Because the 32X’s memory controller ignores hardware atomic instructions over the cartridge bus, the author had to fall back to a forty-year-old trick called <dfn>Peterson's Algorithm</dfn>.

If you have never encountered it, Peterson's Algorithm is a purely software-based way to achieve mutual exclusion. Instead of relying on a specialized CPU lock, two threads communicate their desire to enter a critical section by writing to a shared flag array and yielding priority via a shared turn variable.

It is dope, and it naturally begs a question. If a couple of retro developers could achieve safe locking purely in software, why do modern CPUs dedicate vast amounts of complex silicon to hardware atomic operations?

(Yes, I know hardware atomics like IBM's 1964 Test-and-Set predate modern store buffers by decades. The argument here isn't that atomics were invented to solve the problem we are about to look at, but that their modern purpose has functionally shifted.)

To understand why pure software locking is effectively dead in production, we can model Peterson’s algorithm in TLA+. Under Sequential Consistency—where memory operations happen exactly in the order they are written—the logic is remarkably elegant.

VARIABLES flag, turn, pc

Init ==
    /\ flag = [i \in {0, 1} |-> FALSE]
    /\ turn = 0
    /\ pc = [i \in {0, 1} |-> "Start"]

Thread(i) ==
    \/ /\ pc[i] = "Start"
       /\ flag' = [flag EXCEPT ![i] = TRUE]
       /\ turn' = 1 - i
       /\ pc' = [pc EXCEPT ![i] = "Wait"]
    \/ /\ pc[i] = "Wait"
       /\ (flag[1 - i] = FALSE \/ turn = i)
       /\ pc' = [pc EXCEPT ![i] = "Critical"]
    \/ /\ pc[i] = "Critical"
       /\ flag' = [flag EXCEPT ![i] = FALSE]
       /\ pc' = [pc EXCEPT ![i] = "Start"]
       /\ turn' = turn

If we run this specification through the TLC model checker, it works perfectly. The state space is incredibly tiny, exhausting itself after fewer than 30 distinct states. There are no deadlocks, no safety violations, and no race conditions. It is just clean mathematical logic doing exactly what we expect.

But Sequential Consistency is a comforting lie. Modern processors aggressively reorder reads and writes to improve execution efficiency. Waiting for a write to travel all the way to main memory before executing the next instruction would leave the CPU idling for hundreds of cycles.

Before we go further, a quick caveat: I am not a silicon architect, so please forgive this extremely crude model of a store buffer. I just want to capture the mathematical essence of delayed memory visibility. If we modify our TLA+ code to simulate a modern L1 cache—where a thread writes to a local buffer before the main memory actually updates—we introduce a slight delay between a thread setting its flag and the other thread being able to read that updated flag.

Let’s run TLC on the weak-memory version of our model.

Error: Invariant MutualExclusion is violated.
Error: The behavior up to this point is:
State 1: <Initial predicate>
State 2: Thread(0) writes flag[0]=TRUE to local store buffer
State 3: Thread(1) writes flag[1]=TRUE to local store buffer
State 4: Thread(0) reads flag[1] == FALSE (buffer hasn't flushed)
State 5: Thread(1) reads flag[0] == FALSE (buffer hasn't flushed)
State 6: Both threads enter "Critical"

Then the physics arrived.

The visual difference in the state graph is staggering: what was once a neat, tidy chain of 30 nodes explodes into a chaotic, unreadable web of combinatorial branches, and TLC spits out a fatal counterexample. Because both threads buffered their flag writes, they both read the old memory state, assume the coast is clear, and violently crash into each other inside the critical section. This isn't just a quirk of formal modeling. As documented on Wikipedia, this exact read-write reordering is why Peterson's inherently fails on modern CPUs.

Which brings us back to the Sega 32X. If Peterson's is so fragile under the realities of hardware, how did the Linux port survive?

The Cakehonolulu post reveals a phenomenal punchline: the software-only port only functioned because of an inaccurate emulator. When the developer tested the code on real, physical Sega 32X hardware, the system instantly locked up. It turns out the write pins from the SH-2 processor to the Genesis cartridge area aren't even physically wired. The software was screaming into a hardware void. Avoiding hardware primitives is mathematically and physically fragile.

This failure perfectly illustrates a concept I want to introduce: the <dfn>Complexity Firewall</dfn>.

Concurrency is hair-pullingly frustrating, and if you struggle to model memory consistency in your head, please don't feel bad. It is not you, it is the unforgiving combinatorics of weak memory. We rely on modern hardware atomics not just because they execute instructions faster. We rely on them to absorb this uncheckable state-space explosion directly into the silicon. The hardware designers lock away the chaos of store buffers and delayed cache coherency behind a single atomic instruction, saving software engineers from immediate verification bankruptcy.

Of course, this could all be completely wrong. I am analyzing this strictly through the lens of a software verification practitioner, and actual silicon architects might categorize the evolution of microarchitectures completely differently.

But examining that emulation failure clarifies the relationship between the code we write and the chips that run it. Hardware isn't just executing our code; it's enforcing epistemic boundaries. We rely on silicon to handle the combinatorics not simply because it's fast, but because software engineering relies on a social contract: the hardware people quarantine the physical madness of electrons so the rest of us can just write the damn code.