Crash Fault Tolerance (CFT)

CFT systems are designed to handle fail-stop faults, where a component fails by halting completely. This is a critical simplifying assumption that distinguishes CFT from Byzantine Fault Tolerance (BFT).

• Assumption: Failed nodes stop sending messages and do not corrupt data.
• Implication: The system only needs to detect silence or crashes, not malicious behavior.
• Contrast: BFT systems must handle arbitrary, potentially malicious faults, requiring more complex and expensive consensus protocols like Practical Byzantine Fault Tolerance (PBFT).

CFT systems rely on consensus algorithms to ensure all non-faulty replicas agree on the same sequence of state updates, guaranteeing safety (nothing bad happens).

• Primary Mechanism: Protocols like Raft and Paxos are the industry standards for CFT consensus.
• Quorum-Based Decisions: Operations are committed once a majority (quorum) of replicas acknowledge them. This ensures progress even if a minority of nodes crash.
• Leader-Based Coordination: Typically, a single elected leader sequences commands, simplifying the replication log management. If the leader crashes, a new election is held.

To remain operational (live) during crashes, CFT systems employ redundancy and automatic failover. The system's availability is a direct function of its replication factor.

• Replication: Data and computation are replicated across multiple, independent nodes.
• Failover: Upon detecting a leader or node crash (e.g., via timeouts), the system automatically promotes a healthy replica to take over. This is central to active-passive or active-active high-availability architectures.
• Trade-off: Increased replication improves availability but adds coordination overhead and resource cost.

A core implementation pattern for CFT is State Machine Replication. Identical deterministic replicas start from the same state and apply the same sequence of commands in the same order.

• Deterministic Execution: Given the same input log, each replica must produce identical state transitions and outputs. This is non-negotiable for correct rollback and recovery.
• Log Replication: The consensus algorithm's primary job is to maintain a consistent, fault-tolerant replicated log of commands.
• Recovery: A crashed and restarted replica can catch up by replaying the committed log from a checkpoint.

To enable efficient recovery and prevent unbounded log growth, CFT systems use checkpointing.

• Periodic Snapshots: The system's full state is serialized to stable storage at intervals.
• Log Compaction: Once a checkpoint is persisted, all log entries preceding it can be safely deleted. This process is called log truncation or compaction.
• Fast Recovery: A newly started replica can load the latest checkpoint and only replay log entries created after that snapshot, drastically reducing recovery time.

CFT operates within a specific system model, defining the assumptions about timing and communication that its algorithms can tolerate.

• Timing Model: Most CFT protocols (like Raft) assume a partial synchronous model—periods of asynchrony are bounded. They use timeouts for failure detection.
• Fault Threshold: A CFT system with N replicas can tolerate f crash faults as long as N > 2f. For example, a 5-node cluster can tolerate 2 simultaneous crashes and still achieve a quorum (3 nodes).
• Network Assumptions: They assume reliable links; messages may be delayed or reordered but are not corrupted (corruption is handled by lower-layer protocols like TCP).

This classic CFT pattern involves a primary (active) node that handles all client requests and one or more backup (standby) nodes that replicate the primary's state. The system tolerates crashes through:

• State transfer: The primary periodically sends its state (or state diffs) to the backups.
• Failure detection: Using timeouts or a monitoring service.
• Failover: A designated backup promotes itself to primary upon detecting the primary's crash. Challenges include ensuring exactly-once semantics during failover and managing split-brain scenarios. It's common in database systems (e.g., PostgreSQL streaming replication) and high-availability service setups.

A fault tolerance technique that periodically saves a complete snapshot of an agent's or system's internal state to persistent storage. This creates a recovery point to which the system can revert after a crash.

• Enables state reversion by providing a known-good point in time.
• Critical for implementing rollback protocols in long-running processes.
• Can be performed at deterministic intervals or after significant state changes.

A formalized procedure that defines the steps for reverting an agent's state or external actions to a previous checkpoint. It ensures data integrity and consistency during recovery.

• Coordinates the state reversion process across distributed components.
• May involve executing compensating transactions to undo external side effects.
• A core component of self-healing software systems and agentic architectures.

A logically inverse operation executed to semantically undo the effects of a previously committed transaction in a distributed system. Used when a simple state reversion is impossible due to external actions.

• Key mechanism in the Saga Pattern for managing long-running transactions.
• Example: If a booking agent charges a credit card, the compensating transaction would be a refund.
• Essential for maintaining business logic consistency during rollbacks that involve irreversible steps.

A system property where, given the same initial state and sequence of inputs, an agent or process will always produce identical outputs and state transitions.

• Fundamental for reliable checkpointing and replay. If execution is non-deterministic, restoring from a checkpoint may lead to a divergent state.
• Enables state machine replication by ensuring replicas process commands identically.
• A design goal for fault-tolerant agent design to guarantee predictable recovery.

A method for implementing fault-tolerant services by ensuring a collection of replicas start from the same state and execute the same commands in the same order.

• Provides high availability (HA) and crash fault tolerance.
• Relies on a consensus protocol (like Raft) to agree on the command log.
• If the primary replica crashes, a backup can take over from the last agreed-upon state, enabling seamless failover.

The property of a distributed system to resist failures where components may behave arbitrarily (maliciously or erroneously), producing incorrect or inconsistent outputs.

• A strictly stronger guarantee than CFT. CFT assumes nodes fail only by stopping (crashing).
• BFT protocols must handle adversarial behavior, making them essential for secure, trustless environments like blockchains.
• Requires more complex coordination and redundancy than CFT systems.