Knowledge Guide
Home › Hands-On Builds › Concurrency Katas

Build a Traffic Light Controller

Build a Traffic Light Controller

Every stateful coordinator you'll ever ship — a deployment orchestrator flipping traffic between blue/green fleets, a feature-flag rollout gate, a distributed lock manager deciding who holds the lease — is this problem wearing a different costume: a small set of mutually exclusive states, several threads racing to read "whose turn is it," and one thread whose job is to change the answer. Get it right and the intersection never has a collision and nobody waits forever. Get it wrong in the one specific way interviewers probe for, and two directions drive at once — and the lock you added didn't save you. This lab makes you build a traffic-light-controlled intersection from an empty file, in Java and Go, break its safety invariant on purpose, and see with your own eyes why "add a lock" is necessary but not sufficient. It also underpins the Traffic-Light-Controlled Intersection Synchronization pattern and the broader Deadlock, Livelock & Starvation foundations — do this lab first, those pages will read like a victory lap.

1. The trap

You're asked to build the controller for a single intersection: cars arrive from the North-South road and the East-West road, and exactly one of the two may have the right of way at any instant. The "obvious" first draft, written by someone who's only ever worked single-threaded:

final class TrafficLightNaive {
    boolean nsGreen = true;   // plain fields, no lock
    boolean ewGreen = false;

    void drive() { /* simulated work */ }

    // controller thread, once a "while(true)" tick:
    void switchLight() {
        nsGreen = !nsGreen;
        ewGreen = !ewGreen;
    }

    // a car thread on direction d:
    void cross(boolean isNs) {
        while (isNs ? !nsGreen : !ewGreen) { /* spin */ }
        drive();
    }

    public static void main(String[] args) throws InterruptedException {
        TrafficLightNaive t = new TrafficLightNaive();
        new Thread(() -> t.cross(true)).start();
        Thread.sleep(50);
        t.switchLight();
    }
}

This dies two different ways the moment you run it with real threads:

Both failures share one root cause: nobody owns "is it safe to change the light," and nobody has a real way to sleep until it changes. You need a lock that makes every read/write atomic and visible, a condition variable so waiting cars actually sleep, and — this is the part everyone forgets — a protocol for the order in which the controller flips things, because the lock alone does not give you that. That gap is the entire lesson of this lab.

2. Scope it like a senior

Before writing a line, pin the contract down. Ask:

Answering these before coding is what "senior" looks like: you're negotiating the spec, not guessing at it.

3. Reason to the design

Attempt 0 — no synchronization. That's Movement 1's trap: plain fields, torn reads, a busy-wait. Nobody's proud of this one; it's the strawman that motivates everything else.

Attempt 1 — add a lock, but get the order wrong. Put every read and write behind a single lock, so each individual field access is now atomic and visible — no more torn reads. Then, trying to be efficient ("minimize dead time between phases"), the controller grants the new direction green before it revokes the old direction's green/yellow:

import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.ReentrantLock;

final class Attempt1 {
    static final int RED = 0, GREEN = 1;
    final ReentrantLock lock = new ReentrantLock();
    final Condition[] cond = { lock.newCondition(), lock.newCondition() };
    final int[] light = { RED, RED };

    void switchPhase(int to, int from) {
        lock.lock();
        try { light[to] = GREEN; cond[to].signalAll(); }   // new direction goes first...
        finally { lock.unlock(); }

        // ...a window exists right here...

        lock.lock();
        try { light[from] = RED; }                          // ...old direction cleared second
        finally { lock.unlock(); }
    }
}

This is the trap that actually catches people, because it feels safe — every single write is inside a lock, so surely nothing can go wrong? But the lock only guarantees that each individual write is atomic and visible. It says nothing about whether the sequence of writes you chose describes a safe state. Between those two lock acquisitions, the old direction is still non-red (green or yellow) and the new direction is already green: both have the right of way. That window is real, and Movement 5 measures it.

Attempt 2 — the fix is a protocol, not more locking. Always fully revoke the old direction (→ RED) before granting the new one (→ GREEN), with an all-red clearance gap in between for real-world safety margin. Two separate critical sections are still fine — the lock was never the problem. What keeps the invariant is the order: revoke(from) always happens-before grant(to), so any reader that acquires the lock in between only ever sees "both red," never "both non-red."

