Systems paper route: MapReduce, Dynamo and Raft

Why it matters

MapReduce, Dynamo and Raft are three different answers to building reliable services from unreliable machines: re-execute deterministic work, stay available and reconcile later, or agree on a single ordered log. Interviews for systems research and distributed-systems roles use them as shared vocabulary, and research interviews in particular test whether you can say exactly what each paper proves, what it measures and under which assumptions. MIT 6.5840 builds its labs around these ideas, which turns reading into implementation.

Core ideas

Suggested order. Read MapReduce first (short, with a clear failure model), then Raft (a precise correctness argument), then Dynamo (an engineering paper full of tradeoffs and production measurements). Paxos Made Simple, assigned in an early 6.5840 lecture, is optional background for Raft.

MapReduce (OSDI 2004).

• Correctness argument (Section 3.3): with deterministic map and reduce functions, the distributed run produces the same output as some fault-free sequential execution. It rests on re-executing failed tasks, ignoring duplicate completion reports and atomically committing outputs (renaming reduce outputs). With non-deterministic functions the guarantee weakens: each reduce output matches some sequential execution, but different reduce outputs may correspond to different executions.
• Assumptions: a single master whose failure aborts the job in the described implementation, a reliable distributed file system, and user code without external side effects.
• Empirical results (Sections 5–6): grep and sort on the authors' cluster, slower completion with backup tasks disabled, behaviour when many workers are killed, and production usage statistics. These reflect 2004 hardware and workloads.
• 6.5840: Lecture 1 and Lab 1, where your coordinator reassigns tasks that do not finish within a timeout and workers write temporary files that they rename atomically.

Raft (USENIX ATC 2014, extended version).

• Correctness argument: the properties in Figure 3 (Election Safety, Leader Append-Only, Log Matching, Leader Completeness, State Machine Safety) and the safety argument in Section 5.4.3, built on the election restriction and the rule that a leader commits entries by counting replicas only for its own term (Figure 8 shows why). Section 9.2 describes a TLA+ specification, a mechanically checked proof of one property that relies on invariants not themselves checked, and an informal proof of State Machine Safety.
• Assumptions: crash-recovery failures with persistent term, vote and log; no Byzantine behaviour; and broadcastTime ≪ electionTimeout ≪ MTBF, which matters for availability only.
• Empirical results: a user study comparing understandability of Raft and Paxos with a paired statistical test, and leader-election timing under different timeout randomization.
• 6.5840: the two Raft lectures and Lab 3 (3A leader election, 3B log, 3C persistence, 3D log compaction), then Lab 4 (fault-tolerant key/value service) and Lab 5 (sharding).

Dynamo (SOSP 2007).

• Design arguments rather than proofs: consistent hashing with virtual nodes; preference lists of N replicas; R and W settings where R + W > N gives overlapping quorums only when strict preference lists are used; sloppy quorums and hinted handoff to stay writable during failures; vector clocks to detect concurrent versions; Merkle-tree anti-entropy; gossip membership. The consistency promise is eventual consistency, with conflicting versions returned to the application for reconciliation.
• Empirical results (Section 6): production latency distributions (average and 99.9th percentile), buffered versus durable writes, load balance across partitioning strategies and how often reads saw divergent versions. They come from one company's workloads and hardware, and the paper states that detailed data on the consistency impact of failures is out of scope.
• 6.5840: Dynamo is not on the current schedule. Read it against the linearizability lecture and Lab 2, whose versioned conditional puts are a single-version alternative to vector clocks, to articulate what Dynamo trades away.

Reading method. For each paper keep two lists: claims with a stated model and an argument (check the argument), and claims backed by measurements (check workload, baseline, environment and variance). Then write one lab experiment that would probe an empirical claim.

Common misconceptions

• "MapReduce executes each user function exactly once." Tasks may run several times; the guarantee concerns committed output and needs deterministic functions plus atomic commits.
• "Dynamo is strongly consistent when R + W > N." Sloppy quorums let writes land outside the preference list, so read and write sets need not intersect; even strict quorums do not give linearizability by themselves.
• "Raft is safe because a majority stored the entry." For entries from earlier terms that is not enough; the commit rule and election restriction together provide safety.
• "The numbers show how these systems perform today." They describe specific clusters and workloads years ago; study the method, not the values.
• "The Raft paper fully mechanically verifies Raft." Its mechanized proof covers one property and relies on unchecked invariants; the rest is an informal proof.

How to approach it

Pair each paper with its lab: MapReduce with Lab 1, Raft with Labs 3–4. Fill the paper guides' structured notes, and after each lab revisit which claims your tests actually exercised. In interviews, be ready to explain a guarantee with its model in one minute and a measured result with its caveats in another.