Chapter 4 Flashcards
just learn it bro (13 cards)
Q: Why do we emulate shared memory in distributed systems?
A:
A distributed programming abstraction where processes interact via shared "registers" (logical storage). Registers support read/write operations, emulating hardware-level shared memory. Implemented via message passing, not physical shared storage. Resembles a distributed file system or collaborative editing space
Shared memory (in distributed systems) = message passing + an abstraction layer that makes communication look like memory access.
Message passing directly = sending and receiving messages explicitly.
In distributed systems, processes run on different machines that don’t physically share memory. However, many programs are easier to design and reason about if they can communicate by reading and writing shared data — just like threads do in a single computer’s memory.
Emulating shared memory gives distributed processes a familiar and simple way to coordinate and share information without worrying about the complex details of message passing, failures, or network delays..
Simple Explanation:
Like a virtual whiteboard that all processes can access, even though they’re on different machines. It feels like real shared memory but works by passing hidden messages.
Q: What is a (1, N) regular register and what guarantees does it offer?
A:
Only one process writes, and the rest read.
Guarantees:
If no write is happening, readers get the last value. If reading and writing happen at the same time, the reader may see either the last value or the one being written.
Simple Explanation:
Imagine a teacher (the writer) writing on a whiteboard. Students (readers) take notes. If the teacher isn’t writing, students see the full message. If the teacher is writing at the same time, students might catch the last message or the new one halfway through.
Q: How does the Read-One Write-All algorithm work?
A:
Writer sends value to all Readers just use their local copy Works with a perfect failure detector Write: 2 steps, O(N) messages Read: local (no messages)
Simple Explanation:
The writer tells everyone the new value. Readers just use what they have stored locally.
Q: How does the Majority Voting algorithm work? Why does it write to a majority?
A:
The writer sends the value to a majority of nodes (not all). The reader asks a majority and returns the latest value it finds. Assumes fail-silent: some processes may fail silently. More robust than Read-One Write-All but a bit slower.
Simple Explanation:
Instead of updating everyone, the teacher (writer) only updates most of the class. When students (readers) want to check the answer, they ask a few classmates and pick the most recent one. This way, even if some students missed it, enough of them will know the latest.
Example: writes to 3/5 nodes
if 2/3 of those written nodes fail it is still written on one of them
so we can use the one of them to get the value
Q: How is an atomic register better than a regular register?
A:
Atomic registers prevent “going back in time.”
Once someone reads a newer value, no one else will read an older value afterward. This strict order makes the system behave like a single, global timeline of events.
Simple Explanation:
Imagine a scoreboard. If one person sees the score change to 10, no one should later see it as 8. Atomic registers make sure everyone agrees on the timeline, even if they get updates at different times.
Q: What are safe, regular, and atomic registers? How do they differ?
Q: What are safe, regular, and atomic registers? How do they differ?
A:
Safe Register: Works only when there’s no overlap between read and write. If reads happen during a write, you might get a random value. Regular Register: Handles overlapping operations better. If a read overlaps with a write, it returns either the last completed value or the one being written. Atomic Register: Strongest type. Even with overlaps, it guarantees a clear order: once you read a new value, no one can read an older one afterward.
Simple Explanation:
Think of a whiteboard:
Safe: If you try to read while someone is writing, you might see gibberish. A safe register only guarantees correct reads when no writes are happening Regular: You either see the last full sentence or part of the new one. A regular register extends this to allow reads during writes but may return older or current values Atomic: You always see a clean, ordered version — like magic! Once someone reads "B", no one ever sees "A" again.
An atomic register provides a consistent global ordering of operations, even during concurrency, making it stronger than the others.
Q: How can we make a regular register atomic using timestamps?
A:
Add a timestamp to each value a writer sends. Readers only accept the highest timestamp they’ve seen. This ensures newer values always replace older ones.
Simple Explanation:
It’s like labeling each note with a date. Even if messages arrive out of order, everyone knows which one is latest. This way, no one accidentally believes an older message is the newest.
Q: What is Read-Impose Write-All, and how does it ensure atomicity?
How it works:
Read: The reader contacts all nodes to get their stored values (with timestamps). Impose: It picks the value with the highest timestamp. Write-All: It then writes that same value back to all nodes to ensure consistency.
Guarantees atomicity by:
Ensuring that every read leaves a trace, making sure later reads see at least that value. Overwrites older values even if they were temporarily missed by other nodes.
Fails when?
Only works under fail-stop assumptions — processes crash and never recover silently.
Analogy:
Like a student asks everyone for the latest answer, then announces it loudly so that everyone hears the same thing and updates their notes.
Q: What is Read-Impose Write-Majority, and how does it improve over Write-All?
A:
Similar to Read-Impose Write-All, but uses majorities instead of everyone. Reader gets the value from a majority, then writes it back to a majority. Works in fail-silent systems.
Simple Explanation:
Instead of asking and telling everyone, you only ask and tell most people. This saves time and still works, because the overlapping majorities make sure no one is too far behind.
Q: What problem do multiple writers cause, and how do we solve it?
A:
If two writers write at the same time, we might not know which value is newer.
To solve this, we use:
Timestamps to order writes. Writer IDs (ranks) to break ties when timestamps match.
Simple Explanation:
It’s like two people trying to update the same Google Doc. If they both type something at once, we decide who wins based on who typed later, or who has higher priority if they typed at the same time.
Q: How does Read-Impose Write-Consult-All work for multiple writers?
How it works (for multiple writers):
A writer consults all nodes to get the latest timestamp. It increments that timestamp and writes its new value to all nodes.
Guarantees atomicity by:
Ensuring every write has a unique, increasing timestamp, avoiding overwrites of newer values. Prevents conflicts between concurrent writers.
Why it helps multiple writers:
By checking before writing, it respects the order of the most recent values, preserving consistency.
Fails when?
Also relies on fail-stop systems.
Analogy:
A writer first asks, “What’s the latest story you’ve heard?” Then adds a newer one with a fresh timestamp so it doesn’t accidentally erase a more recent event.
Q: How does Read-Impose Write-Consult-Majority handle faults better?
A:
Writers ask a majority for the latest timestamp. Then write a newer value to a majority. Safer in fail-silent systems, but takes more steps.
Simple Explanation:
It’s like polling a big group to see the latest message, then sharing your update with most of them. Even if some people miss it, enough will know the correct latest value to keep things on track.
Q: Why does Majority Voting need timestamps but Read-One Write-All doesn’t?
A:
Majority Voting: Writers might update different majorities. Timestamps prevent confusion about which write came last. ROWA: Uses perfect failure detection – writer always knows who’s alive and updates all active copies. No version ambiguity.
Simple Explanation:
ROWA is like a teacher who always knows who’s listening. Majority Voting is like students passing notes – they need timestamps because different groups might get updates at different times.
