7 - Fault Tolerance

Question 1

Dependability

Answer 1

Correctness of one component depends on another component

Question 2

Dependability Example

Answer 2

Web server W requires database D.
D fails, so does W.

Question 3

Dependability requires

Answer 3

Availability
Reliability
Safety
Maintainability

Question 4

Availability

Answer 4

Readiness for usage
A(t) = probability that component is immediately usable

Question 5

Reliability

Answer 5

Continuity of service delivery
R(t) = probability component works over time period [0,t]

Question 6

Safety

Answer 6

Low risk of component failure leading to system failure.

Question 7

Maintainability

Answer 7

Easy and quick to repair

Question 8

When is a system more available but less reliable

Answer 8

more available meaning generally online but less reliable meaning scattered downtime

Question 9

MTTF

Answer 9

Mean Time to Failure
Average time between start and failure

Question 10

MTTR

Answer 10

Mean Time to Repair
Average time of repair

Question 11

MTBF

Answer 11

Mean Time between Failures
MTBF = MTTF + MTTR

Question 12

Availability (expression in relation to MTTF MTBF etc)

Answer 12

time available/whole time
MTTF/MTBF

Question 13

Failure Rate z(t) of component C

Answer 13

z(t) is the (conditional) probability that C initially fails at t.

Question 14

Reliability R(t) of component C

Answer 14

Declines exponentially even if z(t) is constant.
R(t) = e^(-z*t)

Question 15

Density Function

Answer 15

f(t)
Probability of fail at

Question 16

CDF

Answer 16

Cumulative Distribution Function
Probability to fail by t

Question 17

Fault classifications

Answer 17

Permanent: exists until repaired
Intermittent: reappearing
Transient: occurs just once and disappears

Question 18

Fault

Answer 18

Cause of error

Question 19

Error

Answer 19

Part of component that can lead to failure

Question 20

Failure

Answer 20

Component is not running as expected

Question 21

Dealing with faults

Answer 21

Tolerant system
Good fault removal
Fault forecasting

Question 22

Are parallel programs fault tolerant?

Answer 22

Often not fault-tolerant.
Wastes resources
Crashes as soon as one component fails

Question 23

Checkpointing

Answer 23

Save program state in regular intervals and pick up from last one after a crash.

Avoid unneccessary checkpoints - predict crash

Question 24

Failure Types

(one word names)

Answer 24

Halting
Omission
Timing
Response
Arbitrary/byzantine

Question 25

Halting failure

Answer 25

Component stops

Question 26

Omission failure

Answer 26

Failure to respond/receive/send messages

Question 27

Timing failure

Answer 27

Response outside of specified time interval

Question 28

Response failures

Answer 28

Incorrect response. Value or state-transition

Question 29

Arbitrary/byzantine failure

Answer 29

Arbitrary responses at arbitrary times

Question 30

Async or sync: Reliable crash failure detection

Answer 30

Async - cannot be reliably detected Sync - can be reliably detected, detect by timeout but NO CERTAINTY

Question 31

Halt fail types

Answer 31

stop - reliably detectable noisy - eventually reliably detectable silent - client cannot distinguish crash/omission safe - benign arbitrary - unobservable and harmful

Question 32

Information Redundancy

Answer 32

Add extra error detection bits, eg checksum

Question 33

Time redundancy

Answer 33

Designed to repeat action if required

Question 34

Physical Redundancy

Answer 34

Add replicas of components

Question 35

Triple Modular Redundancy

Answer 35

Every device replicated 3 times Each replicate should produce same result. Majority value is used

Question 36

Process Groups

Answer 36

Dynamic group of (mostly) identical processes to achieve fault tolerance via physical redundancy. All members receive all messages

Question 37

Process Group examples

Answer 37

Replicated data store Master-worker scheme

Question 38

Hierarchical Group

Answer 38

One member is coordinator. If coordinator fails, new one must be elected.

Question 39

Flat Group

Answer 39

Members coordinate together Majority decisions Robust against crashes

Question 40

Process Groups: Centralised membership

Answer 40

Group server manages. - Efficient, Simple removal, Message sync easier - Single point of failure, group must be reconstructed if server ceases

Question 41

Process Groups: Distributed membership

Answer 41

Processes inform all of join/leave - More fault tolerant, Many processes must fail before rebuild - Less efficient, crashed processes must be detected, message sync harder

Question 42

k-fault-tolerant group

Answer 42

A group can mask any k concurrent member failures k is called degree of fault tolerance

Question 43

k-fault-tolerant group needs to be how large for halting failures...?

Answer 43

k+1 because one member is enough

Question 44

k-fault-tolerant groups needs to be how large for arbitrary/byzantine failures

Answer 44

2*k +1 are needed because a majority vote is required

Question 45

Consensus

Answer 45

All processes in a process group agree

Question 46

Flooding based consensus: Algorithm for each process

Answer 46

Pi sends its set of commands to all others. For each pair (pi,pj), Pi detects either a Pj message or crash. Pi merges all received commands If Pi detects a crash. - Pi does not exec a command. - Pi runs error routine in next round Else: - Pi selects next command and exec

Question 47

Flooding based consensus: Algorithm after failure

Answer 47

If Pi received all messages, but others did not: - Pi sends msgs and decision from previous round to other processes Elseif Pi did not: - Pi signlas that it did not receive all - Pi runs command from last round

Question 48

Byzantine Consensus: Context

Answer 48

Some generals in the Byzantine Empire may be traitors (faulty processes) and deliberately send false messages

Question 49

Byzantine Consensus: Attack or retreat?

Answer 49

If all (honest) retreat, it is fine. If all (honest) attack, it will succeed. If a subset attacks, it fails.

Question 50

Generally, Byzantine Consensus can be reached when...

Answer 50

if k processes are faulty, then at least n = 3*k+1 are required

Question 51

Failure Detection Types/Methods

Answer 51

Passive Active Gossiping

Question 52

How is a byzantine failure caused?

Answer 52

By a faulty/malicious process producing a false value

Question 53

How many byzantine failures can be tolerated in Triple Module Redundancy (3 voting devices)?

Answer 53

1. If there's 3 devices and 1 gives false results, the other 2 will still agree and create a majority

Question 54

How many crash failures can Triple Modular Redundancy tolerate? and why?

Answer 54

It can tolerate 2. Crashed devices don't return ANY results so it leaves 1 functioning voter and hence, a majority.

Question 55

How many byzantine failures can a system of n voters tolerate?

Answer 55

(n-1)/2 failures

Question 56

How many crash failures can be tolerated by a system of n voters?

Answer 56

n-1 crashes