{ "@context": "https://schema.org", "@type": "Organization", "name": "Brainscape", "url": "https://www.brainscape.com/", "logo": "https://www.brainscape.com/pks/images/cms/public-views/shared/Brainscape-logo-c4e172b280b4616f7fda.svg", "sameAs": [ "https://www.facebook.com/Brainscape", "https://x.com/brainscape", "https://www.linkedin.com/company/brainscape", "https://www.instagram.com/brainscape/", "https://www.tiktok.com/@brainscapeu", "https://www.pinterest.com/brainscape/", "https://www.youtube.com/@BrainscapeNY" ], "contactPoint": { "@type": "ContactPoint", "telephone": "(929) 334-4005", "contactType": "customer service", "availableLanguage": ["English"] }, "founder": { "@type": "Person", "name": "Andrew Cohen" }, "description": "Brainscape’s spaced repetition system is proven to DOUBLE learning results! Find, make, and study flashcards online or in our mobile app. Serious learners only.", "address": { "@type": "PostalAddress", "streetAddress": "159 W 25th St, Ste 517", "addressLocality": "New York", "addressRegion": "NY", "postalCode": "10001", "addressCountry": "USA" } }

Chapter 3 Flashcards

Help god (9 cards)

1
Q

Q: Why do complex distributed systems need broadcast abstractions?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Q: What does best-effort broadcast guarantee?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Q: How does reliable broadcast handle sender crashes?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

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

TOTAL ORDER IN MULTIPAXOS

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

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

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Q: How does logged broadcast avoid duplicates after crashes?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Q: How does probabilistic broadcast achieve scalability?

A

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).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Q1: What is FIFO-Order Broadcast?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Q2: What is Causal-Order Broadcast?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly