स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.)