Chapter 5 Flashcards
Bro loves consensus (11 cards)
Q: What is regular consensus and what are its properties?
A:
Regular consensus is a decision-making process among distributed processes. It requires that:
Validity: The decided value must have been proposed.
Integrity: No process decides more than once.
Termination: Every correct process eventually decides. Agreement: All correct processes decide the same value.
Simple Explanation:
Imagine people voting for a place to eat. They all must agree on a restaurant, can’t vote twice, and the choice has to be one someone actually suggested. Regular consensus ensures this — but only among those who stay online.
Q: Why can’t consensus be solved in purely asynchronous systems?
A:
FLP impossibility says it’s impossible to guarantee consensus in a fully asynchronous system if even one process might crash. That’s because you can’t tell if a process is slow or dead — there’s no reliable way to make a decision.
Simple Explanation:
If a friend doesn’t reply, is it because they’re ignoring you or just lagging? In an async system, you never know — so it’s impossible to safely agree without assuming something extra, like crash detectors.
Q: How does Flooding Consensus work in the fail-stop model?
A:
Processes broadcast their proposed values in multiple rounds. A perfect failure detector (P) is used to ignore crashed nodes. Decision happens when two rounds see the same set of live processes.
Best case: Decide in 1 round Worst case: N rounds Message complexity: Up to O(N³)
Simple Explanation:
Imagine a classroom where students are shouting their lunch choices round by round. Some leave the room (crash). The class watches who stays. When the same group is there for two rounds, they agree on the lunch.
Q: How does Hierarchical Consensus work in the fail-stop model?
A:
Each process has a unique rank. In each round, the next-ranked process proposes a value. If that process is correct (not crashed), its value is chosen. Others wait their turn if earlier ranks fail.
Simple Explanation:
It’s like a ranked speaking queue. If the leader is silent (crashed), the next in line steps up. Eventually someone who’s still around will speak and be followed.
Q: What is uniform consensus and how is it different from regular consensus?
A:
Uniform consensus has the same basic properties, but its agreement condition is stronger: all processes — including faulty ones — must decide the same value.
Simple Explanation:
Even if a process crashes after making a choice, its decision must match everyone else’s. This avoids confusion when looking back at decisions made before the crash.
If someone leaves a group decision early (crashes), uniform consensus still forces them to have agreed with the group.
This way, when people look back, there’s no doubt or contradiction about what was decided.
Q: How does Flooding Uniform Consensus work? And why does it require N rounds?
A:
Same basic idea as Flooding Consensus, but every process must wait exactly N rounds before deciding — no early termination.
Simple Explanation:
You must stay the whole meeting before voting. This prevents someone from deciding too early and crashing, which could break agreement with others.
A:
Because no process can be allowed to decide early and crash — that would break uniform agreement. Waiting N rounds ensures all correct processes have seen the same values and faulty ones haven’t decided prematurely.
Simple Explanation:
It’s like requiring everyone to wait for the full group discussion before picking a winner. This way, no one can secretly make a choice and vanish.
Q: How does Hierarchical Uniform Consensus improve uniformity?
Q: How does Hierarchical Uniform Consensus improve uniformity?
A:
It adds a structured two-step process per round:
Propose Phase – The leader proposes a value and waits for acknowledgments. Decision Phase – Once enough acknowledgments are collected, the leader broadcasts the decision using reliable broadcast.
This ensures:
Even if the leader crashes after deciding, the decision still reaches everyone. All processes (even faulty ones) decide the same value — satisfying uniformity.
Simple Explanation:
The leader checks that everyone is ready before making the final call. Then it shouts the decision loudly (with reliable broadcast), so no one misses it — even if the leader vanishes right after.
Let me know if you want to compare this with regular consensus or flooding!
Q: What is the Epoch-Change abstraction and why is it needed in fail-noisy systems?
A:
It triggers rounds (epochs) with increasing timestamps when leaders change. It ensures that eventually, a correct leader will be used, and no earlier epoch is repeated.
Simple Explanation:
Think of it as retrying consensus with better leadership each time. After enough tries, a stable leader will be trusted by everyone and consensus can succeed.
Q: How does Epoch Consensus ensure safety and progress?
A:
Each epoch has a leader who:
Reads from a quorum to get the latest proposed value. Chooses the highest-round value (if any) to preserve previous decisions. Writes and broadcasts the chosen value.
If a new epoch starts, the current one is aborted. This prevents conflicts between decisions across epochs.
✅ Safety: No two different values can be decided in different epochs (thanks to quorum overlap and value lock-in).
✅ Progress: Eventually, a leader completes a round without being preempted.
Simple Explanation:
It’s like passing a group decision between team captains. Each new captain checks what was already agreed on before continuing — so no one forgets or contradicts past decisions.
Let me know if you’d like a comparison between Epoch Consensus and Paxos too!
Q: What is Leader-Driven Consensus and how does it handle failures?
A:
Runs multiple epochs. Each epoch has a leader trying to complete consensus. If it crashes, the next leader continues using its state. Eventually, the leader stabilizes and consensus is reached.
Simple Explanation:
It’s like trying to land a plane. One pilot tries, and if they fail, the next one takes over from where they left off — until one makes a safe landing (decision).
Q: What is randomized consensus and how does it differ from regular consensus?
A:
Randomized consensus solves agreement in asynchronous systems where deterministic methods cannot guarantee termination. It uses randomization (e.g., a shared “common coin”) to ensure:
Probabilistic Termination: With probability 1, all correct processes eventually decide. Validity: The decided value was proposed by some process. Integrity: No process decides twice. Agreement: All processes decide the same value.
Key Difference:
Unlike regular consensus (which needs failure detectors in crash-prone systems), randomized consensus guarantees termination probabilistically using random coin flips.
Simple Example:
Friends voting on pizza toppings but sometimes deadlocking. When stuck, they flip a shared coin (e.g., “Heads=Pepperoni, Tails=Mushroom”). Even if some friends leave the chat (crashes), they’ll eventually agree, thanks to the coin’s randomness.
Why It’s Used:
Works in asynchronous systems with crashes (fail-silent model). Avoids infinite loops: The coin ensures progress, even if messages are delayed.
