सSaral Shiksha Yojna
Courses/Distributed Systems

Distributed Systems

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

Mock paper · PAPER F — 200 marks

Duration: 180 min • Max marks: 200

Section A — Short Answer Questions [3 marks each]

30 marks
  1. 1.Self-stabilization: define formally. Distinguish from fault tolerance. Give one classical algorithm name.3 m
  2. 2.Mattern's 4-counter termination detection: state the core idea. Why 4 counters?3 m
  3. 3.Hybrid Logical Clocks (HLC) vs Vector Clocks: state ONE key difference each excels at.3 m
  4. 4.Gossip protocol convergence: with N nodes, what is the expected number of rounds for full information dissemination? Justify.3 m
  5. 5.ZooKeeper sessions and ephemeral zNodes: explain how they enable failure detection of clients.3 m
  6. 6.Saga pattern: describe in 2-3 sentences as an alternative to distributed transactions.3 m
  7. 7.State Machine Replication: state the core principle. How does it relate to Raft / Paxos?3 m
  8. 8.Distributed snapshot via Mattern's algorithm: how does it differ from Chandy-Lamport in its core mechanism?3 m
  9. 9.Quorum intersection: prove formally that R + W \> N is necessary AND sufficient for strong consistency.3 m
  10. 10.Causal vs Eventual consistency: state ONE specific operation that is allowed in eventual but forbidden in causal.3 m

Section B — Medium Answer Questions [5 marks each]

