We use analytics cookies.We use cookies to analyze site traffic and improve your experience.
Loading...
2 system design questions lean on this idea. Each walks through the full answer.
System Design Masterclass · Distributed Systems Core
Free preview: the first 2 parts of this 8-part lesson.
Already bought the course? Sign in to read the whole lesson.
this lesson is part of
System Design Masterclass
Unlock this lesson and the 751 other paid lessons
$25 once, by PayPal
See the System Design courseread the rest of this lesson in
System Design Masterclass
Unlock this lesson and the 751 other paid lessons
$25 once, by PayPal
See the System Design coursein Distributed Systems Core
This lesson is part of the full System Design Masterclass. Unlock it along with 769 other lessons for a one-time payment.
One-time payment by card or PayPal
Get Lifetime AccessOne-time payment: UPI, card or netbanking
Get Lifetime Access18 Foundation lessons are free, no payment needed. Try them now
It is easy and good
“It is really nice and good Please join the course”
Every time your browser opens a connection, it runs a finite state machine. Every time Kafka decides whether a message is committed, it runs a finite state machine. Every time your payment gateway processes a charge, same thing.
You might think "I already learned state machines in the last lesson, what's new?" Fair question. The difference is specificity. A generic state machine is a concept. A finite state machine (FSM) is a formal mathematical model with precise definitions, provable properties, and two distinct flavors, deterministic and non-deterministic, that show up everywhere in systems engineering.
The "finite" part is the whole point. The machine has a finite number of states. Not "a lot" of states. Not "we'll add more later." A fixed, countable, enumerable number. This finiteness is what lets us prove things about the machine, that it will always terminate, that it can never reach certain states, that every input produces a predictable output.
This matters practically because when you're designing a distributed protocol, you need to prove it correct. Not "test it a bunch and hope for the best." Prove it. Formally. And FSMs give you the framework to do that. This is how Leslie Lamport designs protocols. This is how the TLA+ specification language works. This is how the engineers at AWS formally verify their distributed systems.
A Deterministic Finite Automaton (DFA) is the simpler one. From any state, given any input, there is exactly one possible next state. No ambiguity. No choices. You're at state A, you receive input X, you go to state B. Always. Every time.
A Non-deterministic Finite Automaton (NFA) allows ambiguity. From state A with input X, you might go to state B or state C. The machine "chooses", or more precisely, it explores all possible paths simultaneously. NFAs are theoretically equivalent to DFAs (you can convert any NFA to a DFA), but the DFA might need exponentially more states.
Here's the formal definition of a DFA, five components, no more, no less:
| Component | Symbol | What It Is |
|---|---|---|
| States | Q | Finite set of all possible states |
| Alphabet | Sigma | Finite set of all possible inputs |
| Transition function | delta | Q x Sigma -> Q (deterministic mapping) |
| Start state | q0 | The initial state |
| Accept states | F | Subset of Q that represent "success" |
The transition function is the key difference between DFA and NFA. In a DFA, delta maps each (state, input) pair to exactly one state. In an NFA, delta maps each (state, input) pair to a set of possible states.
Why this matters for distributed systems: Every node in a Raft cluster runs a DFA. It's either a follower, candidate, or leader. Given an event (election timeout, vote received, heartbeat received), the next state is deterministic. If it weren't, if a node could non-deterministically choose between follower and candidate, the protocol would be unprovable and unreliable.