Distributed Systems
CS3.401Prof. Kishore Kothapalli•Monsoon 2025-26•4 credits
PYQ-style paper · Paper 2 — End Semester (Monsoon-2025 style)
Duration: 180 min • Max marks: 60
Section A — Short Answer Questions (20 points across 8 questions)
0 marks- 1.Explain the difference between causal and FIFO message delivery. Give a 3-process scenario where FIFO is preserved but causal is violated. *[2.5 marks]*
- 2.Given two matrix clocks M1 and M2 at processes Pi and Pj respectively. If M1[k][k] ≤ M2[k][k] for ALL k (diagonals), what can we infer about the events at Pi and Pj? Justify briefly. *[2.5 marks]*
- 3.State the CAP theorem in brief. A real-time stock-trading exchange (where every order must be globally serialized) is being deployed across two data centres. Which of C, A, P should the system prioritize? Justify in 2-3 lines. *[2.5 marks]*
- 4.Termination Detection: Explain the weight-throwing algorithm briefly. Discuss whether it works correctly when (a) a message is duplicated by the network, and (b) a process crashes while holding non-zero weight. *[2.5 marks]*
- 5.GFS leases: What is the purpose of a chunk lease? What happens if the master cannot communicate with the lease holder for an extended period (e.g., due to network partition)? *[2.5 marks]*
- 6.Virtual nodes in consistent hashing: What problem do they solve? Briefly explain with reference to load distribution skew. *[2.5 marks]*
- 7.Distinguish between accidental complexity and inherent complexity in distributed programming. Give one example of each. *[2.5 marks]*
- 8.Wait-For Graph: True / False with explanation: 'In the AND request model, a process P is deadlocked if and only if P lies on a cycle in the wait-for graph.' *[2.5 marks]*
Section B — Long Answer Questions (60 points across 6 questions)
60 marks- 1.Suzuki-Kasami Algorithm **a.** Describe the data structures: token contents (Q and LN), and per-process RN array. Explain what each entry tracks. **b.** Explain why the condition RNj[i] = LN[i] + 1 is essential. What can go wrong if this check is dropped --- give a concrete example. **c.** Argue that the algorithm is starvation-free, despite being broadcast-based rather than timestamp-priority based.10 m
- 2.Distributed MST --- GHS **a.** State and PROVE the Cut Property of MST (assuming distinct edge weights). **b.** In GHS, why is the lowest-weight outgoing edge of a fragment guaranteed to be in the MST? Cite the property used. **c.** Show that the maximum level any fragment can reach during the execution is ⌊log₂ N⌋.10 m
- 3.Phase King --- Boundary Analysis **a.** State the agreement, validity, and termination properties required of a Byzantine agreement protocol. **b.** Explain why Phase King requires n \> 4f. Derive the threshold mult \> n/2 + f from the correctness argument. **c.** For n = 10, f = 3 (so 3f = 9 \< n = 10 \< 4f = 12), show a brief execution where Phase King fails to achieve agreement.10 m
- 4.Dynamo and Consistent Hashing **a.** Explain how Dynamo achieves high availability for writes (sometimes called 'always writeable') and the role of the N, W, R parameters. **b.** What is the W + R \> N quorum invariant? What strong consistency guarantee does it provide when satisfied? **c.** How does Dynamo handle conflicting concurrent writes? Describe the use of vector clocks with a 2-replica example.10 m
- 5.Chord Overlay Network **a.** Consider Chord with m = 4 (so 16 possible IDs). Suppose nodes are at IDs {1, 4, 9, 11, 14}. Compute the finger table of the node at ID = 4. **b.** Explain how lookup(key) works in Chord and argue O(log N) hop complexity. **c.** When a node leaves the system gracefully, what items need to be moved and to which node? Explain monotonicity (no item moves multiple times).10 m
- 6.Distributed BFS in the MPC Model10 m
Track your attempt locally — score and time are recorded in your browser. (Coming soon: timed-attempt mode.)