The Two Generals’ Problem

Share
HTML-code

Comments • 1 981

  • 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

    • steve d
      steve d  25 minutes back

      Doesn"t mention food delivery company by name, shows headline with delivery company's name...

    • 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  4 days back

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

  • Cullenak47
    Cullenak47  35 minutes back

    A sends a messenger to b. If it makes it , b sends both that messenger and a new messenger from b to the castle. Messenger B turns back and messenger A continues to a. B knows if A made it and A knows B made it. Both army’s attack. Solved. I know this wouldn’t work in computers but it is a solution if it were just a puzzle

    • Daniel Newton
      Daniel Newton  3 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  4 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  6 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  6 hours back

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

              • Aaron
                Aaron  6 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  6 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  6 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  5 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  6 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  6 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  7 hours back

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

                      • shinvergil
                        shinvergil  8 hours back

                        The example was weak, imo. But good info.

                        • X
                          X  8 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  8 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  9 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  10 hours back

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

                                • Jake Hartman
                                  Jake Hartman  10 hours back

                                  pls get patreon and premium memberships and no cemmercials thnx

                                  • Z-Statistic
                                    Z-Statistic  11 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  12 hours back

                                      Initially, I completely misread the title.

                                      • Eric Tripps
                                        Eric Tripps  12 hours back

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

                                        • Winston Churchill
                                          Winston Churchill  13 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  14 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  14 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  15 hours back

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

                                                • Matthew Booth
                                                  Matthew Booth  17 hours back

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

                                                  • David Alan Gilbert
                                                    David Alan Gilbert  18 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  18 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  18 hours back

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

                                                        • d
                                                          d  18 hours back

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

                                                          • Crimson Vulpes
                                                            Crimson Vulpes  19 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  19 hours back

                                                              The solution is to use flags as long distance communication

                                                              • Bloodthirsty
                                                                Bloodthirsty  19 hours back

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

                                                                • Patrick Armstrong
                                                                  Patrick Armstrong  19 hours back

                                                                  OMG look at all those IBM PCs!!

                                                                  • Red Jellonian
                                                                    Red Jellonian  20 hours back

                                                                    ...tcp

                                                                    • Anikthias
                                                                      Anikthias  20 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  20 hours back

                                                                        google already does for free what dashlane charges for.

                                                                        • Mostwanted
                                                                          Mostwanted  21 hours back

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

                                                                          • Frank Harr
                                                                            Frank Harr  22 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  10 hours back

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

                                                                            • HudsonA
                                                                              HudsonA  13 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  22 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  22 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  23 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  24 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  1 days 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  1 days back

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

                                                                                        • Wolf Slayer
                                                                                          Wolf Slayer  1 days 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