Distributed Systems
CS3.401Prof. Kishore Kothapalli•Monsoon 2025-26•4 credits
PYQ-style paper · Paper 1 — End Semester (April-2025 style)
Duration: 180 min • Max marks: 57
Part A — Short Answers [3 marks each]
15 marks- 1.Termination Detection: Explain for each situation below whether the Dijkstra-Scholten spanning-tree based termination detection algorithm will work correctly. **a.** Lossy channels (messages or ACKs may be dropped) **b.** Non-FIFO message delivery **c.** Multiple processes simultaneously initiating the algorithm3 m
- 2.Given two vector clocks VC_A = [4, 2, 3] (at P1) and VC_B = [3, 5, 2] (at P3) in a 3-process system. Identify the causal relationship between events e_A and e_B. Justify and explain what each component value tells us about knowledge of other processes.3 m
- 3.True / False with explanation: **a.** In consistent hashing, when a new bucket is added to the system, only a constant number of items (O(1) on average) need to be remapped. **b.** The Maekawa algorithm satisfies fairness --- requests are served in strict timestamp order.3 m
- 4.Acharya-Badrinath algorithm vs Chandy-Lamport: Suppose channels are FIFO but NOT causal. Will Acharya-Badrinath's algorithm still produce a consistent snapshot? Justify.3 m
- 5.CAP applied: A globally distributed payment processing system handles inter-bank transactions. State which of C, A, P it must prioritize and justify in 2-3 lines.3 m
Part B — Long Answers
42 marks- 1.Distributed MST **a.** Explain the role of \"level\" and \"fragment name\" in the GHS algorithm. Why are both needed? **b.** Show that the merge rules (Rule A and Rule B) never create cycles. List at least two structural invariants the algorithm maintains. **c.** State the message complexity of GHS in terms of N (nodes) and E (edges). Justify briefly.10 m
- 2.Mutual Exclusion --- Raymond's Algorithm Variants12 m
- 3.Phase King --- Failure Scenario10 m
- 4.Commit Protocols and Raft **a.** Describe a scenario where 2PC blocks indefinitely but 3PC would not. Explain how 3PC's pre-commit phase avoids the block. **b.** In Raft, when a leader commits a log entry, how is it guaranteed that the entry will survive any future leader election? **c.** Can Raft be used to implement a commit protocol like 2PC? Discuss one advantage and one disadvantage.10 m
Track your attempt locally — score and time are recorded in your browser. (Coming soon: timed-attempt mode.)