The Two Generals’ Problem

Share
Embed
  • Published on Aug 12, 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: www.dashlane.com/tomscott
    MORE BASICS: flash-player.net/p/PL96C35uN7xGLLeET0dOWaKHkAlPsrkcha
    Written by Sean M Elliott and Tom Scott
    Directed by Tomek
    Graphics by Mooviemakers www.mooviemakers.co.uk/
    Audio mix by Haerther Productions 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 dashlane.com/tomscott
    I'm at tomscott.com
    on Twitter at tomscott
    on Facebook at tomscott
    and on Instagram as tomscottgo

Comments • 2 711

  • Tom Scott
    Tom Scott  4 months ago +3470

    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 www.dashlane.com/tomscott

    • Sparkletinkercat
      Sparkletinkercat Day ago

      Heres my idea on how to solve the problem
      Okay so you have sets of 2 people. One is facing towards the start of the sets line and the other is facing towards the start of the opposing armies set lines. This means they can see the next pair ahead of them and the one behind them. So then the ones in the center decide quickly on a time and send it using hand signals to their armies. Say if one person of a pair gets shot on the messages way back and cant recive the message from the other person so the other person of the pair would either step to the side allowing the next pair to see the command or they would also be dead which would quickly tell the pairs infront and behind to move into a position that allows for equal distance between the two and the opposite pair would know the pair had died and would pass the message on to the next pair in line and once they have sucseesfully done that all pairs behind them can either insert themselves bettween rhe other pairs or go back to their army. The equal distance constantly being shifted allows them to always be able to see the next pair and the two people can quickly exchange the hand signal bettween them without looking
      Thus solving the problem
      Hope this made some sense

    • Akin Turhan
      Akin Turhan Month ago

      I have thought about dashlane I want to know the advantage over Google chrome random password generator and manager that is synced with one master password. they don't know any of the passwords either.

    • The Superginge
      The Superginge 2 months ago

      As glad as I am that you're getting sponsored, I feel I should tell people that Firefox is starting to offer this password security option for free, though before anyone gets angry at me, I don't know what level of security it is, comparatively, I just want to make people aware of options!

    • Matti Lüdke
      Matti Lüdke 2 months ago +1

      Why not send a person from each army to the middle of the valley. Then both discuss a time and go back to their army. That way they will know if the message was received by the other army. As the Danger of the route lies in the middle of the valley they will get back safely.

    • صالح
      صالح 2 months ago

      Hey there is a way to solve the 2 genrals problem and it's a horne or war drums because they are loud enugh to hear

  • Xeridea
    Xeridea Hour ago

    Isn't this also called a "nonce"?

  • Mátyás Hale
    Mátyás Hale 5 hours ago

    Tom: *is tired and hungry*
    Also Tom: "damn I KNOW my payment went through but they're telling me it hasn't... mUsT bE tHe tWo GeNErALs PrObLem.... MUst mAKe viDeO!!!"

  • Daniel
    Daniel 7 hours ago

    Why couldn't they put something in a message which the other general had to do if he'd received and acknowledged the message i.e putting troops in an attack formation x amount of hours before the attack was scheduled that general A would be able to see and know that the attack would go ahead

  • diego weiller
    diego weiller 8 hours ago

    Can be solved by sending a messenger from A to be with set time telling B to send aknowledge at 8 for example, at same time (8) A sends one more and they meet halfway, is they do meet, they go back from were they came, and that is a positive.

  • Michael Grouse
    Michael Grouse 13 hours ago

    Idempotency fixes your food problem but NOT the Two Generals' problem. ;)

  • xXUnoriginalNameXx33 - Meygaera

    2:53 maybe I should quit my day job after all....4:48, hold my beer

  • Nipplepotamus
    Nipplepotamus 17 hours ago

    Bad analogy... Simple answer is, General 1 sends his messenger the longest safest route. You send that messenger around the battlefield, knowing the range of the enemies weapons considering you have you army parked outside their base... Not knowing their weapon range is already death and thus you lost already cuz you camped out under fire same with army B. Once army B receieves army A's message they are simply tasked with a large enough bonfire to be seen by army A. The defenders may know that fire means war since armies are camped outside but they know not why that fire is there and if that is the side the armies may attack they may heavily fortify that side of the castle making army A's fight easier. If they don't over fortify the West side where the B fire is at then they still both know to attack at 8PM. No confirmation necessary when real life visiual range is needed not even including telescopes or other long range viewers.

  • Java Fear
    Java Fear 18 hours ago

    General A sends one letter then another shortly afterwards, both with the same information and requesting another two back. General B then sends two letters confirming; the odds of two messengers dying in a row are drastically low.

  • Retrx
    Retrx 20 hours ago

    They both send a messanger, when they hear 2 gunshots they attack.

  • Ivan Cavar
    Ivan Cavar Day ago

    Why not exchange messages just prior to attack?

  • Caden Schoffelman

    Send a guy over telling the other guy your both going to send someone to the middle at 8pm, then you send someone at 8pm to the castle and if they meet up with another armies guy they tell them “we attack at 9pm” then they each head back and can confirm the other person made it past the castle, if they don’t end up meeting with someone in the middle, they finish the trip to the other side to tell them again what time they are each gonna send 1 person to the middle until you can attack.

  • jahaziel herrera
    jahaziel herrera 2 days ago

    Just siege them

  • That Asshole
    That Asshole 2 days ago

    Couldn’t the red army reposition?

  • DiabloMinero
    DiabloMinero 2 days ago +1

    General A sends the entire army over to B's side by labeling one soldier at a time as a "messenger" and sending them over. The majority of the army gets through. They now have a combined army with roughly twice the strength of the original armies and no longer have the valley in the middle. They can agree on a time to attack and then attack.

  • Narobii
    Narobii 3 days ago

    Tom, please don't cook yourself. self cannibalism isn't good.

  • Notecnirp
    Notecnirp 3 days ago +1

    Can’t the messenger come back and say that the other side got the message??

  • Norm
    Norm 3 days ago

    couldn’t the general of army a just wait until his messenger got back with a piece of paper that says “acknowledged”

    • freddy46
      freddy46 2 days ago

      How can they know if the "acknowledged" message came through?

  • Right Wing Safety Squad

    I know this doesn't work for the case of computer networking, but if General A takes his entire army to General B, surely then they'd all know when to attack ;)

  • Mochacocoa
    Mochacocoa 4 days ago

    Isn't it solved in three messengers?
    Messenger 1A tells general B about the time to attack.
    Messenger B tells general A that the time is agreed upon.
    Messenger 2A tells general B his confirmation was received and they're preparing for the agreed upon time.
    Then they both know the other has agreed to attack at the stated time.

    • Frederik Carl
      Frederik Carl 4 days ago

      "Magical computer science, infomation theory land"

  • Justin Moore
    Justin Moore 4 days ago

    Both armies surround the castle and starve the castle of resources. No messages needed. The street creepers and 4 chan have won. Just like the alamo I am going to troll until the end.

  • Federico Olivares
    Federico Olivares 5 days ago

    To me is simple the general's problem
    A sends "is 8pm ok? Send "ok" back for yes, if you dont receive an ok back from me, send "response?" Back 2 more times. If you dont get an ok from me, consider it null. I too will send a 2 "response?" If i dont listen back
    So gen B agrees,
    Sends one Ok
    gets Ok back
    Both attack.
    Gen b sends ok
    doesnt hear back, received "response?"
    Sends ok
    Receives ok
    both attack
    Gen b sends ok
    doesnt hear back, doesnt receive response at all. Asumes A's ok has been intercepted as they would have sent one or more "response?" Back otherwise.
    Sends "response?"

    And so on. If all 5 messagers get caught after the initisl messsge, the attsck wouldnt go through.
    If just 2 Oks do go through, the attsck goes through

  • Phillip Otey
    Phillip Otey 5 days ago

    I mean you need 2 minimum. A keeps sending troops saying: send one troop telling us what time to attack. We will keep sending troops until the package is received, and if the time of attack has not past we are a go.

  • Ady Day
    Ady Day 5 days ago

    Don’t rely on technology too much..nothing is built to last!

  • Name
    Name 7 days ago +1

    Just make an agreement that 2 or more acknowledgements means you can attack

  • Jo 1337
    Jo 1337 8 days ago

    It's 2 am and I regret nothing

  • Vysair
    Vysair 11 days ago

    Or maybe both general could send dozen more message until it hit certain threshold and that will confirm it.

  • 10k12
    10k12 13 days ago

    2:35 why not let them meet in the middle, so if they perish, they perish together and no message is received, but if they manage to meet, they can return and there are no threats on the way back to the generals.

  • Shaurya Pant
    Shaurya Pant 13 days ago

    Well, after both the teams have received confirmation of the other party that they know that you know and will go at 8PM, I don't see any further need of sending messengers. Can someone explain, please?

  • Andre L
    Andre L 13 days ago

    How come this problem exists at all, if the proposed time is 8 pm, and both of them acknowledged the acknowledgments, then why would A and B need to keep sending acknowledgments? They both acknowledged the proposal and acknowledgment, so it's already planned? They both already know that it made it to the other side at least twice, so what's the problem?

    This just feels like it's not really a problem.... How is this line of reasoning incorrect?

  • Markus B
    Markus B 14 days ago +1

    I should be asleep but general B didn’t give me a confirmation

  • john wick
    john wick 14 days ago

    Simply. General A sends a messenger which returns after delivery of the message. If the messenger does not return after a suitable time span. It is safe to assume something happend and another messenger needs to be sent

  • Space Griffin
    Space Griffin 15 days ago +1

    but wouldn't a and b know they've received the message by the third message?

  • DukeOfEarle88
    DukeOfEarle88 15 days ago

    £7.74 word.

  • UberKrassMann
    UberKrassMann 16 days ago

    2:55 starts sweating.....

  • Skepty
    Skepty 16 days ago

    Just tell them to make a fire signal after they do, as confirmation. Not that hard.

  • Ashor
    Ashor 17 days ago

    for the two generals, couldnt one side send a messenger with the message telling them to attack at a certain time (sundown) but to ensure they both know they both have to shoot a cannon ball to the west of the other general at sunrise) if they both observe the cannon ball west of them then they know they will attack at sundown

  • Midhunraj R Pillai
    Midhunraj R Pillai 17 days ago

    I wonder how the generals problem is unsolvable. Please correct me whats the mistake of the solution below,

    Step1: General A sends message saying attack at 6pm
    (Here, A establishes the time)

    Step 2: General B gets the message, sends back an acknowledgement 1 for the message 'we go the time'
    (B gets the time)

    Step 3: General A gets the ACK 1
    (now, A knows that B got the time of attack. But B won't attack because B don't know that ACK 1 is reached at A. so..)
    A sends a confirmation ACK 2 back

    Step 4: General B gets the ACK 2
    (now, B knows that both A and B establishes the time. Also B got the ACK 2, meaning B knows that ACK 1 reached A. But B knows that A won't attack until A confirm that B got the ACK 2. so...)
    B sends a confirmation ACK 3 back

    Ahhhh this trend continues and no one will attack since they cannot make sure that the previous ACK sent by them is reached at the other end!!! I am sorry (T_T)

  • Ivan farlenkov
    Ivan farlenkov 18 days ago

    Have generals send messagers at set periods of time even when there is nothing to send. If there is no messager, ask about it in the next message.

    • Gareth H
      Gareth H 17 days ago

      @Ivan farlenkov You really do not get it. Oh well, nevermind. Stick to flipping burgers.

    • Ivan farlenkov
      Ivan farlenkov 17 days ago

      @Gareth H Why not? If messagee is lost, request to resend will be eventualy get to the other side.

    • Gareth H
      Gareth H 17 days ago

      That is the ping approximation that is used. But it is not a solution to the problem, there is no solution.

  • Monsieur P.
    Monsieur P. 19 days ago

    My bank card would’ve texted me to confirm charge after being pinged to debit my account identical amount of money. It’s kind of stupid that nobody selling the food didn’t notice.

  • Monsieur P.
    Monsieur P. 19 days ago

    😂 these damn apps!

  • novicetheaf
    novicetheaf 19 days ago

    This is a classic lack of dev testing prior to sending it for testing prior to deploying it to the end user, and QA testing.

  • Kevi Kiru
    Kevi Kiru 19 days ago

    Even your paid promotions are interesting to listen to!

  • Oasia
    Oasia 19 days ago

    Why dont the say just to fire a cannon if they recieve the message

  • Julian Danzer
    Julian Danzer 19 days ago

    2:57
    umm...

  • Floofzy Kitty
    Floofzy Kitty 21 day ago

    1:38 What are you talking about? Of course they made it to the other side. Just not the side they intended.

  • Muhammad Adam
    Muhammad Adam 24 days ago

    Surely after the 4 messengers they wouldn't need confirmation any further confirmation because both would have already known that it's agreed upon

  • Terrain
    Terrain 25 days ago

    You didn’t solve the two generals problem, you solved another problem created by it being unsolvable, which arguably is more dangerous than the two generals problem

  • BeforeReform
    BeforeReform 25 days ago

    per your ad... there is *always* the possibility of brute force getting through. It could take years, or decades on average, but there is always a chance someone gets lucky.

  • Angelmarauder
    Angelmarauder 26 days ago

    TCP/IP

  • its_a_trab
    its_a_trab 26 days ago

    You could just send the original guy back.

  • Emerald Block Boat
    Emerald Block Boat 27 days ago

    I'd say that if B received two verifications then do it

  • TARINunit9
    TARINunit9 27 days ago

    Proposition for the two generals problem: instead of sending one messenger, send a pair of messengers. One messenger stays at camp B and the other returns to camp A. If no messengers return to camp A, then it's obvious that the message was intercepted on one of the two trips, so you send another pair

  • Lloyd Thorpe
    Lloyd Thorpe Month ago

    What they should have done is just starve the castle out like they most commonly did

  • The Nintendo Fan
    The Nintendo Fan Month ago

    Honestly, the red army would automatically assume the blue army got the message and would attack on that time

  • Eric ON
    Eric ON Month ago

    Atleast once invocation solves this issue as well. I.e. let the client keep spamming the same request until one confirm has been recieved.

  • Emil Sørensen
    Emil Sørensen Month ago

    I'd definitely not like having a master password that, if lost, renders my entire online life unrecoverable.
    How can you possibly make your one password unforgettable? Chisel it into an immovable rock?

    • seneca983
      seneca983 10 hours ago

      "How can you possibly make your one password unforgettable?"
      Choose "a" as your password or, alternatively, "password".

  • LED Kat
    LED Kat Month ago

    Send the entire army as the messenger

  • Beowulf Macbethson
    Beowulf Macbethson Month ago

    I was watching a video about Morgoth from Lord of the Rings, why am I here.
    Also your video is great and informative.

  • TIMΞ СнΛИGΣ
    TIMΞ СнΛИGΣ Month ago

    But the generals would know after a few acknowledgements? What am I missing here