Layer the fairness question on top: a fixed timer, cycling directions unconditionally regardless of demand, is bounded-wait by construction — nobody can be skipped because nobody is ever asked "do you have traffic?" A demand-actuated scheme has to earn that same guarantee explicitly (a max-wait/aging bound), or it can starve a direction indefinitely. We build the fixed-cycle version; the demand-actuated trap is Movement 7.

Car threads wait on a per-direction condition variable (not one shared condition for both directions) guarded by the same lock as the state, and they recheck their predicate in a while loop after waking — standard condition-variable hygiene (spurious wakeups; a car might wake, re-acquire the lock, and find its direction already flipped back if it was slow to resume). None of that hygiene is this lab's headline lesson — the headline lesson is Attempt 1 above: a lock makes each write atomic; it does not make your protocol correct. You still have to get the order right.

4. Build it — milestones

Build the controller milestone by milestone. Attempt each yourself before reading the reference implementation below — the reveal is positioned after the tests on purpose.

Reference implementation — Java (ReentrantLock + one Condition per direction)

Every write is lock-protected. What actually keeps the invariant is that revoke(from) is always called before grant(to) — never the reverse. Movement 5 shows exactly what breaks if that order flips.

import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.ReentrantLock;

/**
 * A two-direction (NS / EW) traffic light state machine.
 * Correct version: EVERY write is protected by the lock (so no torn/stale
 * reads), AND the protocol always fully revokes the old direction (-> RED)
 * before granting the new one (-> GREEN), with an all-red clearance gap
 * in between. The lock alone is not enough -- see BuggyTrafficController,
 * which holds the same lock on every write yet still breaks mutual
 * exclusion because it gets the ORDER wrong.
 */
public final class TrafficController {

    public enum Light { RED, YELLOW, GREEN }
    public enum Dir { NS, EW }

    private final ReentrantLock lock = new ReentrantLock();
    private final Condition[] greenCond = { lock.newCondition(), lock.newCondition() };
    private final Light[] light = { Light.RED, Light.RED }; // indexed by Dir.ordinal()
    private volatile boolean running = true;

    private final long greenMs, yellowMs;
    private static final long ALL_RED_MS = 5; // M2: clearance gap, both directions RED

    public TrafficController(long greenMs, long yellowMs) {
        this.greenMs = greenMs;
        this.yellowMs = yellowMs;
    }

    /** Car thread: blocks until its direction is GREEN. */
    public void cross(Dir dir) throws InterruptedException {
        lock.lock();
        try {
            while (light[dir.ordinal()] != Light.GREEN && running) {
                greenCond[dir.ordinal()].await();
            }
        } finally {
            lock.unlock();
        }
        // "driving" happens outside the lock -- never hold a lock across a slow op
    }

    /** Atomic read used by the mutual-exclusion monitor -- ONE lock acquisition.
     *  Violated if BOTH directions simultaneously have the right of way (GREEN or
     *  YELLOW) -- i.e. neither is RED. That is the actual collision condition:
     *  a car can legally still be moving on yellow, not just on solid green. */
    public boolean mutualExclusionViolated() {
        lock.lock();
        try {
            return light[Dir.NS.ordinal()] != Light.RED && light[Dir.EW.ordinal()] != Light.RED;
        } finally {
            lock.unlock();
        }
    }

    /** The safe protocol: fully revoke `from` (-> RED), THEN grant `to` (-> GREEN).
     *  Two separate critical sections are fine -- the lock makes each write atomic
     *  and visible; it is the RED-before-GREEN order that keeps the invariant. */
    private void revoke(Dir from) {
        lock.lock();
        try { light[from.ordinal()] = Light.RED; }
        finally { lock.unlock(); }
    }

    private void grant(Dir to) {
        lock.lock();
        try { light[to.ordinal()] = Light.GREEN; greenCond[to.ordinal()].signalAll(); }
        finally { lock.unlock(); }
    }

    /** The controller thread: the whole state machine, one thread, one loop. */
    public void run() {
        Dir cur = Dir.NS;
        grant(cur);

        while (running) {
            sleep(greenMs);
            lock.lock();
            try { light[cur.ordinal()] = Light.YELLOW; }
            finally { lock.unlock(); }

            sleep(yellowMs);
            Dir next = (cur == Dir.NS) ? Dir.EW : Dir.NS;

            revoke(cur);          // old -> RED first ...
            sleep(ALL_RED_MS);    // ... both RED for a beat (M2 clearance gap) ...
            grant(next);          // ... THEN new -> GREEN.

            cur = next;
        }
    }

