Tradeoffs in implementing primary-backup protocols

Abstract

One way to implement a fault-tolerant service is to replicate the state of the service across a primary server and a set of backup servers. Clients make requests to the primary, which then computes the response, informs the backups of the state change, and then replies to the client. If the primary subsequently fails, then a backup takes over as the new primary. Informally, a primary-backup protocol is non-blocking if the primary need not wait for acknowledgments from the backups before responding to the client; otherwise, the protocol is blocking. While most of the existing protocols are blocking, we show that non-blocking protocols can be constructed for the kinds of failures that are expected to occur in many future primary-backup systems. We implement and measure the performance in failure-free runs of two kinds of non-blocking protocols - one based on point-to-point communication and one based on broadcast - and compare the results with conventional blocking primary-backup protocols. Finally, we discuss extending our results to runs with failures.