chapter 7

Question 1

what is Dependability of components.

Answer 1

A component C depends on C∗ if the correctness of C’s behavior depends on the correctness of C∗’s behavior.

Question 2

what are reqs for dependability? list and describe them.

Answer 2

Availability - readiness to be used
Reliability - Continuity of service delivery
Safety - Very low probability of catastrophes
Maintainability - How easy can a failed system be repaired

Question 3

what is Reliability R(t)?

Answer 3

probability that a component has been up and running continuously in the time interval [0,t)

Question 4

what are the traditional metrics to measure realiability?

Answer 4

• Mean Time To Failure (MTTF): Average time until a component fails
• Mean Time To Repair(MTTR): Average time it takes to repair a failed component.
• Mean Time Between Failures(MTBF): MTTF + MTTR

Question 5

what is Availability A(t)?

Answer 5

Average fraction of time that a component has been up and running in the interval [0,t)

Question 6

how can we calculate Availability A(t)?

Answer 6

A = MTTF /MTBF = MTTF /(MTTF + MTTR )

Question 7

describe faliure and give example

Answer 7

• May occur when a component is not living up to its specifications.
  – A crashed program

Question 8

describe error and give example

Answer 8

• Part of a component that may lead to a failure
  – A programming bug

Question 9

describe fault and give example

Answer 9

• The cause of an error
  – A sloppy programmer

Question 10

describe fault prevention and give example

Answer 10

• Prevent the occurrence of a fault
  – Don’t hire sloppy programmers

Question 11

describe fault tolerance and give example

Answer 11

• Build a component that can mask the occurrence of a fault
  – Build each component by two independent programmers

Question 12

describe fault removal and give example

Answer 12

• Reduce the presence, number, or seriousness of a fault
  – Get rid of sloppy programmers

Question 13

describe Fault forecasting and give example

Answer 13

• Estimate current presence, future incidence, and consequences of faults
  – Estimate how a recruiter is doing when it comes to hiring sloppy programmers

Question 14

what is a Crash failure?

Answer 14

Component halts, but behaves correctly before halting

Question 15

what is an Omission failure?

Answer 15

• Failure in sending or receiving messages
  – Receiving omissions: sent messages are not received
  – Send omissions: messages are not sent that should have

Question 16

what is a Timing failure?

Answer 16

• Output [ response ] is correct, but lies outside a specified interval.
  – Performance failures: the component is too slow

Question 17

what is a Response failure?

Answer 17

• The components response is incorrect
  – Value failure : The value of the response is wrong
  – State transition failure : The server deviates from the correct flow of control and into a wrong state

Question 18

what is an Arbitrary failure?

Answer 18

Component produces arbitrary output and be subject to arbitrary timing failures

Question 19

what is a Commission failure?

Answer 19

A component takes an action that it should not have taken

Question 20

what is a Deliberate failure

Answer 20

can be omission or commission failures, that stretch out to the field of security

Question 21

describe if possible, how we can Distinguishing between a crash or omission/timing failure.

Answer 21

1. Asynchronous system: no assumptions about process execution speeds or message delivery times → cannot reliably detect crash failures.
2. Synchronous system: process execution speeds and message delivery times are bounded → we can reliably detect omission and timing failures.
3. Partially synchronous systems: most of the time, we can assume the system to be synchronous, yet there is no bound on the time that a system is asynchronous → can normally reliably detect crash failures.

Question 22

what assumptions can we make about crash failures?

Answer 22

• Fail-stop: The component exhibits crash failures, but its failure can be detected (either through announcement or timeouts)
• Fail-noisy: Crash failures, eventually reliably detectable
• Fail-silent: The component exhibits omission or crash failures; clients
  cannot tell what went wrong
• Fail-safe: The component exhibits arbitrary, but benign failures (they can’t do any harm)
• Fail-arbitrary Arbitrary, with malicious failures

Question 23

what is the Basic approach to Process Resilience?

Answer 23

replicate a process and organize them into a group; if a
process in the group fails the others take over.

Question 24

what are the 2 techniques to achieve process resilience?

Answer 24

flat groups
hierarchical groups

Question 25

describe a flat group

Answer 25

- all processes are equal - good for fault tolerance since information exchange immediately occurs with all group members - imposes higher overhead as control is completely distributed - hard to implement

