सSaral Shiksha Yojna
Courses/Distributed Systems

Distributed Systems

CS3.401
Prof. Kishore Kothapalli•Monsoon 2025-26•4 credits
Sample Papers/200-mark paper · PAPER C — 200 marks

200-mark paper · PAPER C — 200 marks

Duration: 180 min • Max marks: 200

Section A — Short Answer Questions [3 marks each]

30 marks
  1. 1.Define the 'height' of an event in Lamport's scalar clock (with d = 1). Give one practical use of height beyond ordering.3 m
  2. 2.Given a 3-process system with vector clocks VC_A = [3, 1, 2] (at P1) and VC_B = [3, 1, 2] (at P2): both vectors are identical. What does this imply about the two events? Discuss in 2-3 lines.3 m
  3. 3.Causal channels over non-FIFO networks: outline (1-2 sentences) how vector clocks can be used at the receiver to implement causal-order delivery.3 m
  4. 4.In Chandy et al.'s diffusion algorithm for OR-model deadlock detection, define the 'dependent set' DS_i of process P_i and explain how its size affects num_i counter initialization.3 m
  5. 5.In Raft, distinguish between 'term number' and 'log index'. Can two entries at the same index ever have different terms across different servers? Justify.3 m
  6. 6.GFS chunk replica placement: state two specific criteria the master uses when picking the chunkserver for a new replica.3 m
  7. 7.Consistent hashing: if the underlying hash function itself changes (e.g., switching from MD5 to SHA-1), how many items must be remapped on expectation? Justify.3 m
  8. 8.Distinguish a Resource Allocation Graph (RAG) from a Wait-For Graph (WFG). Which is simpler and why?3 m
  9. 9.Lamport-Shostak-Pease for N=7, t=2: state (i) whether agreement is possible, (ii) the round complexity, (iii) the message complexity per round in OM(t).3 m
  10. 10.True/False with explanation: 'In the GHS algorithm, a fragment can be ABSORBED (Rule A) into a higher-level fragment without changing the absorbing fragment's level.'3 m

Section B — Medium Answer Questions [5 marks each]

50 marks
  1. 1.CAP applied: A distributed multiplayer game maintains a global leaderboard updated as players complete matches. Discuss which of C, A, P should be prioritized. Mention how techniques like eventual consistency or sharding can mitigate the trade-off.5 m
  2. 2.Scalar Clock Numerical (4 processes): P1, P2, P3, P4. Events in real-time order: (1) P1 local event, (2) P1 sends m1 to P3, (3) P2 local event, (4) P2 sends m2 to P4, (5) P3 receives m1, P3 local event, P3 sends m3 to P2, (6) P4 receives m2, (7) P2 receives m3. Compute Lamport timestamps for all events.5 m
  3. 3.Maekawa Quorum Design for N=9: Construct 9 quorums R0, R1, \..., R8 (one per process) satisfying: (i) i ∈ Ri, (ii) Ri ∩ Rj ≠ ∅ for all i,j, (iii) |Ri| = K for some K, (iv) each node in exactly D quorums. State K and D.5 m
  4. 4.Suzuki-Kasami Race Condition: 2 processes P1 and P3. Initially P2 holds the token (idle, Q=[], LN=[0,0,0]). At time t=10, P1 broadcasts REQUEST(1, 1). At t=11, P3 broadcasts REQUEST(3, 1). Due to network delays, P2 receives P3's request first (at t=12) and P1's at t=13. Trace what happens.5 m
  5. 5.2PC Coordinator Crash After Sending Some Commits: Coordinator C has 4 participants P1, P2, P3, P4. All replied 'ready T'. C writes \<commit T\>. C sends 'commit' to P1, P2 successfully, then CRASHES before sending to P3, P4. Trace what P3 and P4 must do.5 m
  6. 6.Phase King for n=12, f=2 --- Success Trace: At end of phase 1 (king honest), what is the count threshold for keeping local majority? Show how a process with initial value v=0 ends with v=0 even when faulty processes broadcast 1.5 m
  7. 7.GHS Trace on 5-Node Linear Graph: Nodes A, B, C, D, E in a line with edges A-B(1), B-C(2), C-D(3), D-E(4) AND an additional edge A-E(10) creating a long cycle. Show the MST construction step by step.5 m
  8. 8.Mitchell-Merritt with 4 Processes in Linear Chain: P1 → P2 → P3 → P4, with P4 → P1 closing the cycle. Labels (private, public): P1=(2,2), P2=(8,8), P3=(5,5), P4=(11,11). Trace probe propagation and identify when deadlock is detected.5 m
  9. 9.Chord Lookup with m=4: 6 nodes at IDs {1, 3, 6, 9, 12, 14}. Starting at node 1, look up key 11. Show node 1's finger table, the lookup path, and the number of hops.5 m
  10. 10.Termination Detection --- Dijkstra-Scholten Trace: 4 nodes A, B, C, D. A initiates. A sends to B, B sends to C, B sends to D. Then computations complete. Show parent pointers, deficit values, and ACK sequence leading to termination detection.5 m

