स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.)