The Two Generals’ Problem

Share
HTML-code
  • Published: 12 August 2019
  • Time to tell a story about idempotency, computer science, and the Night of the Multiple Orders. • Sponsored by Dashlane —try 30 days for free at: https://www.dashlane.com/tomscott

    MORE BASICS: https://www.youtube.com/playlist?list=PL96C35uN7xGLLeET0dOWaKHkAlPsrkcha

    Written by Sean M Elliott and Tom Scott
    Directed by Tomek
    Graphics by Mooviemakers https://www.mooviemakers.co.uk/
    Audio mix by Haerther Productions https://haerther.net/

    Thanks to Dashlane for sponsoring the video! If you're techie enough to watch this video, you should be using a password manager. Get a 30-day free trial at https://dashlane.com/tomscott

    I'm at https://tomscott.com
    on Twitter at https://twitter.com/tomscott
    on Facebook at https://facebook.com/tomscott
    and on Instagram as tomscottgo

Comments • 2 079

  • Tom Scott
    Tom Scott   4 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

    • Liberals Get the Bullet Too
      Liberals Get the Bullet Too  2 days back

      Why don't the two generals have the messengers meet in the middle, and each return with confirmation of having met? This should immediately double the survivability of any particular messenger - they're only travelling half the hostile distance.
      Further, you could have a second set of messengers in an intermediate space to act as a witness or a redundancy.

    • steve d
      steve d  3 days back

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

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

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

    • ERMAN ATES
      ERMAN ATES  4 days back

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

  • jammin023
    jammin023  4 hours back

    I wish these videos had been around back when I was doing Soft Eng at uni... your explanations are so much clearer than my lecturers could manage!

    • Orion Red
      Orion Red  4 hours back

      This is exactly how I ended up with two gallons of milk in my fridge and two loaves of bread in my cupboard last week. It's also how I ended up with a gallon of spoiled milk and a loaf of stale bread this week.

      • ruwiki
        ruwiki  6 hours back

        "it's unsolveable"

        me at 2 am: well, there must be a way ...

        • Oz El Coskuner
          Oz El Coskuner  6 hours back

          Just giving thumbs down for showing 2 long (unskippable) ads. I hope creators puts some pressure on YouTube. Because YouTube literally don't give a damn about feelings of customers who are not paying. WHY WE STARTED WATCHING YOUTUBE? The biggest argument was "so that you don't have to watch long commercials of TV and get brainwashed". Now average ad on YouTube is surpassing TV. Anyway, since I got Amazon prime, I reduced YouTube time to 2 hours a week. Much happier. And I will never pay for YouTube, just because their approach. You cannot shove your will down to people's throat and expect success. When I see YouTube logo, I see a RABID DOG with dollar symbols on his red eyes. Disgusting.

          • John Dean
            John Dean  8 hours back

            There IS answer to the Two Generals' Problem: go to your local chippie.

            • Airpolygon
              Airpolygon  10 hours back

              Very interesting!

              • Rens Breur
                Rens Breur  11 hours back

                But this anecdote isn't REALLY an example of the two generals problem right? The only 'attacker' is the server processing the order request. The two generals problem can't be solved by using a unique key.

                • Joseph Thomas
                  Joseph Thomas  12 hours back

                  Can you find a different shirt?

                  • iammaxhailme
                    iammaxhailme  14 hours back

                    "Next time, I'll just cook for myself"


                    Or, you can just call the restaurant and place your order verbally. Magic!


                    I don't know how it is in the UK, but in NYC you sometimes get it a bit cheaper this way becuase apps take a cut

                    • Jonathan Tikhonoff
                      Jonathan Tikhonoff  15 hours back

                      Actually the two general story is already solved through encryption system. I know of one encryption system that can confirm to both users at same time that each other got the message. I assume that Deliveroo didn't use such encryption because it might be thought of as a bit too complicated and too costly for such simple service.



                      Source: I took cryptography class few years ago so my memory are a bit shaky on details but I clearly remembered Bob, Alice, and Oscar model system about this problem.

                      • Nubby Tope
                        Nubby Tope  18 hours back

                        The main problem is that they built a castle in a valley.

                        • ruwiki
                          ruwiki  5 hours back

                          @Nubby Tope as well

                        • Nubby Tope
                          Nubby Tope  5 hours back

                          ruwiki - fortifications like castles are built on high ground.

                        • ruwiki
                          ruwiki  6 hours back

                          why? to protect an important river crossing, for example.

                      • Zen Lucas-Divers
                        Zen Lucas-Divers  21 hours back

                        wouldn't the best option to just meet somewhere else, send a message to one side and keep doing so until a messenger gets through and tell them to meet a one point so that you can attack together.

                        • M
                          M  21 hours back

                          And then that "idempotency key" resets when you hit "try again" :D

                          • less kiss
                            less kiss  18 hours back

                            The fact you spent £1,795 inc vat per minute of this videos graphics is beyond me

                        • Techno_mage_21
                          Techno_mage_21  22 hours back

                          Maybe a joke comment cause excuse my incompetence but why isn’t the problem set in 3D? Cause then they could just go around?

                          • Zachary Wilson
                            Zachary Wilson  23 hours back

                            Are you in the Centre for Computing History in Cambridge?

                            • less kiss
                              less kiss  18 hours back

                              very close to this idea. Her paper was entitled "Network layer protocols with Byzantine robustness"

                          • Caleb_ Artzs
                            Caleb_ Artzs  1 days back

                            Why not A send a messager at same time as B? So both can meet at the middle and both can go back and inform there general's

                            • Deep hug
                              Deep hug  1 days back

                              to prevent jamming of wireless signals.

                              • soap's alt
                                soap's alt  1 days back

                                The messengers could meet in the valley and then return with an agreement.

                                • Jose Rojas
                                  Jose Rojas  21 hours back

                                  without some form of instantaneous communication, neither general will never know with 100% confidence that the other general's messenger made it back safely to relay the agreement. The point is there's always some assumptions made at some point by one general that the last message went through and by the other general that the previously sent messages were sufficient to proceed with 'enough confidence'.

                              • BleedingRaindrops
                                BleedingRaindrops  1 days back

                                this is a really cool problem. and a really great explanation. Not being a software engineer myself, a lot of why I'm here is through sheer curiosity, but your explanations are always entertaining and easy to understand, so I keep them on a backlog for the day they become relevant to me. Thanks for keeping this channel awesome.

                                • Deep hug
                                  Deep hug  1 days back

                                  attack. If you stop receiving messages, count 1 for each missed message, Reset counter if you receive a message. If count exceeds 6, attack. If the number "I last saw mess

                              • XerO
                                XerO  1 days back

                                couldnt you just send one messenger with a message to have the a messenger from each side to meet at some kind of halfway point and then return to their general

                                • George Hugh
                                  George Hugh  1 days back

                                  Castles aren't built in valleys, generally, generally.

                                  • ruwiki
                                    ruwiki  6 hours back

                                    well, if they protect a river crossing

                                • Lou
                                  Lou  1 days back

                                  You could just get past the castle with your whole force, telling the other force to attack with you - so you become one big army. Problem solved?

                                  • CS:GO сФинщини

                                    Bitcoin solved the Byzantine generals' problem

                                    • ruwiki
                                      ruwiki  6 hours back

                                      blockchain you mean

                                  • Emily An
                                    Emily An  1 days back

                                    I earn like 20 quid an hour for deliveroo it’s not bad 😂

                                  • =NolePtr
                                    =NolePtr  1 days back

                                    I've never heard it referred to as an idempotency key. I've always heard it called a "nonce"

                                    • jammin023
                                      jammin023  4 hours back

                                      The problem is that word means something else in British English...

                                  • Giovanni Joe
                                    Giovanni Joe  1 days back

                                    Super informative! Thanks very much for the great content!

                                    • Emily An
                                      Emily An  1 days back

                                      story short I got 50 quids worth of Wagamamas for free.

                                  • flutty bitch
                                    flutty bitch  1 days back

                                    You are my new favorite channel. Subscribed.

                                    BTW, I had the same problem when purchasing Dragon Age: Inquisition. Took a month for EA to return my money.

                                    • Michael Thomas
                                      Michael Thomas  1 days back

                                      "A single human error is never the root cause"

                                      Tell that to my development manager who came in to the position with nothing more than a background in marketing & graphic design and understands absolutely nothing about coding anything more complicated than changing a few things on an HTML template.


                                      edit: I don't even work in tech currently, so I'm just meme-ing not speaking from experience.

                                      • Orion Red
                                        Orion Red  4 hours back

                                        Well, you're dead on.

                                    • Dan Scherck
                                      Dan Scherck  1 days back

                                      Interesting factoid: The Spanning Tree Protocol, used in Networking to prevent network loops, was invented by Radia Perlman, whose doctoral thesis at MIT was on something very close to this idea. Her paper was entitled "Network layer protocols with Byzantine robustness"

                                      • Magic Morgan
                                        Magic Morgan  1 days back

                                        The fact you spent £1,795 inc vat per minute of this videos graphics is beyond me

                                        • Bluestripe
                                          Bluestripe  2 days back

                                          I had this with steam with a gift and sent 3 skyrims to my friend, by the time we'd realised the refund was no longer possible.

                                          • NikoHD203
                                            NikoHD203  2 days back

                                            I feel so smart now😂

                                            • Real Sky Luke
                                              Real Sky Luke  2 days back

                                              *I was a sub before you hit 200k, WTF WHEN DID YOU BLOW UP???!!!!! 1.8 Million!!! I never even noticed!!!!*

                                              • Reagan Epps
                                                Reagan Epps  2 days back

                                                I know this probably wouldn’t work with computer science stuff but if they sent a messenger to meet the other and they both go back that might work

                                              • alnoso
                                                alnoso  2 days back

                                                i dont get food delivery apps
                                                is it so hard to call a human and say "hey i want a pizza"

                                                • Sebastian Nielsen
                                                  Sebastian Nielsen  2 days back

                                                  There is actually a way to "solve" this problem, and that is continually send messages. They could contain a number, my message number, and the last message number I saw from you. Of course they must be encrypted and end2end verified.
                                                  Continuially send these messages, lets say with 10 minutes apart. Stop sending messages 1 hour before the attack.
                                                  If you stop receiving messages, count 1 for each missed message, Reset counter if you receive a message. If count exceeds 6, attack.
                                                  If the number "I last saw message number X" is more than 6 - (count), attack.

                                                  Regardless on how the adversiary capture the messages, it will result in a successful attack.

                                                  HINT: This is how alarm system works to prevent jamming of wireless signals.

                                                  • Ptao Tom
                                                    Ptao Tom  2 days back

                                                    Seems like once both generals have received at least one acknowledgement they can just attack since the time hasn't changed.

                                                • Black Light
                                                  Black Light  2 days back

                                                  youtube recommended, wtf? Why? I neither understand computer logics or having problems with my food arriving.

                                                  • Alexander Cavrich
                                                    Alexander Cavrich  2 days back

                                                    I

                                                    • less kiss
                                                      less kiss  2 days back

                                                      err, Works fine for me... sounds like user error....

                                                  • Drake H.
                                                    Drake H.  2 days back

                                                    Wouldn't you be able to include a signal response request in the initial message (talking about the two generals problem) - like general a gives a time and requests that general b light a large fire in a visible area to confirm receipt and agreement of the message.

                                                    • [TRCZ] NoidEXE
                                                      [TRCZ] NoidEXE  2 days back

                                                      4:55 but how can you make the same order three times and the server not notice it's the same order? I mean can't you use a pseudo random number generator or something? You only get the next random number if you receive a confirmation or cancel the order. That way if the server gets the same random number for the same client it can tell it's the same order. I'm just a game designer so maybe it's harder than this but I can't think of why it wouldn't work.

                                                      • less kiss
                                                        less kiss  2 days back

                                                        What if someone wanted to do the same order for multiple people. A certain restaurant verifies double orders

                                                    • Mike Pratt
                                                      Mike Pratt  2 days back

                                                      Suggestion for dinner next time - Salmon in a dishwasher..?

                                                      • Alexi Hickin
                                                        Alexi Hickin  2 days back

                                                        I work for deliveroo and I remember this evening, i delivered Wagamamas to a house who had already received their order. I had to wait with them while they got a refund, long story short I got 50 quids worth of Wagamamas for free.

                                                        • Alexi Hickin
                                                          Alexi Hickin  2 days back

                                                          I earn like 20 quid an hour for deliveroo it’s not bad 😂

                                                          • Raymon Crane
                                                            Raymon Crane  2 days back

                                                            Those look like HP 7933/7935 disk drives in back. Used to fix those back in the day.

                                                            • roasted pancakes
                                                              roasted pancakes  2 days back

                                                              Just send two million messengers with a paper each towards the blue army. The paper should have a time to attack and a check mark at the bottom of the page. Make the blue army check every single paper and send all of the messengers back. Then both armies will have a reasonable guarantee that each army got the message. Alternatively, reroute one of the armies to meet the other army and have a combined attack with both armies.

                                                              • TelFiRE
                                                                TelFiRE  2 days back

                                                                There’s nothing unethical about ordering food. I work for Grubhub. Yes there are things I would rather have different, but wouldn’t at their job? By not ordering food all you’re doing is denying me money and making my job harder

                                                                • TelFiRE
                                                                  TelFiRE  2 days back

                                                                  And frankly the only unethical think you’re is to frame this is a question of ethics. Businesses are allowed to have different policies and people are allowed to agree or disagree on those policies without it being a matter of ethics. If you don’t want to work there you don’t have to

                                                              • Simon Johnson
                                                                Simon Johnson  2 days back

                                                                It's not "unsolvable", the word is "insuperable - Pedant

                                                                • Ask to seduce Miss
                                                                  Ask to seduce Miss  2 days back

                                                                  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