Skip to content

Latest commit

 

History

History
70 lines (56 loc) · 2.4 KB

consensus.md

File metadata and controls

70 lines (56 loc) · 2.4 KB

CAP theorem

In the presence of network partition, one has to choose between consistency and availability (tradeoff).

  • Consistency: Every read receives the most recent write or an error
  • Availability: Every request receives a (non-error)response - without the guarantee that it contains the most recent write
  • Partition tolerance: The system continues to operate despite an arbitrary number of messages being dropped(or delayed) by the network between nodes

Consensus

All non-faulty processes decide the same value(data consistency)

Model

  • synchronous model
  • asynchronous model

Fischer-Lynch-Paterson (FLP) result：

You can't do agreement in an AsynchronousMessagePassing system if even one crash failure is allowed, unless you argument the basic model in some way, e.g. by adding randomization or failure detectors.

Challenge

  • faulty processor
  • Byzantine faults, weakest type of failure and the most difficult kind to deal with. Allow arbitrary failures including malicious faults
    1. failure to return a result
    2. return of an incorrect result
    3. return differing results to different parts of the system

Solutions?

Common fault tolerant (unreliable processors, no malicious processors)

  1. Paxos
  2. Raft

Byzantine fault tolerance (Byzantine Generals' Problem, arbitrary failures)

  1. Byzantine Paxos
  2. Practical Byzantine Fault Tolerance Algorithm (PBFT)
  3. Zyzzyva
  4. Aardvark
  5. RBFT

Proof Of Work

  1. [Bitcoin POW]
  2. Cuckoo Cycle adopted by aternity
  3. Equihash adopted by Zcash

Proof Of Stake

  1. Ethereum Casper
  2. Delegated Proof of Stake
  3. Cardano Ouroborous
  4. Algorand
  5. Tendermint

Summary

openness throughput fault tolerance Consumption latency
2PC NO Good
Paxos Bad Good
Raft Bad Good
PBFT Bad Good
POW Good Bad
POS Good Bad
DPOS Medium Medium
Ouroborous Good Medium