What is a State Machine
Before delving into Replicated State Machines, let us first understand what a State Machine is. A state machine reads a series of inputs. Every time it reads an input, it sheds its old state and goes into a new one. Each state knows which state the machine goes into for a given input.
Consider a soda vending machine that accepts only quarters and vends one soda at a time for $0.25.
What are the possible states of the vending machine:
1. Idle State: Waiting for coin input. On receiving coin, transitions to Has Money State
2. Has Money state: Has a quarter and waiting for crank turn input. Once input is received, transitions to Sold State
3. Sold state: Crank Turned, dispenses soda, transitions to Idle State.
In this example, the soda vending machine is a state machine
1. Idle State
2. Has Money State
3. Sold State
1. Coin input
2. Crank turn input.
In each state, the vending machine knows which state it will transition to based on the input it receives.
The Vending machine is a deterministic state machine. Apply an input to a state, it will only transition to a single state.
So what are Replicated State Machines
The Soda vending machine is a simple application. Each machine maintains its own state independent of any other soda machine anywhere in the world.
Consider an application like Facebook. It serves 2 Billion people all over the globe, and probably employs millions of servers to do the job.
Two of the most critical non functional requirements of such an application are
1. Fault Tolerance: The application must be able to, fully or partially, operate when some part of the system fails. Most applications will use replication to achieve fault tolerance i.e. Each request will be processed by all servers i.e. Replicated State Machines
2. Transparency: Regardless of the actual number of servers in the network, the output he client sees should be the same as if the input is being processed by a single highly available server. The server process has to be deterministic, and all replicas have to be consistent.
All non-faulty replicas should arrive at the same output given the same inputs in a particular order. For the entire application to be consistent, it is important that all the replicas be given the same inputs in the same order. Once inputs are correctly replicated, each server’s state machine process them in order and outputs are returned to clients.