सSaral Shiksha Yojna
Courses/Distributed Systems

Distributed Systems

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

200-mark mock paper · PAPER A — 200 marks

Duration: 180 min • Max marks: 200

Section A — Short Answer Questions [3 marks each]

30 marks
  1. 1.Derive the bounds [T + min, T + RTT − min] in Cristian's algorithm. Define each symbol.3 m
  2. 2.Compare Chandy-Lamport and Acharya-Badrinath on: (i) channel requirement, (ii) total number of messages, (iii) what gets explicitly recorded.3 m
  3. 3.True / False with explanation: (a) In Raft, a leader can overwrite committed log entries from previous terms. (b) GFS atomic record append guarantees exactly-once semantics.3 m
  4. 4.Phase King with n = 8 and f = 2: state (i) the minimum number of phases required and (ii) the majority threshold for round 1. Justify briefly.3 m
  5. 5.Weight-throwing termination detection: what happens if a process receives weight but never sends it back (e.g., its work never completes)? What is detected (or not)?3 m
  6. 6.Consistent hashing: items with IDs 5, 12, 19, 28 are placed using h(x) = (3x + 1) mod 32. Buckets are at positions 10, 20, 25, 30 on the ring. Which item goes to which bucket?3 m
  7. 7.Compare vector and matrix clocks on: (i) storage overhead per process, (ii) per-message piggyback size, (iii) information available beyond pairwise causality.3 m
  8. 8.Define a knot in a wait-for graph. How does it differ from a Strongly Connected Component (SCC)? Give an example of an SCC that is NOT a knot.3 m
  9. 9.In Maekawa's algorithm with N = 25 processes, what is the quorum size K? What is D (number of quorums each process belongs to)? Justify briefly.3 m
  10. 10.In Lamport's mutual-exclusion algorithm, what specific scenario does the REPLY message protect against? Construct a 2-line argument.3 m

Section B — Medium Answer Questions [5 marks each]

50 marks
  1. 1.CAP applied: A national-scale electronic health records (EHR) system spans multiple hospitals. Doctors need access to patient history regardless of network conditions. Discuss which trade-off is appropriate. What modifications could mitigate the cost?5 m
  2. 2.Scalar Clock Numerical: Consider 3 processes P1, P2, P3 with the following events (in real-time order): P1 executes 2 local events, sends m1 to P2, then 1 local event. P2 receives m1, executes 1 local event, sends m2 to P3. P3 executes 1 local event, receives m2, executes 1 local event. Compute Lamport scalar timestamps for ALL events using d = 1.5 m
  3. 3.Suzuki-Kasami Trace: 4 processes P1..P4. Initially P1 holds the token (idle). Sequence: P3 requests (sn=1), P2 requests (sn=1), P1 enters CS and finishes, P4 requests (sn=1). Show the token's Q and LN evolution at each step.5 m
  4. 4.2PC Failure Trace: Coordinator C and 3 participants P1, P2, P3. C sends 'prepare T'. P1 and P2 reply 'ready T'. P3 replies 'abort T'. Trace what C does, what is logged at each site, and what messages are exchanged. Why is this safe?5 m
  5. 5.Byzantine n = 7, f = 2: One round of Phase King execution. Initial values: P1=0, P2=0, P3=0, P4=1, P5=0, P6=faulty, P7=faulty. King in this phase = P1 (honest). Show the round-1 broadcasts (faulty processes lie selectively), the mult counts, and the resulting values at non-faulty processes after round 2.5 m
  6. 6.Mitchell-Merritt Trace: 3 processes P1, P2, P3 in a cycle P1 → P2 → P3 → P1 (all blocked). Initially their (private, public) labels are (5, 5), (7, 7), (3, 3). Trace the algorithm (blocks already done; now transmit), show how public labels propagate, and at which step deadlock is declared.5 m
  7. 7.Chord Lookup: m = 5 bits, 8 nodes at IDs {3, 8, 14, 21, 23, 25, 27, 30}. Starting at node 3, trace the lookup for key 25 using Chord's finger table mechanism. Show how the lookup proceeds and the number of hops.5 m
  8. 8.GHS Merge Step: Two equal-level (L = 2) fragments F1 with name 7 and F2 with name 11. F1's lowest-weight outgoing edge has weight 13 leading to F2; F2's lowest-weight outgoing edge has weight 13 leading to F1. Apply Rule B and state the new fragment's name, level, and what messages are sent.5 m
  9. 9.Dynamo Concurrent Writes: Replicas R1, R2, R3 for key K. Client A writes v1 via R1; client B (during partition) writes v2 via R2. After healing, R3 syncs. Trace the vector clock evolution and show what reads return at each step.5 m
  10. 10.Maximal Independent Set: Consider a 6-node cycle graph C6 (nodes 0,1,2,3,4,5 with edges (i, i+1 mod 6)). List all maximal independent sets, and the MAXIMUM independent set. What is the size relation between maximum and maximal?5 m

