PadhaikoAll subjects

Fault Tolerance and Reliability

Distributed and Cloud Computing (ENCT 411)

Open in the Padhaiko app

8.1 Dependability Concepts: Availability, Reliability, Safety, Maintainability, MTTF, and MTTR

Definition

Dependability and Its Four Pillars

Dependability is the trustworthiness of a computing system such that reliance can justifiably be placed on the service it delivers. It comprises four core properties:

  1. Availability (): Readiness for correct service at any given instant in time (probability the system is operational right now).
  2. Reliability (): Continuity of correct service over a continuous time interval without interruption.
  3. Safety: Absence of catastrophic consequences on users and the environment even if a temporary failure occurs (e.g., fail-safe traffic lights defaulting to all-red).
  4. Maintainability: Ability to undergo repairs, upgrades, and recovery rapidly and easily after failure.

Quantitative Metrics: MTTF, MTTR, MTBF, and Availability

AspectAvailabilityReliability
Question Answered"Is the system working right now?""Did the system run without any interruption for hours?"
Sensitivity to Brief OutagesTolerates tiny frequent crashes if MTTR is near zeroAny single crash during breaks reliability ( drops)
ExampleA web server crashing for once per hour has A -hour spacecraft burn or surgery monitor crashing for fails completely

8.2 Fault, Error, and Failure; Failure Models and Byzantine Fault Tolerance

The Fault–Error–Failure Causal Chain

  1. Fault: The root cause (hardware defect, software bug, cosmic bit-flip, severed fiber cable). Faults may be transient (one-time interference), intermittent (recurring sporadically), or permanent (burned-out disk).
  2. Error: An unintended internal state inside the system produced when an active fault is triggered (e.g., corrupted variable in RAM).
  3. Failure: Observed deviation of the system's external service from its specification when an error propagates to the service boundary.

Classification of Distributed Failure Models

Taxonomy of Distributed System Failure Models (Simplest to Most Severe)
Failure ClassDescriptionRepresentative Examples
Crash (Fail-Stop / Fail-Silent)Server halts permanently and stops producing outputs (fail-stop if peers can reliably detect the halt)Power loss, kernel panic
Omission (Send / Receive)Server fails to send outgoing messages or drops incoming messagesFull NIC ring buffer, dropped UDP packets
Timing (Performance)Server produces the correct value, but too early or too late (violates deadline)Heavy GC pause, CPU starvation
Response (Value / State)Server returns an incorrect value or transitions to wrong stateBuggy calculation, corrupted disk sector
Arbitrary / ByzantineNode fails arbitrarily: crashes, lies, sends conflicting values to different peers, or colludes maliciouslyCompromised node, silent memory corruption

Byzantine Fault Tolerance (BFT)

To mask up to faulty processes:

(Minimum generals to tolerate traitor; nodes to tolerate traitors.)


8.3 Failure Detection, Process Resilience, and Redundancy Techniques

8.3.1 Failure Detection

In asynchronous networks, a slow node cannot be distinguished with certainty from a crashed node (unreliable failure detectors):

8.3.2 Process Resilience via Process Groups

To survive individual process crashes, identical processes are organized into process groups:

8.3.3 Redundancy Techniques

  1. Information Redundancy: Adding extra check bits to detect or correct bit errors—Parity bits, CRC, Hamming ECC, and Erasure Coding (e.g., Reed-Solomon -of- fragments).
  2. Time Redundancy: Repeating an operation when a transient fault occurs (packet retransmissions, idempotent RPC retries, instruction replay).
  3. Physical / Hardware Redundancy: Adding spare hardware components in active or standby configurations:
    • Active Replication / Triple Modular Redundancy (TMR): identical modules execute in parallel and feed a hardware/software majority voter (2-of-3)—masking any single module failure instantaneously!
    • Passive / Hot-Warm-Cold Standby: Backup node takes over when primary fails.

8.4 Checkpointing, Message Logging, and Rollback Recovery

When a long-running distributed computation crashes, restarting from scratch wastes hours of work. Backward error recovery rolls processes back to a previously saved checkpoint on stable storage.

8.4.1 Consistent Global Checkpoints and the Domino Effect

