MIT 6.824 - Distributed Systems & Fault Tolerance

A programming model where Map(k1, v1) processes raw inputs to emit intermediate (k2, v2) pairs, and Reduce(k2, list(v2)) aggregates intermediate values per key. The master node tracks worker state (idle, in-progress, completed). Fault tolerance is achieved via re-execution: if a worker fails, its in-progress or completed Map tasks are reassigned to other workers.

A primary-backup state machine replication system operating at the virtual machine level. The primary VM streams all non-deterministic events (such as hardware interrupts, instruction clock reads, and network packets) over a logging channel to the backup VM. The backup executes identical input sequences to maintain exact state synchronization.

A failure state in distributed systems where network partitioning splits cluster nodes into isolated groups, causing multiple nodes to independently assume leadership. This leads to conflicting state updates and data corruption. It is prevented using majority quorums requiring $Q>N/2$ nodes to elect leaders or commit operations.

A strong consistency model guaranteeing that all operations appear to execute atomically at a single point in time between their invocation and response according to a global real-time clock. Once a write completes, all subsequent reads across any node must return that value or a newer value.

A weak consistency model guaranteeing that if no new updates are applied, all replicas will eventually converge and return identical values when queried. It maximizes availability and performance (AP in CAP) at the cost of transient stale reads.

A protocol pattern where multiple fault-tolerant nodes execute identical deterministic operations in the same relative sequence. If all replicas start in state $S_0$ and apply identical command log entries $I_1,I_2,\dots ,I_n$, they transition through identical intermediate states and produce matching outputs.

Raft divides time into logical terms incremented monotonically. When a follower's election timer expires without receiving heartbeats (AppendEntries), it transitions to candidate, increments the term, votes for itself, and sends RequestVote RPCs. It becomes leader upon receiving votes from a majority of nodes.

The leader appends client commands to its local log as uncommitted entries and sends AppendEntries RPCs to followers. Followers append entries to their logs and reply. Once replicated to a majority quorum, the leader marks the entry committed, applies it to its local state machine, and returns the output to the client.