सSaral Shiksha Yojna
Courses/Distributed Systems

Distributed Systems

CS3.401
Prof. Kishore Kothapalli•Monsoon 2025-26•4 credits
Sample Papers/Mock paper · PAPER 2 — 100 marks

Mock paper · PAPER 2 — 100 marks

Duration: 180 min • Max marks: 100

Section A — Multiple Choice (10 × 2 = 20 marks)

20 marks
  1. 1.Which of the following is NOT a challenge specific to distributed systems? **(A)** Unreliable communication **(B)** Lack of global knowledge **(C)** Branch prediction misses **(D)** Lack of synchronisation across nodes2 m
  2. 2.In Lamport's scalar clock, the receive rule on getting message m with timestamp Cmsg is: **(A)** Ci := Cmsg + 1, then deliver **(B)** Ci := max(Ci, Cmsg), then Rule 1, then deliver **(C)** Ci := Ci + Cmsg, then deliver **(D)** Ci := min(Ci, Cmsg), then deliver2 m
  3. 3.Acharya--Badrinath's snapshot algorithm assumes channels are: **(A)** FIFO **(B)** Causal **(C)** Non-FIFO **(D)** Synchronous2 m
  4. 4.The synchronization delay of Suzuki--Kasami's algorithm when the requesting node does NOT already hold the token is: **(A)** Zero **(B)** Maximum message transmission time **(C)** 2 × max message transmission time **(D)** O(log N)2 m
  5. 5.Which algorithm uses 'probes' that travel in the OPPOSITE direction of WFG edges? **(A)** Chandy--Misra--Haas **(B)** Mitchell--Merritt **(C)** Ho--Ramamoorthy **(D)** Chandy's diffusion2 m
  6. 6.Lamport--Shostak--Pease's Byzantine Agreement algorithm requires how many pulses to tolerate t Byzantine faults? **(A)** t pulses **(B)** t + 1 pulses **(C)** 2t pulses **(D)** log t pulses2 m
  7. 7.Which property does the 3PC protocol provide that 2PC does NOT? **(A)** Atomicity **(B)** Tolerance of Byzantine failures **(C)** Non-blocking under bounded fail-stop failures **(D)** Lower message overhead2 m
  8. 8.In Raft, when a follower receives an RPC with a higher term than its own, it should: **(A)** Reject the RPC **(B)** Start a new election **(C)** Update its term and become a follower (or stay one) **(D)** Increment its own term to match2 m
  9. 9.In GHS, an edge marked as 'reject' means: **(A)** It belongs to the MST **(B)** Both endpoints are in the same fragment **(C)** It is currently being tested **(D)** Its weight is unknown2 m
  10. 10.In GFS, leases are granted by the master to: **(A)** Clients, to authorize them to write **(B)** One replica per chunk, designating it as the primary **(C)** Chunkservers, to allow them to delete chunks **(D)** Applications, to lock files2 m

Section B — Multiple Select (5 × 4 = 20 marks)

20 marks
  1. 1.Which of the following are TRUE about matrix clocks? **(A)** mt[i,i] is the local logical clock of process pi **(B)** Row mt[i, *] is equivalent to pi's vector clock **(C)** They can be used to safely discard obsolete messages **(D)** Message overhead per send is O(n)4 m
  2. 2.Which of the following correctly describe the Lai--Yang snapshot algorithm? **(A)** It works on non-FIFO channels **(B)** Every process is initially red and turns white upon snapshot **(C)** White messages were sent before the sender recorded its snapshot **(D)** Channel state is computed as white messages sent minus white messages received4 m
  3. 3.Identify the strategies for handling deadlocks in distributed systems: **(A)** Deadlock Prevention **(B)** Deadlock Imitation **(C)** Deadlock Avoidance **(D)** Deadlock Detection4 m
  4. 4.Which of the following are valid mechanisms or messages in Maekawa's V2? **(A)** FAILED **(B)** INQUIRE **(C)** RELINQUISH / YIELD **(D)** PROBE4 m
  5. 5.Which of the following are TRUE about Byzantine Agreement? **(A)** Impossible deterministically in asynchronous systems even with one crash **(B)** Requires n ≥ 3f + 1 in synchronous setting **(C)** Lower bound on rounds is f + 1 **(D)** Achievable with n = 2f + 1 in synchronous setting4 m

Section C — Short Answer (4 × 5 = 20 marks)

20 marks
  1. 1.Differentiate between logical concurrency and physical concurrency. Can two events be logically concurrent but not physically concurrent? Justify with an example.5 m
  2. 2.What is the Singhal--Kshemkalyani differential technique? What problem does it solve, and what extra storage does each process require?5 m
  3. 3.Explain the four states of a file region in GFS after a mutation: consistent, defined, undefined, and inconsistent.5 m
  4. 4.Explain why the simple version of Maekawa's algorithm can deadlock. What property of the quorum design makes this possible despite the intersection requirement?5 m

Section D — Long Answer (4 × 10 = 40 marks)

40 marks
  1. 1.Describe the Chandy--Lamport snapshot algorithm in detail. State the marker sending rule and marker receiving rule. Explain why it requires FIFO channels and what the termination condition is. Also state the message complexity and prove that conditions C1 and C2 are satisfied.10 m
  2. 2.Explain the synchronous Byzantine Agreement problem. State the impossibility result for N = 3 and f = 1 using a three-scenario argument. Then describe the Phase King algorithm and explain why having f + 1 phases (with one guaranteed non-malicious king) is sufficient to reach agreement.10 m
  3. 3.Describe in detail the GFS write protocol from client request to acknowledgement. Cover: how a primary is determined, the role of leases and version numbers, how data flow differs from control flow, and the role of the primary in ordering writes. Then list at least three failure modes that can leave the file region in inconsistent or undefined state.10 m
  4. 4.Describe Suzuki--Kasami's broadcast algorithm. State what the token contains, what data structures each non-token-holder maintains, and the three rules (Request CS / On receiving REQUEST / Release CS). Discuss its message complexity and synchronization delay in both best and worst cases.10 m

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