Lower Bounds for a Primary–Backup Implementation of a Bofo Service
Navin Budhiraja, Keith Marzullo, Fred B. Schneider, Sam Toueg · 2013
Introduction One way to implement a fault-tolerant service is the primary-backup or primarycopy approach [1]. With this approach, a service is implemented by a collection of servers. One server is designated as the primary; the others are called backups. Clients send requests to the primary and any responses to requests come from the primary. If the primary fails, then a failover occurs after which one of the backups assumes the role of the primary. With the primary-backup approach, a request from a client to the service can be lost if sent to a faulty primary. However, periods during which requests can be lost are bounded by the length of time that elapses between the failure of the primary and the takeover by a backup. Such behavior is an instance of what we call a bofo service (bounded outage finitely often); an (i, #)--bofo service is one in which requests that are not processed fall into at most i intervals of time, each interval having a length of at most #. Thus, in an (i, #)