Distributed consensus
Distributed system
https://en.wikipedia.org/wiki/Distributed_computing A distributed system is a system whose components are located on different networked computers, which communicate and coordinate their actions by passing messages to one another. The components interact with one another in order to achieve a common goal. Three significant characteristics of distributed systems are: concurrency of components, lack of a global clock, and independent failure of components.
Properties of distributed system
- Concurrency: Each computer executes events independently at the same time.
- Lack of a global clock: There is no single global clock that determines the sequence of events happening across all computers in the network.
- Independent failure of components: It’s impossible to have a system free of faults.
- Crash-fail: The component stops working without warning (e.g., the computer crashes).
- Omission: The component sends a message but it is not received by the other nodes (e.g., the message was dropped).
- Byzantine: The component behaves arbitrarily.
- Message passing
- Sync
- Async
Details of distributed consensus
Symmetric, leader-less:
- All servers have equal roles
- Client can contact any server
Asymmetric, leader-based:
- Leader
- Follower
- Candidate: Candidate of a leader
- At any given time, one server is in charged, others accept its decision.
- Client communicates with leader
Byzantine fault tolerant
Both Paxos and Raft are not Byzantine fault-tolerant. The paper Byzantine General’s Problem
by Leslie Lamport, Robert Shostak, and Marshall Pease provided the first proof to solve the Byzantine General’s problem:
it showed that a system with x Byzantine nodes must have at least 3x + 1 total nodes in order to reach consensus
(Only works in synchronous environment).
We’re going to take a look at two algorithms (DLS and PBFT) that brought us closer than ever before to breaking the Byzantine + asynchronous barrier.
- DLS algorithm
- PBFT algorithm
- Nakamoto Consensus: Instead of every node agreeing on a value, f(x) works such that all of the nodes agree on the probability of the value being correct. Rather than electing a leader and then coordinating with all nodes, consensus is decided based on which node can solve the computation puzzle the fastest.