Section C — Long Answer Questions [10 marks each]

120 marks
  1. 1.Logical Clocks --- Comprehensive Treatment a. Define scalar, vector, and matrix clocks. State the update rules R1 and R2 for each. b. Prove vector clocks are STRONGLY consistent: ei → ej ⇔ vi \< vj. Cover all cases. c. Give one application where matrix clocks are STRICTLY required (vector wouldn't suffice).10 m
  2. 2.Mutual Exclusion --- Algorithm Comparison and Selection a. Construct a comparison table for Lamport, Ricart-Agarwala, Maekawa, Suzuki-Kasami, Raymond on 5 metrics: msgs/CS, sync delay, FIFO need, fairness, scalability. b. Recommend a specific algorithm for: (i) a system of 1000 nodes spread globally, (ii) a system of 10 nodes in a single rack. Justify each.10 m
  3. 3.Deadlock Detection --- Complete Treatment a. Explain centralized vs distributed vs hierarchical control. Give one advantage and disadvantage of each. b. Compare AND-model and OR-model algorithms on what deadlock criterion they detect (cycle vs knot). c. Explain how false (phantom) deadlocks can arise and one technique to mitigate them.10 m
  4. 4.Byzantine Agreement --- Lamport-Shostak-Pease a. Describe the recursive Oral Messages algorithm OM(t). State its base case and recursive step. b. Trace OM(1) for N = 4 processes (one source, three lieutenants), with one lieutenant being faulty. Show the messages and the majority decisions.10 m
  5. 5.Phase King --- Correctness and Bound a. Why does Phase King require n \> 4f? Derive the threshold mult \> n/2 + f from the agreement invariant. b. Compare Phase King and LSP on resilience and round complexity. Why might one use Phase King despite its weaker bound?10 m
  6. 6.Snapshot Algorithms --- Three Worlds a. State C1 and C2 (consistent global state conditions) precisely. b. Trace Chandy-Lamport on a 3-process system: P1 initiates, sends marker on C12 and C13. Show how P2 and P3 record their states and channel states. Use a concrete message exchange. c. What would change in this trace if channels were non-FIFO? Why does Chandy-Lamport break?10 m
  7. 7.Commit Protocols and Raft as Commit a. Explain the 2PC blocking problem with a concrete scenario. b. Show how 3PC pre-commit unblocks the situation. State the assumptions 3PC relies on. c. Argue why Raft-based commit (replicating commit/abort decision via Raft log) does not block, comparing with 3PC.10 m
  8. 8.Raft Comprehensive --- Election and Replication a. Describe Raft's leader election: how candidates emerge, what RequestVote contains, how votes are awarded, and how split votes are resolved. b. Describe Raft's log replication: AppendEntries RPC, commit rule (majority), and how the leader brings a divergent follower back to consistency.10 m
  9. 9.GHS Algorithm --- Deep Trace a. State the three combining rules A, B, C precisely. Why must higher-level fragments wait? b. Walk through the test → accept/reject → connect cycle. What state changes happen at each step? c. State and justify the total message complexity O(N log N + E).10 m
  10. 10.GFS --- Read, Write, and Consistency a. Describe the read protocol step-by-step. Why is the master not on the data path? b. Describe the write protocol. Explain the role of leases, version numbers, primary, secondaries, and pipelined data flow. c. Explain why concurrent successful writes can yield 'consistent but undefined' regions. Why is this acceptable for GFS workloads?10 m
  11. 11.Consistent Hashing and Chord --- Detailed a. State the four properties of a good hash function for consistent hashing (Karger et al.): balance, monotonicity, spread, load. b. Describe Chord's finger table structure. Why are there log N entries? c. When a node N joins the system, what items move and from where? Argue this is O(K/N) on expectation, where K is total items.10 m
  12. 12.MPC --- Distributed Selection10 m

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