सSaral Shiksha Yojna
Courses/Distributed Systems

Distributed Systems

CS3.401
Prof. Kishore Kothapalli•Monsoon 2025-26•4 credits
Sample Papers/200-mark paper · PAPER D — 200 marks

200-mark paper · PAPER D — 200 marks

Duration: 180 min • Max marks: 200

Section A — Short Answer Questions [3 marks each]

30 marks
  1. 1.Distinguish NTP stratum 0 from stratum 1. Why is stratum 0 not directly used by clients?3 m
  2. 2.Compare 2PC, 3PC, and Paxos on three dimensions: blocking behavior, message complexity, fault tolerance.3 m
  3. 3.In Singhal-Kshemkalyani's vector clock optimization, what is the purpose of the LU array (Last Update)? How does it differ from the LS array (Last Sent)?3 m
  4. 4.Sketch (1-2 lines) why Maekawa's quorum size cannot be smaller than √N. What property does this come from?3 m
  5. 5.Give one DIFFERENT example each of inherent and accidental complexity in distributed programming (different from previous papers).3 m
  6. 6.Chord successor list: what is its purpose, and what is its typical size? How does it differ from the finger table?3 m
  7. 7.Define causal-order broadcast vs total-order broadcast. Which is strictly stronger?3 m
  8. 8.In Raymond's algorithm, suppose a non-leaf node has exactly ONE child. Does the algorithm still function correctly? Discuss any inefficiency.3 m
  9. 9.GFS snapshots are described as 'cheap.' What specifically makes them cheap compared to a naïve file copy?3 m
  10. 10.Quick comparison: Cassandra vs DynamoDB --- list two key differences in their data model or consistency model.3 m

Section B — Medium Answer Questions [5 marks each]

50 marks
  1. 1.CAP applied: A global content delivery network (CDN) caches static web assets across regions. Discuss the C/A/P trade-off. How does the CDN typically resolve it?5 m
  2. 2.Vector Clock Numerical (3 processes, longer trace): Events sequence --- (1) P1: local, (2) P1: send m1 to P2, (3) P2: receive m1, (4) P2: local, (5) P2: send m2 to P3, (6) P3: local, (7) P3: receive m2, (8) P3: send m3 to P1, (9) P1: receive m3. Compute vector timestamps for all 9 events.5 m
  3. 3.Matrix Clock Numerical: 3 processes; P1 sends a message to P2 carrying its matrix. Initial matrices all-zero. P1 has done 2 local events; P2 has done 1; P3 has done 3 (independently). P1 sends to P2. Compute P2's matrix BEFORE and AFTER receiving P1's message.5 m
  4. 4.Lamport Mutex with FIFO Violation: 3 processes. P1 sends REQUEST(ts=1) then RELEASE on channel C12, but due to a FIFO violation, RELEASE arrives before REQUEST at P2. Describe what goes wrong and how it manifests.5 m
  5. 5.Suzuki-Kasami Concurrent Requests: P1 and P2 both broadcast REQUEST at almost the same time (both with sn=1). Token is at P4. Network delays cause REQUEST(2, 1) to arrive at P4 first, then REQUEST(1, 1). Trace the protocol carefully --- what happens to the second request?5 m
  6. 6.Mitchell-Merritt Priority Extension: 3 processes blocked in a cycle, with public labels P1=7, P2=7, P3=12. Equal labels at P1 and P2 --- explain how the priority extension breaks the tie and resolves deadlock.5 m
  7. 7.Byzantine with N=6, f=2: Determine if agreement is solvable. If yes, state the bound that justifies it and the round complexity. If no, explain the impossibility.5 m
  8. 8.Raft Leader Election Trace: 5 servers S1-S5. Leader is S1 (term 3). S1 crashes. Random timeouts: S2 expires first (term 4), broadcasts RequestVote. S3 votes yes; S4 expires shortly after, broadcasts RequestVote (term 4 also). Trace the election outcome.5 m
  9. 9.GHS on Star Graph: 6 nodes --- central node C connected to leaves L1, L2, L3, L4, L5 with edge weights 1, 2, 3, 4, 5 respectively. Trace the MST construction.5 m
  10. 10.Chord Node Leave: Ring has nodes at IDs {2, 7, 13, 20, 25} with m = 5. Node 13 leaves gracefully. Currently node 13 holds items with hash values 8, 10, 12, 13. Show where these items go and update the affected finger tables.5 m

Section C — Long Answer Questions [10 marks each]

