सSaral Shiksha Yojna
Courses/Distributed Systems

Distributed Systems

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

Answer Structure Templates

University exams reward formatting. Use these.

Algorithm trace (DME / snapshot / consensus)

  1. State assumptions (FIFO? synchronous? failure model? N? f?).
  2. List per-site data structures.
  3. Number the rules (Request / Receive / Enter / Release).
  4. Show the message timeline with timestamps on a diagram.
  5. State termination condition.
  6. Quote complexity (msgs, rounds, sync delay).

Compare-and-contrast (clocks / DME / 2PC vs 3PC / OM vs Phase King)

  1. One-line shared definition.
  2. Side-by-side table (≥ 5 rows: msgs, rounds, assumption, channel, failure model).
  3. State the failure mode of the weaker option with a concrete example.
  4. Conclude with 'when to use which'.

Impossibility / lower-bound proof (Byzantine, FLP)

  1. State the problem precisely (synchronous? async? f bound?).
  2. Set up the adversarial scenario (constructive: faulty source sends conflicting values).
  3. Derive the contradiction (loyal nodes can't distinguish two scenarios).
  4. Quote the bound (n ≥ 3f+1, f+1 rounds).
  5. Cite the seminal result (FLP, Lamport-Shostak-Pease).

Correctness argument (safety / liveness)

  1. State safety property (at most one in CS).
  2. State liveness property (every requester eventually enters).
  3. Invariant-based safety argument.
  4. Bounded-pending-requests liveness argument.
  5. Note fairness (FIFO timestamp order).

Architecture case-study (GFS, Spanner, Raft, Dynamo)

  1. Workload assumptions (large files? append-mostly? globally consistent?).
  2. Three-pillar architecture diagram (control plane, data plane, client).
  3. Failure model + recovery mechanism.
  4. Consistency story (defined / eventually consistent / linearizable).
  5. Trade-off summary against alternatives.

Numerical (msg count / round count / chunk arithmetic)

  1. List N, f, K, etc.
  2. Write the formula symbolically.
  3. Substitute numbers.
  4. Show intermediate arithmetic.
  5. Box final answer with units.