Consensus is impossible

Summary

This video explores the concept of impossibility proofs in distributed systems through a playful analogy of a Bizarro version of Scrabble. The game involves three players with secret letters trying to agree on the highest letter, but a single fault can break the system, demonstrating that it's impossible for computers to always agree on a result with 100% certainty. The discussion delves into the nature of network faults, Byzantine faults, and how distributed systems manage these challenges. It highlights the importance of knowing system limitations and embracing trade-offs to ensure reliable performance in the real world.

Takeaways

• 😀 Impossibility proofs are methods of reasoning that show what problems are logically impossible within certain systems, helping researchers avoid wasting time on impossible solutions.
• 😀 In distributed systems, impossibility proofs are essential for understanding the limits of what can be done with networked devices and how faults affect system behavior.
• 😀 The game of Bizarro Scrabble serves as a metaphor for explaining how faults and local knowledge limitations in distributed computing systems lead to logical contradictions.
• 😀 In the Bizarro Scrabble game, players can only communicate through passing tiles, which simulates point-to-point communication in distributed systems.
• 😀 Fault tolerance in distributed systems is expressed as a ratio (e.g., 2T+1) and ensures the system works despite faults by requiring extra nodes for redundancy.
• 😀 A fault, like a player picking a blank tile at random, can create a scenario in which the system (game) enters a state of logical impossibility, even with a single fault.
• 😀 This 'single fault scenario' in the game demonstrates that it's impossible for all players to agree on the correct letter in the presence of faults, highlighting limitations in networked systems.
• 😀 Real-life distributed systems, like databases and bank account balances, are also vulnerable to faults and inconsistencies due to network issues, making fault tolerance crucial.
• 😀 While 100% certainty and flawless communication might seem ideal, in practice, most distributed systems aim for high reliability (e.g., 99.99999%) and can function with a small amount of downtime.
• 😀 Solutions to problems like Byzantine faults (which create fabricated messages) may involve adding more players or adjusting algorithms to identify faulty messages, though these changes don't guarantee perfect outcomes.

Q & A

What is the main objective of the Bizarro version of Scrabble described in the video?

The main objective of the Bizarro version of Scrabble is for each player to have a secret letter, and the players must agree on the highest letter in a given round.

How does Rick's action with the blank tile demonstrate an impossibility in distributed computing?

Rick’s action of picking a blank tile and randomly selecting a letter proves that it’s impossible for three computers to agree on a letter with 100% certainty, illustrating a flaw in distributed systems that can occur with any network involving more than two devices.

What is an impossibility proof, as explained by Brooklyn Zeno?

An impossibility proof is a way of reasoning about a problem to establish the boundaries of what is logically possible. It helps in identifying situations where a proposed algorithm may lead to contradictions or be incompatible with reality.

Why are impossibility proofs useful in research and engineering?

Impossibility proofs help researchers and engineers understand the limits of what is possible, allowing them to avoid wasting time on solutions that are logically impossible, and to focus on practical approaches within known boundaries.

How does the concept of 'local knowledge' apply to distributed systems?

In distributed systems, 'local knowledge' refers to the information a node (or player) has access to directly, such as the tile in front of them or messages they've received. Nodes can't be sure of the global state, such as the status of other nodes or network failures.

What does the term 'fault tolerance' mean in distributed systems?

Fault tolerance refers to a system's ability to continue functioning despite failures. It is often expressed as a ratio of redundancy, such as 2T+1, which indicates how many faults can be tolerated while still maintaining the system's functionality.

What is the scenario described in the script that proves the game cannot work with 100% certainty?

The scenario involves Rick, who picks a blank tile, sends a random letter, and causes a situation where two players, Quty and Rick, correctly answer 'D', while Peaches incorrectly answers 'A'. This creates a logical inconsistency where no player can be definitively declared correct.

What are Byzantine faults, and how do they affect distributed systems?

Byzantine faults occur when nodes in a distributed system send incorrect or conflicting messages, making it difficult to determine which information is trustworthy. These faults pose a challenge in ensuring consensus and correct operation in the system.

How could adding a fourth player solve part of the issue in the Bizarro Scrabble game?

Adding a fourth player would increase redundancy, allowing the majority rule to apply and prevent a split-brain state. However, it would not resolve the core issue of a fabricated letter (like the 'A' Rick created) causing a false majority.

What is the trade-off between reliability and system performance in distributed systems?

In distributed systems, there's often a trade-off between achieving high reliability and system performance. While 100% certainty is impossible, systems aim for high reliability (e.g., 99.9999%) where minor downtime is acceptable, reflecting a balance between performance and fault tolerance.