Consensus (computer science) - Wikipedia

Consensus in Distributed Computing

• Definition: The consensus problem involves multiple processes or agents in a distributed system agreeing on a single data value, despite potential process failures.
• Core Requirements:
  • Termination: Every correct process eventually decides on a value.
  • Integrity: The decided value must have been proposed by a process (prevents trivial/arbitrary outputs).
  • Agreement: All correct processes must decide on the same value.
• Performance Metrics: Evaluated by running time (rounds of message exchange) and message complexity (total traffic generated).
• Failure Types:
  • Crash Failure: A process abruptly stops and does not resume.
  • Byzantine Failure: A process behaves arbitrarily, potentially sending contradictory or malicious data. These are more disruptive and harder to mitigate.
• Key Protocols & Models:
  • Single-value: Paxos (agrees on one value).
  • Multi-valued: Multi-Paxos and Raft (agree on a series of values/history).
  • Communication: Can be synchronous (rounds) or asynchronous (no timing guarantees).
• Impossibility Result: The FLP impossibility result (1985) proves that deterministic consensus is impossible in a fully asynchronous system if at least one process can suffer a crash failure. Randomized algorithms are often used to circumvent this.
• Permissioned vs. Permissionless:
  • Permissioned: Fixed, known set of authenticated participants.
  • Permissionless: Open participation; requires mechanisms like Proof of Work (Bitcoin), Proof of Stake, or Proof of Space to mitigate Sybil attacks.
• Real-world Applications: Cloud computing, blockchain, database transaction ordering, state machine replication, clock synchronization, and control of multi-agent systems (UAVs, robots).