Relationship between primary-backup and state machine replication

Question

Who can talk about the relationship between primary-backup and state machine replication from a high level view?

In my opinion, primary-backup is a kind of state machine replication. But it need additional mechanism to ensure all replications agree on a primary node which is not necessary in generic state machine replication...

Is it right? Or have any idea?

Answer 1

In my opinion, primary-backup is a kind of state machine replication. But it need additional mechanism to ensure all replications agree on a primary node which is not necessary in generic state machine replication...

I do not agree with what you said: they are similar because both try to implement a fault-tolerant service with different properties.

To my understanding, primary-backup makes synchrony assumptions (regarding local clocks of processes, the time it takes local computations of processes, and latency of communication channels) to provide safety properties: therefore, if you have an asynchronous system or if you have a system behaves asynchronously time to time, primary-backup does not work.

The SMR approach provides stronger consistency guarantees compared to primary-backup approach. Unlike the parimary-backup approach, classical State Machine Replication(SMR) protocols such as Paxos and PBFT can provide safety in an asynchronous system (at least they do not violate safety guarantees), and SMR protocols need synchrony to provide liveness (it depends on the SMR protocol but it is true for Paxos and PBFT).

Finally, many SMR protocols such as Paxos and PBFT make use of primary-backup approach to provide liveness. In these systems, a primary is elected and the primary assigns sequence numbers to client requests and proposes them to others. If a primary fails, the system runs a view change protocol to replace the failed primary.

Although I have tried to provide a high-level answer, the real answer depends on the considered SMR and primary-backup protocols: to compare the two protocols, we need to know provided safety and liveness properties. Furthermore, we need to know the considered system model, and assumptions made.

Resources:

1 Budhiraja, Navin, et al. "The primary-backup approach." Distributed systems 2 (1993): 199-216.

2 Castro, Miguel, and Barbara Liskov. "Practical byzantine fault tolerance." OsDI. Vol. 99. No. 1999. 1999.

3 Lamport, Leslie. "Paxos made simple." ACM SIGACT News (Distributed Computing Column) 32, 4 (Whole Number 121, December 2001) (2001): 51-58.

Answer 2

this is an answer from zookeeper's wiki

What is the difference between primary-backup and state machine replication?

A state machine is a software component that processes a sequence of requests. For every processed request, it can modify its internal state and produce a reply. A state machine is deterministic in the sense that, given two runs where it receives the same sequence of requests, it always makes the same internal state transitions and produces the same replies.

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 orders by the replicas. Replicas agree on the execution order of client requests using a consensus algorithm like Paxos. Client requests that are sent concurrently and overlap in time can be executed in any order. If a leader fails, a new leader that executes recovery is free to arbitrarily reorder any uncommitted request 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, 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).