Module 10a - Fault Tolerance

Question 1

Describe the concept of Availability for fault tolerance in distributed computing

Answer 1

The system should operate correctly at any given instant in time.
Ex: a real system may be 99% available

Question 2

Describe the concept of Reliability in distributed computing

Answer 2

The system should run continuously without interruption.

Ex: A real system may have a mean time between failures (MTBF) of one month

Question 3

Describe the concept of Safety in distributed computing

Answer 3

Failure of the system should not have catastrophic consequences.
Ex: your car can still come to a complete stop if the ABS fails

Question 4

Describe the concept of Maintainability in distributed computing

Answer 4

A failed system should be easy to repair.

Ex: disks can be replaced easily in a RAID

Question 5

Define the term “error” in distributed computing

Answer 5

Error: A part of a system’s state that might lead to a failure.
Ex: dropped or damaged network packet

Question 6

A ____ may lead to an _____ which may lead to a _____

Answer 6

fault
error
failure

Question 7

Define the term “fault” in distributed computing

Answer 7

Fault: The cause of an error
Ex: When a person talking on the phone walks into an elevator

Question 8

What are the 3 types of faults?

Answer 8

Transient faults
Intermittent faults
Permanent faults

Question 9

What is a transient fault?

Answer 9

Transient faults occur once and then disappears

Ex: a bird flies in front of a microwave receiver

Question 10

What is an intermittent fault?

Answer 10

Intermittent faults occur, vanish, then reappear. They are difficult to debug.

Question 11

What is a permanent fault?

Answer 11

Permanent faults occur and will continue to exist until a faulty component is replaced.

Ex: burnt out power supply in a server

Question 12

What are the 5 types of failures in distributed systems?

Answer 12

Crash failure
Omission failure
Timing failure
Response failure
Arbitrary failure

Question 13

What is a Crash failure?

Answer 13

A server halts, but is working correctly until it halts

Question 14

What is an Omission failure?

Answer 14

A server fails to respond to incoming requests

Question 15

What is a Timing failure?

Answer 15

A server’s response lies outside the specified time interval

Question 16

What is a Response failure?

Answer 16

A server’s response is incorrect

Question 17

What is an Arbitrary Failure?

Answer 17

A server may produce arbitrary responses at arbitrary times

Question 18

In Distributed Systems, we mask failures using _______. One example of this is _______ computing units

Answer 18

redundancy

replicating

Question 19

A software technique for providing redundancy is to create a group of redundant identical processes. They can be classified as a Flat group, or a Hierarchical group.

Describe both of these paradigms.

Answer 19

Flat Group:
All processes behave in the same way. They are simply replicas of each other.

Hierarchical Group:
There is 1 coordinator processes, and numerous worker processes.

Question 20

What are Flat groups? how can you implement them?

Answer 20

All processes play an equal role, there is no concept of a primary, or a backup.

Implemented using quorum-replications.

Question 21

What are Hierarchical groups?

Answer 21

There is a distinguished primary/coordinator node, which coordinates the actions of the other nodes which are backup/worker nodes.

Implemented using primary-backup server. Consensus problem is required to be solved for this

Question 22

What is the consensus problem?

Answer 22

• We assume that each process has a procedure propose(val) and a procedure decide()
• First, each process proposes a value by calling the propose function once and specifying a value at the initial state of the process
• Next, each process learns the value agreed upon by calling the decide() function

Question 23

3 friends are trying to figure out what to do on a Friday night. Their proposals are all different activities:
Friend #1: proposes to go see a movie
Friend #2: proposes to go to a restaurant
Friend #3: proposes to sit at home

Next, the 3 friends all decide and go to the movie.

This is an analogy of what type of problem?

Answer 23

The Consensus Problem

Question 24

In the consensus problem, there are 2 safety properties: Agreement, and Validity. Describe them.

Answer 24

Agreement: Two calls to decide() never return different values

Validity: If a process calls decide() with response x, then some process must have invoked a call to propose(x)

Question 25

In the consensus problem, what is the liveness property?

Answer 25

Liveness: is a process calls propose(x) or decide() and does NOT fail, then that process must eventually terminate

Question 26

What are the names of the 3 properties of the consensus problem?

Answer 26

Safety Agreement
Safety Validity
Liveness Property

Question 27

Solving consensus in a failure-prone distributed environment depends on 4 design factors. What are they?

Note: these 4 factors influence if a consensus problem is solvable

Answer 27

1. Async vs Sync processes (is the time for an execution bounded)
2. Communication Delays (is there a bound with network delay on message delivery)
3. Message delivery Order (FIFO vs LIFO)
4. Unicast vs multicast

Question 28

RPC systems may exhibit 5 classes of failure scenarios. What are they?

Answer 28

1. Client is unable to locate the server (url doesn’t resolve to network address or network address doesn’t give a connection)
2. The request message from the client to the server is lost
3. The server crashes after receiving a request
4. The reply message from the server to the client is lost
5. The client crashes after sending a request

Question 29

What does it mean for a request to be “idempotent”?

Answer 29

Repeated executions have the same effect as one execution.

Question 30

When an RPC server crashes upon request, often the request can be reissued. What are the effects of this? In what case is this fine?

Answer 30

The request may be processed multiple times by the service handler. The client may not know how much of the execution transpired. This is fine if the execution is idempotent

Question 31

Sometimes when an RPC server crashes upon request, a strategy can be to ______ and report a failure. There is no ______ that the request has been processed.

Answer 31

give-up

guarantee

Question 32

Suppose an RPC server crashes upon request. What do the following terms correspond to:

1. at-least-one semantics
2. at-most-one semantics
3. exactly one semantics

Answer 32

1. at-least-one semantics is when the request is reissued
2. at-most-one semantics is when the client gives up
3. exactly one semantics is when the client determines if the request is processed and reissues accordingly

Question 33

What does “exactly one semantics” mean in the context of an RPC server crashing upon receiving a request?
Why is this scheme difficult to implement?

Answer 33

The client determines if the request is processed and reissues accordingly.

It is difficult to implement because the server may not have a way of knowing wether a particular action has been completed.

Question 34

Suppose we have a client-server RPC set tup. The client follows an always re-issue strategy if it does not receive a response.

In what case would this lead to duplicated computation from the server?

Answer 34

If the server executes & completes the request, and then crashes right before sending the response. The client would reissue the request and the server would compute the request twice

Question 35

What is the definition of fault tolerence?

Answer 35

the characteristic by which a system can mask the occurrence and recovery from failures.