Distributed Systems
CS3.401Prof. Kishore Kothapalli•Monsoon 2025-26•4 credits
Mock paper · PAPER 3 — 100 marks
Duration: 180 min • Max marks: 100
Section A — Multiple Choice (10 × 2 = 20 marks)
20 marks- 1.Tanenbaum's definition of a distributed system emphasizes that: **(A)** It appears to the end-user as a single computer **(B)** It uses a shared global clock **(C)** All nodes are identical **(D)** Communication happens via shared memory2 m
- 2.Berkeley's UNIX algorithm computes the broadcast time as the: **(A)** Time of the most accurate node **(B)** Average of all reported times **(C)** Median of UTC samples **(D)** Time of the leader node2 m
- 3.In Lamport's scalar time, the tuple-based total order on (timestamp, process_id) for two events e1 \< e2 implies: **(A)** e1 → e2 always **(B)** Either e1 → e2 or e1 || e2 **(C)** e2 → e1 **(D)** e1 and e2 happen at the same process2 m
- 4.The Ricart--Agrawala algorithm requires: **(A)** FIFO channels **(B)** Causal channels **(C)** No FIFO requirement **(D)** Synchronous physical clocks2 m
- 5.In the Chandy--Misra--Haas algorithm for the AND model, the probe (i, j, k) means: **(A)** Process i, j, and k are deadlocked **(B)** i is the blocked initiator, j is the sender, k is the receiver **(C)** i is the receiver, j is the sender, k is the resource **(D)** i, j, k are the three processes in the cycle2 m
- 6.Which of the following is TRUE about a knot in the WFG? **(A)** It is the same as a simple cycle **(B)** It is a strongly connected component with no outgoing edges (in OR model implies deadlock) **(C)** Only one node in a knot is deadlocked **(D)** Knots cannot exist in the AND model2 m
- 7.The synchronous crash-failure consensus algorithm requires: **(A)** f rounds **(B)** f + 1 rounds **(C)** 2f rounds **(D)** log f rounds2 m
- 8.In 2PC, the log record \<ready T\> at a participant indicates: **(A)** The transaction has been committed **(B)** The transaction has been aborted **(C)** The participant has voted YES and is waiting for the coordinator's decision **(D)** The participant is about to start the transaction2 m
- 9.In Raft, log entries become committed when: **(A)** The leader writes them to its log **(B)** They are replicated on a majority of servers **(C)** All servers acknowledge them **(D)** A new term begins2 m
- 10.GFS handles deleted files by: **(A)** Immediately removing them from chunkservers **(B)** Renaming them to a hidden name; physically removing after 3 days **(C)** Encrypting them and keeping forever **(D)** Marking them as 'cold' and migrating to slow storage2 m
Section B — Multiple Select (5 × 4 = 20 marks)
20 marks- 1.Which of the following are correctly matched (algorithm --- primary property)? **(A)** Lamport's mutex --- requires FIFO channels **(B)** Ricart--Agrawala --- requires FIFO channels **(C)** Chandy--Lamport snapshot --- requires FIFO channels **(D)** Acharya--Badrinath snapshot --- requires causal channels4 m
- 2.Which of the following are GFS design assumptions? **(A)** Component failure is the norm rather than the exception **(B)** Workload is dominated by small random writes **(C)** High sustained bandwidth is more important than low latency **(D)** Multi-GB files are common4 m
- 3.Which of the following are valid resource-request models in deadlock theory? **(A)** Single Resource model **(B)** AND model **(C)** OR model **(D)** XOR model4 m
- 4.Which of the following are TRUE about Raft? **(A)** Tolerates Byzantine failures **(B)** Uses randomized timeouts for leader election **(C)** Has a strong leader (decisions flow through leader) **(D)** Was designed to be more understandable than Paxos4 m
- 5.In the GHS algorithm, which of the following statements are TRUE? **(A)** An edge is added to the MST if it connects two fragments with DIFFERENT names **(B)** A fragment with higher level always waits for a lower-level neighbour **(C)** Rule B merges two equal-level fragments and increments the level by 1 **(D)** Test messages can be deferred if the receiver's level is lower4 m
Section C — Short Answer (4 × 5 = 20 marks)
20 marks- 1.Define the four performance metrics for distributed mutual exclusion algorithms and give the formula for system throughput.5 m
- 2.What is the difference between consistent and strongly consistent clocks? Show with an example that scalar (Lamport) clocks are not strongly consistent.5 m
- 3.Explain Rules A, B, and C of the GHS algorithm's fragment-combining strategy.5 m
- 4.Why does GFS not become bottlenecked by its single master? List at least three architectural choices that prevent this.5 m
Section D — Long Answer (4 × 10 = 40 marks)
40 marks- 1.Describe Lamport's mutual-exclusion algorithm in full detail. State the three rules (requesting, executing, releasing the CS) and the two conditions L1 and L2 for entering the CS. Explain why REPLY messages from every process are required and why FIFO channels are essential. Compute and justify the message complexity per CS invocation.10 m
- 2.Describe in detail the three control organisations for distributed deadlock detection (Centralized, Distributed, Hierarchical), giving the advantages and disadvantages of each. Then explain the Ho--Ramamoorthy Two-Phase algorithm and how it reduces false deadlock detection. Construct or describe a scenario where a phantom deadlock could appear if the protocol were sloppy.10 m
- 3.Describe the Raft consensus algorithm. Cover its three sub-problems (leader election, log replication, safety) in detail. Explain the role of terms, randomized election timeouts, the AppendEntries RPC, and the leader-completeness safety property.10 m
- 4.Explain the Three-Phase Commit (3PC) protocol. Compare it with 2PC, focusing on how 3PC avoids the blocking problem. State the assumptions under which 3PC operates, describe each phase, and explain how a new coordinator (elected after the original fails) decides whether to commit or abort.10 m
Track your attempt locally — score and time are recorded in your browser. (Coming soon: timed-attempt mode.)