Paxos in Pictures: Lamport's Distributed Consensus Algorithm
Вставка
- Опубліковано 24 тра 2017
- Paxos is a computer algorithm to help a network of computers agree on a proposed value. It is hard to understand at first. This video attempts to explain Paxos intuitively yet rigorously. The content comes from Lamport's 2001 paper "Paxos Made Simple".
Note that this video is not as rigorous as the paper it's based on. Specifically, it doesn't contain a precise statement of what Paxos accomplishes and it doesn't say how to optimize Paxos or deal with corner cases. For that, please see the referenced paper "Paxos Made Simple". The intent of THIS video is simply to provide a nice explanation and a visual illustration of the basic idea behind the algorithm.
Slides:
justinppearson.com/research.ht...
References:
Lamport, Leslie (2001). Paxos Made Simple ACM SIGACT News (Distributed Computing Column) 32, 4 (Whole Number 121, December 2001) 51-58.
research.microsoft.com/en-us/u...
en.wikipedia.org/wiki/Paxos_%...
More videos, projects, code, presentations, contact info: justinppearson.com
(c) 2017 Justin P. Pearson. All rights reserved.
After searching and learning a number of tutorials about Paxos algorithm, I would have to say this one is the best one for both explanation, example and slides, especially for the beginners. Clean, Simple and easy to understand the general idea of Turing Award winnner's contribution.
One of the most clean explanation i've ever seen, not only for Paxos but for computer science topics in general. Thank you.
At your service! Thanks for your kind words.
Love this, thank you!
Best explanation of Paxos I've seen. Thank you.
Best explaination on Paxos ... Amazing clarity... Thank you
by far the best video about the paxos algorithm damn
really awesome explanation.. I have gone through many video's and documents. Finally I got an idea.Thanks
Very clear presentation. Thanks !
Wonderful explanation and THANK YOU!
Super crystal explanation. A+.
Thank you for doing this.
It is essentially “Paxos made simple, made simple”😃
Haha, thank you for your kind words!
I love how he almost jucked himself!
Great explanation!
Thank you ! It was really really helpful
Nice explanation. Thanks.
Awesome, great job! :)
Thank you ! Nice explanation.
Happy to help!
You are the best. Thank you very much
You are most welcome! Thanks for the feedback.
Bestest explanation for paxos ever.
Can we get the slides?
Thanks very much! Yup, the slides are here: justinppearson.com/research.html#paxos-in-pictures-lamport-s-distributed-consensus-algorithm
hi, the explanation is super cool! and could you please upload the subtitle as well? since the auto-generated subtitle is recognized as korean, very confusing and weird. that will greatly help those people who has a little difficulty in catching with your speaking speed or who is non english native speaker, thanks a lot!
When is the proposal saved in acceptors ? after it has learnt that majority has accepted the value rightt?
Actually, the Acceptors don't worry about majorities. Rather, they do two things: (1) they remember the highest-numbered proposal they've ever seen, (for the purposes of sending the highest-numbered proposal to the Proposers), and (2) for any AcceptRequest they receive, they forward it inside a Decision message to all Learners. (Check out 7:00)
This was pretty awesome. Some minor comments though
1. Style: Loved the "You're Here" icons
2. Style: Maybe you can go a bit easy on "By the way"
3. Content: You mentioned that all nodes start with local unique IDs. I'm not clear about how they are mapped and ordered globally. More concretely, why is Carl's request #2 and Alice's request #1? Which component is doing lexicographical comparison?
4. Content: How long does the system wait to determine that there are no proposals bouncing on the network?
Thanks again for such a great demo!
Thanks for the feedback @Manu Anand. Regarding (3): Paxos assumes that each node has an ID that can be ordered with respect to other IDs and won't change in the middle of running Paxos. There are lots of options for this: If all the nodes are running on the same machine, you could use the process number (found by running `ps` at the command line). If the nodes are distributed across a network, each could use its IP address, interpreted as a string or as a 4-byte integer. Then, each node starts their Prepare Requests at 1 and they append their own name (process id) to it. So Alice's first Prepare Request is numbered (1,"alice"), which comes before Carl's Prepare Request of (1,"carl"). In the video, I just used #1 and #2 for brevity.
Regarding (4): Because Paxos was designed for an asynchronous system (where there is not an upper bound on how long a message could be in the air), Paxos specifies only that the nodes will "eventually" reach consensus. In reality, we can't wait forever, so some heuristic is used (probably based on estimates of probabilities of packet times and packet drops).
Great video but there's one thing I'm not getting.
It seems like once everybody agrees on "carl 4ever" there can never be anything else. While "carl 4ever" can't be undone, there can be another consensus on a 2nd value, right? If this were for a distributed database, you would want the system to get consensus on multiple statements in an order and not have the system only accept one statement ever.
So once everybody agreed on "carl 4ever" how and when does the new round start?
Good question @112Nelo. You are correct -- once Paxos completes, no node can ever change the agreed-upon value. But as you point out, that doesn't seem useful in a real-world system; a distributed database needs to be continually coming to consensus on lots of new values. One solution is to have an array that you use as a transaction log for the state of the database. Each element of the array records a database transaction, and the nodes run Paxos on each element of the array. This ensures that each node has the same transaction log, and therefore each node's database is in the same state. For more information, see the class project that implemented this idea:
justinppearson.com/projects.html#mapreduce-paxos-class-project
A common misconception, that I also fell victim to, is that PAXOS == a distributed log algorithm (a log being an immutable sequence of values). But thats not it, PAXOS is used to select a singular value. You tie multiple PAXOS 'rounds' together to make the log. This is what funskits says in his reply, I am just reiterating it. Hope this helps you and others!
Hay quá, ghé nhà nhau chơi
Is your real name Carl? :D
joao4evr