Fault Tolerance - Week 3

Question 1

Fault tolerance

Answer 1

operate in an acceptable way when a (partial) failure occurs.

Question 2

Types of Failure

Answer 2

Omission Failures
Timing Failures
Response Failures
Arbitrary (byzantine) failures
Crashes

Question 3

Omission Failures

Answer 3

Server fails to respond to incoming messages

Server fails to receive incoming messages
Server fails to send messages

Question 4

Time failures

Answer 4

Server fails to respond within a certain time

Question 5

Response failures

Answer 5

A server’s response is incorrect

Question 6

Arbitrary (byzantine) failures

Answer 6

A component produces output it should never have produced (may not be detected as incorrect): arbitrary response at arbitrary times

Question 7

Crashes

Answer 7

Server halts

Question 8

Fault-tolerance / Failure masking - through redundancy

Answer 8

Physical redundancy
Time redundancy
Information redundancy

Question 9

Physical redundancy

Answer 9

Having a backup server (no definition given in the slides)

Question 10

Time redundancy

Answer 10

An action is performed, if need be, again and again.
Especially helpful when faults are transient and intermittent

Question 11

Information redundancy

Answer 11

e.g. Send extra bits when transmitting information to allow recovery

Question 12

Two generals problem - unreliable network

Answer 12

If the two generals don’t attack at the same time they die, they are on separate mountains.

With an unreliable channel:
G1 -> G2: Let’s attack at 9am
G2 -> G1: I received your message to attack

G2 doesn’t know if G1 received the message

In general there is no way to guarantee both generals got the message

Question 13

Two generals problem - reliable network

Answer 13

If the two generals don’t attack at the same time they die, they are on separate mountains.

Assume a reliable communication channel

If one general is a traitor, with four generals you can spot the traitor

Question 14

Redundancy Pros

Answer 14

Helps increase reliability
- increase probability that the system operates correctly at any given moment

Question 15

Redundancy Cons

Answer 15

Creates several problems
- consistency of replicas (e.g. data on all replicas need to be updated)
- should improve (somehow) system performance.

Has a cost (monetary or other)

Even in the presence of redundancy, we need to make sure that any failure won’t leave our system in an inconsistent (corrupted) state

Question 16

Triple modular Redundancy

Answer 16

A task is replicated three times, then fed to a series of three voters, can tell if one of the processes failed since it won’t match the other 2, the correct information is then passed to the next process by each voter (see image in Week3 OneNote)

Through replication three times, even if one component fails, the output will still be correct.

Used in airplanes. Chance of something going wrong is very low but still not zero.

Question 17

Replication for performance

Answer 17

Placing a copy of data close to the process using it, time to access the data decreases.

Useful for scalability, e.g:
- Server needs to handle more requests, can replicate the server and subsequently dividing the work.
- Caching: web browsers store a copy of a website to avoid the latency of fetching it from the originating server again.

Question 18

Capacity Planning

Answer 18

The process of determining the necessary capacity to meet a certain level of demand - extends beyond distributed computing.

E.g. Monte Carlo simulation re. number of servers

Question 19

Replication Cons

Answer 19

Cost of maintaining replicas

Consistency problems
To ensure consistency all modifications have to occur on all copies, when and where determines the price of replication

Replica management
- Where to place replica servers to minimize overall data transfer?
- In general is a classic optimisation problem, but in practice often a mangement/commercial issue