Distributed Systems
CS3.401Prof. Kishore Kothapalli•Monsoon 2025-26•4 credits
Mock paper · PAPER 5 — 100 marks
Duration: 180 min • Max marks: 100
Section A — Multiple Choice (10 × 2 = 20 marks)
20 marks- 1.Which of these is the strongest message-ordering model? **(A)** Non-FIFO **(B)** FIFO **(C)** Causal **(D)** Random2 m
- 2.In Lamport's scalar clock, before executing any event (send, receive, or internal), a process must: **(A)** Reset its clock to 0 **(B)** Increment its clock by d (d \> 0) **(C)** Broadcast its current clock to all **(D)** Wait for a global tick2 m
- 3.Which of the following snapshot algorithms uses message colouring? **(A)** Chandy--Lamport **(B)** Lai--Yang **(C)** Acharya--Badrinath **(D)** Alagar--Venkatesan2 m
- 4.Maekawa's algorithm achieves message complexity of: **(A)** O(N) **(B)** O(log N) **(C)** O(√N) **(D)** O(N log N)2 m
- 5.If 12 processes participate in Byzantine Agreement, what is the maximum number that can be Byzantine while keeping agreement solvable? **(A)** 2 **(B)** 3 **(C)** 4 **(D)** 52 m
- 6.The Mitchell--Merritt deadlock detection algorithm works on the: **(A)** AND model **(B)** Single resource request model **(C)** OR model **(D)** AND-OR model2 m
- 7.The Lamport--Shostak--Pease algorithm tolerates t Byzantine failures using a recursive procedure that operates over how many participating processes at each recursion level? **(A)** Doubles at each level **(B)** Decreases by 1 (N, N − 1, N − 2, ...) **(C)** Stays at N throughout **(D)** Halves at each level2 m
- 8.Which is TRUE about 2PC's behavior under network partitioning? **(A)** 2PC violates atomicity under any partition **(B)** If coordinator and all participants are in the same partition, the protocol is unaffected **(C)** 2PC automatically resolves partitions via leader election **(D)** Partitioning has no effect since 2PC ignores network state2 m
- 9.The Cut Property of MSTs (with distinct edge weights) states that: **(A)** The heaviest edge in any cycle is in the MST **(B)** The lightest edge crossing any cut is in the MST **(C)** Every cut contains exactly one MST edge **(D)** The MST has exactly N edges2 m
- 10.In GFS, stale replicas are detected via: **(A)** Checksums on each chunk **(B)** Chunk version numbers maintained by the master **(C)** Periodic full-replica comparison **(D)** Heartbeats containing data hashes2 m
Section B — Multiple Select (5 × 4 = 20 marks)
20 marks- 1.Which of the following pairs are correctly associated (concept --- algorithm)? **(A)** Markers --- Chandy--Lamport **(B)** White/Red colouring --- Lai--Yang **(C)** SENT/RECD arrays --- Acharya--Badrinath **(D)** Probes --- Phase King4 m
- 2.Which of the following are TRUE about logical-clock comparison? **(A)** Vector clocks are strongly consistent **(B)** Scalar clocks alone induce a total order over events **(C)** Matrix clocks include vector clocks as rows **(D)** Matrix clocks enable safe discarding of obsolete information4 m
- 3.Which of the following statements about distributed mutual exclusion are TRUE? **(A)** Suzuki--Kasami's worst-case message count per CS is N **(B)** Raymond's tree-based algorithm has O(log N) message complexity **(C)** Lamport's algorithm requires bidirectional channels **(D)** Maekawa's algorithm always terminates without additional messages4 m
- 4.Which of the following are TRUE about the GFS master? **(A)** Metadata is kept in memory at the master **(B)** The master is on the data path for every read/write **(C)** Operation log is replicated on multiple remote machines **(D)** The master uses checkpointing to keep the operation log small4 m
- 5.Which of the following are TRUE about Byzantine Agreement? **(A)** No solution exists if n \< 3m + 1 **(B)** No solution exists in an asynchronous system even with 1 faulty process **(C)** Lower bound on rounds is m + 1 **(D)** Validity says all processes must decide on the source's value, even if source is faulty4 m
Section C — Short Answer (4 × 5 = 20 marks)
20 marks- 1.What is a fragment in GHS? When is a single edge added to the MST, and what determines whether an edge is internal vs. outgoing in the algorithm?5 m
- 2.Explain the role of LN[1..n] in Suzuki--Kasami's algorithm. Why is the condition RNj[i] = LN[i] + 1 used before sending the token to a requester?5 m
- 3.What are the four states of a node and the three states of an edge in the GHS algorithm? Briefly explain the transition between edge states.5 m
- 4.Explain why Byzantine Agreement is impossible for N = 3 processes when one can be faulty. Use the three-scenario argument briefly.5 m
Section D — Long Answer (4 × 10 = 40 marks)
40 marks- 1.Compare and contrast the five mutual-exclusion algorithms covered in the course: Lamport's, Ricart--Agrawala, Maekawa, Suzuki--Kasami, and Raymond. For each, specify: type (token / non-token), message complexity per CS, synchronization delay, FIFO requirement, and any distinctive features.10 m
- 2.Describe the Lai--Yang snapshot algorithm for non-FIFO channels in detail. Explain how messages and processes are coloured, when a process records its snapshot, how channel state is computed (formula), and the storage overhead. Compare with Chandy--Lamport.10 m
- 3.Describe Chandy--Misra--Haas's distributed edge-chasing deadlock detection algorithm for the AND model. State the format of a probe, the rules for sending and receiving probes, the conditions checked at the receiver, and the moment of deadlock declaration. Argue informally why the algorithm is correct (no false deadlocks under steady state).10 m
- 4.Describe the architecture of GFS in detail. Cover: the three component types (master, chunkservers, clients), what metadata the master holds, how the master is made fault-tolerant, the role of heartbeats, replica placement, re-replication, rebalancing, and garbage collection. Explain how GFS supports snapshots via copy-on-write.10 m
Track your attempt locally — score and time are recorded in your browser. (Coming soon: timed-attempt mode.)