Asynchronous Networks and Node Failure Models

To design algorithms that reach consensus and maintain data integrity, you must define the formal timing assumptions of the network and the failure models of the participating nodes.

If your protocol assumes a synchronous network or crash-stop nodes when running on commodity cloud infrastructure, it will inevitably experience data corruption, split-brain states, or deadlocks.

---

1. Network Timing Assumptions

Distributed systems literature classifies network synchrony into three distinct models:

[!IMPORTANT] Why Cloud Networks are Asynchronous:
A packet sent between two AWS EC2 instances usually arrives in $1\text{ms}$. However, during a network switch reconvergence, garbage collection pause, or hypervisor CPU steal, that packet can be delayed by $15,000\text{ms}$ without being dropped. The sender cannot determine whether the receiver crashed or is merely delayed.

---

2. The Hierarchy of Node Failure Models

Nodes in a distributed cluster can fail in several distinct ways, ordered from easiest to hardest to tolerate:

1. Crash-Stop (Fail-Stop)

• Behavior: A node operates correctly until it crashes. Once crashed, it halts execution and never returns.
• Quorum Requirement: To tolerate $f$ crash-stop failures, a cluster requires $N\ge 2f+1$ nodes (e.g. 3 nodes tolerate 1 failure; 5 nodes tolerate 2 failures).

2. Crash-Recovery (Fail-Recovery)

• Behavior: A node crashes unexpectedly, halts, reboots after some time, and rejoins the cluster.
• Requirement: The node must persist its state (current term, votedFor, commitIndex) to an append-only Write-Ahead Log (WAL) with synchronous fsync before responding to RPCs. Otherwise, upon rebooting, the node could vote for a different leader in the same term, causing a split-brain.

3. Omission Failures

• Behavior: A node remains running, but silently drops incoming or outgoing network packets due to kernel socket buffer overflow or firewall misconfigurations.

4. Byzantine (Arbitrary) Failures

• Behavior: A node exhibits arbitrary, non-crash behavior. A Byzantine node can forge messages, send conflicting votes to different peers (equivocation), or intentionally lie about its internal state.
• Quorum Requirement: Tolerating $f$ Byzantine nodes requires: $N\ge 3f+1$
• Example: In a 4-node cluster ($f=1$), even if 1 node lies to Node A and tells the truth to Node B, the remaining 3 honest nodes form a supermajority ($2f+1=3$) to safely reach consensus.

---

3. The FLP Impossibility Theorem (Fischer, Lynch, Paterson)

Published in 1985, the FLP Impossibility Result is one of the most fundamental theorems in distributed computing:

[!CAUTION] The FLP Impossibility Theorem:
In an asynchronous network, no deterministic consensus protocol can guarantee both Safety (agreement on a valid value) and Liveness (guaranteed termination) in the presence of even a single unannounced crash failure.

Why is Deterministic Consensus Impossible in Pure Async Networks?

Because a healthy node that is experiencing extreme network latency is indistinguishable from a node that has crashed. Any deterministic algorithm that guarantees termination (Liveness) risks making a decision before hearing from the delayed node, violating Safety (Consistency).

How Practical Consensus Algorithms (Raft & Paxos) Circumvent FLP:

1. Sacrifice Deterministic Liveness: Raft guarantees absolute Safety at all times (no split-brain or data corruption), but sacrifices deterministic liveness during severe network partitions.
2. Randomized Timers: Raft uses randomized election timeouts (e.g. $150\text{ms}-300\text{ms}$) to break symmetry during split votes, ensuring the cluster regains liveness with $99.999\%$ probability as soon as the network becomes partially synchronous.
3. Partial Synchrony Assumption: Raft assumes that while the network can be asynchronous during partitions, it will eventually experience periods of bounded delay ($\Delta$) where heartbeats can be successfully exchanged.

---

4. Code Deep-Dive: Heartbeat Lease Failure Detector

In a Crash-Recovery model, nodes use heartbeat leases to distinguish between dead nodes and active leaders:

---

5. Production Failure Postmortem: The "Gray Failure" Flapping Outage

Incident Context:

A 5-node Cassandra and Raft metadata cluster running on a major cloud provider suffered repeated leader flapping and high write latency.

The Root Cause:

1. Node 3's virtual network interface experienced a hardware CRC checksum error that dropped $90\%$ of outbound data packets, but allowed $100\%$ of small TCP SYN/ACK packets through.
2. Because the node was not dead (Crash-Stop), standard ping health-checks reported it as healthy.
3. However, when Node 3 attempted to replicate write logs to followers, the replication RPCs timed out. Node 3 repeatedly lost leadership, triggered new elections, and caused the cluster to spend $45\text{ minutes}$ in non-stop leader transition cycles.

The Architectural Fix:

• Dual-Metric Health Checks: Monitor not only raw TCP reachability, but also application-level throughput and RPC success rates.
• Pre-Vote Protocol Phase: In Raft, a candidate must conduct a speculative PreVote round to confirm it can communicate with a quorum of peers before incrementing its term and causing a disruption.

---

6. Chapter 1 Graduation Summary Matrix

You have completed Chapter 1: Introduction to Distributed Systems and Network Fundamentals.