consensus algorithms

• what is consensus?

Consensus is a fundamental problem in fault-tolerant distributed systems. Consensus involves multiple servers agreeing on values. Once they reach a decision on a value, that decision is final. Typical consensus algorithms make progress when any majority of their servers is available; for example, a cluster of 5 servers can continue to operate even if 2 servers fail. If more servers fail, they stop making progress (but will never return an incorrect result). 

https://raft.github.io/

A curated selection of artisanal consensus algorithms and hand-crafted distributed lock services.

https://github.com/dgryski/awesome-consensus

• Paxos is a family of protocols for solving consensus in a network of unreliable processors. Consensus is the process of agreeing on one result among a group of participants. This problem becomes difficult when the participants or their communication medium may experience failure.

Consensus protocols are the basis for the state machine replication approach to distributed computing

https://en.wikipedia.org/wiki/Paxos_(computer_science)


Paxos algorithm, which is obtained by the straightforward application of consensus to the state ma-
chine approach for building a distributed system
The Problem
Assume a collection of processes that can propose values. A consensus al-
gorithm ensures that a single one among the proposed values is chosen.
https://www.microsoft.com/en-us/research/uploads/prod/2016/12/paxos-simple-Copy.pdf

Paxos  is a simple protocol that a group of machines in a distributed system can use to agree on a value proposed by a member of the group
The basic idea is that each proposal has a unique number.  Higher numbered proposals override lower-numbered ones
http://read.seas.harvard.edu/%7Ekohler/class/08w-dsi/mazieres07paxos.pdf

• What is Raft?

Raft is a consensus algorithm that is designed to be easy to understand. It's equivalent to Paxos in fault-tolerance and performance. The difference is that it's decomposed into relatively independent subproblems, and it cleanly addresses all major pieces needed for practical systems.

An Introduction to the Raft Distributed Consensus Algorithm