Chapter 3 Flashcards
Help god (9 cards)
Q: Why do complex distributed systems need broadcast abstractions?
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.
Q: What does best-effort broadcast guarantee?
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.
Q: How does reliable broadcast handle sender crashes?
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
Q: Why is “uniformity” stricter than regular reliable broadcast?
TOTAL ORDER IN MULTIPAXOS
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.
Q: How does stubborn broadcast work in crash-recovery systems?
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.
Q: How does logged broadcast avoid duplicates after crashes?
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.
Q: How does probabilistic broadcast achieve scalability?
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).
Q1: What is FIFO-Order Broadcast?
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.
Q2: What is Causal-Order Broadcast?
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.