Unit 5

Unit 5: Fault Tolerance and Consensus - Complete Notes

---

1. Introduction to Fault Tolerance

Definition:

• Fault Tolerance is the ability of a system to continue functioning correctly even in the presence of faults (e.g., hardware failures, software bugs, network issues).

Why It’s Important:

• Ensures system reliability and availability.

• Example: A banking system must continue working even if a server fails.

Key Concepts:

1. Fault:

   • A defect or failure in a system component.

   • Example: A crashed server or a broken network link.

2. Error:

   • A deviation from correct behavior due to a fault.

   • Example: Incorrect data due to a faulty sensor.

3. Failure:

   • The system’s inability to perform its intended function.

   • Example: A website going offline due to a server crash.

Techniques for Fault Tolerance:

1. Redundancy:

   • Adding extra components to ensure system functionality.

   • Example: Replicating data across multiple servers.

2. Checkpointing:

   • Periodically saving the system state to recover from failures.

   • Example: Database systems saving transaction logs.

3. Recovery:

   • Restoring the system to a correct state after a failure.

   • Example: Rebooting a server after a crash.

---

Mind Map for Introduction to Fault Tolerance:

Fault Tolerance  
├── Definition  
│   └── System functioning despite faults  
├── Key Concepts  
│   ├── Fault (Example: Crashed server)  
│   ├── Error (Example: Incorrect data)  
│   └── Failure (Example: Website offline)  
└── Techniques  
    ├── Redundancy (Example: Data replication)  
    ├── Checkpointing (Example: Transaction logs)  
    └── Recovery (Example: Server reboot)

---

2. Distributed Commit Protocols

Definition:

• Distributed Commit Protocols ensure that a distributed transaction is either fully committed or fully rolled back across all nodes.

Why It’s Important:

• Ensures data consistency in distributed systems.

• Example: A distributed database must ensure that all nodes agree on whether to commit or abort a transaction.

Types of Commit Protocols:

1. Two-Phase Commit (2PC):

   • A coordinator ensures all participants agree to commit or abort.

   • Phases:

     1. Prepare Phase: Coordinator asks participants if they are ready to commit.

     2. Commit Phase: If all participants agree, the coordinator sends a commit request.

   • Example: Distributed databases like MySQL Cluster.

2. Three-Phase Commit (3PC):

   • Adds a pre-commit phase to reduce blocking in case of failures.

   • Phases:

     1. Prepare Phase: Same as 2PC.

     2. Pre-Commit Phase: Coordinator ensures all participants are ready to commit.

     3. Commit Phase: Coordinator sends the final commit request.

   • Example: High-availability systems like Google Spanner.

Comparison:

Feature	Two-Phase Commit (2PC)	Three-Phase Commit (3PC)
Phases	2 (Prepare, Commit)	3 (Prepare, Pre-Commit, Commit)
Blocking	Can block if coordinator fails	Non-blocking due to pre-commit phase
Use Case	Simple distributed systems	High-availability systems

---

Mind Map for Distributed Commit Protocols:

Distributed Commit Protocols  
├── Two-Phase Commit (2PC)  
│   ├── Phases: Prepare, Commit  
│   └── Example: MySQL Cluster  
├── Three-Phase Commit (3PC)  
│   ├── Phases: Prepare, Pre-Commit, Commit  
│   └── Example: Google Spanner  
└── Comparison  
    ├── Phases, Blocking, Use Case

---

3. Byzantine Fault Tolerance

Definition:

• Byzantine Fault Tolerance (BFT) is the ability of a system to tolerate arbitrary (malicious) faults, where nodes may behave unpredictably or maliciously.

Why It’s Important:

• Ensures system reliability even in the presence of malicious nodes.

• Example: Blockchain systems must tolerate malicious nodes trying to disrupt the network.

How It Works:

1. Consensus Algorithms:

   • Nodes agree on a single value despite malicious behavior.

   • Example: Practical Byzantine Fault Tolerance (PBFT).

2. Redundancy:

   • Multiple nodes verify and agree on the correctness of data.

   • Example: Replicating transactions across multiple nodes in a blockchain.

Real-World Example:

• Blockchain Networks: Bitcoin and Ethereum use BFT to ensure consensus among nodes, even if some nodes are malicious.

---

Mind Map for Byzantine Fault Tolerance:

Byzantine Fault Tolerance (BFT)  
├── Definition  
│   └── Tolerates arbitrary/malicious faults  
├── How It Works  
│   ├── Consensus Algorithms (Example: PBFT)  
│   └── Redundancy (Example: Blockchain)  
└── Real-World Example  
    └── Blockchain Networks (Bitcoin, Ethereum)

---

4. Impossibilities in Fault Tolerance

Definition:

• Impossibilities in Fault Tolerance refer to theoretical limits on what can be achieved in fault-tolerant systems.

Key Impossibility Results:

1. FLP Impossibility:

   • It is impossible to achieve consensus in an asynchronous distributed system with even a single faulty process.

   • Implication: No algorithm can guarantee consensus in all cases.

   • Example: In a network with delays, consensus may not always be reached.

2. CAP Theorem:

   • A distributed system cannot simultaneously provide Consistency, Availability, and Partition Tolerance.

   • Implication: Systems must trade off between these properties.

   • Example:

     • CP Systems: Prioritize Consistency and Partition Tolerance (e.g., distributed databases).

     • AP Systems: Prioritize Availability and Partition Tolerance (e.g., NoSQL databases).

Real-World Example:

• Distributed Databases: MongoDB (AP system) prioritizes availability, while PostgreSQL (CP system) prioritizes consistency.

---

Mind Map for Impossibilities in Fault Tolerance:

Impossibilities in Fault Tolerance  
├── FLP Impossibility  
│   ├── No consensus in asynchronous systems with faults  
│   └── Example: Network delays  
├── CAP Theorem  
│   ├── Trade-off between Consistency, Availability, Partition Tolerance  
│   └── Example: MongoDB (AP), PostgreSQL (CP)  
└── Real-World Example  
    └── Distributed Databases

---

Summary of Unit 5: Fault Tolerance and Consensus

• Fault Tolerance ensures system reliability despite faults, using techniques like redundancy and recovery.

• Distributed Commit Protocols (2PC, 3PC) ensure atomicity in distributed transactions.

• Byzantine Fault Tolerance handles malicious behavior in distributed systems.

• Impossibility Results (FLP, CAP) define theoretical limits in fault-tolerant systems.

---

Final Mind Map for Unit 5:

Unit 5: Fault Tolerance and Consensus  
├── Fault Tolerance  
│   ├── Definition, Key Concepts (Fault, Error, Failure)  
│   └── Techniques (Redundancy, Checkpointing, Recovery)  
├── Distributed Commit Protocols  
│   ├── Two-Phase Commit (2PC)  
│   ├── Three-Phase Commit (3PC)  
│   └── Comparison (Phases, Blocking, Use Case)  
├── Byzantine Fault Tolerance (BFT)  
│   ├── Definition, How It Works (Consensus, Redundancy)  
│   └── Real-World Example (Blockchain Networks)  
└── Impossibilities in Fault Tolerance  
    ├── FLP Impossibility (No consensus in asynchronous systems)  
    ├── CAP Theorem (Trade-off: Consistency, Availability, Partition Tolerance)  
    └── Real-World Example (Distributed Databases)

---