It's super simple. You have a network where sometimes messages don't get delivered. One agent (process, site ... ) sends a message m to a collection of other agents distributed around the network. How can the sender be sure that at least some number of the intended recipients got the message. This is what databases do with commit protocols. Essentially the same problem is generalized for so-called distributed consensus protocols - of which Paxos is a very complicated example. The simple solution is that the sender keeps sending either until a timeout happens or it gets ack messages from whatever number of recipients it needs to be sure got the message. That's it. If the recipients are executing a deterministic state machine and the messages are the inputs to that state machine, you can be sure all the ones that have received the same messages in the same order are in the same state.

It's goal in the end is very simple: you have N different state machines and you want every state machine to process the same operations in the same order. To do that you need they agree every time a new operation must be processed. (Multi) Paxos is an agreement algorithm that does that.

To add context, Paxos allows you to have the the same state across multiple servers without any manual master/replica failover, with allowances for a minority of the servers to go down due to upgrades or failures and with clients getting the same results no matter which of the servers they connect to. (In distributed systems this is called Consensus.)

It's used in distributed datastores like Zookeeper and Exhibitor, which are used in situations where you need both consistently and as close to zero downtime as possible. It also influenced Raft, a similar but simpler algorithm to accomplish the same goals. Raft is used by etcd, which is the database that powers Kubernetes.

Raft has a great website with deeper explanations at https://raft.github.io/

Start with understanding "Consensus problem". Paxos is one of the famous solution. There is blog called "The Paper Trail" which has lots of articles on this topic[1]. You should start with the oldest post IMO (from Three General Proble,, FLP impossibility, 2/3 phase locking, to Paxos). Once you have an idea, you can readup the "Paxos made simple"[2].

In distributed systems, each node needs to agree on facts (which could be value of a key, ordering of operations on an object etc...), and Paxos helps you with that.

[1] https://www.the-paper-trail.org/tags/consensus/ [2] https://lamport.azurewebsites.net/pubs/paxos-simple.pdf