सSaral Shiksha Yojna
Courses/Distributed Systems

Distributed Systems

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

Mock paper · PAPER E — 200 marks

Duration: 180 min • Max marks: 200

Section A — Short Answer Questions [3 marks each]

30 marks
  1. 1.Bully Algorithm for leader election: briefly describe its mechanism. State the message complexity in the worst case for N processes.3 m
  2. 2.Failure Detector: define COMPLETENESS and ACCURACY. Distinguish strong from weak forms of each.3 m
  3. 3.State the FLP Impossibility Theorem precisely. What does it imply for asynchronous consensus?3 m
  4. 4.Distinguish RELIABLE broadcast, FIFO broadcast, CAUSAL broadcast, and TOTAL-ORDER (atomic) broadcast. Which is strictly the strongest?3 m
  5. 5.Linearizability vs Sequential Consistency: state both definitions concisely. Which is strictly stronger?3 m
  6. 6.Paxos roles: define proposer, acceptor, learner. Can one process play multiple roles? Why is this common?3 m
  7. 7.Quorum systems: define READ quorum (R) and WRITE quorum (W). State the intersection requirement for strong consistency.3 m
  8. 8.Hybrid Logical Clocks (HLC): what problem do they solve that pure logical clocks and pure physical clocks cannot solve alone?3 m
  9. 9.Token Ring mutual exclusion: how does the ring rotate, and what is the synchronization delay in the worst case?3 m
  10. 10.Distributed lock service: list three core properties such a service must provide.3 m

Section B — Medium Answer Questions [5 marks each]

50 marks
  1. 1.CAP applied to ZooKeeper: ZooKeeper guarantees consistency under partial failures. State which of C/A/P it sacrifices and how this manifests when a partition isolates a minority of nodes.5 m
  2. 2.Bully Algorithm Trace: 5 processes with IDs 1, 2, 3, 4, 5. Current leader is 5. Process 5 crashes. Process 2 detects this first and initiates election. Show the complete message exchange and identify the new leader.5 m
  3. 3.Failure Detector Classes --- Chandra-Toueg Hierarchy: identify the four classes P, ◇P, S, ◇S in terms of their completeness/accuracy guarantees. Which class is needed for solving consensus in partial-synchrony?5 m
  4. 4.Paxos Single-Decree Trace: 2 proposers P1, P2 and 3 acceptors A1, A2, A3. P1 sends prepare(1) and gets promise from A1, A2 (A3 unreachable). P1 then sends accept(1, 'v1'). Simultaneously, P2 sends prepare(2) which reaches A2, A3. Trace the outcome carefully.5 m
  5. 5.Linearizability Violation: 2 processes P1, P2 and a shared register R initially 0. P1 writes R=1 (returns OK). P2 reads R --- could P2 see 0 in a sequentially consistent system but not a linearizable one? Construct an explicit history that distinguishes the two.5 m
  6. 6.Token Ring Mutex Trace: 4 processes in a ring P1 → P2 → P3 → P4 → P1. Token currently at P1. Sequence of requests: P3 wants CS (token at P1), then P2 wants CS, then P1 wants CS again. Trace the token rotation and CS executions.5 m
  7. 7.Total-Order (Atomic) Broadcast Implementation: outline how atomic broadcast can be built on top of a consensus primitive. Explain the role of each consensus round.5 m
  8. 8.Spanner TrueTime: define TT.now() as an interval [earliest, latest]. Explain the 'commit-wait' rule and why it ensures external consistency.5 m
  9. 9.G-Counter CRDT (state-based): 3 replicas R1, R2, R3. Each tracks its own increment count. R1 increments twice, R2 increments three times, R3 increments once. Merge R1's state and R2's state. Then merge with R3. Show the merged states.5 m
  10. 10.Multi-Paxos Optimization: in single-decree Paxos, each decision requires 2 round trips. How does Multi-Paxos reduce this to \~1 round trip after a stable leader is established? Explain briefly.5 m

Section C — Long Answer Questions [10 marks each]

