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.
@@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.
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 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.
Why isn’t it the case that once both generals know the other is aware of the plan (which will be clear after an exchange of the first few messages) then it doesn’t matter about sending confirmations. If they’ve both sent 5 (random number) confirmation messages to each other it doesn’t matter anymore because you both know the other has without a doubt seen the first message
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.
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...
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
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.
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
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 :/
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?
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
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.
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.
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.
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.
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.
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!
great! totally underrated content!!
Nice video. I don't think you ever created the follow video about the "Byzantines Generals Problem"
Thank you
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.
5:30 There ARE a few practical approaches.
6:35 MessEngers.
Best video for two generals' problem. thanks for your solution!
Wow...i really appreciate this explanation.
Suppose there's a probability p that a given message Makes it through is there a strategy which maximizes the chances of coordination
Why isn’t it the case that once both generals know the other is aware of the plan (which will be clear after an exchange of the first few messages) then it doesn’t matter about sending confirmations. If they’ve both sent 5 (random number) confirmation messages to each other it doesn’t matter anymore because you both know the other has without a doubt seen the first message
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
awesome video ，thank you
Best explanation video
thanks!
let the generals whatsapp each other they confirm with two blue tick mark
I will write that in my exam!
Loving your work Finematics!
Thanks Jeanette!
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.
Thank you.
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...
thanks
Long distance visible signals were created for this very purpose
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
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.
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!
EPIC!
bro draws like a freaking printer, like its so clean and... sharp idk how
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
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.
It would end on an Even number of confirmations sent / Odd number of messages, 9 11 or 13 messages
so much easier today, just pick up the phone and call him
Can't you use smoke signals.
6:22...how does the general know there was 100 messages sent ?
05:45
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 :)
Solution: stand there and wait for everyone in the valley to die
why not send more than 1 messenger at different times
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.
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.
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.
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.
Why was the gangster black? He could have been any colour but black. Thank you
for the knowledge though.
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.
Why don’t the generals just FaceTime?
Gentlemen, stake your HEX.
Tom Scott plagiarized you.