Question 26

describe a Hierarchical group.

Answer 26

- All communication go through a single coordinator - Loss of the coordinator brings the entire group to a halt - not really fault tolerant and scalable - easier to implement

Question 27

what is a K-fault tolerant group?

Answer 27

When a group can mask any k concurrent member failures (k is called degree of fault tolerance).

Question 28

How large does a k-fault tolerant group need to be?

Answer 28

- Assume crash/performance failure semantics ⇒ a total of k + 1 members are needed to survive k member failures. - Assume arbitrary failure semantics, and group output defined by voting ⇒ a total of 2k + 1 members are needed to survive k member failures.

Question 29

describe the assumptions and basic idea of Flooding-based consensus

Answer 29

Assume: - Fail-stop semantics - when a process crashes, this can be reliably detected. - Reliable failure detection - a process P can indeed reliably detect that Q crashed - Unreliable communication Basic idea: - A client contacts a Pi requesting it to execute a command - Every Pi maintains a list of proposed commands - A process group P = {P1,...,Pn} - In round r, Pi multicasts its known set of commands C to all other processes

Question 30

what are the assumptions made by Paxos consensus?

Answer 30

- An asynchronous system - Communication may be unreliable (meaning that messages may be lost, duplicated, or reordered) - Corrupted messages are detectable (and can thus be discarded) - All operations are deterministic ( can't be interrupted ) - Process may exhibit halting failures, but not arbitrary failures, nor do they collude.

Question 31

what are the Essentials of a Paxos consensus?

Answer 31

1. client - a thread that requests to have an operation performed 2. proposer - a thread that takes a client’s request and attempts to have the requested operation accepted for execution 3. acceptor - a thread that operates in a quorum to vote for the execution of an operation 4. learner - a thread that eventually performs an operation

Question 32

what are the guarantees of a Paxos consensus?

Answer 32

1. Safety (nothing bad will happen): - Only proposed operations will be learned - At most one operation will be learned (and subsequently executed before a next operation is learned) 2. Liveness (something good will eventually happen): - If sufficient processes remain non faulty, then a proposed operation will eventually be learned

Question 33

How can we reliably detect that a process has actually crashed using the general model?

Answer 33

- Each process is equipped with a failure detection module - A process p probes another process q for a reaction: ---- q reacts →q is alive ---- q does not react within t time units → q is suspected to have crashed Note: in a synchronous system: - a suspected crash is a known crash - referred to as a perfect failure detector

Question 34

what do we call a perfect failure detector in practice? and what are it's two important properties?

Answer 34

- the eventually perfect failure detector 1. Strong completeness : every crashed process is eventually suspected to have crashed by every correct process. 2. Eventual strong accuracy : eventually, no correct process is suspected by any other correct process to have crashed.

Question 35

what is the implementation of the eventually perfect failure detector?

Answer 35

- If p did not receive heartbeat from q within time t → p suspects q. - If q later sends a message (received by p): ---- p stops suspecting q ---- p increases timeout value t - Note: if q does crash, p will keep suspecting q.

Question 36

What can go wrong during RPC communication?

Answer 36

1: Client cannot locate server 2: Client request is lost 3: Server crashes 4: Server response is lost 5: Client crashes

Question 37

what are the RPC communication: Solutions 1 and 2?

Answer 37

1: report back to client 2: Just resend message

Question 38

what are the RPC communication: Solutions 3?

Answer 38

3: We need to decide on what we expect from the server: A. At-least-once-semantics: The server guarantees it will carry out an operation at least once, no matter what. [ read ] B. At-most-once-semantics: The server guarantees it will carry out an operation at most once. [ write, transfer 10k ]

Question 39

what are the RPC communication: Solutions 4?

Answer 39

4: Detecting lost replies can be hard, because it can also be that the server had crashed. You don’t know whether the server has carried out the operation Solution: None, except that you can try to make your operations: - idempotent: repeatable without any harm done if it happened to be carried out before.

Question 40

what is an orphan computation?

Answer 40

Client crashes but The server is doing work and holding resources for nothing

Question 41

what are the RPC communication: Solutions 5?

Answer 41

- Orphan is killed (or rolled back) by client when it reboots - Broadcast new epoch number when recovering ⇒ servers kill orphans - Require computations to complete in a T time units. Old ones are simply removed.