120 marks
  1. 1.Time Synchronization --- Use Cases and Choice **a.** For each of: (i) GPS-coordinated distributed sensors, (ii) cluster of databases in a single data center, (iii) blockchain validators globally, (iv) financial trading systems --- recommend the appropriate synchronization protocol (Cristian / Berkeley / NTP / logical clocks). Justify. **b.** Discuss why GPS-time itself is insufficient for distributed consensus, even though it's highly accurate.10 m
  2. 2.Vector Clock Optimization Trade-offs **a.** Describe Singhal-Kshemkalyani's optimization in full detail: LS array, LU array, message format, and the update rules. **b.** Why does this optimization REQUIRE FIFO channels? Construct a non-FIFO scenario where it fails. **c.** Quantify: for N=100 processes where each message changes only 5 clock entries on average, what's the storage reduction vs full vector clock piggybacking?10 m
  3. 3.Acharya-Badrinath Snapshot --- Full Trace and Correctness **a.** Describe the algorithm in detail: token broadcast, local snapshot, SENT/RECD arrays, channel state inference. **b.** Trace on 3 processes P1, P2, P3 with the following pre-snapshot activity: P1 → P2: 2 messages (1 received); P2 → P3: 1 message (received); P3 → P1: 1 message (in transit when snapshot starts). Compute SENT, RECD, and channel states. **c.** Argue why causal channels are required (FIFO insufficient).10 m
  4. 4.Mutex Robustness to Failures **a.** For each of Lamport, Ricart-Agarwala, Maekawa, Suzuki-Kasami, Raymond: state how it behaves if one process CRASHES while holding the right to enter CS (or holding the token). **b.** Among these, which is most resilient to crashes? Most fragile? Justify. **c.** What modifications would you propose to make Suzuki-Kasami crash-tolerant?10 m
  5. 5.Deadlock Strategies --- Prevention vs Avoidance vs Detection **a.** Describe each strategy at a conceptual level. State one classical algorithm for each. **b.** In a distributed system with frequent CS contention, which strategy would you choose? Justify with cost-benefit. **c.** Why is prevention rarely used in distributed systems despite its simplicity?10 m
  6. 6.Lamport-Shostak-Pease OM(2) Trace **a.** Describe OM(2) for N=7, t=2 in detail: pulse structure, recursion depth. **b.** Trace the algorithm with the source broadcasting value v=0 and two faulty lieutenants (L5, L6). Show how honest lieutenants reach consensus.10 m
  7. 7.Commit Protocols --- Failure Recovery Comparison **a.** Tabulate how 2PC, 3PC, and Raft-based commit handle each failure mode: (i) participant crash before vote, (ii) participant crash after vote, (iii) coordinator crash before any commit message, (iv) coordinator crash after some commits sent. **b.** For each, indicate which scenarios result in BLOCKING vs progressing.10 m
  8. 8.GFS Write Fault Tolerance --- Deep Dive **a.** Describe what happens during a write if: (i) the client crashes mid-protocol, (ii) the primary chunkserver crashes, (iii) one secondary chunkserver crashes. **b.** How does version numbering ensure that stale replicas are never elected as primary?10 m
  9. 9.Consistent Hashing --- Properties Proofs **a.** Define formally and prove the BALANCE property: with random hash function, each bucket gets approximately K/N items in expectation (K items, N buckets). **b.** Define and prove MONOTONICITY: when a new bucket joins, only items hashing to its newly-acquired arc move. **c.** Why do virtual nodes improve the balance bound from O(log N / N) to closer to 1/N?10 m
  10. 10.MPC Selection --- Complete Walkthrough **a.** State the k-th smallest selection problem in MPC. Describe the high-level algorithm using median-of-medians. **b.** Compute the round complexity assuming S = N\^ε per machine. Show the recurrence and solve it. **c.** Total work (sum of computation across all machines): is it O(N) or higher? Justify.10 m
  11. 11.Phase King Correctness --- Inductive Proof **a.** State the invariant maintained at the end of the first phase with an honest king (call this 'good phase K'). **b.** Prove the invariant assuming n \> 4f, covering all sub-cases of process behavior in that phase. **c.** Argue by induction that the invariant is preserved through all subsequent phases (even with malicious kings).10 m
  12. 12.Termination Detection --- Comprehensive Robustness **a.** Tabulate how weight-throwing and Dijkstra-Scholten handle each failure mode: (i) delayed messages, (ii) lost messages, (iii) duplicated messages, (iv) process crashes, (v) network partitions. **b.** Identify the single biggest weakness of each algorithm. Propose a high-level mitigation strategy.10 m

Track your attempt locally — score and time are recorded in your browser. (Coming soon: timed-attempt mode.)