Solutions: Coordinated Checkpointing & Message Logging

  1. Coordinated Checkpointing: Processes synchronize via a distributed snapshot (Chandy-Lamport style) to record a globally consistent recovery line free of orphan messages. Eliminates the domino effect and needs only the latest checkpoint on disk, at the cost of coordination pauses.
  2. Message Logging (Sender-Based or Receiver-Based): Combines periodic uncoordinated checkpoints with logging every received message and non-deterministic event stably before delivery. On crash, the process reloads its last checkpoint and replays logged messages deterministically without forcing healthy peers to roll back!
    • Pessimistic Logging: Log each message synchronously to stable storage before delivering it (zero orphan processes, slight runtime latency).
    • Optimistic Logging: Buffer logs in RAM and flush asynchronously (zero runtime penalty, minor rollback risk if crash occurs before flush).

8.5 High Availability and Disaster Recovery: Failover, Geo-Redundancy, RPO, and RTO

Definition

Recovery Point Objective (RPO) and Recovery Time Objective (RTO)

High Availability (HA) & Disaster Recovery (DR) Topologies

Disaster Recovery Strategies: Trade-Offs in Cost, RPO, and RTO
DR StrategyStandby StateTypical RPOTypical RTOCost & Characteristics
Backup & RestoreCold (snapshots in object storage)Hours to Hours to daysLowest cost; provision infra and restore backups from scratch
Pilot LightCore DB replicating; compute offMinutesTens of minutesLow cost; spin up and scale app servers on disaster
Warm StandbyScaled-down production stack runningSeconds to minutesMinutesModerate cost; scale up existing standby instances and switch DNS
Multi-Site Active-ActiveFull geo-redundant capacity serving live traffic in multiple RegionsNear-zero ()Near-zero (automatic DNS/anycast health failover)Highest cost ( infra); zero idle waste, supports regional routing

Worked Out Examples

Example 8.1

8.1

A cloud database server has and (assume exponential failure distribution).

  1. Calculate its steady-state availability and expected downtime hours per -hour year.
  2. Calculate the composite availability if two identical independent servers are deployed in active-passive/active-active failover redundancy.
  3. Calculate the reliability of a single server running continuously without failure for .

1. Single-Server Availability and Annual Downtime:

2. Redundant Two-Server Parallel Availability:

3. Single-Server Reliability over ():

Answer:
  1. Single-server availability ( downtime).
  2. Two-server redundant availability .
  3. Reliability for without crash .
Example 8.2

8.2

  1. A distributed consensus cluster must remain safe and operational despite up to simultaneous node failures. Calculate the minimum total number of replicas required under (a) Crash-fault tolerance (Paxos/Raft) and (b) Byzantine fault tolerance (BFT).
  2. Triple Modular Redundancy (TMR): Each of three identical voting processor modules has reliability over a mission window. Assuming independent failures and a perfect majority voter, calculate the overall TMR system reliability (works if at least of modules succeed).

1. Minimum Replicas for :

  • Crash Fault Consensus (Paxos/Raft): replicas.
  • Byzantine Fault Tolerance (BFT): replicas.

2. TMR Reliability Calculation ():

Thus TMR raises mission reliability from to , cutting failure probability from down to !

Answer:
  1. For : Crash consensus needs ; BFT needs .
  2. TMR reliability ().
Example 8.3

8.3

Disaster Recovery & Checkpointing Sizing:

  1. An e-commerce payment database processes transactions/second, and management mandates and .
    • At most how many committed transactions could be lost under a asynchronous replication lag, and what DR architecture satisfies ?
  2. A database snapshot must be restored across a internal storage fabric during disaster recovery. How long does the raw data restore take, and how much time remains inside the RTO budget for failure detection and DNS/load-balancer cutover?

1. RPO Transaction Exposure and DR Topology:

  • With and , at most transactions could be unshipped in an asynchronous log buffer (so synchronous multi-AZ or asynchronous WAL shipping is needed).
  • A Backup & Restore or Pilot Light strategy takes minutes to hours, violating . Either Hot/Warm Standby with automated failover or Multi-Site Active-Active is required.

2. Storage Restore & Cutover Budget: Restoring over a fabric takes:

Leaving for health-probe failure detection and automated DNS/load-balancer cutover—showing why sub- RTO demands pre-warmed replicated standbys rather than cold snapshot copies.

Answer:
  1. risks up to transactions (use synchronous/near-sync replication); requires automated Hot Standby or Active-Active failover.
  2. Even at , restoring takes , leaving almost no margin for detection and cutover without live standby replicas.

