Distributed Systems
CS3.401Prof. Kishore Kothapalli•Monsoon 2025-26•4 credits
Mock paper · PAPER 4 — 100 marks
Duration: 180 min • Max marks: 100
Section A — Multiple Choice (10 × 2 = 20 marks)
20 marks- 1.Consensus is impossible in asynchronous systems when: **(A)** There are more than 100 processes **(B)** Even one process may crash **(C)** Messages are FIFO-ordered **(D)** The network is fully connected2 m
- 2.In vector clocks, two timestamps vh and vk are concurrent (vh || vk) iff: **(A)** All components are equal **(B)** Some component of vh is less than the corresponding component of vk AND some component of vk is less than vh's **(C)** All components of vh are less than vk **(D)** Their sums are equal2 m
- 3.Maekawa's V1 simple algorithm can deadlock primarily because: **(A)** FIFO is not guaranteed **(B)** Quorums don't intersect **(C)** Concurrent requests can split the quorum votes, leaving no requester with a full set of replies **(D)** Messages can be lost2 m
- 4.Which of the following is an example of physical-clock synchronization? **(A)** Lamport's scalar clock **(B)** Vector clock **(C)** Cristian's algorithm **(D)** Matrix clock2 m
- 5.The number of messages required per CS execution in Ricart--Agrawala's algorithm is: **(A)** N − 1 **(B)** 2(N − 1) **(C)** 3(N − 1) **(D)** N²2 m
- 6.In Mitchell--Merritt's algorithm, deadlock is detected when: **(A)** A probe value returns to the originator **(B)** A node's PUBLIC label appears in a probe it receives back **(C)** Two probes meet at a node **(D)** A timer expires2 m
- 7.Which of the following is TRUE about the Lai--Yang snapshot algorithm? **(A)** It requires FIFO channels **(B)** Channel state is recorded using marker messages **(C)** White messages were sent before the sender's snapshot, red messages after **(D)** It has lower storage cost than Chandy--Lamport2 m
- 8.In Raft, a server becomes a candidate when: **(A)** It receives a heartbeat from another candidate **(B)** Its election timer expires without receiving a heartbeat **(C)** The leader explicitly demotes it **(D)** Half the cluster crashes2 m
- 9.GHS detects that the algorithm has terminated (the entire graph is one fragment) when: **(A)** Every node has level 1 **(B)** Both endpoints of the core edge report no outgoing edges (report ∞) **(C)** All edges are marked as 'branch' **(D)** The leader announces termination2 m
- 10.GFS uses copy-on-write for snapshots so that: **(A)** Snapshots can be encrypted in place **(B)** Snapshot creation is fast --- chunks are physically copied only on first write **(C)** Old chunks can be garbage-collected immediately **(D)** Snapshots are stored on different chunkservers2 m
Section B — Multiple Select (5 × 4 = 20 marks)
20 marks- 1.Which of the following are TRUE about Lamport's mutual-exclusion algorithm? **(A)** Requires FIFO channels **(B)** Message complexity is 2(N − 1) per CS **(C)** Uses three message types: REQUEST, REPLY, RELEASE **(D)** Synchronization delay equals max message transmission time4 m
- 2.Which statements about Acharya--Badrinath's snapshot algorithm are TRUE? **(A)** Requires causal channels **(B)** Uses arrays SENTi[1..N] and RECDi[1..N] **(C)** Total message count is 2n **(D)** Uses message colouring (white/red)4 m
- 3.Which of the following can cause inconsistent or undefined regions in GFS? **(A)** Primary write succeeds but a secondary fails **(B)** Concurrent successful writes from multiple clients **(C)** Atomic record append with a replica retry **(D)** Reading from a stale replica that missed a version-number increment4 m
- 4.Which of the following are TRUE about Raymond's tree-based algorithm? **(A)** Uses a token **(B)** Logical structure is a directed tree with token-holder as root **(C)** Each node has a Holder pointer to its parent on the path to the root **(D)** Message complexity is O(N) per CS4 m
- 5.Which of the following are valid types of failures studied in synchronous distributed systems? **(A)** Crash failure (fail-stop) **(B)** Byzantine failure **(C)** Timing failure (synchronous violation) **(D)** Quantum failure4 m
Section C — Short Answer (4 × 5 = 20 marks)
20 marks- 1.Explain the OR resource-request model. Define a knot and explain why a knot is the correct deadlock criterion in the OR model (as opposed to a simple cycle).5 m
- 2.What is event counting in Lamport's scalar clock (with d = 1)? What does the 'height' of an event represent?5 m
- 3.Describe the optimization in GHS where 'reject' messages need not always be sent. Why is this optimization valid?5 m
- 4.Briefly describe the Roucairol--Carvalho optimization over the Ricart--Agrawala algorithm. In the best case, how many messages are sent per CS execution?5 m
Section D — Long Answer (4 × 10 = 40 marks)
40 marks- 1.Describe the synchronous consensus algorithm for crash failures in detail. State the algorithm pseudocode, explain why exactly f + 1 rounds are required, prove that termination, validity, and agreement all hold, and compute the total number of messages.10 m
- 2.Describe Vector Clocks and Matrix Clocks. For each, state the data structure, update rules (R1, R2), and primary use case. Then explain the unique property of matrix clocks (the min over k of mt[k,i] ≥ t condition) and give an application of this property.10 m
- 3.Describe Maekawa's mutual-exclusion algorithm Version 2 in detail. State the role of FAILED, INQUIRE, and YIELD messages. Trace through a 3-process scenario (e.g., processes 0, 1, 2 with their quorums) showing how V2 resolves a deadlock that V1 would have suffered.10 m
- 4.Describe the GFS read and write protocols in full detail. Highlight how data flow is decoupled from control flow during writes, the role of the primary replica, leases, version numbers, and the pipelined data push. Also explain why concurrent writes can produce 'consistent but undefined' regions.10 m
Track your attempt locally — score and time are recorded in your browser. (Coming soon: timed-attempt mode.)