Two Generals' Problem Explained

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

"Some constraints and tradeoffs in the design of network communications" paper ►

Donations:
Bitcoin ► 18ngQa7qzfg9RpstBz3ZCSm2fAzm6tqaa4

Referral links:

If you like this video, give it a like, share it and subscribe to my channel.
Thanks for watching!

[chrysalis]

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.

[alexandrughiurutan]

Can't wait for the generalized version. Byzantine generals problem.

[caseylocke]

Thank you so much for making such a clear video! I love Tom Scott, but I think your video is better explained.

[anreoil]

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.

[zhouyou]

Best video for two generals' problem. thanks for your solution!

[thefluffyshark]

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?

[dudeofchicken]

let the generals whatsapp each other they confirm with two blue tick mark

[Spoonfork]

Nice video. I don't think you ever created the follow video about the "Byzantines Generals Problem"

[PedroOjeda]

Did you ever make the byzantine problem video?

[faizalmakhrus]

Wow...i really appreciate this explanation.

[zilla]

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

[morethejamesx]

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

[yaakovgrunsfeld]

Suppose there's a probability p that a given message Makes it through is there a strategy which maximizes the chances of coordination

[lockscad]

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

[jimflagg]

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.

[MuradBeybalaev]

5:30 There ARE a few practical approaches.
6:35 MessEngers.

[sirpentplayz]

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

[xx_Ashura_xx]

take your whole army, go to the other general, confirm, go back, done

[Raph.q]

6:22...how does the general know there was 100 messages sent ?

[clintmontgomery]

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.