Chapter 3

Question 1

Q: Why do complex distributed systems need broadcast abstractions?

Answer 1

A:

Client-server limitations: Bilateral interactions (one client ↔ one server) fail for group coordination.

Multiparticipant challenges: Sender crashes cause inconsistent message delivery.

Solution: Broadcast ensures agreement on delivered messages across processes.

Simple Explanation:
Client-server works for 1:1 tasks (like a phone call), but group tasks (e.g., multiplayer games) need a “megaphone” (broadcast) so everyone hears the same message, even if the sender crashes.

Question 2

Q: What does best-effort broadcast guarantee?

Answer 2

A:

Validity: If the sender is correct, all correct processes deliver the message.

No duplication/creation: Messages aren’t duplicated or forged.

Weakness: No agreement if the sender crashes mid-broadcast.

Simple Explanation:
Best-effort ensures delivery only if the sender stays alive. Like mailing a letter to everyone—if you vanish mid-mailing, some might never get it.

Question 3

Q: How does reliable broadcast handle sender crashes?

Answer 3

A:

Agreement: If any correct process delivers a message, all correct processes do.

Two approaches:

    Lazy: Retransmits only after detecting sender crashes (uses failure detector P).

    Eager: Always retransmits, no failure detector.

Cost: O(N²) messages in worst case.

Simple Explanation:
Even if the sender crashes, reliable broadcast ensures everyone hears the message eventually. Think of it as a relay race: if one runner drops the baton, others pick it up.

Basically, If the sender gets one message through, everyone gets it

Question 4

Q: Why is “uniformity” stricter than regular reliable broadcast?

TOTAL ORDER IN MULTIPAXOS

Answer 4

A:

Uniform agreement: If any process (even faulty) delivers a message, all correct processes must deliver it.

Use case: Prevents inconsistent external actions (e.g., payments or prints).

Algorithm: "All-Ack" waits for all correct processes to acknowledge a message.

Simple Explanation:
Uniformity ensures no secrets: if a crashed process delivered a message before failing, everyone must know. Like a group contract where all signatures are required.

Question 5

Q: How does stubborn broadcast work in crash-recovery systems?

Answer 5

A:

Feature: Delivers messages infinitely often if the sender is correct.

No logging: Relies on retransmissions, not stable storage.

Algorithm: Uses stubborn links to resend messages perpetually.

Simple Explanation:
Stubborn broadcast acts like a broken record—repeats messages endlessly. Even if a process crashes and recovers, it will eventually catch the message.

Question 6

Q: How does logged broadcast avoid duplicates after crashes?

Answer 6

A:

Mechanism: Logs delivered messages in stable storage.

Recovery: After a crash, checks the log to skip duplicates.

Trade-off: Adds logging overhead but ensures exactly-once delivery.

Simple Explanation:
Logged broadcast writes received messages in a “diary” (stable storage). After a crash, it reads the diary to avoid re-delivering old messages.

Question 7

Q: How does probabilistic broadcast achieve scalability?

Answer 7

A:

Gossip protocol: Randomly forwards messages to k targets (fanout) over R rounds.

Probabilistic validity: High (but not 100%) chance all correct processes deliver the message.

Efficiency: O(N) messages with careful fanout/round tuning.

Simple Explanation:
Instead of shouting to everyone, probabilistic broadcast whispers to a few, who whisper to others. Like a rumor—it spreads exponentially, reaching most (but maybe not all).

Question 8

Q1: What is FIFO-Order Broadcast?

Answer 8

A:

Guarantee: Ensures messages from the same sender are delivered in the exact order they were sent.

Implementation: Uses sequence numbers (e.g., Algorithm 3.12). Each sender tags messages with incrementing numbers (1, 2, 3...); receivers buffer and deliver them in sequence.

Use Case: Prevents inconsistencies in actions from a single source (e.g., sequential updates to a file).

Simple Explanation:
FIFO is like a coffee shop queue: your orders are handled in the sequence you placed them. If you order a latte first and a croissant second, you always get the latte first.

Question 9

Q2: What is Causal-Order Broadcast?

Answer 9

A:

Guarantee: Ensures messages are delivered in global cause-effect order across all senders.

Implementation:

    Causal Past Lists (Algorithm 3.13): Messages include a history of all preceding messages.

    Vector Clocks (Algorithm 3.15): Uses a fixed-size array to track message counts per sender.

Use Case: Avoids logical inconsistencies (e.g., delivering a reply before the original message).

Simple Explanation:
Causal order is like a conversation: you can’t respond to a question before hearing it. If Alice asks “What’s the time?” and Bob replies “2 PM,” everyone hears the question first, then the reply.