Foncé

The Two Generals’ Problem

Tom Scott
S'abonner
Vues 1 036 077
98% 46 823 680

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: frvid.com/group/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 twitter.com/tomscott
on Facebook at facebook.com/tomscott
and on Instagram as tomscottgo

Ajoutée

 

12 août 2019

tom scotttomscottthe basicscomputer sciencetwo generals problemtwo generals' problemthe two generals problemidempotencyidempotency keyidempotency tokenidempotence

Partager:

Lien:

Télécharger:

Charger le lien.....

Ajouter à:

Ma playlist
À regarder plus tard
Commentaires 1 976
Tom Scott
Tom Scott Il y a 23 jours
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
Andrew F
Andrew F Il y a jour
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 Il y a jour
who would put the castle in the valley but a computer tech
ERMAN ATES
ERMAN ATES Il y a jour
It was very well put. Animations were only fabulous. Thanks
John Jennings
John Jennings Il y a 3 jours
Glad to know Dashlane is sponsoring you and you trust them! Been using them for 3 years now
Treqqing
Treqqing Il y a 3 jours
Could you do an episode on the flat earth
soSAMuk's UK slot channel
soSAMuk's UK slot channel Il y a 11 heures
Why do kids toys adverts have to say “batteries not included?”
TheDeathMongrel
TheDeathMongrel Il y a 12 heures
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 Il y a 12 heures
General A sends "8pm" General B sends "8pm ack" - General a doesn't attack unless it receives the ack...
Aaron
Aaron Il y a 13 heures
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 Il y a 13 heures
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 Il y a 13 heures
Hey, I'm allowed to watch a series called "The Basics" even if I am working on safety of flight software!
1dgram
1dgram Il y a 11 heures
@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 Il y a 13 heures
Now, can you do one that explains why idempotency is pronounced like that? I've always read it as i-dem-potency
KryskZ09
KryskZ09 Il y a 13 heures
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 Il y a 14 heures
You are so handsome hehe I like your channel! Greats from Brazil.
shinvergil
shinvergil Il y a 14 heures
The example was weak, imo. But good info.
X
X Il y a 14 heures
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 Il y a 15 heures
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 Il y a 16 heures
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 Il y a 16 heures
This is a shitty hypothetical, as reasonable suggestions will not be accepted.
Jake Hartman
Jake Hartman Il y a 17 heures
pls get patreon and premium memberships and no cemmercials thnx
Z-Statistic
Z-Statistic Il y a 18 heures
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 Il y a 18 heures
Initially, I completely misread the title.
Eric Tripps
Eric Tripps Il y a 19 heures
So the idempotency token solves the double send error but how does it solve the generals problem?
Winston Churchill
Winston Churchill Il y a 19 heures
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 Il y a 21 heure
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 Il y a 21 heure
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 Il y a 22 heures
"idempotency". One of the sexiest words in computer science that no one really knows how to pronounce.
Matthew Booth
Matthew Booth Il y a jour
I've always pronounced this EYE-dem-POE-tent.
David Alan Gilbert
David Alan Gilbert Il y a jour
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 Il y a jour
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 Il y a jour
Just saw at kings cross, sorry didn't say hello, was running late, love the boss
d
d Il y a jour
I thought the title was “2 genders problem” and I came for the comments
Crimson Vulpes
Crimson Vulpes Il y a jour
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 Il y a jour
The solution is to use flags as long distance communication
Bloodthirsty
Bloodthirsty Il y a jour
How about lighting the biggest fire the blue general has ever seen
Patrick Armstrong
Patrick Armstrong Il y a jour
OMG look at all those IBM PCs!!
Red Jellonian
Red Jellonian Il y a jour
...tcp
Anikthias
Anikthias Il y a jour
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 Il y a jour
google already does for free what dashlane charges for.
Mostwanted
Mostwanted Il y a jour
Had this with dominos, same I had the instinct to Not risk paying again..that's just silly
Frank Harr
Frank Harr Il y a jour
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 Il y a 17 heures
True, that's got going to work either. Nothing does. I'm trying to fit this solution into the parable.
HudsonA
HudsonA Il y a 20 heures
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 Il y a jour
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 Il y a jour
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 Il y a jour
A lot of FUD in the intro, when this problem is not affecting people in the real world hardly at all anymore.
Ricky
Ricky Il y a jour
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 Il y a jour
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 Il y a jour
The solution is send them information in quantum entanglement state. (-;
Wolf Slayer
Wolf Slayer Il y a jour
even thieves can't avoid a traceable digital fingerprint....just a logical fact.
4our 20wenty
4our 20wenty Il y a jour
The actual same thing happens to me
Louis Wouters
Louis Wouters Il y a jour
But they don't know that we know they know!
Ursula Panzer
Ursula Panzer Il y a jour
Just go around the castle and talk to them
Vagabond Wastrel
Vagabond Wastrel Il y a jour
obviously war drums or bag pipes.
The Sinful Gamer
The Sinful Gamer Il y a jour
That problem isn't nearly that difficult. Once A has sent B a message, B sends a message back, confirming they got that message, A then sends a confirmation that they have indeed got the message, if they get a reply to that message, they are all good, considering they both at this point understand at 8pm they would attack, both would attack.
HudsonA
HudsonA Il y a 19 heures
The problem is the last message is always crucial, but only one side knows if it got through, and the receiver knows that the sender needs to know that it got through. A sends message 1, and A must find out if that message was sent. So B sends message 2 to A, to confirm the crucial message 1. Because message 2 confirms message 1, message 2 is also crucial. So B needs confirmation on message 2. Thus A sends message 3 to confirm the crucial message 2, but this makes message 3 crucial, so B sends message 4 to confirm it. But if message 3 was crucial, then B has to know that A got its confirmation, which makes message 4 crucial. So A receives message 4, which is crucial, thus it needs confirmation, so they send message 5, which is now crucial because A needs to know if B knows the crucial message 4 was confirmed. Because message 5 is now crucial, B has to send message 6 to let A know B got it, but this makes message 6 crucial. This repeats forever. Both sides know that they need confirmation, but they also know that the tentative time hasn't changed. After 100 messages each asking for confirmation on the same time, it would be safe to attack at that time without confirmation, but a computer would have to be programmed to give it a threshold over which to attack without confirmation.
Matt Kazachinsky
Matt Kazachinsky Il y a jour
Am I the only one that got an ad for that same company?
ano nym
ano nym Il y a jour
Couldn't the message chain be: Red: We attack at 8PM. Blue: we both Attack at 8PM, please confirm that this message is recieved. Red: Your message is recieved, we will both attack at 8. Regardless of if the last message makes it, they will both have the agreement to attack.
ano nym
ano nym Il y a 21 heure
@Cobalt57 True, saw that I had one to few, but if blue replied again, they would both know! Or am I missing something?
Cobalt57
Cobalt57 Il y a 22 heures
If the last message from Red doesn't make it, Blue could go on faith, but they'd rather have a guarantee Red is going to attack. And Blue knows that maybe their own message didn't get through, if so then Red won't be sending a reply, and they know Red won't attack alone, thus the problem in the video. You don't know your confirmation got through unless you get a further confirmation back. So no end to the chain, if you're looking for that absolute guarantee.
FateEntity
FateEntity Il y a jour
Video IMMEDIATELY jumps into it and I felt lost and confused about what was going on. Maybe have a small few second intro or a preface? Disliked.
TechByte
TechByte Il y a jour
So how exactly does this fix the two generals problem? There’s still now way for each general to know if his message made it...
terrorzilla
terrorzilla Il y a jour
Had a similar problem ordering pizza in the USA recently. I actually got the order acknowledgement and tracker notice after the pizza arrived. Like you, I suspected it had worked and was right.
Famalamadingdong GE/PD
Suggest recipes for Tom to cook tbh
Mohsen Javaed
Mohsen Javaed Il y a jour
Brexit
Cheese Borger
Cheese Borger Il y a jour
These comments are excellent, wish I could see them more than once!
Cheese Borger
Cheese Borger Il y a jour
These comments are excellent, wish I could see them more than once!
Sean Webb
Sean Webb Il y a jour
Captain Kirk would have solved the problem.
Paul Anderson
Paul Anderson Il y a jour
Figured it out - the general would turn his entire division, including himself into messengers. Crisis averted, you're welcome.
shake bake
shake bake Il y a jour
Please do a video that explains to us simple/matrix folk, why we have to enjure annoying adverts that nobody acknowledge's, understands or care's for. Let alone ever buys from? The moon landing or 9/11 makes more sense 🚀🙄
Gold Fishy
Gold Fishy Il y a jour
But his token solution doesn’t actually solve the generals problem presented in the beginning. However, a solution to the generals problem was discovered in 2009. That solution was Bitcoin. Seriously. Google it.
SnipahWoolF
SnipahWoolF Il y a jour
Wrong! there is a solution for this Problem, it's called quantum entanglement.
Luny Moon
Luny Moon Il y a jour
Couldn't you just have the messengers meet in the middle, shout the time, and then run back quick as they can?
Dank_Bandit
Dank_Bandit Il y a jour
To solve the two generals problem, just tell the other side to raise tall flags before the attack begins to signal that its time. Is there some way that wouldn't work? Both sides of the valley are above the castle so that won't be blocking their view.
Kronus Exodues
Kronus Exodues Il y a 2 jours
okay, what about the solution of brute forcing this? A sends B a hundred messages that they'll attack at midnight. many of them might get decepted, but a few ought to get through. A then just relies on the brute force being successful, B relies on A relying on it, both attack at midnight and win. and if B gets that message multiple times, that's no tragetdy either. Is that brute force approach something that get's done in practice?
GoodISnipr
GoodISnipr Il y a 2 jours
Call of Duty is a game of Rock, Paper, Scissors. Play split screen local. Choose a loadout. Only 1. The other player, if they see what you chose, can then choose their loadout to have a very high kill/death ratio. But, this is why there are 5 custom loadout slots. Use them wisely and then take what you've learned and apply the principles in reality.
Tevan Pinrut
Tevan Pinrut Il y a 2 jours
Power to the deliveroo strikers tho
StoneyGames
StoneyGames Il y a 2 jours
got randomly recommended this video an hour after it came out......... i am now subbed and have been bingeing your videos
Clarence's Real Life
Clarence's Real Life Il y a 2 jours
why did I watch this so long hahaha
Nathaniel Echeverria
Nathaniel Echeverria Il y a 2 jours
Walk around
jimifloydrix
jimifloydrix Il y a 2 jours
Re: idempotency. How does the phone know that it's the same order twice? How do you prevent the phone from creating a new idempotency key the second time you request something?
Nil Haul
Nil Haul Il y a 2 jours
Quantum computing
Ask to seduce Miss
Ask to seduce Miss Il y a 2 jours
attack from different locations then one of the Generals takes their army there and waits for the agreed time.
Chuck
Chuck Il y a 2 jours
Only drawback to Dashlane is cost. Free as single use, but to sync it is expensive..
Ask to seduce Miss
Ask to seduce Miss Il y a 2 jours
Solution: General A marches his army through the danger zone suffers losses and meets up with General B and army. They agree to attack at a set time. If it’s important that t
Jimmy Jams
Jimmy Jams Il y a 2 jours
Take the long way round, at night?
filevans
filevans Il y a 2 jours
where do they ever put castles in valleys? I've never seen one, all the ones I've seen are on hilltops
Prof.Tu.nichts
Prof.Tu.nichts Il y a 2 jours
Use Smoke signs
Tay Woode
Tay Woode Il y a 2 jours
I almost read the title as “The two genders problem” and was about to comment that there is only two genders, not 72 😂
Ultra .26
Ultra .26 Il y a 2 jours
I thought it said the 2 genders problem
Leopard Bra Brado
Leopard Bra Brado Il y a 2 jours
not accurate, a castlee would have been built on the highest point :)
Logan
Logan Il y a jour
Not neccessarily if the valley is an important trade route and it is surrounded my steep cliffs
Prochain
The Two Generals’ Problem
8:26
Fame is Lame
9:51
Vues 1 525 735
How Auto-Tune Works
2:41
Why You Can't Trust Me
9:38
The Bielefeld Conspiracy
2:21