Algorithms

In this section, we will discuss the key algorithms in detail. We'll be looking at the two main types of fault-tolerant algorithms, CFT and BFT.

CFT algorithms

We'll begin by looking at some algorithms that solve the consensus problem with crash fault tolerance. One of the most fundamental algorithms in this space is Paxos.

Paxos

Leslie Lamport developed Paxos. It is the most fundamental distributed consensus algorithm, allowing consensus over a value under unreliable communications. In other words, Paxos is used to build a reliable system that works correctly, even in the presence of faults.

Paxos was proposed first in 1989 and then later, more formally, in 1998 in the following paper:

Lamport, L., 1998. The part-time parliament. ACM Transactions on Computer Systems (TOCS), 16(2), pp.133-169.

The paper is available here:

https://lamport.azurewebsites.net/pubs/lamport-paxos.pdf.

Note that Paxos works...