Given the inherent complexity and component independence in distributed systems, failures are inevitable. Robust mechanisms for failure detection and sophisticated recovery strategies are paramount to ensure continuous operation, data consistency, and system resilience.

Comprehensive Taxonomy of Failures in Distributed Systems:

• Crash Failures (Fail-Stop): A process simply halts its execution and ceases all communication. It does not perform any incorrect actions before stopping. This is the simplest failure model to handle.
• Omission Failures:
• Send-Omission: A process fails to send a message it was supposed to send.
• Receive-Omission: A process fails to receive a message that was sent to it.
• Timing Failures:
• Clock Skew: Differences in time readings between processes' local clocks.
• Performance Failure: A process responds too slowly (e.g., violates a deadline).
• Omission with Arbitrary Delay: A message is sent but arrives arbitrarily late.
• Arbitrary (Byzantine) Failures: A process can behave in any way, including malicious, unpredictable, or inconsistent actions (e.g., sending different values to different recipients, forging messages, crashing and restarting at arbitrary points).
• Network Failures:
• Message Loss: Messages are dropped by the network.
• Message Corruption: Message content is altered during transit.
• Message Reordering: Messages arrive at the destination in an order different from their send order.
• Message Duplication: Identical messages are delivered multiple times.
• Network Partition: The network splits into segments such that processes in different segments cannot communicate.

Recovery Approaches: Rollback Recovery Schemes (Focus on Consistency):

Rollback recovery is a class of techniques designed to restore a distributed system to a consistent global state after a failure, typically by reverting some or all processes to a previously saved state (checkpoint).
- Local Checkpoint (Independent Checkpointing):
- Mechanism: Each process in the distributed system periodically and independently saves its own local state to stable storage (e.g., disk). This saved state is called a "local checkpoint." Processes do not coordinate their checkpointing efforts with other processes.
- Advantages: Simple to implement at the individual process level. Low overhead during normal operation (no synchronization required).
- Fundamental Challenge: The Domino Effect: If a process (P_i) fails and then recovers by restoring its state from its latest local checkpoint (C_i), it effectively "undoes" any messages it sent after C_i. If another process (P_j) had received such a message from P_i after P_i's checkpoint C_i, and P_j then subsequently created its own checkpoint (C_j), the global state (C_i, C_j) becomes inconsistent. To restore consistency, P_j is then forced to roll back to an earlier checkpoint (C_j'), which might then force other processes that interacted with P_j to roll back, creating a cascade of rollbacks that can propagate through the entire system.

Challenges of Recovery Approaches:

• Interaction with the Outside World (The Output Commit Problem):
• Challenge: Distributed systems interact with entities outside their fault-tolerance domain (e.g., human users, external databases, physical actuators, other independent services). If a system rolls back, it faces the problem of "uncontrolled effects."
  • Redundant Output: If a message or action was sent to the outside world after a consistent checkpoint but before a failure leading to a rollback, that action cannot be undone. If the system simply rolls back and re-executes, it might send the same message/perform the same action again (e.g., a duplicate money transfer, sending the same email twice), causing unintended and potentially harmful side effects.
  • Lost Input: Similarly, input messages received from the outside world might be "lost" if the process rolls back past the point of their reception without careful logging.

Coordinated Checkpointing and Recovery Algorithms:

To circumvent the domino effect and ensure recovery to a globally consistent state, coordinated checkpointing protocols are employed. These protocols ensure that all participating processes take their checkpoints in a synchronized manner, effectively creating a "consistent cut" in the system's execution history.
- Koo-Toueg Coordinated Checkpointing Algorithm (A Classic Example):
- Core Principle: This algorithm achieves consistent global checkpoints by coordinating processes to ensure that for any two processes P_i and P_j, if P_j's checkpoint reflects receipt of a message from P_i, then P_i's checkpoint also reflects the sending of that message.
- Mechanism (Two-Phase Protocol):
1. Phase 1: Initiating and Tentative Checkpoints:
- Initiation: A designated coordinator process (or any process detecting a need for a checkpoint) begins the protocol by recording its own local state as a tentative checkpoint and then sends a MARKER message to all other processes in the system via all its outgoing communication channels.
- Propagation and Local Checkpointing: When any non-coordinator process (P_k) receives a MARKER message for the first time in a new checkpointing round:
- P_k immediately suspends its normal application execution (to avoid creating new inconsistent states while checkpointing).
- P_k records its current local state as a tentative checkpoint.
- P_k then propagates the MARKER message to all its own outgoing communication channels.