L6: Byzantine Fault Tolerance
Vložit
- čas přidán 27. 07. 2024
- Describes the Byzantine Generals Problem in a hopefully understandable way. Inspired by the original paper by Leslie Lamport, Robert Shostak and Marshall Pease:
people.eecs.berkeley.edu/~luc...
Want more? Go read about "Practical Byzantine Fault Tolerance and Proactive Recovery" by Miguel Castro and Barbara Liskov:
www.pmg.csail.mit.edu/papers/b...
You can also read about (or watch the infinite number of videos on) Bitcoin/Blockchain. Sadly due to the Bitcoin mania many of these descriptions are less-than-fully-accurate as far as the fault model goes, so don't bet your money based only on them. ;-)
===
See www.distributedsystemscourse.com for more information about this series, the class project, and links to slides.
0:00 Introduction
0:14 Failure classification
6:00 Consensus: The Two Generals Problem
8:10 Two Generals Problem: solved?
11:54 The problem
15:25 The question
19:35 Simulation proof
21:11 What can you do?
21:37 Inductive Solution for Oral Messages
23:01 How this works with m=1
24:39 Running Time
I've made a presentation based on what I've learned from your video, my professor from uni was really impressed, thanks a lot!
Same lol
Hands down still the best explanation of this topic on the internet.
Thank you!
Sir, Thank you for putting the effort to make these videos. The content is very informative and I admire your presentation skills.
Many thanks!
This video was "too easy" to understand. Thank you for making it so clear!
precisely stated and crisp delivery...Enjoyed it and keep up the good work!!
@Chris, thanks for making this video! It's one of the better resources I found as an intro to the BGP> I really wish you had shown an example of the BGP where m > 1 though. That part is the part I have a hard time wrapping my head around.
same here
Absolutely beautiful, thank you for explaining the complicated ideas in the papers in such a clear manner.
You are so welcome!
Hello Chris,
I have to thank you for helping me get my dream job. I learned distributed system for my exam from your videos - you explain it so well and simple, it's just amazing. Keep up with the great work and thank you so much - for both knowledge and motivation. Have a nice day and don't forget to enjoy yourself!
Will do, and thank you for the very nice note!
@@DistributedSystems Hello Chris,
Your videos are really amazing. Could you please help in real time simulation of pbft over any simulator like cooja or any. It will be very helpful for me. Thanks in advance.
Amazing visualization for BGP! It really helps to understand the issue. Also, your explanations in comments make my learning robust! Thanks.
Glad you like it!
very good video. We need many more people like you to explain all these complicated stuff, cause many people cannot read complicated lemma, proof in all those maths /CS journal
paper.
I've never seen such a wonderful tutorial like this before. Thanks !
Thanks!
Thank you so much Chris for explaining this so beautifully!
Very easy to digest. Thank you very much for taking time to make this video!
You're welcome!
This is SUPERB stuff! Finally someone who talks in a very simple and non-encrypted non-mathematical non-nonsense manner! You ROCK!
Thanks!
GREEEEEEAAT EXPLANATION. Thank‘s a lot for this content, I put your link for my Video in the description- got a nice project where BFT is using. Would be very grateful for any feed🙏🙌
Thanks, glad it is useful. ;-)
Thank you so much ! I would love to see you make more videos :D
You take me to the new world.It is so fun !thank you
10:37 to 10:38 is really important
Great work! Made me understand the Byzantine Agreement problem and its solution!
Good stuff. Appreciate the succinct explanation.
This video deserves more likes and views!
Great video, I really like that u give us to solve problem
Another amazing tutorial :)
Amazing lecturer! Thanks so much
The Greatest Presentation of BFT ever!
Thanks!
excellent video! helps me a lot! thanks so much!
Thank you for the explanation!
Really awesome explanation
How are you able to explain things so clearly!? Amazing
Glad you like it. The short answer: iteration. I keep on refining my explanations until I can't think of any possible way of simplifying them any more, and only then do I record a video. Sadly, this takes a lot of time. :-)
Brilliant lecture! Thank you!
Absoulutely nailed the topic. Thank you.
Glad you enjoyed it!
Very well explained, thanks.
Great explanations, thanks.
Thank you . Great explanation ..
This is such a great explanation , 10/10!
Thanks!
@@DistributedSystems 100/100
Thank you so much! This is crystal clear!
Glad you liked it!
excellent of excellence.. I love your video tutorials
Thank you!
Amazing explanation, thank you very much!
You're very welcome!
Hi, thank you very much for the amazing video. One problem is still spinning around my head. I a case with two traitors, e.g. two lieutenant, how pass one a wrong message. My n=7 (1 commander, 6 lieutenants). Im sum i got 36 messages (6 send by the commander, 30 send by the lieutenants) in a 6 x 6 matrix. For each lieutenants i got (A, A, A, A, R, R) so they would agree on attack. How is the table with m = .. and O (n^x) to read in that context. May someone can give an example for my case? Thank you :)
Great Tutorial on this problem! :)
Well explained . Kudos
Great talk!
o man the explaination is beautiful I love u so fucking much! thank u . Please make a video about pbft ~
This is the professor that I would like to see in the class.
Thanks!
I am just wondering aloud - is there any similarity between the 2 Generals problem and prisoner's dilemma from game theory...
Hi Chris Colohan. I am a student and I would like to know where can I find the paper with the mathematical proof of the Oral messages. Good video and explanation!
I'm barely learning about this because I like bitcoin. I've read different consensus algorithms, but it's difficult for me to understand because I have no math or computer background.
Is bft the general category and PoW or PoS different implementations? Or are they all different?
Great video!
Thank you!
hey man great video, thanks!
Thank you!
thanks, that was great
I have a doubt, can anyone please help me with how does the numbers of messages sent increases exponentially with an increase in the no of traitors? how are 0 messages being sent when there are no traitors and how are n^2 messages being sent when there i 1 traitor (m=1)?
How does the time complexity become O(n ^(m + 1)) ?
Really great lecture! Do you have links to the follow on papers? Looking in particular for ones dealing with allowing for cryto
Chris Colohan thank you!
Thanks!!
Bear-zantine generals are so cute!
Why can’t consensus be reached with 6 generals if there are 2 traitors? 3 would say attack, 2 would say retreat.
Excellent (:
Thank you.
OMG
Great video for Byzantine problem. The point is the last message may be lost again and again no matter how many ACKs.
Thanks!
this is the best side of the internet
Thanks!
Thanks for the video. One question though. How is consensus reached when one faulty commander is giving faulty information to 4 loyal lieutenants?.
Say p0 is the traitor commander and sends 0 to p1, 0 to p2, 1 to p3, 1 to p4. How are they going to be able to reach to a consensus since majority cannot be achieved?
That's a good question!
The simple consensus algorithm presented here is answering the question "if there are enough non-evil computers in your system, is it possible to get a consensus?" And the answer is "yes, but only if you are lucky enough to promote a non-evil lieutenant to act as the commander. Otherwise consensus will not be achieved". So the system is "safe" -- if you get a consensus, it is a good one, otherwise you don't get a consensus.
But as you point out, safety is not enough for most real applications! You also want your system to be "live". In this case, liveness could be expressed as "if there are enough non-evil computers to achieve consensus, will consensus be eventually achieved?"[1]
So how do we add a liveness property to our algorithm?
There are many ways to do this, but one way is to tell clients to use randomness and timeouts. When a client wants consensus, have them pick a lieutenant randomly to act as a commander. That way they have a chance of picking a good one. And then if the commander doesn't respond with a consensus before your timeout expires, pick a new commander at random and try again. Eventually you'll talk to a good commander, and assuming enough computers are non-evil, consensus will be achieved.[2]
I'm being a bit sloppy with my definitions here, if you start reading papers on consensus algorithms you'll find that there are all sorts of interesting problems that need to be solved when building a real system. If you want to dive deeper into this on CZcams, Lindsay Kuper does a great job going into more details in some of her videos: czcams.com/users/lindseykuper
===
[1] If you were feeling pedantic, you might add other constraints: like when considering liveness computers can't switch between non-evil and evil partway through the algorithm's execution (otherwise you'd have to consider each and every transition point and figure out all possibilities and make sure your algorithm still works).
[2] This solution assumes that there exists a useful timeout value (a.k.a., it is safe to assume that consensus will be achieved in a fixed amount of time). Sometimes systems don't have this property. For example, in a system running on cell phones, sometimes phones turn off, or go out of range. So any design has to account for the fact that nodes may lose connectivity with each other for indeterminate periods of time. If you are building such a system, then you'd have to ask yourself: "is liveness is even possible to achieve?" And if so, you'd have to carefully define what you mean for the system to be "live".
@@DistributedSystems Thank you!
Can you explain why the Bitcoin blockchain would need a 51% attack to take it down as opposed to >33% shown in this video?
That's because bitcoin solves byzantine fault tolerance using computational power (And every other general or nodes believes him because it is nearly impossible to solve the puzzle with few power or time thus all other nodes trust his work). 51% attack means 51% computational power resting in a single owner(say nearly impossible super computer). So that computer can effectively produce hash or solve the puzzle faster than the rest of the world( 49% computing power ). Thus producing the blocks much faster than the entire world.
To be more specific consider A with 51% of computational power and rest of the world (B-Z) having 49% of computational power.Nearly it takes 10 minutes to create a block.Bitcoin nodes accept the longest chain as valid. So considering this scenario A can solve the puzzle much faster than rest of the world. Thus nullifying the work of others and A alone can create blocks thus making the system i.e bitcoin, worthless.
Amazing video. The bears actually helped too lol.
I like my bearzantine generals too. ;-)
In two generals scenario assuming that network works, being one general a traitor, why no consensus is required? If a general A sends a message "I'll atack" to general B (traitor) and he responds "Ok, I'll attack too" and don't attack, is there no problem?
When we are discussing the two generals problem, we are assuming that the generals can't become traitors -- the idea is to model a system with working nodes, but unreliable communication.
If you assume that a general can become a traitor, then there is no solution -- as we learn later in this video if you have 1 traitor then there is no solution unless you have at least 4 generals.
I have a question, in bitcoin when they use this solution with more than million nodes, won't it prove it be extremely expensive and complicated, so instead is there any other solution to this problem without having to spend these many resources
I'm currently developing a video comparing consensus approaches, including the one used by Bitcoin. Subscribe if you want to be notified when it is done. ;-)
It depends on what you think "the problem" is.
If your goal is to create a replicated system which survives some node failures -- the Bitcoin approach is incredibly slow, wasteful of resources, and overly complex. You are way better off adopting either a fail stop consensus solution like Paxos or Raft, or a byzantine fault tolerant solution like the simplest one presented here, or PBFT (Practical Byzantine Fault Tolerance, a better solution that uses cryptography to solve consensus in a faster, but sadly more complex and harder to explain way than solution presented here). Fortunately for the Bitcoin folks, simply solving consensus isn't their goal. They want to create a crytpocurrency, which adds a whole bunch of other constraints.
The success of Bitcoin has launched entire fields of research trying to answer the question "can't we do this in a less resource intensive and crazily complex way?" So far there isn't a clearly better way of doing it (if you believe "the market" as the final word on this), although there are many solutions which improve on Bitcoin, including a series of Proof of Stake algorithms which avoid the wasteful energy usage of Bitcoin's Proof of Work.
Chris Colohan thanks so much and yes I will subscribe, also that means that if someone is able to find a solution to the byzantine generals, one that requires less resources, it would make them pretty rich
I didn't under stand that how 4 traitors in 12 generals will not be tolerated. As each will receive attack(actual value) from 7 generals and retreat(false value by traitors) from 4 traitors. In this case there is attack value in majority and they will attack. I am thinking there is
bitcoin.stackexchange.com/q/85660/85725
Good question. You had me stumped for a minute, so I had to reason this out:
a) We know that you can't solve the case with 3 generals where one of them is a traitor, given the example shown in this video. Clearly the threshold is not 50% in this case.
b) We have a proof in this video that this generalizes this. It proves that there is no solution to 3m+1 generals with >m traitors.
c) You are claiming that a simple majority vote solves this problem for 12 generals and 4 traitors.
So either (a) is incorrect, (b) is an invalid proof, or (c) doesn't work.
I'm going to claim that if you look closely at (a), you won't find a hole. It is correct, since we just exhaustively enumerate all the cases in the video (check me on this!).
The proof in (b) is subtle and hard to understand. Try reviewing it a few times and see if you can find a hole.
But does (c) work in all cases? If the commander is loyal, then it sends an order to all lieutenants, and that means that all 11 lieutenants hear the same thing (either attack or retreat). The 7 loyal lieutenants will hear the correct order from the commander, a correct relay of that order from 6 of their peers, and an incorrect order from 4 of their peers. By taking the majority, they can come into consensus, great.
If the commander is a traitor, then it can send a different order to all lieutenants. Let's say it says "attack!" to loyal lieutenants 1..4, and "retreat!" to loyal lieutenants 5..8. The traitorous commander then orders its three traitorous lieutenants to agree with it -- to tell 1..4 "attack!" and tell 5..8 "retreat!". If 1..4 and 5..8 simply used majority vote, they would not agree, and consensus would fail.
So the majority vote algorithm you propose doesn't achieve consensus if the commander is a traitor. (And arguably it doesn't work with only 3 traitors either if the commander is a traitor. Or 2 either...)
Of course it is possible I misunderstanding the algorithm you are proposing in (c). But does this answer clarify matters?
Bitcoin was nearly trading at $650 at the time this video was made!
And yet... I still have yet to purchase a single cryptocurrency asset.
@@DistributedSystems Sorry that you are missing out :)
well explained @24:21
Thanks!
15:33 Why is it Point to Point and not Peer to Peer Communication?
Peer to peer implies that nodes can talk to each other -- but does not specify that one node can't talk to more than one node at a time (broadcast).
Point to point implies that there is no broadcast mechanism available, and all communication is done between pairs of nodes.
There may be a solution to the two generals problem. The two generals with their armies must meet. In computer terms the question is how to make a temporary super node that is an aggregate of several nodes.
Absolutely -- but if you do that, you've effectively solved the "one generals problem", as you've combined the two generals into one. If your problem allows you to use a centralized solution instead of a distributed one, then lots of things become simpler. (And doing this is a great solution if your problem allows for it!)
Point taken. However since data is easier to move around and transform than armies are, couldn't you make copies of the "armies" to combine into a single amalgam that would have a deliberately short life span. The idea is that the nodes are preserved but the interaction of the two nodes together might, by some means (still thinking about how this would be done) guarantee that each node has to be honest about their intent once the amalgam is reviewed by both. (PS it may be obvious by now that I am not an IT guy I just like thinking about problems. Thank you for posting the video and responding to my comment)
@@domainofdotart6125 Yup, that works. But once you've done that, you have designed a system which effectively has a single master and a hot spare. Which is a perfectly good design -- it is quite popular in databases, for example. But it is not good enough if you are trying to design a system which can withstand all possible node failures at all times, or that requires near instantaneous fail-over.
Think of a bank processing financial transactions. With a replicated database, you can take your money out of your account on the main server using an ATM, and then there is a small window of time before that money gets debited out of your account on the replica server (while the replication happens). If your main server dies during that time, is it okay for the bank to forget about giving you your money? What do they do when the count of bills is off at the end of the day?
You may deem this to be "okay", if you have an insurance policy which covers this situation (and your insurance bill is cheaper than redesigning your system to tolerate this type of fault). But you'd deploy a byzantine fault tolerant solution if you deem it to be "not okay".
2:24 don't know about Boeing :D
"They built a Byzantine fault tolerant flight system into these aircraft" Lol I can't fault you for not knowing about the Boing 737 but it is ironic that you mention it.
I'm curious what aspect of the 737 you think applies here. As I understand it the 737 series up until the 737NG uses a somewhat traditional hydraulic control system, without control computers in the loop (it does have an A and B system so that a leak or pressure failure in one hydraulic circuit doesn't cause controls to be lost). The trim controls were electric, but I don't believe there was any computer logic in the trim controls outside the autopilot (but I could be wrong).
The 737Max (which was not certified by the FAA until 5 months after this video was published, and not delivered to a customer until 7 months later) has gotten notoriety for its trim control systems failures. From skimming some articles I don't see anything saying the flight controls were changed from hydraulic to fly-by-wire, so I assume they remained hydraulic. The trim controls continued to be electric, but the MCAS system was added in the stabilizer trim path -- and it had some serious design flaws. In particular, a single bad AoA input managed to cause fatal trim runaway*.
I'm not aware of anywhere in the 737 (or 737Max) that used a Byzantine Fault Tolerant approach. From what I read, even in the 737Max they had two redundant flight control computers, and if one was suspected to be bad the pilots could toggle control to the second independent computer. There was no automated consistency monitoring between the computers (this has been changed after the grounding of the fleet).
Is there a place where Byzantine fault tolerance is used in the 737? I'm a flying geek (can you tell?) so I'd love to learn more. :-)
* An aside -- I once encountered a trim runaway due to a stuck switch while I was flying a Cessna 172. It is not a fun thing to deal with even in such a simple plane.
This was a great video! Have you heard of Hedera Hashgraph which is BFT?
Is it coincidence that you don't put 737 Max series in fault tolerant category ? 😂
:-) The 737 Max incidents happened after I made this video.
The solution is using public key cryptography
That is a good solution but... it then creates a key distribution problem, which (depending on the domain) may be hard too.
Doesn't BitCoin solve the Byzantine Generals problem?
Nope.
Bitcoin allows a large number of computers to come to a tentative consensus. Which can then later change if a larger number of computers come along (so, was it really a consensus?). In effect, it solves a different problem. Also, it is orders of magnitude slower in coming to this tentative consensus.
This is not to say that Bitcoin is bad. It lets you achieve a form of consensus among computers when arbitrary computers can join or leave the system at any time. This is a very different problem space than what the Byzantine Generals Problem paper describes.
If you want to learn more about the relationship between the Byzantine Generals Problem and Bitcoin consensus, see the videos later in this series I made on this topic:
czcams.com/video/LFZDpF_A-BE/video.html
czcams.com/video/Jp7T9qtuRIE/video.html
czcams.com/video/f1ZJPEKeTEY/video.html
czcams.com/video/MVPkHPEsC4Y/video.html
@@DistributedSystems thanks, I am going through your Block Chain Vids right now. Currently working on a small scale distributed system where I assume low availability but all actors are trusted. Since the implementation is for small WLAN network I have yet to find any suitable solution out there and likely will develop a custom protocol. :) Your videos are a great help, thanks.
The proof of the impossibility solutiom wasn't well explained
Sorry to hear about that. I initially had a lot of trouble wrapping my head around that proof myself, and so I attempted to simplify it as much as possible for this video. It is possible I went too far. Do you have any suggestions on how it could be improved? Thanks!
@@DistributedSystems surly, thanks for your effort. I am just aiming to understand it from the Pease's article... I think it is important to follow the whole proof ( step by step ). Thanks for your reply
Too big brain for me
Bearzantine lol!
:-)
0/10 not zero based indexing /s
Loving your videos. lieutenant -> /lɛfˈtɛnənt/
Thanks! The Canadian in me totally agrees, but I currently live in the US so I'm using American pronunciations.
Great explanation !! Thank you.
Great explanations, thanks.