Failure Models: Crash, Omission and Byzantine

What can go wrong, formally

Algorithms are proven correct against a failure model, so you must know which one you are in. In the crash-stop model a node works correctly until it halts and never returns. Crash-recovery is more realistic: a node may crash and later restart with whatever it saved to stable storage (disk), losing its memory. Omission failures drop messages. Network partitions split the cluster into groups that cannot talk to each other. All of these are benign: a node may stop or be silent, but it never lies. A Byzantine failure is the opposite: a node may send arbitrary, even malicious or contradictory messages. Raft and Paxos assume crash-recovery nodes and an unreliable network that can delay, drop, duplicate or reorder messages, but not Byzantine behaviour. Tolerating liars needs heavier protocols such as PBFT, covered later.

The group project

In a WhatsApp group planning a trip, a friend whose phone dies (crash) or who misses messages (omission) is annoying but honest. A friend who tells half the group 'we leave Friday' and the other half 'we leave Sunday' is Byzantine. Plans that survive the first kind of friend are much simpler than plans that survive the second.

Disks count too

Crash-recovery correctness assumes that data the protocol says is persisted (current term, vote, log entries) really reached the disk before a reply is sent. Skipping fsync for speed silently turns a safe protocol into an unsafe one: after a power cut a node may forget a vote and vote twice in the same term.

Quick check: Which failure is Raft NOT designed to tolerate?

• A node crashing and restarting from disk
• Messages being delayed or reordered
• A network partition that isolates the leader
• A node that sends deliberately conflicting messages to different peers