स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.)