Section C — Long Answer Questions [10 marks each]

120 marks
  1. 1.Lamport Scalar Clocks --- Applications and Limitations **a.** List three significant applications of scalar clocks in distributed systems. **b.** Identify two specific limitations and propose what stronger clock mechanism addresses each. **c.** Why does Lamport's mutex algorithm need scalar clocks at all? Could it work with arbitrary process IDs alone?10 m
  2. 2.Snapshot Algorithm Correctness --- Comparative Analysis **a.** For each of Chandy-Lamport, Lai-Yang, and Acharya-Badrinath, state ONE correctness invariant they crucially maintain (the key reason each works). **b.** Show how Lai-Yang handles a non-FIFO channel where a post-snapshot message arrives at a process BEFORE that process has snapshotted. **c.** Argue why Chandy-Lamport's marker rules would silently produce an INCORRECT snapshot on non-FIFO channels (specify which condition C1 or C2 fails).10 m
  3. 3.Mutual Exclusion --- Fairness Analysis **a.** Define fairness in distributed mutual exclusion. Distinguish strong (timestamp-order) fairness from weak (no starvation) fairness. **b.** For each of the five algorithms (Lamport, Ricart-Agarwala, Maekawa, Suzuki-Kasami, Raymond), state whether it provides strong fairness, weak fairness, or neither. Justify each briefly. **c.** Construct an explicit scenario where Maekawa V2 violates strong fairness.10 m
  4. 4.Phase King Failure --- Full Construction for n ≤ 4f10 m
  5. 5.3PC Under Partial Failures --- Detailed Analysis **a.** State the three explicit assumptions 3PC relies on. Explain why each is necessary for non-blocking behavior. **b.** Trace a recovery scenario: K = 2, total 4 sites (C + 3 participants). C and one participant fail after Phase 2. How does the new coordinator decide? **c.** What happens if a network partition occurs during Phase 2 (after pre-commit broadcast but before final commit)? Discuss why 3PC's assumptions exclude this.10 m
  6. 6.Raft Safety --- Step-by-Step Proof of Key Properties **a.** State the Election Safety property and prove that at most one leader exists per term. **b.** State the Log Matching Property: if two logs contain entries at the same index with same term, then their prefixes are identical. Argue why AppendEntries' consistency check enforces this. **c.** Argue why a leader for term T never overwrites a log entry committed in term T' \< T.10 m
  7. 7.GHS Message Complexity --- Rigorous Argument **a.** Argue that any node can change fragment names at most O(log N) times during the algorithm. Use the level-doubling property. **b.** Argue that each edge is involved in at most O(1) test messages (after being marked reject or branch, no further tests). Hence test messages sum to O(E). **c.** Combine to derive the O(N log N + E) total complexity. State message complexity in big-O for two graph types: (i) sparse (E = O(N)) and (ii) dense (E = O(N²)).10 m
  8. 8.GFS Atomic Record Append --- Failure Modes **a.** Describe the record append protocol. How does the primary handle the case where the record would straddle a chunk boundary? **b.** Discuss why GFS chose at-least-once semantics over exactly-once. What complexity (and at what cost) would exactly-once require? **c.** Application-level workaround: how can a client detect and skip duplicate records on read?10 m
  9. 9.Dynamo --- Eventual vs Strong Consistency Trade-off **a.** Describe Dynamo's tunable consistency: how do N, R, W parameters trade availability against consistency? **b.** Explain hinted handoff and Merkle tree based anti-entropy. What problem does each solve? **c.** Recommend (N, R, W) for: (i) a shopping cart (writes are critical, reads less so), (ii) a sensor data store (writes dominate, reads rare).10 m
  10. 10.MPC Distributed BFS --- Round Complexity Proof **a.** Argue that naïve BFS in MPC requires exactly D rounds, where D is the graph's diameter. **b.** Sketch the 'frontier doubling' approach: each round, expand by 2× the previous frontier depth (using local subgraph computation). **c.** Derive the resulting round complexity. Why does memory ε matter here?10 m
  11. 11.LSP vs Phase King --- Resilience and Practicality **a.** Compare LSP and Phase King on (i) resilience bound, (ii) round complexity, (iii) message complexity per round, (iv) state per process. **b.** For a Byzantine-tolerant cluster of 100 servers where f ≤ 10, which algorithm would you choose? Justify in 3-4 lines covering message and time costs. **c.** What if f could be up to 33 (one third)? Re-evaluate the choice.10 m
  12. 12.Termination Detection --- Designing a Crash-Tolerant Variant **a.** Briefly state why both Dijkstra-Scholten and weight-throwing fail under process crashes. **b.** Propose a modification to either algorithm that tolerates crash failures (e.g., using checkpointing, replication, or timeouts). Describe the protocol changes. **c.** Discuss the cost (message, storage, latency) of your modification.10 m

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