Two Generals' Problem Explained
Vložit
- čas přidán 27. 07. 2024
- The Two Generals' Problem, also known as the Two Generals' Paradox or the Two Armies Problem, is a classic computer science and computer communication thought experiment that we're going to talk about in this video.
Also, please check the related blog post
finematics.com/two-generals-pr...
"Some constraints and tradeoffs in the design of network communications" paper ►
hydra.infosys.tuwien.ac.at/tea...
Website ► finematics.com
Follow me on Twitter ► / finematics
Donations:
Bitcoin ► 18ngQa7qzfg9RpstBz3ZCSm2fAzm6tqaa4
Lightning ► tippin.me/@finematics
Referral links:
Brave Browser ► brave.com/fin661 (ads-free browsing)
Ledger Nano S ► shop.ledger.com?r=2af228941155 (hardware wallet for crypto)
If you like this video, give it a like, share it and subscribe to my channel.
Thanks for watching!
Thanks Finematics for explaining so well! We need people like you in CS who make it easier for others like us to understand the concept. Visual approach works best.
Thank you Pooja!
@@Finematics Hey, in the last strategy wouldn't the interval to send messengers be 40m? Otherwise they'd be sending an extra messenger. Or is that extra messenger expected? I guess that works because it's just a single extra message but it cuts the communication time in half.
Can't wait for the generalized version. Byzantine generals problem.
Best video for two generals' problem. thanks for your solution!
great! totally underrated content!!
Wow...i really appreciate this explanation.
Thank you so much for making such a clear video! I love Tom Scott, but I think your video is better explained.
Thanks a lot Casey!
awesome video ，thank you
Anyone here from tom scott?
Help. Until now I thought I was an individual.
Haha great guessing. Nice
That guy didn't give solution thankfully this guy did
He definitely plagiarized this guy
T
Yup
Loving your work Finematics!
Thanks Jeanette!
Thank you.
Thank you
Nice video. I don't think you ever created the follow video about the "Byzantines Generals Problem"
Hi Finematics! I love your vids, and seen dozens of them. Can someone please let me know where I can find the Byzantine's Generals' Problem ("next video") that doesnt show up anywhere? thanks
I think I have at least two approaches to this problem, but if people are saying there is no solution, then perhaps I'm wrong :)
In short: Alice sends Bob a message to attack. Bob replies with agreement and a first secret. Alice replies with second secret. Bob replies with same second secret, and they send that second secret a few times until it's clear that both parties are on the same page. Messengers are sent every 20 minutes with their own message and information about the last message their general got, with time stamp. If either party haven't heard about another for 3 hours, the session expires. I mean - they postpone the attack to another day. Simple.
Or, they can just use their cell phones to communicate directly with each other in real time, right?
@@Christopher-of-Columbus Their telephone call could also be caught by enemies :)
... or Alice sends Bob 2 or 3 messengers (the more messengers the better) at the same time with the same message memorized while also carrying a paper or scroll with a fake message in case of capture. Bob repeats the same procedure and sends 2 or 3 messengers back with memorized reply and fake paper reply. If the fake messages are designed effectively to produce a certain effect if read by the enemy then it can confer advantage to Alice and Bob.
Best explanation video
thanks!
5:30 There ARE a few practical approaches.
6:35 MessEngers.
Suppose there's a probability p that a given message Makes it through is there a strategy which maximizes the chances of coordination
wouldn't it work if the general A jut sends back 3rd a message confirming the confirmation because A has agreed a time and B responded therefore the 2 parties are already in agreement so the 3rd message just confirms to B that attack is a go, am I wrong?
Realistically, that would probably happen, but if we take absolute certainty into account, that doesn't work. Because General B can't be certain that the 3rd messanger returned to A.
If B did not get the 3rd message from A, B thinks A may not have received B's second confirmation message, B thinks A may not attack.
6:22...how does the general know there was 100 messages sent ?
let the generals whatsapp each other they confirm with two blue tick mark
I will write that in my exam!
thanks
why not send more than 1 messenger at different times
Can't you use smoke signals.
How am I able to coordinate plans with any friend over text in this case ?!
Text messages are delivered via SMS (short message service), and many implementations of SMS do not guarantee delivery. However, in practical terms about 99.9% of text messages are delivered successfully, so the actual incidence of failed delivery is relatively low. With such a high reliability rate, you can simply use the pragmatic solution offered in the video: send your plan to your friend, and wait for a response. If your friend does not respond within a pre-agreed upon period of time, simply send your message again until you get a response. Your friend will tell you that he got it (ack), and if your friend does not receive another message from you, he can safely (with low probability of failure) assume that you got his ack (because if you didn't, you'd keep sending your plans to him).
Where this system falls apart is if suddenly the reliability of communication drops suddenly, for example if there is a national emergency or a storm takes out a cell tower. But maybe then you and your friend would have bigger things to worry about.
Each side send 1 scout, when they meet up in the middle they will either both die because one is spotted so botg die, or both survive. If they die, both sides send new scouts
Same problem there. How would they both know when to send scouts?
Did you ever make the byzantine problem video?
No, might have to come back to this at some point.
@@Finematics Please Do!
Gen A says I will keep sending messages until you reply and I will stop. Gen B sends the ACK back and if after 40 minutes no new messengers come then Gen B knows it was received. He will get new messages in that time but should stop after the time has passed. You can even put time stamps on the messages so Gen B know how long it took to get the message there and how long to wait.
What if they both send a messenger at the same time? Or at least attempt to send some at the same time?
you can't be certain the messager you sent arrived.
@@thomasb.5643 Yea, I realize that.
Long distance visible signals were created for this very purpose
EPIC!
I'm pretty sure you're incorrect. If general a sends the time and date of the attack and general b sends back the same message to confirm, general a can then send back a confirmation saying I got your confirmation of the date and time. If general b then sends back confirmation saying I'm glad you got my confirmation message. General a can send one last message saying me too. They would then without a doubt know that each other got the message. It's not infinite like you suggested....
I should clarify, yes if any of those messages don't go through then it fails, but that wasn't the problem statement originally you mentioned considering a perfect scenario. In computer programming this can be done by trying to have that kind of a conversation and if any of the messages fail you just start over again from the beginning and try again...
bro draws like a freaking printer, like its so clean and... sharp idk how
It would end on an Even number of confirmations sent / Odd number of messages, 9 11 or 13 messages
05:45
This is not unsolvable. As long as both A, and B receive 1 reply receipt for Any message sent by anyone then consensus has bin reached. With the stipulation that neither A or B can change there reply once it is sent.
With that stipulation, it effectively terminates the infinite regress of uncertainty.
Unfortunately it's complicated than that. When both A and B receive 1 reply receipt each, it's still not sufficient to reach a consensus. Because the every receipt is also a message and they are connected like links on a chain. A (sends message) -> B (sends reply) -> A (now A knows B got his message but to let B know that, A sends confirmation) -> B (now B knows A got his reply but needs to let A know that his confirmation is also received, B sends reply confirmation)
@@tharindu79 you missed the immutable law of my suggestion. For any original message each participant can only expect 1 reply. So A sends an original message ->B. B then sends reply of receipt and expects 1 reply. This also counts as the reply A expects. A then sends the reply to B that terminates expected replies. This law makes a distinction between a reply and a message. For added security replies could be of a different inscription then is used in the original message.
@@clintmontgomery5108 i see. so you terminates the conversation when B gets a reply, to his reply. all is good if the channel is reliable. when it's not, how does this work? because B is expecting a reply to his reply to confirm the attack. even though B gets one, there is no way for A to know that his reply got through to B. so A is still in a dilemma to attack. and this goes on... or is it not?
@@tharindu79 no because A already received 1 confirmation. that’s all that is needed to act.
so much easier today, just pick up the phone and call him
Solution: stand there and wait for everyone in the valley to die
take your whole army, go to the other general, confirm, go back, done
Did you not understand the situation? The only way you can go to the other is to pass by the castle. The castle might see the army and get killed.
@@mrflip-flop3198 go around the castle
Techy Savage that's beyond the scope of the problem id think
The solution of sending bunch of mesg is just the exact implementation of your idea. 👍🏻
This is so autistic dude, there’s a reason Generals are not your typical computer geek. Humans have battled and won wars for millennia without considering or solving this “paradox”
One way to solve the problem is to send the general as a messenger. So my thoughts: general A goes to general b together with a small escort, leaving a message behind for the rest of his army: no matter what happens, we will attack over two days at dawn. The chances of them getting captured are significantly reduced because they are with multiple men and they have decided to only travel at night. They also have the general with them and there is no way for the castle to know what they are up to. If they do get attacked, one or two of the men must have the priority to immediately flee while the others of the escort hold off the attackers. as soon as the message gets delivered to general b, b knows that army a will attack, no matter what happens, over two days at dawn. Therefore a confirmation is not needed, because it won't change the actions of army a anyway.
It's possible that General A and escort dies along the way meaning Army A attacks alone and loses. Army A can ask for more troops 1 by 1. They'll know the message got through when the first person returns, if not send another message. It's not 100% effective though as many will die leaving 1.1x to 1.9x army strength at A roughly instead of 2x as the problem requires. Basically a 99% chance of this or that counts as a system fail even though it would work in the real world. Sending a messenger there and back twice would probably be enough in the real world, army B would know their first acknowledge got through to A. Army A would know their time got through to B twice. Still no good though :/
finally a video that explains the problem and possible solutions! thank you! and fuck all those videos about bitcoin solving it
Have the two messengers be order to tell of their message to the eachother outside of the range of the castle and then return to their respective general with the information.
cant like one go to the general and say
light a white fire and then we will attack
light a yellow fire to let our other general know that you got the information
how would you know if they actually lighted a fire AFTER receiving your message? they could also light a white (or yellow) one just for the kicks and you are fucked.
It can be solved by adding the human element of intent. The generals have to know each other (themselves) better then their momma does so as to accurately predict (decide) when to strike and it will get thru the defenses of the target. This is a 2 minute summary answer not a real one
I thought of the same idea myself :)
Apparently, an absence of messengers solves the problem. Don't worry, another vid stated the answer was: math.
2:24 Just stop at n number of confirmations., two are sufficient. This is not necessarily infinite. 🙄
If you stop at any number of confirmations n, then whoever sent the last confirmation will be uncertain if the other party received the last confirmation.
Why was the gangster black? He could have been any colour but black. Thank you
for the knowledge though.
Why don’t the generals just FaceTime?
Gentlemen, stake your HEX.
Tom Scott plagiarized you.