L6: Byzantine Fault Tolerance 

Same lol

Many thanks!

same here

You are so welcome!

Glad you like it!

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.

You're welcome!

Thanks!

Thank you!

Thanks, glad it is useful. ;-)

Thanks!

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. :-)

Thank you!

Glad you enjoyed it!

You're very welcome!

Glad you liked it!

Thanks!

Thanks!

@@DistributedSystems 100/100

Chris Colohan thank you!

Thanks!

Thank you!

Thank you!

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.

Thanks!

OMG

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 RU-vid, Lindsay Kuper does a great job going into more details in some of her videos: ru-vid.com === [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!

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.

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.

I like my bearzantine generals too. ;-)

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

Thanks!

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".

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?

Thanks!

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.

And yet... I still have yet to purchase a single cryptocurrency asset.

@@DistributedSystems Sorry that you are missing out :)

:-) The 737 Max incidents happened after I made this video.

That is a good solution but... it then creates a key distribution problem, which (depending on the domain) may be hard too.

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: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-LFZDpF_A-BE.html ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-Jp7T9qtuRIE.html ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-f1ZJPEKeTEY.html ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-MVPkHPEsC4Y.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.

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

:-)

Thanks! The Canadian in me totally agrees, but I currently live in the US so I'm using American pronunciations.