50 marks
  1. 1.CAP applied: A global SINGLE SIGN-ON (SSO) authentication service. Justify trade-off and discuss session-token caching strategies.5 m
  2. 2.Mattern's 4-Counter Trace: 3 processes. Tokens carry (k, count, sender_id, value). Trace one full round trip showing how the counter ensures correct termination detection.5 m
  3. 3.HLC Numerical Trace: 3 processes with NTP-skewed physical clocks. P1 physical clock: 10.0; P2: 10.2; P3: 9.9. P1 sends m1 to P2 at P1's time 10.0. P2 receives m1, then sends m2 to P3 at P2's time 10.3. Compute HLC values at each step. Use HLC format (l, c).5 m
  4. 4.PN-Counter Trace: 2 replicas R1, R2. Initial state: all zeros. R1 increments 3 times, decrements once. R2 increments 2 times, decrements twice. Merge R1's state into R2. Show final state and computed value.5 m
  5. 5.Chubby Lock Service: describe how Chubby provides distributed locking via Paxos-backed file-like API. Specifically, how do lock leases prevent split-brain?5 m
  6. 6.Distributed Transaction via Saga: order processing with steps {reserve_inventory, charge_payment, ship_order}. Show the saga's forward execution and the compensating actions if shipping fails.5 m
  7. 7.State Machine Replication via Raft: describe how Raft's log replication implements SMR. What invariants must be maintained?5 m
  8. 8.Self-Stabilizing Mutual Exclusion (Dijkstra's Token Ring): with K-state machines on a ring of N processes, K ≥ N. Brief description of the algorithm --- how stabilization is achieved.5 m
  9. 9.Spanner Read-Only Transactions: explain the optimization that allows read-only transactions to AVOID 2PC. What role does timestamp choice play?5 m
  10. 10.Vector Clock vs HLC for same scenario: 2 processes with 5 send/recv events. Show both vector clock and HLC values side by side. Comment on storage and information content.5 m

Section C — Long Answer Questions [10 marks each]

120 marks
  1. 1.Self-Stabilization --- Dijkstra's Algorithm and Correctness **a.** Define self-stabilization formally: closure + convergence. **b.** Describe Dijkstra's K-state self-stabilizing token-ring algorithm. State the predicate maintained. **c.** Argue convergence: starting from any (possibly corrupted) state, the system reaches a legitimate state in finite time.10 m
  2. 2.Mattern's Snapshot Algorithm --- Color-Based **a.** Describe Mattern's snapshot algorithm: how the global state is captured using a virtual time wave. **b.** Compare with Chandy-Lamport on channel requirements, message complexity, and recorded state quality. **c.** Why is Mattern's approach particularly suitable for transient computations like termination detection?10 m
  3. 3.Hybrid Logical Clocks --- Complete Protocol **a.** Describe the HLC data structure (l, c) and the update rules for send, receive, local event. **b.** Prove that HLC satisfies the causal precedence property: if e1 → e2 (causally), then hlc(e1) \< hlc(e2). **c.** What's the trade-off between HLC and full vector clocks in terms of storage and causality precision?10 m
  4. 4.CRDTs --- Comprehensive Treatment **a.** Detailed walkthrough of OR-Set (Observed-Removed Set): add, remove, merge operations with unique tags. **b.** LWW-Register: how does it use timestamps? Identify and discuss the 'last-writer wins' anomaly. **c.** Sketch CRDT for a Counter where users have nicknames --- handles concurrent increments and rename operations.10 m
  5. 5.ZooKeeper --- Comprehensive Architecture **a.** Describe ZooKeeper's complete architecture: clients, servers (leader + followers), client sessions, watch mechanism. **b.** Walk through 3 canonical use cases: configuration management, leader election, distributed barrier. **c.** Performance: why does ZooKeeper recommend small data (\<1MB per zNode) and low write throughput? What scales horizontally and what doesn't?10 m
  6. 6.Spanner --- TrueTime and External Consistency End-to-End **a.** Describe Spanner's full architecture: zones, spanservers, Paxos groups, tablet-level replication. **b.** Walk through a single read-write transaction: client → leader → Paxos → commit-wait → ACK. **c.** Why does Spanner achieve a 'true' linearizable global database, whereas systems like CockroachDB (without TrueTime hardware) cannot match it?10 m
  7. 7.Distributed Transactions --- 2PC vs Saga vs Distributed Locks **a.** Compare 2PC, Saga pattern, and Distributed Lock-based transactions on: atomicity, isolation, availability, performance. **b.** Construct a scenario where Saga is the right choice and 2PC would be wrong. Explain. **c.** When would distributed locks be preferable to both? Justify.10 m
  8. 8.Publish-Subscribe Systems --- Kafka-Style **a.** Describe Kafka's architecture: brokers, topics, partitions, consumer groups, offsets. **b.** Discuss Kafka's ordering guarantees: per-partition vs cross-partition. **c.** Compare Kafka with traditional message queues (RabbitMQ): when to choose each.10 m
  9. 9.Cassandra --- Eventual Consistency in Practice **a.** Describe Cassandra's architecture: gossip-based membership, consistent hashing for partitioning, vnodes. **b.** Explain tunable consistency: per-query consistency levels (ANY, ONE, QUORUM, ALL). When use each? **c.** Tombstones: what are they, why are they needed, and what is the 'tombstone problem' in Cassandra?10 m
  10. 10.Distributed Caching --- Memcached vs Redis **a.** Describe Memcached's architecture: distributed cache via consistent hashing. Single-machine vs cluster. **b.** Describe Redis Cluster: sharding, replication, single-leader-per-shard architecture. **c.** Compare on data types, persistence, consistency, and use cases.10 m
  11. 11.Distributed System Design Patterns **a.** Describe the CIRCUIT BREAKER pattern: open / half-open / closed states, when to transition between them. **b.** Describe the BULKHEAD pattern: isolating failures in subsystems. **c.** Describe the RETRY pattern with exponential backoff: math behind backoff, and why jitter is needed.10 m
  12. 12.End-to-End Synthesis --- Designing a Distributed E-Commerce Platform **a.** Design a high-level architecture for a global e-commerce platform: product catalog (read-heavy), shopping cart (write-heavy), checkout (transactional). Choose appropriate storage for each. **b.** Walk through a complete checkout flow: cart → inventory check → payment → order persistence → inventory decrement. Identify consistency and availability requirements for each step.10 m

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