सSaral Shiksha Yojna
Courses/Distributed Systems

Distributed Systems

CS3.401
Prof. Kishore Kothapalli•Monsoon 2025-26•4 credits

Last-Week Revision Pack

Every item below is something you should be able to recall cold by exam morning. It is not a study list — it is a triage list for the final 5–7 days.

How to use this page (last 5–7 days)

  1. Day −7 to −3:Read every item top-to-bottom. For any item you can't expand into a 2-minute explanation, open the linked unit/chapterand re-learn it. Don't move on until you can recall the item without looking.
  2. Day −2 to −1: Re-read only — speak each item aloud. If you stumble, mark it mentally and drill it twice more.
  3. Exam morning:Skim once, fast. Don't deep-dive anything. The goal is retrieval priming, not learning.

What each tag means and what to do with it

  • CheatsheetA pointer to a fast-skim page in this course. Open it and re-read in the order suggested. 2–5 minutes per item.
  • High YieldA topic almost certain to appear on the exam. Allocate revision time proportional to its expected mark weight — not equal time per item. Drill until you can answer without notes.
  • Weak AreaA topic the cohort historically struggles with. Treat as high-priority and verify your understanding by explaining it aloud or writing a one-paragraph answer.
  • FormulaAn equation you must reproduce verbatim. Write it out from memory once per day until exam day. If you can't derive it, also re-read the relevant chapter.
  • Memory TriggerA "if you see X → reach for Y" cue for the exam room. Memorise the mapping; you'll only have seconds to recall it under pressure. Pair with the linked framework.
  • DerivationA multi-step proof or derivation. Write it from blank paper — not just read. Re-do until you can produce it in under 5 minutes.
  • Common MistakeA specific error the cohort routinely makes. Memorise the correction and the right phrasing — this is the cheapest mark you can save.
Track your progress:mark the page "Finished" (top-right) once you can recall every item below without looking.

The pack (23 items)

1 Cheatsheet · 5 High Yield · 5 Memory Trigger · 3 Formula · 2 Derivation · 3 Weak Area · 4 Common Mistake
CheatsheetRe-skim the DS cheatsheet in this order: CAP → clocks → snapshots → DME table → deadlock models → Byzantine bounds → 2PC/3PC → Raft → GHS → GFS. The DME comparison table is the densest single piece of marks per minute.High YieldLamport DME = 3(N-1) msgs. Ricart-Agrawala = 2(N-1). Maekawa = 3√N (V1) to 5√N (V2). Suzuki-Kasami = 0 or N. Raymond = O(log N).High YieldByzantine: n ≥ 3f+1 processes, ≥ f+1 rounds, impossible in async (FLP). Phase King needs n ≥ 4f+1 but is polynomial vs OM's exponential.High Yield2PC blocks when all participants have <ready T> but coordinator crashed before deciding. 3PC's PRE-COMMIT phase replicates decision intent → no blocking (but no-partition assumption).High YieldRaft = leader election (randomised timeouts) + log replication (AppendEntries majority commit) + safety (election restriction: most up-to-date log wins).High YieldGFS: single master, 64 MB chunks, 3× replicas across racks, atomic record append, leases serialise mutations, consistency states defined/consistent/undefined/inconsistent.Memory TriggerIf question says 'FIFO channels' → think Chandy-Lamport. 'Non-FIFO' → Lai-Yang. 'Causal' → Acharya-Badrinath.Memory TriggerIf question says 'strong consistency of logical clocks' → vector or matrix; scalar fails.Memory TriggerIf question says 'OR model deadlock' → KNOT (SCC with no outgoing edges), not just cycle.Memory TriggerIf question says 'discard obsolete messages' → MATRIX clock — min_k mt[k,i] ≥ t.Memory TriggerIf 'send only changed entries' → Singhal-Kshemkalyani; needs LS/LU arrays + FIFO.FormulaVector receive: ∀k V[k] = max(V[k], Vm[k]); then V[i]++. Causality: V(e) < V(e') iff component-wise ≤ with at least one strict.FormulaCrash-consensus = (f+1) rounds × n² msgs per round = (f+1)·n² total.FormulaGHS max level = log N. Level k fragment has ≥ 2^k nodes.DerivationWhy N=3, f=1 Byzantine is impossible: faulty source sends 0 to T, 1 to U → loyal T and U see indistinguishable scenarios but must disagree.DerivationWhy 2PC blocks: decision exists only at coordinator after all <ready>; if coord crashes, surviving participants can't tell commit vs abort.Weak AreaMaekawa V2 — memorise FAILED / INQUIRE / YIELD with one-liner each. Most students fumble the deadlock fix.Weak AreaGHS Rules A, B, C — practise on a 4-node graph until you can trace fragment merges by hand.Weak AreaPhase King algorithm — round 1 majority + multiplicity, round 2 king broadcast, adopt majority only if multiplicity > n/2 + f.Common MistakeDon't say 'scalar clocks capture causality both ways.' They only do e → e' ⇒ C(e) < C(e'). Converse fails — concurrent events can have ordered scalars.Common MistakeDon't say 'OR model deadlock iff cycle.' OR model needs a KNOT (SCC with no outgoing edges) — a cycle alone is insufficient.Common MistakeDon't say '2PC handles network partitions.' It does not — sites separated from coordinator block.Common MistakeDon't say 'GFS chunkservers store metadata.' Only the master stores metadata. Chunkservers store data + their own chunk listings reported via heartbeat.