Chapter 3: State Machines

The Finite States That Make Fault Tolerance Possible

🚦 The Traffic Light Analogy

A traffic light has exactly 3 states: RED, YELLOW, GREEN. It can only transition in specific ways (GREEN→YELLOW→RED→GREEN).

This predictability is what makes intersections safe! You KNOW what comes next.

PCCL's state machine is the same idea - by limiting possible states and transitions, we can handle EVERY failure scenario.

Why State Machines Matter

💡 The Key Insight

Previous PCCL attempts failed because they allowed too many states:

Solution: Restrict to finite state machine → every error path is testable!

The Three Levels of State

PCCL tracks state at three levels:

┌─────────────────────────────────────────────────────────────────────────┐ │ THREE LEVELS OF STATE │ └─────────────────────────────────────────────────────────────────────────┘ Level 1: CONNECTION PHASE (per peer) ───────────────────────────────────── "Am I part of the group yet?" ┌────────────┐ ┌────────────┐ │ REGISTERED │ ──── vote ───► │ ACCEPTED │ │ │ passes │ │ └────────────┘ └────────────┘ • REGISTERED: Connected, but can't participate in collectives • ACCEPTED: Full member, can participate in everything Level 2: CONNECTION STATE (per peer) ───────────────────────────────────── "What am I doing right now?" ┌──────┐ ┌───────────────────┐ ┌─────────────────────┐ │ IDLE │◄───►│ VOTE_ACCEPT_PEERS │◄───►│ COLLECTIVE_RUNNING │ └──────┘ └───────────────────┘ └─────────────────────┘ ▲ ▲ │ ┌─────────────────┐ │ └────────►│ SYNCING_STATE │◄──────────────┘ └─────────────────┘ Level 3: COLLECTIVE STATE (per operation tag) ───────────────────────────────────────────── "Where is this specific operation?" ┌───────────────┐ ┌───────────────┐ ┌───────────────┐ │ VOTE_INITIATE │────►│ PERFORMING │────►│ VOTE_COMPLETE │ └───────────────┘ └───────────────┘ └───────────────┘

Level 1: Connection Phase

Phase Description Can Do
REGISTERED Connected to master, waiting for acceptance Wait, receive topology updates
ACCEPTED Voted in by existing peers Everything: collectives, sync, P2P
Connection Phase Transition: ───────────────────────────────────────────────────────────────────────── New Peer Master Existing Peers │ │ │ │─── connect() ───────────►│ │ │ │ │ │◄── phase=REGISTERED ─────│ │ │ │ │ │ │◄── "accept new peer?" ───│ │ │ │ │ │─── vote request ────────►│ │ │ │ │ │◄── all vote YES ─────────│ │ │ │ │◄── phase=ACCEPTED ───────│ │ │ │ │ │◄─────────────── establish P2P connections ─────────►│ │ │ │ ▼ ▼ ▼

Level 2: Connection State

State Description Transitions To
IDLE Ready for any operation Any other state
VOTE_ACCEPT_NEW_PEERS Voting on whether to accept registered peers IDLE (after vote)
SYNCING_SHARED_STATE Synchronizing model weights/optimizer state IDLE (after sync)
COLLECTIVE_COMMUNICATIONS_RUNNING Executing a collective operation IDLE (after complete)

Level 3: Collective State

Each collective operation (identified by a tag) has its own state:

State Description Next State
VOTE_INITIATE Peers voting to start the operation PERFORMING (if all agree)
PERFORMING Actually executing (reduce-scatter, all-gather) VOTE_COMPLETE (when done)
VOTE_COMPLETE Peers confirming they finished (end of operation)

The Golden Rule

⚠️ ONE Operation At A Time!

Within a single peer group, PCCL enforces:

Why? This restriction makes the state space finite and error paths enumerable!

The One-Operation Rule: ───────────────────────────────────────────────────────────────────────── ALLOWED: IDLE → VOTE_ACCEPT → IDLE → COLLECTIVE → IDLE → SYNC → IDLE (sequential, one at a time) NOT ALLOWED: IDLE → VOTE_ACCEPT ─┬─► COLLECTIVE ← CONFLICT! └─► SYNC ← CONFLICT! (parallel operations)

Micro-Consensus

💡 Every Transition Needs Agreement

Before ANY state transition, ALL peers must agree. Like a jury - unanimous verdict required!

Micro-Consensus Flow: ───────────────────────────────────────────────────────────────────────── Master: "Ready to transition to COLLECTIVE_RUNNING?" │ ├──► Peer A: "Ready!" ──┐ ├──► Peer B: "Ready!" ──┼──► Master: "All agreed!" └──► Peer C: "Ready!" ──┘ │ ▼ Broadcast: "GO!" │ ┌─────────────────────────────────┼─────────────────────────────────┐ │ │ │ ▼ ▼ ▼ Peer A Peer B Peer C transitions transitions transitions simultaneously simultaneously simultaneously

Complete State Transition Diagram

┌─────────────────────────────────────────────────────────────────────────┐ │ COMPLETE STATE MACHINE │ └─────────────────────────────────────────────────────────────────────────┘ ┌─────────────┐ │ REGISTERED │ └──────┬──────┘ │ vote passes ▼ ┌─────────────────────────────────────────────────────────────────────────┐ │ ACCEPTED PHASE │ │ │ │ ┌──────────────────────────────────────────────────────────────┐ │ │ │ IDLE │ │ │ └──────────────────────────┬───────────────────────────────────┘ │ │ │ │ │ ┌─────────────────────┼─────────────────────┐ │ │ │ │ │ │ │ ▼ ▼ ▼ │ │ ┌─────────────┐ ┌─────────────┐ ┌─────────────┐ │ │ │ VOTE_ACCEPT │ │ SYNC_STATE │ │ COLLECTIVE │ │ │ │ _NEW_PEERS │ │ │ │ _RUNNING │ │ │ └──────┬──────┘ └──────┬──────┘ └──────┬──────┘ │ │ │ │ │ │ │ │ │ │ │ │ └────────────────────┴────────────────────┘ │ │ │ │ │ ▼ │ │ back to IDLE │ │ │ └─────────────────────────────────────────────────────────────────────────┘

Exercise: Trace the Path

✏️ Scenario

A new peer wants to join and participate in an all-reduce. Trace the states:

  1. New peer connects → Phase: ___
  2. Existing peers vote → Phase: ___
  3. Peer is accepted → Phase: ___, State: ___
  4. All-reduce starts → State: ___, CollectiveState: ___
  5. All-reduce completes → State: ___
Answers:
1. REGISTERED
2. REGISTERED (still waiting)
3. ACCEPTED, IDLE
4. COLLECTIVE_RUNNING, VOTE_INITIATE → PERFORMING → VOTE_COMPLETE
5. IDLE

"RAI-SCV" = Registered → Accepted → Idle → Sync/Collective/Vote

The journey of a peer through PCCL states!

Chapter Summary