Each server stores a log (a series of commands)
Its state machine executes the log in order
Consensus algorithm ensure logs are consistent
Key properties
- Safety: never return incorrect result
- available as long as any majority of servers are up
- Do not depends on timing
- A command can complete as soon as majority of the cluster responded (no wait for slow servers)