Paxos is a consensus algorithm executed by a set of processes, termed replicas, to agree on a single value
in the presence of failures. Replicas may crash and subseqently recover. The network may drop messages
3
Figure 2: API for fault-tolerant log.
between replicas. Replicas have access to persistent storage that survives crashes. Some replicas may submit
values for consensus. If eventually a majority of the replicas run for long enough without crashing and there
are no failures, all running replicas are guaranteed to agree on one of the values that was submitted. In our
system, the value to be agreed upon is the next entry in a (replicated) log as described in the introduction.