Page History

...

Paxos can be used for primary-backup replication by letting the primary be the leader. The problem with Paxos is that, if a primary concurrently proposes multiple state updates concurrently and fails, the new primary may apply uncommitted updates in an incorrect order. An example is presented in our DSN 2011 paper (Figure 1). In the example, a replica can should only apply the state update B after applying A. Applying The example shows that, using Paxos, a new primary and its follows may apply B after C, as can happen with Paxos, results in a reaching an incorrect state that has not been reached by any of the previous primaries, making recovery incorrect.

A workaround to this problem using Paxos is to sequentially agree on each state updateupdates: a primary proposes a state update is proposed by the primary only after it commits all previous state updates are committed. Since there is at most one uncommitted update at a time, a new primary cannot incorrectly reorder updates. This approach, however, results in poor performance.

Zab does not need this workaround. It Zab replicas can concurrently agree on the order of incremental state updates in parallel while preventing new primaries from recovering uncommitted updates in an incorrect order. Zab does that by adding an extra synchronization phase to recoverymultiple state updates without harming correctness. This is achieved by adding one more synchronization phase during recovery compared to Paxos, and by using a different numbering of instances based on zxids.

...