The Two Generals’ Problem

Share
HTML-code

Comments • 1 979

  • Tom Scott
    Tom Scott   3 weeks back

    Yes, I had help with the graphics for this series. There's no way I'd have animated that myself! On that note, thanks to Dashlane for sponsoring and helping me hire an animator: their free trial link is https://www.dashlane.com/tomscott

    • Andrew F
      Andrew F  1 days back

      How is it unsolvable? Wouldn't you just need a maximum of two confirmations sent in order after the original message? If you get at least one confirmation in the correct order after the original message then you know both parties received the original, right? What am I not understanding here?

    • john smith
      john smith  1 days back

      who would put the castle in the valley but a computer tech

    • ERMAN ATES
      ERMAN ATES  2 days back

      It was very well put. Animations were only fabulous. Thanks

    • John Jennings
      John Jennings  3 days back

      Glad to know Dashlane is sponsoring you and you trust them! Been using them for 3 years now

    • Treqqing
      Treqqing  4 days back

      Could you do an episode on the flat earth

  • Daniel Newton
    Daniel Newton  1 hours back

    Have each army send a messenger when they're ready. When the two messengers meet in the middle (taking precautions to avoid getting spotted), each one goes back to their army and says "we're good to go". If the messengers don't make it back, they will assume that they died so can send another, until the two meet and send a return message.

    • Kingsly9802
      Kingsly9802  1 hours back

      >If you are in computer science and working on a problem that involves potential loss of life, I really hope you aren't watching a series called "The Basics".
      But they're fun!

      • soSAMuk's UK slot channel

        Why do kids toys adverts have to say “batteries not included?”

        • TheDeathMongrel
          TheDeathMongrel  3 hours back

          2 Generals is an interesting conundrum in and of itself but I think it's a poor paradigm for avoiding the processing of repeated messages. In 2 Generals, no one proceeds without an acknowledgment. It's a Schrodinger's Cat problem. You don't know the answer until 8 p.m. when either everyone is at the castle or is still waiting for another acknowledgment. Applying idempotency (which would be against the "strict" rules) to 2 Generals, still wouldn't solve the problem. It would only affirm that additional messages, if any, are the same (attack at 8 p.m.), and only if the messages actually make it. 2 Generals doesn't guarantee message delivery in either direction, so even with idempotency tokens, Army B may still take no action if they don't get their acknowledgment.


          With the delivery issue, if the additional messages don't make it, it doesn't matter, the other side will respond appropriately to the original message. In delivery, the return acknowledgment goes far beyond the 2 Generals' (receipt of message), as you can get an erroneous message, a success or failure, and is likely not to have an effect on processing if no acknowledgment is sent.


          In any case, I think the delivery problem and applications of idempotency tokens as you've described, is its own best explanation of what's going on, not 2 Generals, which idempotency can't be used to solve (again strict rules).

          • Max Mouse
            Max Mouse  3 hours back

            General A sends "8pm" General B sends "8pm ack" - General a doesn't attack unless it receives the ack...

            • Aaron
              Aaron  4 hours back

              General A sends 2 Messengers. Both go to general B to confirm the message was received. Both go to General A but when passing the castle at the exact halfway point one messenger goes back to general b the other goes on to a. They both know the message was received by general b and the acknowledgement got through back to a.

              • Jasmine
                Jasmine  4 hours back

                An interesting follow up would be the Byzantine general's problem - what if there were multiple generals that could back stab each other?

                • 1dgram
                  1dgram  4 hours back

                  Hey, I'm allowed to watch a series called "The Basics" even if I am working on safety of flight software!

                  • 1dgram
                    1dgram  2 hours back

                    @Jasmine It's one if those words that are pronounced differently in the UK than in the US. You have the correct American pronunciation.

                  • Jasmine
                    Jasmine  4 hours back

                    Now, can you do one that explains why idempotency is pronounced like that? I've always read it as i-dem-potency

                • KryskZ09
                  KryskZ09  4 hours back

                  At the point where he's talking about sending 200 messengers, and I'm thinking of a solution right now, I will see how wrong I am once I finish the video.

                  General A sends a messenger to meet a messenger sent by General B half way to the valley, one with a letter of an estimated time and another of "Hey, here's my letter"
                  The messengers swap messages, both now know that once they leave the 50% point they're free of danger. They make their way back to their sending General with the opposing General's note in hand.
                  Repeat this process once the messenger arrives at their designated outpost, this time with the other General agreeing (or disagreeing) with the time. If they disagree, repeat this process.
                  Now they have the correct schedule and a guarantee that the messenger has arrived.

                  Edit: I guess I was incorrect, although my answer wasn't explored. I would assume that it would cause more margin of error though.
                  I still don't understand the concept of an idempotence key, sure you're ensuring nothing if fulfilled twice, but what if it breaks to begin with? There's no way for the other side to know...

                  • Aline Fernanda
                    Aline Fernanda  5 hours back

                    You are so handsome hehe
                    I like your channel! Greats from Brazil.

                    • shinvergil
                      shinvergil  5 hours back

                      The example was weak, imo. But good info.

                      • X
                        X  5 hours back

                        their is an almost guaranteed way to get it to work
                        general A sends a message, general B continues to send a message until general A responses, if another messenger from general B arrives, General A can assume general B didnt receive the message, and send another message, once General As messenger arrived, at which point no more messages from general B will arrive, so they both attack
                        edit: this is under the assumption that the fail rate of messengers is below 100% and their is plenty of time between attacks

                        • Mr. Pinkpig
                          Mr. Pinkpig  6 hours back

                          Wait couldn't one messenger for A and one messenger from B meet in the valley and give each other a set time?

                          • Tulip
                            Tulip  7 hours back

                            So this is how the generals communicate

                            Messenger one: we attacking at 8
                            General 1:cool let me sound a confirmation
                            Messenger two: i can confirm that we are attacking at 8
                            General 2: alright, let me send a confirmation Messenger one: we attacking at 8
                            General 1:cool let me sound a confirmation
                            Messenger two: i can confirm that we are attacking at 8
                            General 2: alright, let me send a confirmation Messenger one: we attacking at 8
                            General 1:cool let me sound a confirmation
                            Messenger two: i can confirm that we are attacking at 8
                            General 2: alright, let me send a confirmation Messenger one: we attacking at 8
                            General 1:cool let me sound a confirmation
                            Messenger two: i can confirm that we are attacking at 8
                            General 2: alright, let me send a confirmation Messenger one: we attacking at 8
                            General 1:cool let me sound a confirmation
                            Messenger two: i can confirm that we are attacking at 8
                            General 2: alright, let me send a confirmation Messenger one: we attacking at 8
                            General 1:cool let me sound a confirmation
                            Messenger two: i can confirm that we are attacking at 8
                            General 2: alright, let me send a confirmation Messenger one: we attacking at 8
                            General 1:cool let me sound a confirmation
                            Messenger two: i can confirm that we are attacking at 8
                            General 2: alright, let me send a confirmation Messenger one: we attacking at 8
                            General 1:cool let me sound a confirmation
                            Messenger two: i can confirm that we are attacking at 8
                            General 2: alright, let me send a confirmation Messenger one: we attacking at 8
                            General 1:cool let me sound a confirmation
                            Messenger two: i can confirm that we are attacking at 8
                            General 2: alright, let me send a confirmation Messenger one: we attacking at 8
                            General 1:cool let me sound a confirmation
                            Messenger two: i can confirm that we are attacking at 8
                            General 2: alright, let me send a confirmation Messenger one: we attacking at 8
                            General 1:cool let me sound a confirmation
                            Messenger two: i can confirm that we are attacking at 8
                            General 2: alright, let me send a confirmation

                            • Killer Germ
                              Killer Germ  7 hours back

                              This is a shitty hypothetical, as reasonable suggestions will not be accepted.

                              • Jake Hartman
                                Jake Hartman  8 hours back

                                pls get patreon and premium memberships and no cemmercials thnx

                                • Z-Statistic
                                  Z-Statistic  9 hours back

                                  So the solution to the two generals problem is to send a third of your army into the dangerous valley, all of them with a message to attack at a certain time with the survivors to ally with the other general, and then assume the message got through.

                                  • Hater Bart
                                    Hater Bart  9 hours back

                                    Initially, I completely misread the title.

                                    • Eric Tripps
                                      Eric Tripps  10 hours back

                                      So the idempotency token solves the double send error but how does it solve the generals problem?

                                      • Winston Churchill
                                        Winston Churchill  10 hours back

                                        I know that this video is not about military tactics, but it would be extremely easy, I feel, to coordinate that attack.

                                        • Paul Brooks
                                          Paul Brooks  12 hours back

                                          Theoretically quantum entanglement, more specifically quantum computing does in fact solve this problem. For reference, research the two slits photon phenomena.

                                          • Bill Green
                                            Bill Green  12 hours back

                                            I must be missing something as I see how it stops you getting two pizzas but I don't see how it helps the generals at all.

                                            • Paul Nikonowicz
                                              Paul Nikonowicz  13 hours back

                                              "idempotency". One of the sexiest words in computer science that no one really knows how to pronounce.

                                              • Matthew Booth
                                                Matthew Booth  15 hours back

                                                I've always pronounced this EYE-dem-POE-tent.

                                                • David Alan Gilbert
                                                  David Alan Gilbert  15 hours back

                                                  Now, can you do one that explains why idempotency is pronounced like that? I've always read it as i-dem-potency

                                                  • Arindam Nandi
                                                    Arindam Nandi  16 hours back

                                                    An interesting follow up would be the Byzantine general's problem - what if there were multiple generals that could back stab each other?

                                                    • D.N.A Travel
                                                      D.N.A Travel  16 hours back

                                                      Just saw at kings cross, sorry didn't say hello, was running late, love the boss

                                                      • d
                                                        d  16 hours back

                                                        I thought the title was “2 genders problem” and I came for the comments

                                                        • Crimson Vulpes
                                                          Crimson Vulpes  16 hours back

                                                          Sun Tzu says "Never attack a fortified position."
                                                          but my answer for the "Two Generals problem" would be...
                                                          "If you received this message, and you wish to join forces, fire a flaming arrow into the air at midnight."

                                                          • Schadenfreude
                                                            Schadenfreude  17 hours back

                                                            The solution is to use flags as long distance communication

                                                            • Bloodthirsty
                                                              Bloodthirsty  17 hours back

                                                              How about lighting the biggest fire the blue general has ever seen

                                                              • Patrick Armstrong
                                                                Patrick Armstrong  17 hours back

                                                                OMG look at all those IBM PCs!!

                                                                • Red Jellonian
                                                                  Red Jellonian  17 hours back

                                                                  ...tcp

                                                                  • Anikthias
                                                                    Anikthias  18 hours back

                                                                    General A: "General B, I propose to you a plan of attack. Upon receiving this message, send one of your messengers back with mine. At the midway point, yours shall turn around and return to you. An hour after both our messengers have arrived, we will commence the siege; should either messenger not return, the other must also have been spotted and destroyed."

                                                                    Repeat this process until the messenger of General A returns, and begin the siege.

                                                                    • J G P
                                                                      J G P  18 hours back

                                                                      google already does for free what dashlane charges for.

                                                                      • Mostwanted
                                                                        Mostwanted  18 hours back

                                                                        Had this with dominos, same I had the instinct to Not risk paying again..that's just silly

                                                                        • Frank Harr
                                                                          Frank Harr  19 hours back

                                                                          O.K., so A can just keep sending a proposal until one of B's acceptance has been recieved. B assume A is serious and A assumes B is . . . well, nothing. A doesn't have to. Clever.

                                                                          • Frank Harr
                                                                            Frank Harr  8 hours back

                                                                            True, that's got going to work either. Nothing does. I'm trying to fit this solution into the parable.

                                                                          • HudsonA
                                                                            HudsonA  11 hours back

                                                                            It's not that B knows A is serious, but B has to know that A got its reply, both sides need to know this. What if B never gets any message and A attacks anyway?

                                                                        • cubeincubes
                                                                          cubeincubes  20 hours back

                                                                          Huh?

                                                                          • Dominykas Turčinavičius

                                                                            "A single human error is never the root cause"
                                                                            A single human error: I'm about to end this man's whole career

                                                                            • RipleySawzen
                                                                              RipleySawzen  20 hours back

                                                                              To say this problem is unsolvable is ludicrous. The only way that happens is if the trip is somehow one-way. Otherwise, the sender can just keep sending the request till it gets a confirmation. Computers can do this literally millions of times a second, so probability dictates this eventually WILL happen 100.0000000% of the time. You can make the probability arbitrarily as high as you like.


                                                                              Now, if there is some significant packet loss going on somewhere, you just display the "Cannot contact server" message and send a few dozen cancellation packets just to be sure.

                                                                              • dfasdfasdfasdf
                                                                                dfasdfasdfasdf  20 hours back

                                                                                A lot of FUD in the intro, when this problem is not affecting people in the real world hardly at all anymore.

                                                                                • Ricky
                                                                                  Ricky  22 hours back

                                                                                  The great part of this episode of the basics is that it is more like 2 episodes, one about the generals problem, and one about password managers.

                                                                                  • a z
                                                                                    a z  22 hours back

                                                                                    The two general's problem is nonsenical because war is never planned and structured this way. Instead the following applies:
                                                                                    There will be ONE general and TWO commanders each commandeering one army. The general plans and sends messages to the commanders and they execute his/her commands relaying relevant feedback to the general so the general has realtime information on the state of play from the perspective of each commander. Extrapolating, you see this in IT in every large corporate as the admin (or general) sends out messages to each commander (each computer attached to the corporate network) with the computers relaying realtime statuses back to the admin.

                                                                                    By contrast the foodordering problem is one of STRUCTURE and is analogous to the following battle structure. you are the general, you have one army and one commander but the army is fragmented into different specialisms (eg tanks, jet fighters, ground soldiers etc etc ) with each specialism controlled by a lieutenant. The structure SHOULD BE that the general commands the commander and the commander relays to each lieutenant HOWEVER some of the lieutenants are BYPASSING the commander and relaying directly to the general thereby creating INFORMATION-CONFUSION, and this is combined with the fact information lines between the general and the commander have been cut. The general thus doesn't have correct realtime information.

                                                                                    Therefore the solution is that the lieutenants ONLY exchange information with the commander and anytime general-commander information lines are cut the commander issues a "STOP WHAT YOU ARE DOING" command to every lieutenant.

                                                                                    Extrapolating and applying this to the food ordering system, the user (general) is communicating with the app (commander), the app then communicates to each lieutenant (eg food ordering, delivery, payment etc etc) and anytime the information line between user-general and app-commander is cut the app-commander issues a "STOP WHAT YOU ARE DOING" command to every lieutenant

                                                                                    • Neodimium
                                                                                      Neodimium  23 hours back

                                                                                      The solution is send them information in quantum entanglement state. (-;

                                                                                      • Wolf Slayer
                                                                                        Wolf Slayer  23 hours back

                                                                                        even thieves can't avoid a traceable digital fingerprint....just a logical fact.

                                                                                        • 4our 20wenty
                                                                                          4our 20wenty  1 days back

                                                                                          The actual same thing happens to me

                                                                                          • Louis Wouters
                                                                                            Louis Wouters  1 days back

                                                                                            But they don't know that we know they know!