CS 425 Midterm Visual Guide: Distributed Systems in Motion

Distributed systems become confusing between steps. A request was sent—but did it arrive? A message arrived—but can the application use it? One replica acknowledged a write—but what do the others know?

These nine interactive diagrams revisit the midterm topics with smaller examples, checked against the slides and transcripts of Cloud Computing Concepts, Part 1. They are teaching models, not performance measurements or complete product implementations.

Predict the next step before pressing the button. Captions explain what changed and why. Diagrams scroll horizontally on narrow screens. Logical time keeps the entire message graph visible and reveals only timestamps.

1. Communication: silence does not explain what happened

A client reaches its timeout without a response. The server might still be working, might have completed the operation and lost its reply, or might have stopped.

A synchronous system model assumes known processing and transmission bounds; an asynchronous model does not. This differs from blocking versus non-blocking APIs. Even a known bound must be considered alongside delivery and failure assumptions.

Compare “Reply lost” and “Server crashed.” The client’s observation is identical; the server-side outcome may not be. Timeout means unknown outcome, not definitely unexecuted.

A practical consequence: retries with side effects need an idempotency key, queryable operation state, or reconciliation. A longer timeout does not remove uncertainty.

2. P2P: locating content is not downloading it

These mechanisms address different parts of the problem.

• Gnutella flooding: ask neighbors to keep searching. Each hop consumes TTL; Query IDs prevent repeated forwarding. QueryHit replies follow the reverse path.
• Chord lookup: place nodes and keys on a ring. Each finger is successor(n + 2^i), enabling large jumps before reaching the key’s successor.
• BitTorrent rarest-first: after finding peers, choose which missing piece to download. Count copies among current neighbors, not across the entire network.

Flooding starts with fixed TTL 3. “Next step” advances one hop rather than increasing TTL. Only first-discovery paths are highlighted, not every duplicate or reply.

Chord locates key 143 via 19 → 96 → 120 → 151. Key 143 is not a node: 151 is its first clockwise successor. Current routing tables and healthy peers are assumed; maintaining them costs additional work.

3. Gossip: fast dissemination is not a per-round guarantee

Push says, “Here is an update.” Pull asks, “Do you know something I am missing?” Push-pull attaches known updates to queries and can receive updates in responses.

Push-pull does not need a central decision to switch modes when half the group is informed. A peer generally does not know that fraction.

Compare coverage and packet counts together. A pull query and response are separate packets. A successful reply without new data is not packet loss.

A fixed random seed allows replay. Each participating peer chooses two others with replacement per round. Newly informed peers forward in the next round. Rounds are a teaching convenience, not a synchronization requirement.

Continue after full coverage to see redundant traffic. Retention and stopping policies are omitted; gossip also cannot cross a permanent network partition.

4. SWIM: an indirect ACK is not a suspicion refutation

Probes gather evidence; dissemination spreads membership decisions. Updates can be piggybacked on ping and ACK traffic.

Follow all three paths:

1. Indirect ACK: P0 cannot hear P3 directly and asks P1/P2 for help. P3 acknowledges P1, which relays the ACK to P0. This bypasses some path failures without increasing an incarnation.
2. Refute suspicion: both probing stages time out. P0 records suspect(P3,4). P3 learns of the suspicion, increments its own incarnation, and disseminates alive(P3,5). P0 receives it before the suspicion deadline and restores alive status.
3. No response: the suspicion deadline expires. P0 records failed and spreads that decision.

The displayed status is P0’s membership view, not omniscient truth. An isolated but running process can be falsely suspected. In the course state machine, a falsely removed member must rejoin, not simply undo removal with a larger incarnation.

5. Logical time: calculate from locally available information

Use the fixed graph for both Lamport and vector clocks. Every process starts at zero. Filled dots are internal events; each message endpoint is also an event.

For Lamport clocks:

• Internal event or send: increment the local clock.
• Receive: max(local clock, message timestamp) + 1.

Before P1’s first receive from P2, its clock is 3 and the message carries 7. The result is 8, not 4.

For vector clocks, take the component-wise maximum on receive, then increment the receiver’s component. The caption shows the operands; e1 means increment only P1’s component.

