11Fault-Tolerant Systems11.1. What is a Fault ?Any action that does not conform to the given specification of a system is viewed as a fault. Historically, models of failures have been linked with the users level of interaction with a system. A VLSI designer may focus on stuck-at-0 and stuck-at-1 faults only, where the output of a gate is permanently stuck to either a 0 or a 1 regardless of input variations. A system level hardware designer, on the other hand, may be ready to view a failure as any arbitrary or erroneous behavior of a module as a whole. A drop in the power supply voltage, or radio interferences due to a lightning, or a cosmic shower, often causes transient failures that may temporarily perturb the system state without causing any permanent damage to the system. Finally, even if hardware does not fail, software may fail due to improper or unexpected changes in the specifications of the system. Before any discussion about how to tolerate such faults, it is important to present a proper characterization of the various kinds of faults that can occur in a system.11.2. Classification of FaultsOur view of a distributed system is essentially a process-level view, so we begin with the description of some important types of failures that are visible at the process level. Note that each type of failure at any level may be caused by a failure at some lower level of abstraction. Thus, a process may cease to produce an output when a wire in the circuit breaks. A complete characterization of the relationship between faults at different levels is beyond the scope of our discussion. Our classification of failures is as follows:Halting Failure. When a process that is expected to produce one or more messages, or change the values of some process variables, ceases to do so on a permanent basis, a halting failure occurs. Note that this is an irreversible change. Halting failures are also known as crash failures.In a variation of this model, halting failures are treated as reversible, i.e. a process may play dead for a finite period of time, and then resume operation. This includes thecase in which the faulty process is repaired and restarted after some time. Such failures are called napping failuresByzantine Failure. Byzantine failures correspond to completely arbitrary failure patterns, and is the weakest of all the failure models. As an example, let N.i denote the set of neighbors of a process i. Assume that i is expected to send a value x to every process in N.i. If process i does not send the intended value x to each of its neighbors, then the failure is called a byzantine failure. The following are some examples of inconsistent behaviors possibly caused by byzantine failure:¥ Two distinct neighbors j and k receive values x and y, where x ≠ y.¥ Every neighbor receives a value z where z ≠ x.¥ One or more neighbors do not receive any value from process i.Some of the possible causes of byzantine failures are¥ The total or partial breakdown of a link joining i with one of its neighbors ¥ Software problems in process i¥ Hardware synchronization problems - assume that every neighbor is connected to the same bus, and trying to read the same copy sent out by i, but since the clocksare not synchronized, they may not read the value x exactly at the same time. If x is a time-sensitive variable, then different neighbors of i may receive differentvalues from process i.¥ Malicious action by process i.Transient Failure. Certain types of fault actions have temporary effects on the global state of a system. Such failures perturb the global state in an arbitrary way, but the effect of the agent inducing this failure is not perceived thereafter. This is called a transient failure.A special kind of transient failure applicable to message-passing models only is the omission failure. Consider a transmitter process sending a sequence of messages to a receiver process. If the receiver does not receive some of the messages sent by the transmitter, then it is an omission failure. In real life, this can be caused either by transmitter malfunction, or by the loss of messages in transit.Software Failure. Software does not fade or erode with time. Assume that a system running under the control of a program S is producing intended results. If the system suddenly fails to do so even if there is no hardware failure, there is a problem withspecifications. If {P}S{Q} is a triple in programming logic, and the precondition P is inadvertently weakened, then there is no guarantee that the postcondition Q will always hold!The situation can be explained using the example of a pop machine. This pop machine delivers a can of pop, when a user inserts 50cents into the machine. The machine is designed to accept quarters and dimes only. If an uninformed user tries to buy a can of pop with ten nickels, then the machine will fail to deliver the pop, since the machine is not designed to accept nickels! This malfunction may be viewed as a software failure.Temporal Failure. Real time systems require actions to be completed within a specific amount of time. When this deadline is not met, a temporal failure occurs.11.3. Specification of FaultsWe present here a general model for specifying an arbitrary type of failure. This model was proposed by Arora and Gouda in [AG93]. A system description consists of (i) a set of specified actions S representing the fault-free system, and (ii) a set of fault actions F. The actions of F can be expressed using notations similar to those used in S.The faulty system consists of the union of all the actions in both S and F, and will be denoted by S F. An example of such a specification follows.Assume that a system, in absence of any fault, sends out the message "a" infinitely often (i.e. the output is an infinite sequence aaaaa...). However, a failure "occasionally" causes a message to change from "a" to "b". This description can be translated to the following specification1 :define x : booleana , b: messageinitially x = true;S::do x → send a odF::do true → send b odWith a weakly fair scheduler, the difference between the behaviors of S and S F becomes perceptible to the outside world.1 This specification is not unique. Many other specifications are possible.A halting failure of S can be represented using the following specification for F:F :: do true →x := false odAfter this fault action is executed, the system ceases to produce an output -- a condition that cannot be reversed using the actions in S or F.Now, consider a system that receives a message msg, and forwards it to each of its N neighbors {0, 1, 2, ..., N-1}. This can be specified byS::initially j = 0, flag = falsedo¬flag ∧ msg = a→x := a; flag := true(j < N) ∧ flag→send x to j; j := j+1j = N→j := 0; flag := falseodThe following fault action on the above system specifies a form of byzantine failure, since it can cause the process to send a to some neighbors, and send b to some others.F::do flag→x := b od{b ≠ a}Under the broad class of byzantine failures, specific fault behaviors can be modeled using appropriate specifications. Consider the following example. Here, the fault-free system executes a non-terminating program that sends out the integer sequence 0,1,2,0,1,2 .... Once the fault actions are executed, the faulty system changes every third integer from 2 to 9.define k : integer; {k is the body of a message}x : boolean;initially k = 0; x = true;S::do k < 2 →send k; k := k+1x ∧ (k = 2)→send k; k := k+1k ≥ 3 →k := 0;odF::do x→¬ x¬ x ∧ (k = 2) →send 9; k:= k+1odNo separate specification is necessary for software failures -- it is adequate to explicitly write down the preconditions and the postconditions of the fault-free system, and observe that these hold for the application at hand.Finally, temporal failures are detected using a special predicate "timeout", which becomes true when an event does not take place within a predefined deadline. An example is given below: Consider a process i broadcasting a message every 60 seconds to all of its neighbors. Assume that the message propagation delay is negligibly small. If process j does not receive any message from process i within 62 seconds (i.e., it keeps a small allowance before passing a verdict), it permanently sets a boolean flag f.i. indicating that process i has undergone a termporal failure. This can be specified asdefine f.i: booleaninitially f.i = falseS::¬ f.i ∧ message received from process i → skipF::timeout (i,j)→ f.i := trueHere, the truth of the predicate timeout (i,j) implies that the deadline has elapsed on the arrival of the message from j to i. It is quite possible that process i did not undergo a halting failure, but slowed down due to unknown reasons. The exact mechanism for asserting the predicate timeout (i,j) is as follows: Process j has a local variable called timer that is initialized to the value of the deadline T. After this, timer is decremented with every tick of the local clock. If (timer = 0), then the predicate timeout is asserted, otherwise, after the event occurs, timer is reset to T and the next countdown begins.Note that the correct use of timeout is based on the existence of synchronized clocks. If the local clocks of the processes i and j are not synchronized (at least approximately), then they can drift arbitrarily -- as a result, there will no correlation between i's measure of 60 seconds and j's measure of 70 seconds. In an extreme case, j's 62 seconds can be less than i's 60 seconds, so that even if process i sends a message every 60 seconds, process j will timeout and set f.i.11.4. Fault-Tolerant SystemsThe first step in designing a fault-tolerant system is to understand what is meant by tolerating a fault. There are three different concepts in the area of fault-tolerance:¥ Fault Masking¥ Fault Recovery¥ Graceful DegradationFault MaskingIn this case, the occurrence of faults does not have any visible effect in the eyes of an external observer. Let {P}S{Q} be a computation, and F represent the fault-actions.Then the system masks the actions of F iff wp(S F , Q) = P', and P ⇒ P'.Fault RecoveryEvery fault-tolerant system cannot mask failures. In such a cse, the faulty behavior will be visible in the eyes of an external observer. An important issue in such cases is the duration of the fault actions and the faulty behavior. Let S be a computation that satisfies the triple {P}S{Q}, and F denote the fault actions. Also, let R be a predicate representing the "weakest postcondition" in presence of failures. This implies {P}S F {R}, and intuitively R is the "worst-case result" produced by the faulty system. If R ⊆ Q , then the system is able to mask the actions of F . Otherwise, the fault is not of the masking type. However, if the failure is transient and the actions of F are no longer enabled following the corruption of the global state, then in some cases the system eventually recovers, and satisfies the postcondition Q . This is possible when R ⇒wp(S,Q). Fig. 11.1. illustrates the situation.timecompleteshere completeshereFig. 11.1. An illustration of fault recoverySystems that (i) guarantee recovery when started from an arbitrary initial state (i.e. P = true) and (ii) maintain the desired postcondition, are known as self-stabilizing systems.Graceful DegradationMany systems can neither mask, nor fully recover from the effect of failures. However, some of them exhibit a degraded behavior that falls short of the normal behavior, but is still "acceptable." The notion of acceptability is highly subjective, and is entirely dependent on the user running the application. Some examples of degraded behavior are as follows:1. Consider a taxi booth where customers call to order a taxi. Under normal conditions,(i) each customer ordering a taxi must eventually get it, and (ii) these requests must be serviced in the order in which they are received at the booth. In case of a failure, a degraded behavior which may be acceptable corresponds to the case when only condition(i) is satisfied.2. While routing a message between two points in a network, a program computes the shortest path. In the presence of a failure, if this program returns another path which is not the shortest path but one that is "marginally longer" than the shortest one, then this may be considered acceptable.3. A pop machine returns a can of soda when a customer inserts 50cents in quarters, dimes, or nickels. After a failure, if the machine refuses to accept dimes and nickels, but returns a can of soda only if the customer deposits two quarters, then it may be considered acceptable.Detection of FailuresThe implementation of fault-tolerance of any type requires a mechanism for detecting failures. This in turn depends on specific assumptions about the degree of synchronization like the existence of synchronized clocks, lower bound on the processor speed, or upper bound on message propagation delays, as described in Section 2.1.3. The transition from a fully synchronous to a fully asynchronous system is a gradual one, and it is possible to deal with a system that is only partially synchronous. The implementation of fault-tolerance depends on the degree of synchronization.As the first example, let us consider whether a halting failure can be detected in a message passing system. Without any assumption about synchronized clocks, or an upper bound of message propagation delays, or a lower bound of process execution speeds, it is impossible to detect a halting failure, because it is not feasible to distinguish between a crashed process, and a healthy process which is executing actions "very slowly." However, in a fully synchronous system, timeout can be used to detect halting failures.As another example, consider how omission failures can be detected. The problem is as hard as the detection of halting failures, unless the channels are FIFO. With a FIFO channel, a sender process i can attach a sequence number seq with every message m as described below:do true →send <seq, m>;seq := seq + 1odWhenever a receiver process j receives two consecutive messages whose sequence numbers are m and n, and n ≠ m+1, it suspects an omission failure.The detection of byzantine failures also requires a fully synchronous system. Several protocols for masking inconsistencies caused by byzantine failures are available in the published literature -- these are known as byzantine agreement protocols.In the following sections, we will present specific examples of implementing fault-tolerance with halting and omission failures. Byzantine agreement and self-stabilizing systems will be presented in subsequent chapters.11.5. Halting FailuresNext we present examples of two widely used methods for masking the effect of halting failures.Triple Modular redundancyIn synchronous systems, a widely used method of masking the effects of halting failures is the use of triple modular redundancy. Consider a process B that receives an input value x from a process A, computes the function y = f(x), and sends it to a third process C. If B fails by stopping, then C does not receive any value of y.Fig 11.2. Implementing fault-tolerance using Triple Modular RedundancyTo mask the effect of B's failure, process B is replaced by three processes B0, B1, and B2 as shown in Fig. 10.1. Even if one of these three processes undergoes a halting failure, process C still receives the correct value of f(x), as long as it computes the majority of the three incoming values. Note that when the majority is computed, the output of the faulty process can be substituted by an arbitrary default value. A generalization of this approach leads to n-modular redundancy that helps mask the halting failure of m or fewer processes, where n ≥ 2m+1.Atomic transactionsIn a distributed database system, let A be a composite object with components A.0, A.1, ..., A.n. Consider a transaction that assigns a new value x.i to each component A.i. We will represent this operation by A := x. The transaction A := x is called atomic, when "either all or none" of the assignments A.i := x.i are completed. Note that a halting failure can allow a fraction of these assignments to be completed, and violate the atomicity property.To make such a transaction look atomic in the face of crash failures, Lampson proposed the idea of stable storage. A stable storage maintains two copies of A (i.e two copies of every component A.i), and allows two operations update and inspect to access the components. Let us designate the two copies of A by A0 and A1 (Fig 11.3). Process P, which performs the update operation, updates each copy, stamps these updates with (i) the timestamp T, and (ii) a unique signature S called checksum, which is a function of x and T.Fig. 11.3 The model of a stable storage. P performs the update operationand Q performs the inspect operation{procedure update}1A0 := x;{copy 0 updated -- operation not necessarily atomic} 2T0 := time;{timestamp assigned to copy 0}3S0 := checksum (x, T0){signature assigned to copy 0}4A1 := x;{copy 1 updated -- operation not necessarily atomic} 5T1 := time;{timestamp assigned to copy 1}6S1 := checksum (x, T1){signature assigned to copy 1}Process Q, which performs the inspect operation, checks for both the copies, and based on the times of updates as well as the values of the checksums, chooses the correct version of A that satisfies the criterion of atomic update.{procedure inspect}A if S0 = checksum (A0, T0) ∧S1 = checksum (A1, T1) ∧T0 > T1→accept A0B S0 = checksum (A0, T0) ∧S1 = checksum (A1, T1) ∧T0 < T1→accept A0 or A1C S0 = checksum (A0, T0) ∧S1 ≠ checksum (A1, T1) →accept A0D S0 ≠ checksum (A0, T0) ∧S1 = checksum (A1, T1) →accept A1f iCase A corresponds to a failure between steps 3 and 4 of an update. Case B represents no failure -- so any one of the copies is acceptable. Case C indicates a failure between steps 1-3, and case D indicates a failure between steps 4-6. It is important to note that as long as A0 and A1 are properly initialized, and P fails by stopping at any point during steps 1-6 of the update operation, one of the guards A-D must be true for process Q.Stable storage is widely used in client-server models to survive crashes. The two copies A0 and A1 are maintained on two disks on two separate drives. Data can also be recovered when instead of a halting failure by process P, one of the two disks crashes.11.6 Omission FailuresOmission failures are usually caused by transient malfunctions of the channel. In the OSI model of a computer network, omission failures are typically handled either in the data-link layer or in the transport layer. The principle behind handling omission failures is to detect the disappearance of an expected message or an acknowledgement (using sequence numbers and timeouts), and then arrange for a retransmission. Due to the transient nature of this failure, it is assumed that if a message is sent "a large number of times", then it will eventually be received.A widely used transport layer protocol for handling omission failures is the sliding window protocol. This protocol works on a channel where message propagation delays have upper bounds. In the sliding window protocol, there are two processes, a sender process S and a receiver process R, connected by a pair of channels as shown in Fig.11.4. The channel is not a FIFO channel. Process S sends out a sequence of messages m[0], m[1], m[2], ...from an infinite tape, and process R, after receiving each message m[i], decides whether to accept it and forward it to the upper layers of protocol, and then sends an acknowledgement back to S. Both messages and acknowledgements may occasionally be lost or delayed, that is determined by timeouts and retransmissions. The goal of the sliding window protocol is to satisfy the following three crieria:W1.Every message sent out by S should eventually be received by R.W2. No message should be accepted and forwarded to the upper protocol layers more than once.W3. The receiving process R should always forward messages m[i] before m[i+1].Thus, if S sends out the sequence a b c d e ..., then from the persprective of process R, W1 rules out accepting this sequence as a c d e ..., W2 rules out the possibility of accepting it as a b b c c c d e ..., and W3 prevents it from being accepted as a c b d e ....An obvious solution is the so called stop-and-wait protocol. Process S will send one message m[i], and wait for its acknowledgement from R. If the message or the acknowledgement is lost, then m[i]is retransmitted. Otherwise, the next message m[i+1] is sent by S.Fig 11.4. Sliding window protocolThe approach is logically correct, but this restricted version suffers from poor throughput in as much as the sender has to wait for at least two round-trip delays before transmitting a new message. An obvious generalization is the sliding window protocol, that is based on the following scheme:¥The sender is allowed to continue the send action without receiving the acknowledgements of at most w messages (w > 0), where w is called thewindow size". If no acknowledgement to the previous w messages is receivedwithin an expected period of time, then the sender resends those w messages.¥ The receiver anticipates the sequence number j of the next incoming message. If the anticipated message is received, then R accepts it, sends the correspondingacknowledgement back to S, and increments j. Otherwise, R sends out anacknowledgement corresponding to the sequence number j-1 of the previousmessage accepted by it.It is important to note that both the messages and the acknowledgements have to include the sequence number which is an integral part of the decision making process. Thus the i th message will be sent out by S as (m[i], i), and the corresponding acknowledgement will be returned by R as (ack, i). The program is described below.program window;{program for process S}define next, last, w : integer;initially next = 0, last = -1, w > 0;and both channels are emptydo last < next ≤ last + w→send (m[next], next);next := next + 1(ack, j) is received→if j > last→ last := jj ≤ last→ skipf itimeout (r,s)→∀i: last < i ≤ last + w :: send (m[i]. i)od{program for process R}define j : integer;initially j = 0;do(m[next], next) is received→if j = next→accept the message;send (ack, j);j:= j+1j ≠ next→send (ack, j-1)fi;odTo demonstrate that this protocol satisfies the three criteria W1 - W3, we outline an inductive proof.Basis. Message m[0] is eventually accepted by R. To show this, note that if m[0]is lost in transit, then either the guard (j ≠next)is enabled for R, or no acknowledgement is returned, and (last = -1)holds. Messages are sent by S until (next = w-1), and the acknowledgements returned (if any) by R have no impact on the state of S. After this, the guard timeout is enabled for process S, and it sends m.0 through m[w-1] for a second round. In a finite number of rounds of retransmission, m.0 must reach R, the guard (j=next) is enabled, and m[0] is accepted. Furthermore, since j can only increase after a message is accepted, the condition (j = 0) cannot be asserted for a second time. So, m.0 is accepted exactly once.Inductive Step. Assume that R has accepted every message from m[0]through m[k] (k > 0), j = k+1, m[k+1] has already been transmitted by S, so the condition last < k+1 ≤ next holds. We need to show that eventually m[k+1] is accepted by R.If m[k+1] is lost in transit, then no guard is enabled for R. When the remaining messages in the current window are sent out by S, the acknowledgements (ack, k) returned by R do not cause S to increment the value of last beyond k.Eventually the guard timeout is enabled for process S, and it retransmits messages m[last+1] through m[last + w] -- this includes m[k+1]. In a finite number of rounds of retransmission, m[k+1] is received and accepted by R.Finally, for process R, the value of j never decreases. Therefore m[i] is always accepted before m[i+1]The Alternating Bit ProtocolThe alternating bit protocol is a special version of the sliding window protocol, for which w=1.A major hurdle in implementing the sliding window protocol described earlier is that, an arbitrarily large sequence number must accompany the body of the message. Accordingly, neither messages nor acknowledgements can be represented in bounded space. The alternating bit protocol avoids this problem by appending only a 1-bit sequence number to the body of the message. However, the scheme works only when the channels are FIFO. Accordingly, the alternating bit protocol is suitable for application in the data-link layer. The protocol is described below:program ABP;{program for process S}define sent, b : 0 or 1;next : integer;initially next = 0, sent = 1, b = 0and both channels are emptydo sent ≠b→send (m[next], b);next := next +1; sent := b(ack, j) is received →if j = b → b := 1-bj ≠ b →skipf itimeout (r,s)→send (m[next-1], b)od{program for process R}define j : 0 or 1;initially j = 0;do(m[next], b) is received →if j = b → accept the message;send (ack, j);j:= 1 - jj ≠ b → send (ack, 1-j)odWithout going through a formal proof, we demonstrate why the FIFO property of the channel is considered essential for the alternating bit protocol.Fig 11.5. A global state of the alternating bit protocol.Consider the global state of Fig 11.5 that was reached in the following way. m[0] was transmitted by S and accepted by R, but its achnowledgement (ack, 0) was delayed -- so S transmitted m[0]once more. When (ack, 0)finally reached S,it sent out m[1].Since the channel is not FIFO, assume that m[1] reached R before m[0]. This was accepted by R, and (ack,1) was sent back to S. On receipt of this (ack,1) S sent out m[2].Now m[0] with a tag 0 reaches R, and R accepts it, as it mistakes it for m[2] since both m[0] and m[2] have the same tag 0! Clearly this possibility is ruled out when the channels are FIFO.11.7. Concluding RemarksThe examples presented in this chapter illustrate methods of implementing primarily the masking type of fault-tolerance. If the specification of the possible type of fault F is known, then in an F-tolerant system, no occurrence of F should be perceptible to the user of the protocol.Many variations of sliding-window protocol are used in real aplications. Unlike the one discussed in this chapter, most handle two-way communications, where each node can act both as a sender and Another generalization that reduces the number of retransmissions involve the use of a receive buffer. Good messages that are received by R after the loss or the corruption of an earlier message are not discarded, but saved in R's local buffer, and acknowledged. Eventually, the sender learns about it through the timeout mechanism, and selectively transmits the lost or the corrupted messages.An important class of fault-tolerant systems deals with reaching consensus, where a number of processes communicate with one another in a faulty environment to reach an agreement. Distributed consensus is an extensively studied area of research, and some。