120 marks
  1. 1.Leader Election --- Bully vs Ring Algorithm **a.** Describe the Bully algorithm in detail: election initiation, ELECTION/OK/COORDINATOR messages, recovery. **b.** Describe the Chang-Roberts Ring algorithm: how the token traverses the ring, comparison with own ID, election conclusion. **c.** Compare message complexity, time complexity, and assumptions of both. When would you choose each?10 m
  2. 2.Failure Detectors --- Chandra-Toueg Hierarchy **a.** Formally define COMPLETENESS (strong, weak) and ACCURACY (strong, weak, eventual strong, eventual weak). Build the eight resulting classes table. **b.** Why is ◇W (eventually weak) the weakest class that can solve consensus in partial synchrony? What's the proof sketch? **c.** Discuss why PERFECT failure detectors P are typically impractical to implement in real distributed systems.10 m
  3. 3.FLP Impossibility --- Proof Outline and Implications **a.** State FLP precisely (Fischer-Lynch-Paterson 1985). What system model does it assume? **b.** Sketch the proof's key idea: bivalent configurations and the indistinguishability argument. **c.** List three practical ways real consensus algorithms circumvent FLP.10 m
  4. 4.Paxos --- Single-Decree Complete Algorithm **a.** Describe Phase 1 (Prepare/Promise) and Phase 2 (Accept/Accepted) of single-decree Paxos in full detail. **b.** Prove that Paxos guarantees safety: at most one value is chosen. **c.** Why does Paxos guarantee progress in the absence of failures and dueling proposers? What can go wrong?10 m
  5. 5.Multi-Paxos and Practical Optimizations **a.** Describe how Multi-Paxos replicates a LOG of decisions efficiently. State the role of the 'distinguished leader' and 'pipelining'. **b.** Compare Multi-Paxos with Raft on (i) leader's role, (ii) log management, (iii) understandability. **c.** Real systems using Multi-Paxos: list two production examples and briefly mention one engineering decision each.10 m
  6. 6.Memory Consistency Models Hierarchy **a.** Define and compare: Strict Consistency, Linearizability, Sequential Consistency, Causal Consistency, Eventual Consistency. Order them from strongest to weakest. **b.** Give a concrete distributed example illustrating each (e.g., shopping cart, leaderboard, version control, file system, social timeline). **c.** Why is Linearizability extremely expensive in geo-distributed settings? State the inherent latency lower bound.10 m
  7. 7.Group Communication --- Broadcast Hierarchy **a.** Define the four broadcast levels: Reliable, FIFO, Causal, Atomic. State the delivery guarantee at each. **b.** Show how Causal broadcast can be implemented on top of FIFO broadcast using vector clocks at receivers. **c.** Show that Atomic broadcast is EQUIVALENT (mutually reducible) to consensus.10 m
  8. 8.ZooKeeper / Chubby --- Architecture **a.** Describe ZooKeeper's data model (zNodes: persistent, ephemeral, sequential). **b.** Describe how ZAB (ZooKeeper Atomic Broadcast) provides atomic broadcast and supports failure recovery. **c.** Use case: implement distributed mutex using ephemeral sequential zNodes. Outline the algorithm.10 m
  9. 9.Distributed Shared Memory --- Models and Implementation **a.** Describe page-based DSM (Ivy-style): page ownership, fault handler, false sharing. **b.** Compare Release Consistency and Entry Consistency: what synchronization primitives does each require? **c.** Why have software DSM systems largely been replaced by explicit message-passing models (MPI, RPC) in HPC?10 m
  10. 10.Spanner --- TrueTime and External Consistency **a.** Describe TrueTime API and its hardware basis (GPS + atomic clocks at each data center). **b.** Explain Spanner's commit-wait protocol. Why does waiting until TT.now().earliest \> commit_timestamp suffice for external consistency? **c.** What is the typical TrueTime uncertainty window in production, and why does this set a lower bound on transaction latency?10 m
  11. 11.CRDTs --- Conflict-Free Replicated Data Types **a.** Define STATE-based (CvRDT) and OP-based (CmRDT) CRDTs. State the convergence conditions for each. **b.** Describe in detail: G-Counter (grow-only), PN-Counter (positive-negative), OR-Set (observed-removed set). For each, state the merge operation. **c.** Limitation: why can't all data structures be made into CRDTs? Give one example of an operation that breaks CRDT semantics.10 m
  12. 12.Gossip Protocols --- Anti-Entropy and SWIM **a.** Describe the epidemic gossip model: how does information spread? State the convergence time in terms of N (nodes). **b.** Describe SWIM membership protocol: failure detection via direct ping + indirect ping via random subset. **c.** Compare gossip-based failure detection with heartbeat-based detection on scalability and false-positive rates.10 m

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