Causality implies increasing Lamport timestamps, but scalar order does not prove causality. Vector precedence requires all components less than or equal, with at least one strictly smaller. If each vector has a larger component than the other, the events are concurrent.

The reveal order is one legal walkthrough, not a physical global clock for concurrent events.

6. Multicast ordering: received does not mean deliverable

A receiver can store a message in a hold-back queue and deliver it only when the ordering rule allows.

Watch arrival order, waiting messages, and the delivered log.

FIFO protects one sender’s sequence. If B receives A’s sequence 2 before 1, it waits, delivers 1, then releases 2. Other senders have independent counters.

Causal ordering checks dependencies too. B observes A’s m1 before sending m2, so C cannot deliver m2 first. The vector (1,1,0) requires C to have delivered A’s first multicast. These counters track multicasts, unlike clocks that advance on every local, send, or receive event.

Total ordering gives recipients a shared sequence. The diagram uses the course’s sequencer: independent x and y receive numbers y:1, x:2. A recipient with x:2 still waits for 1. This does not mean y caused x; total order alone does not automatically imply FIFO or causal order.

Ordering is not reliable delivery. If a missing message never arrives, waiting does not resolve itself. Retransmission, membership changes, and sequencer recovery need additional mechanisms.

7. MapReduce: data placement determines what recovery recomputes

Input splits contain red blue and blue blue. Mappers emit (word,1); shuffle routes equal keys to one reducer; reduce sums each group.

The result is red=1, blue=3. The three blue values come from both mappers, not a one-to-one mapper–reducer pairing.

In “Lost map output,” replicated HDFS input survives but worker-local output becomes unavailable. If the reducer has not fetched that partition, re-run its map task from surviving input. The distinction is durable input/final output versus recomputable intermediate output.

For a straggler, a second attempt runs the same reduce task. Adopt the first successful result rather than adding both together. A hot key is still large on another worker: speculation does not eliminate skew.

The diagram omits YARN resource-allocation exchanges. Safe re-execution requires suitable reproducibility; arbitrary external side effects do not automatically become exactly-once.

8. Quorums: intersection starts the argument, not ends it

There are N=5 replicas. A write waits for W acknowledgements; a read waits for R responses. Assume one completed write with no concurrent writes or failures, changing W replicas from v1 to v2.

The read set is deliberately placed as far from the write set as possible:

minimum overlap = max(0, R + W − N)

Try R=2, W=2: the read can miss the update. Change to R=3, W=3: every read set includes at least one replica that acknowledged the write. Responses still require correct version reconciliation.

2W > N means successful write sets intersect. It does not make the shared replica automatically lock or serialize writes. Incomplete writes, concurrent writes, version rules, and changing replica sets need further reasoning.

Larger R or W needs more responsive replicas. This is an availability and latency trade-off, not a cost-free strong-consistency switch.

9. Cassandra: flush, compaction, and repair have different scopes

• Flush: turn a memtable into an on-disk SSTable.
• Compaction: merge SSTables and reconcile versions within one replica.
• Repair: address disagreement between replicas.

The read example has three SSTables. A’s Bloom filter says “definitely absent,” so skip it. B says “maybe,” but its index reveals a false positive. C actually holds the value. A Bloom filter neither returns a value nor proves presence with a positive result.

Repair reads only R1 and R2. Updating R2 to v3 does not update uncontacted R3. Newest observed is not necessarily newest anywhere.

Version note: this diagram illustrates blocking read repair, repairing before replying. Cassandra 4.0 introduced per-table BLOCKING/NONE settings; read repair is not universally asynchronous background work and does not replace other repairs. Apache Cassandra documentation

Four questions for revision

1. What does this process know now, and what is only an inference?
2. Who or what condition is it waiting for?
3. Which state changed? Did other replicas change too?
4. Does recovery need retransmission, recomputation, or durable state?

Answering these along a diagram is more useful than memorizing algorithm names alone.

Sources and scope

The primary references are the supplied slides and transcripts for Indranil Gupta’s Cloud Computing Concepts, Part 1. These are redrawn study aids, not official interactive course material.

Each section states its simplifying assumptions. Keep course models separate from current product behavior.