
# Epaxos

## Big Ideas
- No leader
  - any replica can act as a leader at any time
- hope for non-conflicts
  - for a kv store a conflict is key equality
- separate "commit" from "execute"
- "replicated log" is now a 2d set of subspaces

Fast Path
- propose a cmd and all known deps
- optimistically hope we don't learn any new conflicts
- if so, we need .....

Slow Path
- a second round, only if we learn new deps

![pic](epaxosExample.png)

&nbsp;<p>
&nbsp;<p>
&nbsp;<p>
&nbsp;<p>
&nbsp;<p>
&nbsp;<p>
&nbsp;<p>
&nbsp;<p>

[pic](epaxosProtocol.png)

## Execution

"commit" => promise to commit at a specific slot
"execute" => more similar to commit in other systems, *asynchronous*
- commit msgs after client notified

reads vs writes
- execute only needed on a read

Algorithm:
1. get set of all depends yet to be executed
1. use Tarjan to separate into strongly connected components
1. foreach SCC in inverse topological order
   - sort commands in seq number order
   - execute in increasing seq number order

## Opts
- thriftiness: only mcast to nearby quorum


**Coolness:**
- *never need slow path for N=3*
- "geo-replicated" w/o having to talk to a single remote site

**Not-Coolness:**
- No numbers, no implementation, for N>5.

Why?

