For a proposal i with value x:
1. Ask everyone not to participate in proposals older than i, get a majority to agree and send back any previously accepted values.
2. Ask everyone to accept proposal i with the newest previously accepted value or x if none, get a majority to accept.
- On failure, restart with i > max(previous proposals)
That is the Paxos algorithm.
Its fault-tolerance comes from the fact that you can tolerate losing the minority (1 out of 3 / 2 out of 5). There's no magic. If the majority fails, Paxos blocks. If two proposers keep blocking each other's proposals by going through round 1, Paxos can take forever.
The goal of Paxos is to agree on 1 value. Once consensus is reached (majority agrees), the value can never be changed, since no one can complete round 1 without getting back the newest accepted value from at least one node. However, you can run Paxos again and again to agree on a sequence of values (e.g. transitions in a state machine). This is Multi-Paxos.
The Paxos algorithm is optimal, but Multi-Paxos allows for a lot of optimizations and there is no clearly defined implementation. A pretty typical optimization is to elect a leader (through Paxos) which makes the proposals. This avoids duelling proposers and ensures you have a node that is always aware of the latest accepted value. Making this optimization requires you to make decisions that fall outside the scope of Paxos, such as how long a node remains leader, what happens if the leader fails, and what happens if two nodes think they are the leader. These optimizations can easily cause you to lose the fault-tolerance and consistency guarantees that Paxos gives you within the scope of reaching consensus on a single value.
It's important to remember that Paxos itself is easy to understand and a lot of the problems in Multi-Paxos can be solved by running Paxos. You need to familiarize yourself with it as though it was a programming construct.