The Two Generals’ Problem

评论 

  1. Tom Scott

    Tom Scott

    2 年 前

    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

    • Hatori64

      Hatori64

      10 天 前

      but how about the actual generals in 15th century war?

    • max mustermann

      max mustermann

      13 天 前

      as a teacher I would start with the problem being about emails/ordering food right away, the castle example distracts from the actual (and understandable) problem, it causese more confusion and questions due to all the logical solutions not applying

    • Dominoz 2

      Dominoz 2

      15 天 前

      @Savage van wizardwitch “magical computer science theory land”

    • Dominoz 2

      Dominoz 2

      15 天 前

      @absol761 if A goes to B, A doesn’t know if it has reached B until it comes back to confirm. But B doesn’t know if the messenger has come back to A, so it has to go back to B to tell it it has, but A isn’t sure if the messenger has told them, so it has to go back to A, B doesn’t know so messenger goes to B, A doesn’t know so it goes back to B… it’s not dumb, it’s a large problem with only practical not theoretical solutions that usually work

    • Dominoz 2

      Dominoz 2

      15 天 前

      @DarkPulse Gaming “magical computer science theory land”

  2. Mvp 63

    Mvp 63

    3 小时 前

    For the generals a tells b to attack at 8 and a attacks when b does

  3. Twiztd Bliss

    Twiztd Bliss

    6 小时 前

    Surround castle (Check), Fill in Valley with concrete (To do). Problem solved

  4. deanmoncaster

    deanmoncaster

    6 小时 前

    Just like Microsoft active directory works for updating the directory. Only update if the is is higher

  5. Sebastian Hvam Daugaard

    Sebastian Hvam Daugaard

    16 小时 前

    each general could send a messenger and they would meet in the midle and go back to their bases

  6. Crimson Ace

    Crimson Ace

    19 小时 前

    What about having one general send a seal back, or signature with the original runner, to acknowledge that the message was received?

  7. Dennis19901

    Dennis19901

    天 前

    In IP/TCP communication, each side keeps track of a message number (SYN) and acknowledgement number (ACK). These numbers are both communicated to the other side as well. When one side receives a message, an acknowledgement number is sent for the received message, which increments based on the amount of data received. If the ACK received is ever lower than the current SYN, it knows that data has been lost and sends every message again from the last valid ACK received. It can also ACK multiple messages at once, and even tell the sender what particular range of messages it did not receive. It also has a timeout, where it will just assume the other side has lost connection.

  8. TheLukio

    TheLukio

    天 前

    IRL the two generals problem is solved by both generals discussing their strategy before positioning their armies. Like this there is no interference by the castle and both have the same knowledge of time and place of the attack.

  9. Carson Coder

    Carson Coder

    天 前

    Send a message then b will send a confirmation and a will send the message again if a does not get the confirmation

  10. Toshiro Yamada

    Toshiro Yamada

    天 前

    I use googles password generator for all mine but then I guess the problem is they are impossible to remember.

  11. MasterGhostf

    MasterGhostf

    天 前

    One idea, is to give your messenger a group of times, set them to the middle of the valley. Meet up with the other messenger, they go back to their general, come back with some agreements. Messenger returns to both camps, with the agreement made. In this situation, it doesnt matter when they attack, only that they attack. One general lists times, the other chooses, and they go back. Not fool proof, but a solution. It has it flaws.

  12. J P

    J P

    天 前

    Is this the same as the Byzantine Fault Tolerance?

  13. Pteromandias

    Pteromandias

    2 天 前

    What is this guy's accent?

  14. Radioactive Elephant 🧣

    Radioactive Elephant 🧣

    2 天 前

    But wait. Couldn't the two generals meet up somewhere with their army like on a different part of the valley where they can't get caught and attack together from there or is that impossible (in this scenario) too?

  15. 0der Guy

    0der Guy

    2 天 前

    why dont the generals just call eachother with their cellphones??

  16. noobscrub

    noobscrub

    2 天 前

    I misread dashlane as doordash and was very confused about the sponsor of this video for a bit

  17. Eric Hahn

    Eric Hahn

    3 天 前

    It is solvable, if you receive a message which contains your old message and the old message of the other general, then you know that it was received.

  18. SteveN Kenney

    SteveN Kenney

    3 天 前

    I'm 2 minutes into the video and have it solved. The castle only has so many supplies while the armies could receive theoretically infinite supplies from their home country, so they lay siege. After a few months of siege, enough defenders have died so that either one army could take it on, or they str8 up surrender. If you think this wouldnt work, they could use a smoke signal to signify an attack, and could leave it up for how many half hours it will be into the day, so say a smoke signal of 8 hours will mean 4 pm the next day

  19. MorgyMorgs

    MorgyMorgs

    3 天 前

    Couldn’t the messenger just go round the long way

  20. Henry Works

    Henry Works

    4 天 前

    "I was tired and hungry, just like many of their employees." OOOOOH, sorry, I just burned myself off of that roast.

  21. Peter Wac

    Peter Wac

    4 天 前

    What if boththe information "passing" each other in the half way, creates a new information like passed qnd carrying back

  22. N S

    N S

    4 天 前

    Couldn't one general just see the other general attack, from across the valley, and then also attack? That would be the case in the animation presented in this video. But if the fortress sis o big it's blocking the view of the other side. Carrier pigeons would be the way. And it's not like the messengers would have to ride right next to the castle. Seems like a flawed analogy from the get go, especially, as mentioned by many already, a castle in the middle of a valley.

  23. Ethan Tan

    Ethan Tan

    4 天 前

    What if a messenger from A goes to B and gives the message and makes sure B knows it, then returns to A?

    • Guy Maimon

      Guy Maimon

      3 天 前

      @Ethan Tan so if a would assume b didn't get it, a wouldn't attack and b would attack

    • Ethan Tan

      Ethan Tan

      3 天 前

      @Guy Maimon if the soilder got captured, then a would assume b didn't get the message. Fair point though.

    • Guy Maimon

      Guy Maimon

      3 天 前

      How does B know A got confirmation? How does A know B got the message if the soldier is captured on his way back?

  24. Eager Aurora

    Eager Aurora

    4 天 前

    Or! You could use a different way of communication, like a flare or war horn to signal that theyre immediantly attacking. Granted, this only apploes to attacking

  25. Ray Krypson

    Ray Krypson

    4 天 前

    Why can't each side send one messenger where both would meet in the valley, trade correspondence and then return to their respective sides? That solves the feedback problem of whether or not the message was successfully transmitted. If a respective messenger fails to return, then the respective army will know the message failed to deliver, and the other army will know of the dead messenger's fate when their messenger returns to say that they never showed up.

  26. Antoninus Bruhus

    Antoninus Bruhus

    4 天 前

    The answer to the problem is rather simple: Starve the castle out and make them surrender

  27. Uruke Hoodlin

    Uruke Hoodlin

    4 天 前

    Solution to the problem. General A: Sends two messengers. Messenger 1: Heads to General B. Messenger 2: Heads to middle. Messenger 1: Tell general B to attack at noon if Messenger 2 arrives. Messenger 1: Heads to middle. Messenger 1: Confirm if Messenger 2 is present. Messenger 1: Heads to General A to confirm Messenger 2 was present. Messenger 2: If present when Messenger 1 arrived at middle then head to General B to confirm attack. General A: If no messenger arrives then do not attack General A: If Messenger 1 states that Messenger 2 was missing then do not attack. General A: If Messenger 1 states that Messenger 2 was present then do attack. Genera B: If no messenger arrives then do not attack. General B: If messenger 2 arrives then attack.

  28. Slizmaster

    Slizmaster

    4 天 前

    Solution: hope for the best

  29. John Cooke

    John Cooke

    4 天 前

    Smoke signal. fixed it. Imagine being this aggressively stupid.

  30. Dr. Doppeldecker

    Dr. Doppeldecker

    4 天 前

    Both generals could send a person at the same, the two meet in the middle and make up a time to attack. Now both messengers can tell the time and are certain both parties receive the message.

    • Guy Maimon

      Guy Maimon

      3 天 前

      @Dr. Doppeldecker nope, the question is unsolvable don't waste too much time trying.

    • Dr. Doppeldecker

      Dr. Doppeldecker

      3 天 前

      @Guy Maimon i thought the only dangerous spot for the messenger is right in front of the castle.

    • Guy Maimon

      Guy Maimon

      3 天 前

      No they're not, what if one of them gets captured on the way back from the meeting?

  31. Mareoio

    Mareoio

    4 天 前

    what if the messenger just comes back to prove that general b got the message?

  32. dog your mom

    dog your mom

    4 天 前

    MY BROTHER FIGURED IT OUT! If your messenger comes back then the message was sent. all you have to do is send your message until your person comes back and you're set.

  33. Ora

    Ora

    5 天 前

    Im a little confused. So if the messenger has been in both camps twice why is that not enough for both camps to know that they both know the timing?

  34. Zakk Marks

    Zakk Marks

    5 天 前

    I tried to subscribe after this video and it said “error subscribing”…. Then I checked and the subscription actually went through. 😭

  35. SaGa

    SaGa

    5 天 前

    Have the Generals ever heard of a mirror reflecting light?

  36. Michael Cranston

    Michael Cranston

    5 天 前

    The answer is so simple that is is stupid. General A sends a messenger who must return with the confirmation from General B. If confirmation is not received: General A sends another messenger with the same mission until the messenger safely returns with the confirmation from General B. It is a single repeating loop "If statement" logic. If the terms were not met to continue, loop around and do it again, if the terms are met, move on to the next step. How the hell is that supposed to be complicated?

  37. uniqueusername_1024

    uniqueusername_1024

    5 天 前

    “I know.” “I know you know.” “I know you know I know.” … When I was little, I was so confused by this. Good to know it’s actually an unsolvable problem!

  38. racke

    racke

    5 天 前

    tell the messenger to come back

  39. Da Mighty Shabba

    Da Mighty Shabba

    5 天 前

    ....You lost me at.... Huh?

  40. The Unfortunate General

    The Unfortunate General

    5 天 前

    cant they just unite into one?

  41. Iiro Ovaskainen

    Iiro Ovaskainen

    5 天 前

    Short answer: a really big horn

  42. gfixler

    gfixler

    5 天 前

    Tom (@1:20): "This is a magical, computer science land problem, btw, so reasonable suggestions, like semaphore, or telescopes don't apply." 80% of commenters: "RADIOS!" "BONFIRES!" "MEET BEFOREHAND!" People, it's a math problem, not the real world. Radios, fires, and meetings don't exist in this particular scenario. It's simply a problem of shared knowledge, when there's no way to know if a message made it to the other side. All answers will only entail sending and receiving messages and responses to messages, and the fact that you can't ever know if the other side received a message, unless you receive a message acknowledging they did. The end.

  43. gfixler

    gfixler

    5 天 前

    I've never heard "idempotency" pronounced that way before. I've only ever heard the stress put on the "po," not the "dem."

  44. Gillanator

    Gillanator

    5 天 前

    Just light a big smoke signal when you receive the message

  45. Pit W.

    Pit W.

    6 天 前

    "Expecting returns!!!" - Why do people have to go in full rage mode immediatly? Can't you just ask nicely for your return, and escalate when there is a problem? No, the world needs to know how important YOU are and that YOU are expecting returns. Thank you Karen, that is what I always wanted to know

  46. hello

    hello

    6 天 前

    why dont u just get a flare shoot it and it says 8pm

  47. siegheilyolo

    siegheilyolo

    6 天 前

    Too much overthinking. You could have just called the restaurant and check if the order is OK.

  48. Garvey

    Garvey

    6 天 前

    Smoke signals, fire signals or horns like they used to back in the day

  49. John Thicc

    John Thicc

    6 天 前

    With the key regarding the two generals valley scenario, I feel like even with a key that army B would still not know if A had actually received the confirmation message. Meaning it wouldn't have solved the issue. Am i misunderstanding?

  50. TLGame

    TLGame

    6 天 前

    Imagine being the line cooks on that day. "I swear I made this order two times already."

  51. Hey Zeus Cree Stow

    Hey Zeus Cree Stow

    7 天 前

    Light a dang ole fire

  52. George Allan

    George Allan

    7 天 前

    Blundering my way through automation I've been using a schedule but what I really need is idempotency, im excited about tomorrows google results, thanks Tom!

  53. RobMacKendrick

    RobMacKendrick

    7 天 前

    There's also a cat in the castle. And until both armies smash down the gate and locate that cat, it's both alive and dead. As are the armies, until they successfully arrive at the castle simultaneously. And Tom's Deliveroo driver. Somehow.

  54. BetaPlain

    BetaPlain

    7 天 前

    Just send 2 messengers If one doesn't make it you have the other

    • Z. Smith

      Z. Smith

      6 天 前

      And if they both don’t make it?

  55. Loli is not child p**n U idiot sandwich

    Loli is not child p**n U idiot sandwich

    7 天 前

    The messengers could meet in the middle

  56. TONK_reatomizzed

    TONK_reatomizzed

    8 天 前

    you could use canons to distroy that castle many canons on genral a and many canons at genral b

  57. 331 TNT

    331 TNT

    8 天 前

    After you get the third message, you dont need to send more? since you both know that the message has been back and forth at least 1 time. So no need. Problem solved

  58. Average Noob

    Average Noob

    8 天 前

    thats why we have radios-

  59. Dan Lo Bianco

    Dan Lo Bianco

    8 天 前

    You said the two generals problem is intractable (it is) and yet, at the end, you claimed to have solved it with an idempotency token. I think you skipped a step where you identify that Deliveroo's problem, in this case, is not a two generals problem, so this isn't a solution to it. Also disappointed that Byzantium didn't get hinted at, but I suppose it is basics.

  60. I stand with ISRAEL 🇮🇱

    I stand with ISRAEL 🇮🇱

    8 天 前

    How about show up and if the Allie doesn’t don’t attack

  61. Ch Pe

    Ch Pe

    8 天 前

    Sending messengers on a risky path to deliver messages is the plot line for a lot of good movies including but not limited to 1912. I use Bitwarden.

  62. Alex

    Alex

    8 天 前

    You look like Matthew Macfadyen.

  63. The Doc

    The Doc

    8 天 前

    They both send a messenger at the same time who meet in the middle and exchange messages and return to their respective sides, each guy only makes half a trip and since they never leave their respective territories both generals can see that their guy made it back because they are safe since they never did the dangerous journey

    • Panzerkampfwagen VI Tiger I Ausf E

      Panzerkampfwagen VI Tiger I Ausf E

      8 天 前

      Thats what I was thinking the entire video

  64. Kenny Cho

    Kenny Cho

    8 天 前

    You just publicly, for free did the software engineers’ jobs. What an intelligent wizard you are!

  65. UNICORNPOTATO 07

    UNICORNPOTATO 07

    8 天 前

    Couldn't they just like morse code or something

  66. Johnny Charles

    Johnny Charles

    8 天 前

    Literally if you sent 5 messengers everyone would know to go.

  67. DerDolf

    DerDolf

    8 天 前

    Why the Generals dont light a Bonfire to signal the beginning of a siege/attack just like in the Medieval times

  68. Michael Fisher

    Michael Fisher

    8 天 前

    MORSE CODE! Fire cannons in Morse code or spotlights or something!

  69. Robin33

    Robin33

    9 天 前

    how does it solve the generals' problem though? I don't get it

    • Andrew Gilfrin

      Andrew Gilfrin

      8 天 前

      It's doesn't. It solves a computer problem that looks like the two generals problem, but doesn't actually solve it.

  70. Coma Tose

    Coma Tose

    9 天 前

    This is too funny ... Learn how to code noobs.

  71. MicroDog7S

    MicroDog7S

    9 天 前

    How does Apple messenger know that my text has been “Delivered”? They also have the option of allowing the sender of a text to know if you’ve “Seen” their message.

    • Guy Maimon

      Guy Maimon

      3 天 前

      Your phone just keeps asking until it gets an answer.

    • Europa

      Europa

      7 天 前

      Read receipts. The recipient's phone sends a message to the sender's phone acknowledging receipt. Since it relies on the recipient's phone to send the confirmation message, if you disable read receipts in your settings, the sender will not know if you have read the message.

  72. It'sGood

    It'sGood

    9 天 前

    Bit of a tangent - but why do so many people get so upset when a company doesn't immediately handle their problem, especially during a major issue? Deliveroo is set up to deal with an average of X many queries a day, and probably has capacity for like X +50%. So when 100 time X people contact them due to a wide ranging issue, there's no way they can respond and resolve your problem within normal time limits. Especially if then the same people contact them multiple times saying things like "It's been 12 hours and you haven't refunded my kebab money yet! This is the worst thing that has every happen to a human".

  73. Krokey

    Krokey

    9 天 前

    Why would you build a castle in a valley though?

  74. Bradmakesgains

    Bradmakesgains

    9 天 前

    That doesn’t work for computers though

  75. Bradmakesgains

    Bradmakesgains

    9 天 前

    Easy, send a messenger to the other army to tell them to send a messenger at the same time as you do at a certain time, then the two messengers high five on the way to the other side and confirm to the other side that they did see the other messenger make it past the castle and that their army will charge at a certain time.

    • Joshua Tsang

      Joshua Tsang

      5 天 前

      But what if one of the 'high-five' messengars was captured after the 'high-five'? This will result in one army attacking and the other not attacking.

  76. Ninja Wiz

    Ninja Wiz

    9 天 前

    Thank you very much.

  77. siratthebox

    siratthebox

    9 天 前

    "Unsolvable" A sends a time to B, If it doesn't receive an ack within a reasonable timeframe it re-sends the time. Once A receives the ack, the message is delivered and the time is agreed. B receives a time from A, B sends an ack, If B receives a new time from A, it sends a new ack.

  78. Fyrun

    Fyrun

    9 天 前

    I think I solved it. General 1 will send a scout at dawn, or any predetermined time, along a predetermined path and will continue to do so daily. Once a scout reaches general 2, they will be informed to do the same. Then both generals will wait for a scout to come through the valley and give them the following message: "I have passed another Scout, and can confirm that they made it past the castle." (Meaning both scouts can give the message) Upon hearing this, the generals will wait until dawn to advance for the castle.

    • Fyrun

      Fyrun

      9 天 前

      In terms of computing, best I can think of is a program or executable file that can read both and determine if both went out. Then send that result to both providers.

  79. N van der Mark

    N van der Mark

    9 天 前

    How about a General C.

  80. Lazy Lee

    Lazy Lee

    9 天 前

    That's not the solution for the 2 generals problem because the general on the left will still not receive any confirmation. There are so many logical errors in this video...

  81. Mark Graham

    Mark Graham

    9 天 前

    You didn't explain why the same order sent multiple times has the same token. What's the mechanism?

  82. Jarjar Binks Sith Lord

    Jarjar Binks Sith Lord

    9 天 前

    You could decide to attack at night under the cover of darkness and have the other general fire an arrow on fire to signal that they got it.

  83. Dd FU

    Dd FU

    9 天 前

    Can't both sides keep sending the 1 guy until that one guy makes it there and back? Why can't general A just send the whole army?

  84. Attomic Doggo

    Attomic Doggo

    9 天 前

    Couldn't you just make a bucket line of soilders along the valley and when they see the message has gone through, they tell the person next to them and so on, untill it reaches the other army? Or is that a dumb response?

    • Attomic Doggo

      Attomic Doggo

      7 天 前

      @KucklePuff Not if they waived a white flag.

    • KucklePuff

      KucklePuff

      7 天 前

      Well now you’d have a whole lotta soldiers getting shot at

  85. Amiable Modron

    Amiable Modron

    9 天 前

    I can't wrap my head around the problem, since it seems like after a guy's traveled back and forth a hundred times shouting "Yes! 8am on Friday is good for everyone and everyone has agreed!" then I don't get how they don't have total confidence that they both know.

    • Amiable Modron

      Amiable Modron

      9 天 前

      @Gordon Walsh Do we even need a messenger for this problem? Seems like they could be within speaking distance of each other and it's still an issue. A: "We're doing 8am, but only if you can confirm you've gotten this message and are also doing 8am." B: "Message received. We'll also do 8am if you confirm you're also doing 8." A: "Yes, you're doing 8 too, right?" B: "Yes, you're doing 8 too, right?" A: "Yes, you're doing 8 too, right?" I.e. "Can you confirm that you got my confirmation of your confirmation of my confirmation of your confirmation of my confirmation of..." etc. I've never seen this as a problem in everyday speech. We're clearly dealing with it somehow. I guess from pure logic >99.999999999% certainty someone heard you isn't technically the same as "total certainty," but it would be solipsistic to not treat it as such in practice.

    • Gordon Walsh

      Gordon Walsh

      9 天 前

      It might help to look at it from the point of view of the messenger. Any time a message is sent, be it a new proposed schedule or a confirmation of some kind, it represents some level of uncertainty or carries information that alters the decision-making or confidence of the generals. If it did not, there would be no reason to send the message. If this message is not received, then that uncertainty goes unresolved. The problem occurs if this is the last message before the attack. Normally, the generals could just send another message, right? But the previous logic applied to any message sent, so if there is a finite number of messages sent before the attack, then the problem occurs with the last one. If there is an infinite number of messages, then you have theoretically solved the confidence aspect, but then you could never have the attack.

  86. 2bad

    2bad

    9 天 前

    just make them send a smoke signal after receiving the message simple as

  87. 808

    808

    9 天 前

    You could solve this with quantum entanglement. A general would know a message had been viewed without needing to send a message to verify.

  88. Voidstalker123

    Voidstalker123

    10 天 前

    Bro just tell blue you'll start attacking when they do.

  89. Angry Velociraptor

    Angry Velociraptor

    10 天 前

    I said for the red messenger to send a blue messenger a message saying to meet them halfway with a proposed time, if they get spotted, the message won’t go through on both sides so they know not to attack or if red goes to meet and blue isn’t there, then they know the message didn’t get through, only when the messenger comes back they know then to attack 😅

  90. Melyssa Hawes

    Melyssa Hawes

    10 天 前

    why don't they send 2 messengers to the middle and then they agree to both go back to say that they've met up🧍‍♀️ is that dumb lmao

    • Melyssa Hawes

      Melyssa Hawes

      9 天 前

      @It'sGood holdup ur right i just figured they would only get shot in the very middle lmao

    • It'sGood

      It'sGood

      9 天 前

      How does either side know that the other one got back?

  91. Arcadius

    Arcadius

    10 天 前

    Couldn't one of the generals just light a fire or do a certain musical note on a drummer boy or something to indicate the message was received?

  92. Clone3A7

    Clone3A7

    10 天 前

    The solution is to just have the messanger walk back And if they dont send another one and so on until they do make it back

  93. Hopesedge

    Hopesedge

    10 天 前

    Solution: Agree to a code of acknowledgement beforehand, and attack so long as 3 messages arrive after initial plan. Red sends: attack 5pm, repoias Blue sends back: time confirmed dedrioas Red: matchian Blue: cantoberia Red: lisotath ect ect until one of the messages is intercepted and doesn't receive an appropriate response, or doesn't receive a response at all, once that happens stop all messaging and follow through with the initial time. In this case the code would run something along the lines of 10 individual words that are to be sent in order as responses to the previous word. The enemy wouldn't be able to do anything without the time given initially, and the response would immediately confirm that blue have received the time given initially.

    • Dr. Spaceman

      Dr. Spaceman

      9 天 前

      dude wtf

  94. Peter Conroy

    Peter Conroy

    10 天 前

    1. They could negotiate a time before their forces arrive 2. They both a messenger and tell them not to come back unless they make contact with a messenger from the other army, that way, if the messenger never returns, their respective army doesn't attack

  95. TxMastermind

    TxMastermind

    10 天 前

    Both send 1 messenger and the messengers wait until a specific time if the messengers see each other by the specific time they continue if they don’t they return and try again until a pair sees each other

  96. jukappa

    jukappa

    10 天 前

    Easy, just quantum entangle the generals.

  97. Dustyn Cartwright

    Dustyn Cartwright

    10 天 前

    A signal fire on either side in stead of messenger. fire/smoke AS the signal

  98. KidEatVideo

    KidEatVideo

    10 天 前

    So, about the solution to the riddle or whatever: why don’t general A to genders B a message that’s says: ‘if you receive this message and are willing to cooperate to destroy the castle - attack the castle immoderately and we shall follow thou!’. So they attack and we join and that’s how it’s done.

  99. Shan Albert

    Shan Albert

    11 天 前

    one messenger from team A goes to team B, the messenger from team A goes to the middle of the castle with a messenger in team B and they go back to their teams at the same time. when they are back they will attack

  100. Deon's Fringe Gaming

    Deon's Fringe Gaming

    11 天 前

    I was half-expecting a solution to this problem to be something like NordVPN ad :D.

下一个