    public void stop() {
        lock.lock();
        try {
            running = false;
            greenCond[0].signalAll();
            greenCond[1].signalAll();
        } finally {
            lock.unlock();
        }
    }

    static void sleep(long ms) {
        try { Thread.sleep(ms); } catch (InterruptedException ignored) { Thread.currentThread().interrupt(); }
    }
}

Reference implementation — Go (sync.Mutex + one *sync.Cond per direction)

Line-for-line the same design as the Java version — a controller goroutine owns the state machine, car goroutines block on Cross:

package trafficlight

import (
    "sync"
    "time"
)

type Light int

const (
    Red Light = iota
    Yellow
    Green
)

type Dir int

const (
    NS Dir = iota
    EW
)

const allRedGap = 5 * time.Millisecond // M2: clearance gap, both directions Red

// Controller is a two-direction traffic light state machine: one Mutex plus
// one *sync.Cond per direction. Every write is lock-protected (no torn
// reads), AND the protocol always fully revokes the old direction (-> Red)
// before granting the new one (-> Green), with an all-red gap in between.
// The lock alone is not enough -- see BuggyController, which holds the same
// lock on every write yet still breaks mutual exclusion because it gets the
// ORDER wrong.
type Controller struct {
    mu        sync.Mutex
    greenCond [2]*sync.Cond
    light     [2]Light
    running   bool
    greenMs   time.Duration
    yellowMs  time.Duration
}

func NewController(green, yellow time.Duration) *Controller {
    c := &Controller{running: true, greenMs: green, yellowMs: yellow}
    c.greenCond[NS] = sync.NewCond(&c.mu)
    c.greenCond[EW] = sync.NewCond(&c.mu)
    return c
}

// Cross blocks a car goroutine until its direction is Green.
func (c *Controller) Cross(dir Dir) {
    c.mu.Lock()
    for c.light[dir] != Green && c.running {
        c.greenCond[dir].Wait()
    }
    c.mu.Unlock()
    // "driving" happens outside the lock -- never hold a lock across a slow op
}

// MutualExclusionViolated is the atomic monitor read -- ONE lock acquisition.
func (c *Controller) MutualExclusionViolated() bool {
    c.mu.Lock()
    defer c.mu.Unlock()
    return c.light[NS] != Red && c.light[EW] != Red
}

// revoke and grant are two SEPARATE critical sections -- that's fine. What
// keeps the invariant is calling revoke(from) before grant(to), never the
// reverse.
func (c *Controller) revoke(from Dir) {
    c.mu.Lock()
    c.light[from] = Red
    c.mu.Unlock()
}

func (c *Controller) grant(to Dir) {
    c.mu.Lock()
    c.light[to] = Green
    c.greenCond[to].Broadcast()
    c.mu.Unlock()
}

// Run is the controller goroutine: the whole state machine, one goroutine,
// one loop.
func (c *Controller) Run() {
    cur := NS
    c.grant(cur)

    for {
        time.Sleep(c.greenMs)
        c.mu.Lock()
        if !c.running { c.mu.Unlock(); return }
        c.light[cur] = Yellow
        c.mu.Unlock()

        time.Sleep(c.yellowMs)
        c.mu.Lock()
        stillRunning := c.running
        c.mu.Unlock()
        if !stillRunning { return }

        next := EW
        if cur == EW { next = NS }

        c.revoke(cur)         // old -> Red first ...
        time.Sleep(allRedGap) // ... both Red for a beat (M2 clearance gap) ...
        c.grant(next)         // ... THEN new -> Green.

        cur = next
    }
}

func (c *Controller) Stop() {
    c.mu.Lock()
    c.running = false
    c.greenCond[NS].Broadcast()
    c.greenCond[EW].Broadcast()
    c.mu.Unlock()
}

Both compile clean: javac -Xlint:all *.java produces zero warnings; go build ./... and go vet ./... are clean; both were exercised end to end (multiple car goroutines/threads crossing across dozens of phase switches) before writing this page.

5. Break it — the test that fails

Change exactly one thing: swap the order of revoke and grant around a phase switch. Everything else — the lock, the conditions, the loop — is byte-for-byte identical. This is the "shave dead time between phases" optimization someone will actually propose in review.

