5 ms·

I've tried googling paxos algorithm a bit, but don't understand what it does and why it is useful. Could someone please explain it to me like I'm five?

antirez 7y ago
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.
- antpls 7y ago
  Does Paxos work in adversarial environment (where some nodes are compromised and try to trick the system by sending forged messages) ?
  - yodsanklai 7y ago
    No, but there are other versions who do. Look up byzantine consensus.
deleted 7y ago
[deleted]
truncate 7y ago
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/ https://www.the-paper-trail.org/tags/consensus/ [2] https://lamport.azurewebsites.net/pubs/paxos-simple.pdf https://lamport.azurewebsites.net/pubs/paxos-simple.pdf
vyodaiken 7y ago
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.
dharmab 7y ago
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/ https://raft.github.io/

antirez 7y ago

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.

antpls 7y ago
Does Paxos work in adversarial environment (where some nodes are compromised and try to trick the system by sending forged messages) ?
- yodsanklai 7y ago
  No, but there are other versions who do. Look up byzantine consensus.

deleted 7y ago

[deleted]

truncate 7y ago

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/ https://www.the-paper-trail.org/tags/consensus/ [2] https://lamport.azurewebsites.net/pubs/paxos-simple.pdf https://lamport.azurewebsites.net/pubs/paxos-simple.pdf

vyodaiken 7y ago

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.

dharmab 7y ago

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/ https://raft.github.io/