This is my second time to read through Raft Algorithm, and it is hard to recall what I have learned in first reading. This time I decide to record my thoughts for future recall. Hope it is useful to newbies in distributed systems like me.
What does consensus algorithm mean ?
Consensus algorithm is the process used to achieve agreement on shared state among faulty processes in distributed system.
Introduce Replicated State Machines
Here, we define state machine as State' = Machine(State, Input)
for simplicity. A state machine
can be defined with its start state, and makes progress with sequence of inputs, produces sequence
of intermediate states. For examples:
1 | State' = Machine(State, Input) |
Given a state machine, how can we figure out that it is a replicated state machine ?
First, replicated state machine is deterministic. Given same start state with same sequence of inputs, the state machine always produce same intermediate states.
Second, two state machines built from same logic on possibly different processes or nodes and even possibly different languages must be same. Here we define two state machines as same based on deterministic: given same start state and same sequence of inputs, if two state machines produce same sequence of intermediate states, we say these two state machine are same. Thus given multiple copies of same state machines with same start state, feeding with same sequence of inputs, they must produces same sequence of intermediate states.
Third, states, including start state and intermediate states, and inputs must be self-contained, thus can be replicated to other processes or nodes with help of serialization and deserialization.