सSaral Shiksha Yojna
Courses/Distributed Systems

Distributed Systems

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

Mock paper · PAPER 1 — 100 marks

Duration: 180 min • Max marks: 100

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

20 marks
  1. 1.The CAP theorem states that a networked shared-data system can strongly guarantee at most: (A) All three of C, A, and P simultaneously (B) Any two of Consistency, Availability, and Partition tolerance (C) Only Consistency and Partition tolerance, never Availability (D) Only Availability since partitions are inevitable2 m
  2. 2.Lamport's mutual-exclusion algorithm requires which channel guarantee? (A) Non-FIFO is acceptable (B) Causal ordering (C) FIFO channels (D) Synchronous channels2 m
  3. 3.Which of the following statements about Lamport's scalar clock is TRUE? (A) Scalar clocks are strongly consistent (B) C(e1) \< C(e2) implies e1 happened-before e2 (C) e1 → e2 implies C(e1) \< C(e2) (D) Two events at different processes can never share a timestamp2 m
  4. 4.The Chandy--Lamport snapshot algorithm has a message complexity of: (A) O(N²) where N is the number of processes (B) O(|E|) where E is the set of links (C) O(N log N) (D) 2N2 m
  5. 5.In Maekawa's algorithm, the size of each request set Ri is: (A) N − 1 (B) log N (C) √N (D) N/22 m
  6. 6.Byzantine Agreement with n processes can tolerate at most f faulty processes when: (A) n ≥ 2f + 1 (B) n ≥ 3f + 1 (C) n ≥ f + 1 (D) n ≥ 4f − 12 m
  7. 7.In the OR resource-request model, deadlock corresponds to: (A) A simple cycle in the WFG (B) A self-loop in the WFG (C) A knot in the WFG (D) Any source node with no outgoing edges2 m
  8. 8.The blocking problem in 2PC occurs when: (A) The coordinator times out waiting for prepare replies (B) A participant has \<ready T\> in its log but cannot determine commit/abort because the coordinator failed (C) Two transactions deadlock (D) A site receives a duplicate commit message2 m
  9. 9.In Raft, the role of randomized election timeouts is primarily to: (A) Reduce the term number (B) Prevent split votes among candidates (C) Allow Byzantine fault tolerance (D) Synchronize physical clocks2 m
  10. 10.In GFS, the default size of a chunk is: (A) 4 KB (B) 1 MB (C) 64 MB (D) 1 GB2 m

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

20 marks
  1. 1.Which of the following are required features of a distributed system? (A) A large number of computers (B) A globally shared clock (C) Processes that execute concurrently (D) Processes that fail independently4 m
  2. 2.Which statements about vector clocks are TRUE? (A) They are strongly consistent (B) Two timestamps vh and vk are concurrent iff neither vh \< vk nor vk \< vh (C) Message overhead per send is O(1) (D) They can detect causal precedence directly from timestamps4 m
  3. 3.Identify the algorithms that are TOKEN-based mutual exclusion protocols: (A) Lamport's algorithm (B) Suzuki--Kasami algorithm (C) Maekawa's algorithm (D) Raymond's tree algorithm4 m
  4. 4.Which of the following are TRUE about the Chandy--Lamport snapshot algorithm? (A) It works correctly on non-FIFO channels (B) The recorded global state may not have actually occurred in real execution (C) Markers separate pre-snapshot from post-snapshot messages on a channel (D) It uses message colouring (white/red) to distinguish messages4 m
  5. 5.Which statements about GFS write semantics are correct? (A) Concurrent successful writes produce defined regions (B) Concurrent successful writes produce consistent but possibly undefined regions (C) If any secondary fails, the data region is inconsistent (D) Atomic record append can introduce duplicates if a replica fails and the client retries4 m

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

20 marks
  1. 1.State the two conditions C1 and C2 for a global state to be consistent. Briefly explain each in plain English.5 m
  2. 2.Give the formal upper and lower bounds on the actual server time in Cristian's algorithm. Define each symbol used.5 m
  3. 3.Compare Lamport's and Ricart--Agrawala's mutual-exclusion algorithms on three metrics: message count per CS, FIFO requirement, and types of messages used.5 m
  4. 4.Explain why the recorded global state from Chandy--Lamport may be useful for detecting stable properties even though it might not correspond to any real instantaneous state.5 m

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

40 marks
  1. 1.Describe Maekawa's mutual-exclusion algorithm in detail. State the four properties that request sets must satisfy. Show with an example of 7 processes and quorums S0..S6 how a deadlock can occur in the simple version. Explain how V2 of the algorithm uses FAILED, INQUIRE, and YIELD messages to resolve deadlock.10 m
  2. 2.Prove that vector clocks are strongly consistent, i.e., ei → ej ⇔ vi \< vj. Cover both directions of the implication with a clear argument including the same-process, send/receive, and concurrent-event cases.10 m
  3. 3.Explain the Two-Phase Commit (2PC) protocol. Describe Phase 1 and Phase 2 in detail, the log records written at each step, and how a recovering participant decides what to do for transactions in each of the four log-state cases. End by explaining the blocking problem.10 m
  4. 4.Describe the Gallager--Humblet--Spira (GHS) distributed MST algorithm. Define a fragment, state the three combining rules (A, B, C), and prove that the maximum level a node can have is log N.10 m

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