सSaral Shiksha Yojna
Courses/Distributed Systems

Distributed Systems

CS3.401
Prof. Kishore Kothapalli•Monsoon 2025-26•4 credits
Sample Papers/PYQ-style paper · Paper 1 — End Semester (April-2025 style)

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. 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. 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. 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. 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. 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. 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. 2.Mutual Exclusion --- Raymond's Algorithm Variants12 m
  3. 3.Phase King --- Failure Scenario10 m
  4. 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.)