import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.ReentrantLock;

/**
 * BUGGY -- the ONLY change from TrafficController is the transition ORDER:
 * to shave "dead time" between phases, this version grants the new
 * direction green BEFORE revoking the old direction's green/yellow.
 * Every single write is still inside a lock (no torn reads) -- the lock was
 * never the problem. The protocol is: get the ORDER backwards, and mutual
 * exclusion breaks even though every write is perfectly synchronized.
 */
public final class BuggyTrafficController {

    public enum Light { RED, YELLOW, GREEN }
    public enum Dir { NS, EW }

    private final ReentrantLock lock = new ReentrantLock();
    private final Condition[] greenCond = { lock.newCondition(), lock.newCondition() };
    private final Light[] light = { Light.RED, Light.RED };
    private volatile boolean running = true;

    private final long greenMs, yellowMs;

    public BuggyTrafficController(long greenMs, long yellowMs) {
        this.greenMs = greenMs;
        this.yellowMs = yellowMs;
    }

    public void cross(Dir dir) throws InterruptedException {
        lock.lock();
        try {
            while (light[dir.ordinal()] != Light.GREEN && running) {
                greenCond[dir.ordinal()].await();
            }
        } finally {
            lock.unlock();
        }
    }

    public boolean mutualExclusionViolated() {
        lock.lock();
        try {
            return light[Dir.NS.ordinal()] != Light.RED && light[Dir.EW.ordinal()] != Light.RED;
        } finally {
            lock.unlock();
        }
    }

    // Java -- BuggyTrafficController, the ONLY change from the correct version:
    private void grant(Dir to) {           // still lock-protected, still atomic ...
        lock.lock();
        try { light[to.ordinal()] = Light.GREEN; greenCond[to.ordinal()].signalAll(); }
        finally { lock.unlock(); }
    }
    private void revoke(Dir from) {        // ... but called in the WRONG ORDER below
        lock.lock();
        try { light[from.ordinal()] = Light.RED; }
        finally { lock.unlock(); }
    }

    public void run() {
        Dir cur = Dir.NS;
        grant(cur);

        while (running) {
            sleep(greenMs);
            lock.lock();
            try { light[cur.ordinal()] = Light.YELLOW; }
            finally { lock.unlock(); }

            sleep(yellowMs);
            Dir next = (cur == Dir.NS) ? Dir.EW : Dir.NS;

            // in the phase-switch loop:
            grant(next);   // BUG: new -> GREEN first ...
            sleep(1);      // artificial: widens the window so the demo reproduces on every
                           // run -- in production this shows up intermittently under load,
                           // which is worse, not rarer.
            revoke(cur);   // ... old -> RED second. Window: both non-RED.

            cur = next;
        }
    }

    public void stop() {
        lock.lock();
        try {
            running = false;
            greenCond[0].signalAll();
            greenCond[1].signalAll();
        } finally {
            lock.unlock();
        }
    }

    static void sleep(long ms) {
        try { Thread.sleep(ms); } catch (InterruptedException ignored) { Thread.currentThread().interrupt(); }
    }
}

The monitor: a background thread/goroutine samples mutualExclusionViolated() in a tight loop — a single atomic, lock-protected read of both directions at once, so the monitor's own check can never be the thing lying to you.

Run it (fixed-cycle controller, ~20ms green / ~10ms yellow, sampled for one second):

BUGGY   controller: raw samples-in-violation = 3626744, distinct violation episodes = 22
CORRECT controller: raw samples-in-violation = 0, distinct violation episodes = 0
BUG REPRODUCED: the buggy two-step transition let both directions have the
right of way at once, on every phase switch.

The Go version reproduces identically under go test -race:

=== RUN   TestMutualExclusion_BuggyControllerViolatesInvariant
    breakit_test.go:38: BUGGY controller: raw samples-in-violation = 127586, distinct violation episodes = 28
--- PASS: TestMutualExclusion_BuggyControllerViolatesInvariant (1.00s)
=== RUN   TestMutualExclusion_CorrectControllerNeverViolatesInvariant
    breakit_test.go:73: CORRECT controller: raw samples-in-violation = 0, distinct violation episodes = 0
--- PASS: TestMutualExclusion_CorrectControllerNeverViolatesInvariant (1.00s)
PASS

