...

• A leader proposes values to the followers
• Leaders wait for acknowledgements from a quorum of followers before considering a proposal committed , or (learned)
• Proposals include epoch numbers, which are similar to ballot numbers in Paxos

...

A state machine replication system is a client-sever system ensuring that each state machine replica executes the same sequence of client requests, even if these requests are submitted concurrently by clients and received in different order orders by the replicas. Agreement Replicas agree on the execution order of client requests is ensured through using a consensus algorithm like Paxos. Client requests that are sent concurrently and are not yet completed overlap in time can be executed in an arbitrary order by state machine replicasany order. If a leader fails, a new leader that executes recovery is free to arbitrarily reorder any uncommitted request that since it is not yet completed.

In the case of primary-backup systems, such as Zookeeper, replicas agree on the application order of incremental (delta) state updates, which are generated by a primary replica and sent to its followers. Unlike client requests, state updates must be applied in the exact original generation order of the primary, and only starting from the original initial state of the primary. If a primary fails, a new primary that executes recovery cannot arbitrarily reorder uncommitted state updates, or apply them starting from a different initial state.

In conclusion, agreement on state updates (for primary-backup systems) requires stricter ordering guarantees than agreement on client requests (for state machine replication systems).

What are the implications for agreement algorithms?

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.

Want to know more?

Have a look at our DSN 2011 paper , or contact us!