Distributed Systems 2.2: The Byzantine generals problem

Accompanying lecture notes: www.cl.cam.ac.uk/teaching/212...
Full lecture series: • Distributed Systems le...
This video is part of an 8-lecture series on distributed systems, given as part of the undergraduate computer science course at the University of Cambridge. It is preceded by an 8-lecture course on concurrent systems for which videos are not publicly available, but slides can be found on the course web page: www.cl.cam.ac.uk/teaching/212...

[@yoonsikp]

This should be renamed the among us problem

[@weizhang7344]

so true

[@move1649]

thank you for the series! was searching your name from that data intensive book...looking forward to the 2nd edition!

[@SunnyGuptaTech]

Thanks Martin, the way of explaining the things is really awesome.

[@azixaka]

Great addition to your book. Thank you!

[@hackee647]

Say each general has a secret key they share with only one other general. So generals 1 and 2 have a secret key that only they know, and the same is true for generals 2 and 3 and 1 and 3. Each time they send a message they send two pieces of info, the message, and the message encrypted using the respective key for it's intended recipient. When the receiving party gets the message, they decrypt the encrypted piece in the message and compare it with the unencrypted piece. If they match, they know the message is valid. If they don't match, they know the message was tampered with along the way. This technique is used frequently today using what is known as an HMAC.

[@GooseBerry390]

This won't help if the general sends the wrong message to begin with, along with the correspondingly wrong ciphertext/hash.

[@degenyakuza]

@@GooseBerry390 That’s where the blockchain comes in to play

[@subratsingh6204]

@@degenyakuza 🤔

[@saikun0293]

Good explanation, understood really well!

[@MethodWive]

Very good and interesting examples

[@pinkylover911]

These problems are interesting and entertaining

[@seguirparticipando]

great work!!

[@Bialke]

In chess we called the solution "Zugzwang", when the only viable move is not to move, do not move! The thing is, that the solution is just complete, if the city is captured. So basically it is not about the communication between the troops or generals, it is about the communication between the city and the troops. In the beginning the troops are always a+1, of the city is a.
Zugzwang also is meaning, that a (city) and a+1 (troops) are viable under Zugzwang. (They are living.) To live means they can reproduce, become tired and hungry and they can communicate and have a hierachy. In the end if the generals are under Zugzwang they are out, so soldiers have go in the chain of command.

[@Zeropasswords]

you explain sooooooo well

[@mlworks]

Brilliant stuff.

[@mazenezzeddine8319]

Sounds like the byzantine problem fits more a trust/security course rather than a distributed systems course (through it fits this latter as well given the non 100% reliability of the network/systems/infra etc.. ). Thanks Prof. Kleppmann

[@SpiceAndSauce]

it fit perfectly. Distributed systems heavily rely on consensus and BFT is one of the main things.

[@ibra86ag]

interesting that wikipedia says that "The etymology of Byzantium is unknown.", may be add this info to the wiki page as well?

[@pavelhassan7457]

If you look at the Bank balance and assets of all those three general and how they earned it then you can learn a lot about those general before you appointed them.

[@brands2131]

You said the problem is unsolvable if more then 1/3 of generals are malicious. However didn't Satoshi Nakamoto solve this problem for at least less then 1/2 the generals are malicious? He solved this problem by proposing a "Proof-of-work timechain" (now called the blockchain), and implemented it in Bitcoin in 2008. As long as 51% of miners are honest, than nobody can fool anyone in maliciously crafting a transaction in a decentralized system (no central entity or bank to authenticate valid transactions).

[@_jeeves_]

I'm guessing the difference is that proof of work solves it in a probabilistic manner and doesn't provide iron-clad guarantees.

[@degenyakuza]

@@_jeeves_ It provides iron-clad guarantees, Go read the whitepaper Satoshi actually proved it with probability.

[@aamike82aa]

The actual Greek pronunciation of Byzantine is the one you're using!

[@obaidali8813]

Please make a course on cryptography thank you

[@tomxu1761]

what is the solution in practical to solve two generals and byzantine general probems, for example like this online shopping

[@khaldrogo9451]

Keep watching the series :) he talks about it.

[@theanigos]

Baaizaantaaine vs bizantine :) Nevertheless always love your lecture

[@RaduOleniuc]

Bizantine as the name come from bizantin (Greek and east europe).

[@eternaldoorman5228]

Bizzanteen sounds more like .biz!

[@donaldcarnegie3018]

Honestly this is a really bad analogy to describe this problem.