The exact sample/episode counts wobble a little run to run — real wall-clock scheduling jitter, not a bug in the test — but the qualitative result never wobbles across any run we took: the buggy controller violates mutual exclusion on every single phase switch (one episode per switch, ~20-28 of them per second at this timer speed); the correct controller violates it exactly zero times, always. This is not a rare interleaving you need luck or -race to catch — the window opens on every handoff, deterministically, because the bug isn't a race in the usual "sometimes" sense, it's a protocol error that is wrong on every occurrence. -race confirms there's no data race hiding underneath (every field access is still lock-protected) — which is exactly the point: this bug is not a memory-visibility bug at all, it's a logic bug that a race detector cannot find, because nothing about it is unsynchronized.

The fix is reverting the call order: revoke(cur) before grant(next), with the all-red gap in between. Same two critical sections, same lock, same conditions — only the order of two lines changed, and the invariant holds for the rest of the run.

6. Optimise — with trade-offs

ApproachCorrectness guaranteeComplexityScales to many waitersUse when
Single lock + one Condition per direction (this lab)Native: every write is atomic/visible; YOU must still get revoke-before-grant order rightModerate — you own the transition protocolFine for a handful of waiters; the lock serializes every read/writeDefault choice: a small, in-process FSM with a handful of threads reading/writing shared state
Per-direction semaphoresA binary/counting semaphore per direction encodes "permits to proceed" directly — acquire = wait for your green, release = grant itSimilar to the lock approach; no explicit predicate-recheck loop, but a stray extra release() is a phantom green — a different but equally real bug classComparable to the lock versionWhen you want a library-provided primitive over hand-rolled wait/notify and your waiters don't need a custom predicate
Actor / channel controller (Go channels, or an actor mailbox)The controller goroutine is the ONLY thing that ever touches the state; car goroutines send a "let me cross" message and block on a reply channel — there is no shared mutable state for a get-the-order-wrong bug to corruptHighest — no lock, no condition, but you design and maintain a message protocol insteadScales better with many waiters (no shared-lock contention; only the controller touches state)Any Go program with more than a handful of concurrent cars, or anywhere "no shared mutable state, by construction" is worth the message-passing indirection
Pure FSM engine + a thin threading adapterCorrectness of the state machine itself is provable/unit-testable in complete isolation (feed it events, assert states) — a separate adapter layer translates "FSM says GREEN now" into condition-variable signalsHighest conceptual purity, most moving parts (two layers instead of one)Independent of this axis — this is a testability trade, not a throughput oneWhen the state machine itself has enough states/guards (a real 4-way intersection with turn lanes, say) to be worth testing without spinning up any threads at all

The real judgment call: wiring the FSM logic directly into the same lock that gates the threads (as this lab does) is the pragmatic middle ground — one file, one lock, easy to reason about for a 2-state problem. The moment the state machine itself grows complex (many phases, many conflict pairs, pedestrian requests, emergency overrides), the purity trade flips: you want the FSM's transition logic unit-tested with zero threads involved, and a thin adapter that turns "FSM emitted GREEN(EW)" into grant(EW) calls. Reach for that split only when the FSM is complex enough to justify testing it in isolation — for a lab-sized 2-direction light, it's needless indirection.

7. Defend under drilling

An interviewer will push on the design. These are the follow-ups that come up almost every time, with the answer a staff engineer gives — short, concrete, no hedging.

8. You can now defend

Re-authored/Deepened for this guide. Reference code compiled and executed (javac -Xlint:all; go build, go vet, go test -race) before publishing; the break-it test reproduces the mutual-exclusion violation deterministically on every phase switch, every run. See also: the Traffic-Light-Controlled Intersection Synchronization pattern and Deadlock, Livelock & Starvation.

🤖 Don't fully get this? Learn it with Claude

Stuck on Build a Traffic Light Controller? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🎨 Explain it visually

Build the mental picture, not memorization.

I just read a lesson on **Build a Traffic Light Controller** (Hands-On Builds) and want to truly understand it. Explain Build a Traffic Light Controller from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🤔 Walk me through it (interactive)

Socratic — adapts to where you're stuck.

Teach me **Build a Traffic Light Controller** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🧪 Quiz me & fix my gaps

Active recall exposes what you missed.

Quiz me on **Build a Traffic Light Controller** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.
🧠 Make it stick

Intuition + hook + flashcards for long-term memory.

Help me remember **Build a Traffic Light Controller** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Build the H2O Molecule Barrier