Exercises

Practice Exercises — Fault Tolerance and Reliability

Question 1

Define Availability, Reliability, Safety, and Maintainability. A microservice node has and . Compute its MTBF, steady-state Availability, and Reliability over a continuous -hour interval.

Dependability Terms:

  • Availability: Probability the system is operational at a given instant.
  • Reliability: Probability of continuous failure-free operation over .
  • Safety: Freedom from catastrophic outcomes during failure.
  • Maintainability: Ease and speed of repair/recovery.

Numerical Metrics (, , ):

Answer:

, Availability , Reliability .

Question 2

Distinguish between Fault, Error, and Failure, and rank the five failure models (Crash, Omission, Timing, Response, Byzantine) by severity. How many total nodes are required to tolerate faulty nodes under (a) Crash-fault consensus and (b) Byzantine fault tolerance?

Fault–Error–Failure and Failure Models: A fault (root cause) triggers an invalid internal error state, which propagates to an externally visible failure. Severity increases from Crash (stops cleanly) Omission (drops messages) Timing (late/early) Response (wrong output) Byzantine (arbitrary/malicious/contradictory behavior).

Replica Bounds for :

  • Crash-fault consensus: nodes.
  • Byzantine fault tolerance: nodes.
Answer:

A fault causes an internal error leading to an external failure. For , crash consensus requires nodes and BFT requires nodes.

Question 3

Explain how gossip-based failure detection avoids false positives compared to naive heartbeats. Also compute the system reliability of a Triple Modular Redundancy (TMR) flight controller whose three independent voter modules each have reliability .

Gossip-Based Failure Detection: Instead of declaring a node dead solely when one monitor's direct ping times out (which may be a transient link glitch between those two hosts), protocols like SWIM ask multiple random peers to send indirect probes and disseminate confirmed failures via epidemic gossip—dramatically reducing false suspicions at per-node overhead.

TMR Reliability ():

Answer:

Gossip detection cross-checks indirect probes via random peers to prevent single-link false positives. TMR reliability with is ().

Question 4

What is an orphan message, and how does it cause the domino effect in uncoordinated checkpointing? Compare Coordinated Checkpointing and Message Logging (pessimistic vs. optimistic) as solutions.

Orphan Messages and the Domino Effect: An orphan message is a message whose receipt is saved in a receiver's checkpoint while its send was lost before the sender's earlier checkpoint. Rolling back the sender forces the receiver to roll back before the orphan receipt, potentially invalidating earlier messages in a cascade back to the start (domino effect).

Coordinated Checkpointing vs. Message Logging:

  • Coordinated Checkpointing: Synchronizes all processes to capture a globally consistent cut with zero orphan messages (simple recovery, periodic coordination overhead).
  • Message Logging: Saves periodic local checkpoints plus all received messages stably so a crashed node replays its own log alone without rolling back healthy peers (pessimistic logs before delivery; optimistic buffers in RAM for speed).
Answer:

An orphan message (received in a checkpoint, sent before the sender's checkpoint) triggers cascading rollbacks (domino effect). Coordinated checkpointing captures a consistent global cut, whereas message logging replays logged inputs locally without rolling back other nodes.

Question 5

Define RPO and RTO, and compare Backup & Restore, Pilot Light, Warm Standby, and Multi-Site Active-Active disaster recovery architectures across cost, RPO, and RTO.

RPO and RTO Definitions:

  • RPO (Recovery Point Objective): Maximum tolerable data loss window (drives replication/backup frequency).
  • RTO (Recovery Time Objective): Maximum tolerable downtime window to restore service (drives automation/pre-warming).

DR Architectures Comparison:

  • Backup & Restore: Lowest cost, hours RPO/RTO.
  • Pilot Light: Core DB live-replicated, compute off; minutes RPO, tens-of-minutes RTO.
  • Warm Standby: Scaled-down stack always running; seconds-to-minutes RPO/RTO.
  • Multi-Site Active-Active: Live traffic in multiple Regions; near-zero RPO and RTO at highest infrastructure cost.
Answer:

RPO bounds acceptable data loss and RTO bounds acceptable downtime. Moving from Backup & Restore Pilot Light Warm Standby Active-Active drives RPO and RTO down toward zero at increasing infrastructure cost.

← Virtualization, Containers and Cloud-Native SystemsEdge Computing, Emerging Trends and Case Studies →