Optimal Primary-Backup Protocols Navin Budhiraja* Keith Marzullo* Fred B. Schneider** Sam Toueg TR 92-1299 August 1992 Department of Computer Science Cornell University Ithaca, NY 14853-7501 *Supported by Defense Advanced Research Projects Agency (DoD) under NASA Ames grant number NAG 2-593 and by grants from IBM and Siemens. **Supported in part by the Office of Naval Research under contract N0001 4-91 -J- 1219, the National Science Foundation under Grant No. CCR-8701 103, DARPA/NSF Grant No. CCR-9014363 and by a grant from IBM Endicott Programming Laboratory. ***Supported in part by NSF grants CCR-8901780 and CCR-9102231 and by a grant frnm IBM Endicott Programming Laboratory. Optimal Primary-Backup Protocols Navin Budhiraja*, Keith Marzullo*, Fred B. Schneider?, Sam Toueg*** Department of Computer Science, Cornell University, Ithaca NY 14853, USA Abstract. We give primary--Hbackup protocols for various models of fail- ure, These protocols are optimal with respect to degree of replication, failover time, and response time to client requests. 1 Introduction One way to implement a fault-tolerant service is to employ multiple sites that fail independently. The state of the service is replicated and distributed among these sites, and updates are coordinated so that even when a subset of the sites fail, the service remains available. A common approach to structuring such replicated services is to designate one site as the primary and all the others as backups. Clients make requests by sending messages only to the primary. If the primary fails, then a failover occurs and one of tlie backups takes over. This service architecture is commoiily called the primary-backup or the primary-copy approach [1]. In [5] we give lower bouiids for implementingprim&y-backup protocols under various models of failure. These lower bounds constrain the degree of replication, the time during which the service can be without a primary, aud the amount of time it can take to respond to a client request. In this paper, we show that most of these lower bounds are tight by giving matching protocols. Some of the protocols that we describe have surprising properties. In one case, the optimal protocol is one in which a non-faulty primary is forced to relinquish control to a backup that it knows to be faulty! however, the existence of such a scenario is not peculiar to our protocol. As shown in [5], relinquisliiiig control to a faulty backup is indeed necessary to achieve optimal protocols in some failure models. Another surprise is that in some protocols that adiieve optimal response time, the site that receives the request (i.e. the primary) is not the site that sends the respoiise to tlie clients. We show that this anomaly is not idiosyncratic to our protocols it is necessary for achieving optimal response time. * Supported by Defense Advanced Researdi Projects Agency (DoD) under NASA Ames grant number NAG 2--H593 and by grants from IBM and Siemens. Supported in part by the Office of Naval Research under contract Nooo14-91-J- 1219, the National Science Foundation under Grant No. CCR-8701103, DARPA/NSF Grant No. CCR-9014363, and by a grant from IBM Endicott Programming Laboratory. Supported in part by NSF grants CCR-8901780 and CCR-9102231 and by a grant from IBM Endicott Programming Laboratory. The rest of the paper is organized as follows. Section 2 gives a specification for primary-backup protocols, Sect. 3 discusses our system model, Sect. 4 summa- rizes the lower bounds from [5], and Sect. 5 summarizes our results. Sections 6, 7 and 8 describe the protocols that achieve our lower bounds, and Sect. 9 de- scribes a protocol in which the primary is forced to relinquish control to a faulty backup. We conclude in Sect. 10. Due to lack of space, the description of some of the protocols and all proofs are omitted from this paper. See [4] for a complete description and proofs. 2 Specification of Primary-Backup Services Our results apply to any protocol that satisfies the following four properties, and many primary-backup protocols in the literature (e.g. [1,2,3]) do satisfy this characterization. Pbi: There exists predicate Prmy3 on the state of each site s. At any time, there is at most one site s whose state satisfies Prm.y8. Pb2: Each client i maintains a site identity Des4 such that to make a requesl client i sends a message (only) to Des?? For the next property, we model a communications network by assuming tlint client requests are enqueued in a message queue of a site. Pb3: If a client request arrives at a site that is not the primary, then that request is not enqueued (arid is therefore not processed by tlie site). A request sent to a primary--Hbackup service can be lost if it is sent to a faulty primary. Periods during which requests are lost, however, are bounded by tlie tinie required for a backup to take over as tlie new primary. Such behavior is an instance of what we call bofo (bounded onlage finilety often). We say that an outage occurs at time t if some client makes a request at that tin?e biit does riot receive a response'. A (k, A)--bofo server is one for which all ontages call be grouped into at most k periods, ead? period having duration of at niost A.2 The fiiial property of the primary--Hbackup protocols is that they implen?ent a bofo server (for some values of k and A). Pb4: There exist fixed and bounded values k and A such that the service behaves like a single (k, A)--Hbofo server. Clearly, Pb4 can not be implemented if the number of failures is not bounded. In particular, if all sites fail, then no service can be provided and so the service is not (k, A) for any finite k and A. For simplicity, we assume in this paper that every request elicits a response. 2 Therefore, as well as being finite, the number of sach periods of service oiitages calt occur is also bounded (by k). 3 The Model Consider a system with iis sites and nc clients. Site clocks are assumed to be perfectly synchronized with real time3. Clients and sites communicate through a completely connected, point-to-point, FIFO network. Furthermore, if processes (clients or sites) pi and Pi are connected by a (nonfaulty) link, then we assume for some a priori known ?, a message sent by p? to p? at time t arrives at Pi at some time I' ii (t..t + 6]. We assume that all clients are non-faulty and consider the following types of site and link failures: crash failures (faulty sites may halt prematurely; until they halt, they behave correctly) 4, crash#linkfailures (faulty sites may crash or faulty links may lose messages), receive--Homission failures (faulty sites may crash or omit to receive some messages), send--Homission failnres (faulty sites may crash or omit to send some messages), general--Homission failures (faulty sites may fail by send-omission, receive-omission, or both). Note that link failures and the various types of omission failures are different only insofar as a message loss is attributed to a different component. Link failures are masked by adding redun- dant communication paths; omission failures are masked by adding redundant sites. As we will see, the lower bounds for the two cases are different Let f be tlie maximum number of components that can be faulty (i.e. f is the maximum number of faulty sites in the case of crash, send--Homission, receive omission and general--Homission failures, whereas f is the maximum number of faulty sites and links iii the case of craslidlink failures). 4 Lower Bounds In Tab. 1, we repeat the lower bounds from [5] for the degree of replication, the blocking time and the failover time for the various kinds of faibires. Informally, a protocol is C--Hblocking if in all failure--Hfree runs, the time that elapses from tlie moment a site receives a request until a site sends the associated response is bounded by C. Failover time is defined to be the longest duratioii (over all possible runs) for which there is no primary. however, the failover time bounds only hold for protocols that satisfy the following additional (and reasonable) property. PbS: A correct site that is the primary remains so until there is a failure. The protocols can be extended to the more realistic model in which clocks are only approximately synchronized [7]. ? The lower bounds are also tight for fail-stop failures [10] except for the bouiid on failover time. ? We assume that it takes no time for a site to compute the response to a request. Table 1. Lower Bounds?Degree of Replication, Blocking Time and Failover Time [MFiiliiretype???jReplicationJBlockingtime(C)FailoverTimell Crash fls > f 0 Crash+Link n > f + 1 0 2f? Send--HOmission fls > f ? if f = 1 2f6 2? if f > 1 Receive--HOmission 6 if n < 2f and f 1 5 Summary of Results We first present a primary-backup protocol schema that will be used to derive the protocols for all the failure models. This scherna is based on the propert??s of two key primitives, broadcast and deliver, that sites use to exchange messages. We show that the schema satisfies Pb1 Pb5 by only using these properties iride- pendent of the particular failure model. Ead? failure model crash, crashtlink. send--Homission, receive--Homission and general--Homission--H-is handled with a differ- ent implementation of broadcast and deliver, and in all but one case optimal protocols are constructed. The protocols for crash and crash+link failures show that all the correspond- ing lower bounds are tight. The protocol for general-omission failures uses a translation ted?nique similar to [8], and demonstrates that our lower bounds for general-omission failures are tight, except for the bound on blocking time when f 1. However, for this special case we have derived a different protocol (not described in this paper) having optimal blocking time . In all failure free runs of this protocol, the site that receives the request (i.e. the primary) is not tlie site that sends the response to the client. We show that this behavior is necessary in this paper. We do not show the protocols for send-omission and receive-omission fail- ures il-i this paper because they are similar to the protocol for general-omission failures. These protocols establish that the bounds for send-omission failurcs are tight. For receive-omission failures, the lower hound on blocking time when ?i > 2f and the lower bound on failover time are also tight. However, our pro- tocol does not have optimal replication, as it requires ?s > 2f (rather than ni>[4?2i). Finally, in [5] we proved that all receive-omission protocols having [??2J ? < 2f necessarily exhibit a scenario in which a non-faulty primary is forced to relinquish control to a faulty backup. In Sect. 9, we describe such a protocol; it uses two sites and tolerates a single receive-omission failure. In addition, this protocol is i-blocking and so it demonstrates that our lower bound on blocking time is tight for ?s < 2f and f 1. As in the protocol for general omission when f 1, it is the backup that sends responses to clients. This behavior is shown to be necessary for an important class of protocols. 6 Protocols for the Clients and the (k, A)--Hbofo server Property Pb4 requires that the primary--Hbackup service behave like some (k, A)--H bofo server. Figure 1 gives such a canonical (k, A)--Hbofo server (say s), and Fig. 2 gives the protocol for client i interacting with 5. As with any other bofo server, a client will not receive the response to a request if either the request to 5 or the response from 5 is lost. initialize() cobegin inform--Hchents('Dest = do forever wlien received request from dient c response := H(state,request) state = state a response send response to client c od coend procedure initinlize() state := e procedure inform clients(ic) send (ic) to all cheats Fig. 1. Protocol run by a single (k, A) bofo--Hserver 5 In Fig. 2, respons?--HIime corresponds to the amount of time the client has to wait in order to get the response from 5, which is just the round trip message delay. The exact value for response--Hiirne depends on the failure model being assumed. 7 The Primary--HBackup Protocol Schema We first make the simplying assumption that the links between the clients and the sites are non--Hfaulty and there are no omission failures between the clients and the sites (i.e. only the links between sites can be faulty for crash+link failures, cobegin do forever if received `?Dest = s" then Dest := s od do forever od coend if want to send request send request to Desti if riot received response by response--Htime then recover() /? call some recovery procedure, which might retry */ else Fig. 2. Protocol run by client i interacting with server 5 and omission failures can occur only between sites for omission failures). N\& show in Sect. 7.1 how this assumption can be removed. In order to emulate the server 5 (and consequently satisfy property Pb4) our primary--Hbackup protocol consists of n5 sites (si9??) ead? of which runs the protocol in Fig. 3. The protocol for the clients remains the same. initialize(i) cobegin if i = 0 then priinary(i) else backiip(i) delivery--Hprocess(i) I I failure--Hdetector(i) coend Fig. 3. Protocol run by site 5 to emulate server 5 The procedures prin?ary and backup (shown in Fig. 4) are the same for all the failure models. On the other hand, the implementation of the procedures ini- tialize, broadcast(used in Fig. 4), de1ivery?proccss and failure dctcctor d?ange depending on the particular failure model. However, we ensure that these different implementations always satisfy a set of properties, called Bi Bit b& low. `ve extracted these properties in order to make our proofs modular. In particular we proved that, independent of the failure model, the protocol in Figs. 3 and 4 satisfies Pbi--HPb5, as long as the remaining procedures satisfy Bi Bit. As a result, we could then prove Pbi--HPb5 for any other failure model by just ensuring that the implementation of broadcast delivery--Hprocess and failure--Hdetector for that failure model satisfied Bi--HBli. procedure primary(5) cobegin II inform--Hclients("Dest = 5>") II broadcast((mylastlog,s3,tast(statej)),j) /? to all sites ?/ do forever when received request from client c response := H(state3,request) state, := state1 0 response broadcast((log, 5, response),5) send response to client c od coend procedure backup(k) do forever ((tag,5>,r),5) := Deq(Rqnene&) assume that dequeueing an empty queue does not return any sensible value of tag */ /? synclironizing with the new primary */ iftag mylastlog then ifr ? state? then ifr = 1ast(state?) then skip else state? := state? \ 1ast(state?) else state? := state? 0 r /? logging response from primary */ iftag = log then state? :--H--H state? 0 r /? becoming the primary ?/ if V5 < k : i'autty?[sj] then primary(k) od Fig. 4. The procedures primary and backup We now give the properties Bi Bil. In these properties, dC and r are some constants whose values depend on the failure model. Intuitively, d corresponds to the amount of time that can elapse from the time a message is broadcast to the time it is dequeued by the receiver, C corresponds to the blocking time and T corresponds to the interval between successive "I am alive" messages that sites send to each other (as we will see in the implementation of failure--Hdetector). When we say that a site "halts", we mean that either the site has crashed or has stopped executing the protocol by executing a stop. The array of booleans Faulty? indicates whid? servers 5k believes has halted: Fauttv?kj] being true implies 5k believes that sj has halted. Finally, we define a hroadcast by a site to be sttcc?ssfu! if the site does not halt during the execution of broadcast. The properties can he subdivided according to the procedures to which they relate: Properties of broadcast and delivery--Hprocess: Bi: If Sj initiates a broadcast b' after broadcast 6 then 110 site (lequeues 6' before 6. B2: If Sj initiates a broadcast 6 at time t, then no site dequeues 6 after time t + d. B3: If Sj initiates a broadcast at time t and does not halt by time t + C, then the broadcast is successful. Furthermore, no broadcast takes longer than C to complete. Properties of failure--Hdetector: B4: If Fault???] becomes true, then it continues to be true, unless Sj halts 115: The value of Faulty? [5k1 can only d?ange at time t Ir + d for some integer I> 0. 116: If Faultyj[s?] true at tinm I then 5k has halted by time I. 117: If Sj has not halted by time t1, and 5j, ? ? j has halted by time t where ti 12 + T + d, then Fautty? [si] true by time Ii - Properties of broadcast and delivery--Hprocess interacting with failure--Hdc- tector: B8: No correct site halts in procedures initialize, broadcast, delivery--Hprocess or failure--Hdetector. B9: If Sj initiates a successful broadcast at time 1, then for all non--halted sites 5k, k > j, FaulIy?[sj] false through time [Tt]T + d. BlO: If s? initiates a successful broadcast 6, then for every non--Hhalted site 5?: (FaulIy?[sj] true) ? (5k has dequened 6). 1111: If s? initiates a broadcast 6 at time I and 8k, k > j broadcasts 6', then either no site dequcues 6 after 6', or J?aulty?[sj] false through time t + d. 7.1 Outliiie of the Proof of Correctness We now informally argue that the protocol in Figs. 3 and 4 satisfies Phi--HPbS as long as the procedures initialize, broadcast, delivery--Hprocess and laillire--H detector satisfy Bi?Bii. Define: Prmy?? at time I s? has not halted by time I A Vk < j : Faullyj[s?] true at time I. From the above definition, Phi can now be seen from B6 and the backup protocol in Fig. 4. Pb2 trivially follows from Fig. 2. Pb3 follows from Fig. 4 as no request is sent to a site 5? before Sj becomes the primary. Also, Pb5 holds (from B8 and Fig. 4) as a correct primary continues to be the primary. We now show Ph4. In order to show Pb4, we need to show two things--Hthe state of the new primary is consistent with the state of old primary; and all outages are hounded. We first show that the states are consistent. Starting at the top of Fig. 4: when a site S1 becomes the primary, it first informs the clients of its identity by calling inform--Hclients. For now, ignore the broadcast of (iiylastlog,s? ,--H) by primary Sj. Whenever sj gets a request from a client, it computes the response, d?anges state, broadcasts the log to the backups and sends tlie response back to the client. It can be seen from Fig. 4 that if primary Sj seiids a response r to tlie client, then sj must have executed a successful broadcast of (log, si, r). This fact and properties Bt,132,B9 and BlO imply that (log, Sj, r) must also have been dequeued by any backup 5k before 8k becomes the primary. Thus, the state of 5k will continue to be consistent with the state of Sj iff the states were consistent when Sj became the primary. We show this as follows. Iiiformally, the states of sj and 5k could be inconsistent when sj becomes the primary for tlie following reason. Consider a scenario in which some primary Sj crashes during the broadcast of (log,si, r) for some r It is possible that 5k received (log, 5j, r) and Sj did not. As a result, tlie states of Sj aiid 5k now differ. It is for this reason that Sj broadcasts (mylastlog, Sj, r') where r' Iasl(stat?-) oli becoming the primary. On receiving this, 8k 5??5 that r' ? Iast(state?) --H r and removes r from its state. As a result, stat%- and state? become equal. r ?, not 5k, received (log, Sj, Similarly, 8k would add to its state had s and In the scenario described in the last paragraph, response r is never sent to the client (i.e. there is a service outage). We now show that such outages are bounded. Sj did not send tlie respolise, and so by B3, must have halted by time I (say). Now from B7 either Sj+1 halts or becomes the primary by time I + T + 6. Since no correct site halts (by B8 and Fig 4), and the number of faulty sites are bounded by f, there eventually will be a time when there is a correct primary and no more outages occur From f33, the protocol C--Hblocking. Furthermore, it can be shown from B7, B8 and Fig. 4 that the failover tinie of the protocol is f(d + r) for arbitrarily small and positive T. however, the primary procedure iii Fig. 4 does not work if there are message losses between the clients and the sites (due to link or omission failures). For example, a non--Hfaulty primary might omit to receive all requests from a client due to a failure, violating Pb4. Similarly, inform--Hclients might omit to inform some of the clients. Ilowever, it is relatively easy to account for these failures when clients are non-faulty. Assume that there is an upper bound (say C) be- tween any two requests from a client and that requests carry sequence numbers. If the primary does not receive any requests from a clieiit during an interval of length G or if tlie primary receives some request with a sequence number gap, then the primary halts. Similarly, the primary can detect that a response was lost by having clients acknowledge responses. If such an acknowledgement is not received, then again the primary halts. Properties Pbt--HPb5 can again be shown to be true if we make the above modification in Figs. 2 and 4. 8 Implementation for the various Failure Models In this section, we show how to implement Bi Bil for the various failure mod- els. 8.1 Crash Failures The procedures implementing Bi Bil for crash failures are given in Fig. 5. Whenever we say that a site "delivered Al", we mean that the procedure deliver has been called with Al. Enq adds an element to the bead of a queue and Deq dequeues an element from the tail. procedure initialize(k) state? Rqneue? Vi Fautty?[s?] fatse procedure broadcast(Al, k) send Al to all sites procedure deliver (Al, k) Let Al be of the form (tag, --H, --H) if tag E (log, mylastlog) then Enq(Rqneue?, (Al, k)) procedure delivery?process( k) do forever if received Al then deliver(Al, k) od procedure failure--Hdetector(k) cobegi n for i (J to Co when cunent?tirne = ir: send (alive, 3k, ir) to all sites for i :0 to Co when corrent?tirne = ir + d: Vj : if not delivered (alive, 3>, ir) then Fantty?[s3] := true coend Fig. 5. Procedures for crash failures We now informally argue that Bi--HBil hold for this implementation if d 6 and C 0. B1 holds as channels are FIFO and, B2 holds as d = 6 and the maximum message delivery time is also 6. B3, B4 and B5 can be seen trivially. B6 and B7 can be seen from failure--Hdetector as there are no message losses and message delivery time is atmost 6. B8 holds trivially. It can be shown that if Sj halts at time i, then no site sets Faulty[sj] to true before tin? t + 6. 139, BlO and Bil now follow. The procedures in Fig. 5 require `1s > f, and so the lower bound on the degree of replication is tight. Since C = 0 and d --H 6 from Sect. 7.1, the lower bounds on blocking time and failover time arc tight as well. 8.2 Crash+Link Failures The procedures in Sect. 8.1 do not work if links can fail. For example, if s? sends a message to sk then the message might not reach Sk due to a link failure (whid? will violate B6 and 1310). We therefore replace the implementation in Fig. 5. with the one in Fig. 6, except that deliver is the same as before. For this implementation d --H 26 and C = 0. These procedures use fifo--Hbroadeast and fifo--Hdeliver in Fig. 7 which ensure that intermittent link failures become permanent failures: if Sj fifo--Hbroadcasts a message m to 8k and Sk omits to fifo--Hdeliver m, then sk will not fifo?deliver any subsequent message from Sj. It can be shown (proof omitted) that this new implementation again satisfies 131--H1311 if ?s > f + 1. Informally, this is true because of the following reason. Whenever s? initiates a broadcast of M at time t, it sends A/I to all sites, and the sites then relay A/I to all other sites. Since ?s > f + 1, there is always at least one non-faulty path between any two non-crashed sites, where a path consists of zero or one intermediate sites. Therefore, if Sj does not crash during the broadcast, then all non-crashed sites will deliver AJ by time I + 26. Furthermore 131 will be satisfied because of the FIFO properties of flfo--Hbroadcast and flfo?deliver. This crash+link protocol requires ?s > f + 1, is 0--Hblocking (since C = 0), and has a failover time of f(26 + ?) (since d = 26). Thus, all lower hounds for crash+link failures are tight. 8.3 Geueral--HOn?issiou Failures The implementation of the procedures for general-omission failures is given in Figs. 8 and 9, except delivery--Hprocess which is the same as Fig. 6. Whenever, we say that a site "fifo--Hdelivered Al", we mean that the procedure fifo--Hdeliver was called with M. These procedures were developed using a technique similar to [8] (although modified to work in our non-round-based model) which requires ?s > 2f and d = 26. procedure initialize(k) state? := Rqueue? Dqnene? := c Vi FanUy?[si] := fatse tast-sentk Vi :expected?[5] 0 procedure broadcast(M, k) time :=current?time fifo-broadcast(init, M, Sk, time) procedure delivery-process( k) cobegin II fifo-delivery-proccss(k) do forever (tag, Al, --H? t) :=Deq(Dqaene?) if tag = init then fifebroadcast (echo, Al, Sk, if tag = echo and not dequeued (tag, M, --H, t) before then deliver (Al, k) od coend procedure failiire--Hdetector(k) A3 = (alive, s,, ir) cobegin for i := 0 to co when current--Htime ir: flfo-broadcast( init, Ak, sk, ir) for i =0 to no when current--Htime = ir + d: Vj : if not delivered A3 then Fanttgk[33] := ?rfle coend Fig. 6. Procedures for crasll+liuk failures procedure fifo-hroadcast(tag, Al, sk, send (tag, Al, sk, t,Th?t-sent?) to all tost-sentk :=tost?sent? + 1 procedure fifo-deliver (tag, Al, S3,t) Enq(Dqnene?, (tag, Al, s,, procedure fifi?-delivery--Hprocess (k) do forever if received (tag, Al, 33, t, last3) then if (last3 #expected?[i]) then skip else expected?[j] := erpected?[5] + 1 fifo-deliver (tag, Al, s3,t) od Fig. 7. Procedures for crash+link failures procedure initialize(k) state? Rqnei'e? Dquei'e? :--H--H e Vi : Fau1ty?[si] false currant--Hpnmarw=last?sant? Vi :axpected?[j] 0 procedure broadcast(M, k) time current--Htime fifo-broadcast(init, M, 3k, time) if by time + I fifo--Hdelivered (echo, Al, s? time) for at least n --H f different j then return else stop procedure deliver (Al, k) Let Al be of the form (tag, 5,,--H) if tag ? llog,iiylastlog) then if j 2f, I 26 and C 26. Furthermore, we have developed a protocol for f 1 (omitted in this paper) that is 6--Hblocking. Thus, we establish tbat all lower bounds for general-omission failures are tight. As mentioned earlier, the 6--Hblocking protocol for f 1 has scenarios in which the site that receives the request is not the site that responds to the clients. This is in fact necessary. Define a protocol to be ?pass the buck" if in any failure--Hfree run of the protocol, the site that receives a request is not the site that sends the corresponding response. procedure failure-detector(k) Vi,i : A? := (alive,s3,ir) Vi,j : := (fault,sj,ir) cobegin I for i := 0 to no when current-time = ir: fifo-broadcast(init, Ak, 3k, ir) for i := 0 to no when current-time = ir + ?: Vj if not fifo--Hdelivered (init,A?,s3,ir) then fifo-broadcast (echo, Fj, sk, ir) for i =0 to no when current-time = ir + d: witness? [k] := (s, Ififo--Hdelivered (echo, Ak', 5,, ir)) V5 ? k : witness?[j] := (s?jfifo--Hddivered (echo, A;, Sj, ir) or fifo--Hdelivered (echo, Fj, 5?, ir)) if a5 Iwitness?[5]I < fl --H f then stop if ?j : not delivered A; then Fautty?[sj] := true coend Fig. 9. Procedures for general--Homission failures Theorem 1. Any C--Hblocking protocol, where 0 < 26, for send--Homission failures is `)pass Ilie buck" Proof Omitted iii this paper. See [4]. L] 8.4 Other Failure Models The implementations of the procedures for send-omission and receive-omission failures are similar to those for general-omission failures and so are omitted from this paper. For receiv&omission failures, the lower bound on the degree of replication and the lower bound on blocking time when ns ? 2f and f > 1 are not tight. Finding optimal protocols remains an open problem. however, tlie lower bound on failover time for receive-omission failures, and all lower bounds for send-omission failures are tight. 9 A Surprising Protocol ?Ve now describe a 6--Hblocking protocol tolerating receive-omission failures for the special case of n5 --H 2 and f = 1. This protocol is complex, and so we omit the detailed description and only outline the protocol's operation here. This protocol shows that our lower hound on blocking time when n? < 2f and f 1 is tight. The protocol has the odd (yet necessary as shown in [5]) property that a non-faulty primary is forced to relinquish to a faulty backup. Furthermore, the protocol is `?pass the buck". ?Ve, however, show that most 6--Hblocking protocols tolerating receive omission failures Iiave to be `?pass the buck" Informally, let P be the maximum time between any two successive client requests (possibly from different clients), and let D be such that if some site 5 becomes the primary at time to and remains the primary through time t > to + D when a client i sends a request, then Dest? 5 at time t. We write D < P to mean that D is bounded and F is either unbounded or bounded and greater than D. Then Theorem2. Ana C--Hllocking protocol, where C' < 26, for receive-omission fail- ares with ?s < 2f and D < P is "pass the back". Proof Omitted from this paper. Li Whether a protocol has to be pass the buck" when the relation D ? F does not hold is an open question. We now describe the protocol. There are two sites 5o and si. They commu- iiicate with each other using fifo--Hbroadgast and fifo--Hdeliver shown in Fig. 7. Henceforth, when we say that a site sends a message to the other, we will mean that the message is sent with fifo-broadeast and other site receives it with fifo-deliver. In a failure-free run of this protocol, since the backup responds to the client, the primary forwards any response to the backup (with a green tag as we see below) and the backup sends this response to the client. However, if there is a failure, then the primary responds to the clients. In this case, the primary forwards a response to the backup with a red tag. The backup does not forward a response to the dient if the response lias a red tag. Let ?o initially be the primary. Whenever ?o receives a request from the client, it computes a response r, changes state, and sends (green,r) to si Upon receiviiig this message, si updates its state, acknowledges to ?o, and then sends r to the client. Because it is the backup that responds to the client, the protocol is 6--Hblocking. Site ?o processes a iiew request only after receiving the acknowl- edgement from si for the previous request. Finally, ?o periodically sends alive n?essages to si, and si acknowledges these messages. Suppose that ?o does not get si `s acknowledgement for some message, say, (green,r) (the argument is similar if no acknowledgement is received for an alive message). There are three possibilities: (1) si has crashed, (2) si omitted to receive (green,r) and so did riot send the acknowledgement, (3) ?o omitted to receive the acknowledgement. ?o now waits until it is supposed to send the next alive message. ?o sends this alive message and waits for an acknowledgement We now consider the above three cases separately. Case 1: si has crashed. As a result, ?o does not receive the acknowledgement to the alive message. ?o continues as the primary. From then on, whenever ?o receives a request from the client, it computes the response r, sends (red,r) to ?i, and then sends the response back to the client. Also, ?o continues to send alive messages. Since ?o is correct, it can continue like this forever. Case 2: si is faulty and omitted to receive (green,r). By the property of fifo--H broadcast and fifo--Hdeliver, si will not receive the alive messages that ?o sends. si concludes that ?o has crashed, sends ("5i is primary") to ?o and becomes the primary. After that, it behaves like ?o in case 1 above (including sending alive messages to so). Since 5o is correct, it receives ("5i is primary") (as opposed to case 1) and so it becomes the backup. Also, since ?o is correct it will not omit to receive (red,r') messages that si sends and 50 ?o keeps its state consistent with 5j. Subsequently, ifs0 stops receiving alive messages from si, then si has crashed and 5o becomes the primary once again. Case 3: ?o is faulty. Since 5i is correct, it receives the alive message from ?o, sends the corresponding acknowledgement arid remains the backup (as opposed to case 2). However, by the property of fifo--Hbroadcast and fifo--Hreceive, 5? will not receive this acknowledge to the alive message (or the ("si is primary") message), and so it behaves as in case 1 and continues as the primary. Similar to case 2, s? receives all (red,r) messages that so sends and so its state is consistent with ?o Finally, si becomes the primary if it stops receiving alive messages from ?o Case 2 in the protocol is the odd scenario in which the correct primary ?o is being forced to relinquish to si, known to be faulty. However, this scenario Is not something peculiar to our protocol. ?Ve showed in [5] that relinquishing to a faulty backup is necessary when ns < 2f. 10 Discussion lii [5], we present lower bounds for primary--Hbackup protocols which constrain the degree of replication, tlie failover time, and the amount of time it can take to respond to a client request. In this paper, we derive matd?ing protocols and show that all except two of these lower bounds are tight. Furthermore, we show that in soine cases the optimal response time can only be obtained if tlie site that receives the request is riot site that sends the response to the clients. N\?e have atteinpted to give a characterization of primary-backup that is broad enough to include most synd?ronous protocols that are considered to be instances of the approach. There are protocols, however, that are incomparable to the class of protocols we analyze as these protocols were developed for an asynclironous system [6,9]. ?Ve are currently studying possible characterizations for a primary- backup protocol iii an asynclironous system and expect to extend our resolts to this setting. References 1. 2. PA. Alsberg and J.D. Day. A principle for resilient sharing of distributed resoorces. In Proceedings of the Second Internationai Conference on Software Engineering, pages 627--H644, October 1976. J.F. Barlett. A nonstop kernel. In Proceedings of the Eighth ACM Symposium on Operating System Principles, SIGOPS Operating System Reeiew, volume 15, pages 22--H29, December 1981. 3. 4. 5. 6. 7. 8. 9. 10. Anupam Bhide, E.N. Elnozahy, and Stephen P. Morgan. A highly available net- work file server. In USENIX, pages 199--H205, 1991. Navin Budhiraia, Keith Marzullo, Fred B. Schneider, and Sam Toneg. Optimal primary--Hbackup protocols. Technical report, Cornell University, Ithaca, N.Y., 1992. In preparation. Navin Budhiraja, Keith Marzullo, Fred B. Schneider, and Sam Toueg. Primary--H backup protocols: Lower bounds and optimal implementations. In Proceedings of the Third IFIP Working Conference on Dependable Computing for Critical Appli- cations, 1992. To Appear. Timothy Mann, Andy Hisgen, and Garret Swart. An algorithm for data replication. Tedinical Report 46, Digital Systems Research Center, 1989. CII Neiger and Sam Toueg. Substituting for real time and common knowledge in asynchronous distributed systems. In Sirth ACM Symposium on Principles of Distributed Computing, pages 281--H293, Vancu'iver, Canada, August 1987. ACM SIGOPS-SIGACT. Gil Neiger and Sam Toneg. Automatically increasing the fault-tolerance of dis- tributed systems. In Proceedings of the Seventh ACAl Symposium on Principles of Distributed Computing, pages 248--H262, Toronto, Ontario, August 1988. ACM SIGOPS-SIGACT. B. Oki and Barbara Liskov. Viewstamped replication: A new primary copy method to support highly available distributed systems. In Seventh ACM Symposium on Principles of Distributed Computing, pages 8--H17, Toronto, Ontario, August 1988. ACM SIGOPS-SIGACT. Richard D. Sclllicliting and Fred B. Schneider. Fail-stop processors: an approach to designing fault-tolerant computing systems. ACAL Transactions on Computer Systems, l(3):222--H238, August 1983.