The Two Generals’ Problem

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

Why do kids toys adverts have to say “batteries not included?”

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).

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

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.

An interesting follow up would be the Byzantine general's problem - what if there were multiple generals that could back stab each other?

Hey, I'm allowed to watch a series called "The Basics" even if I am working on safety of flight software!

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...

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

The example was weak, imo. But good info.

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

Wait couldn't one messenger for A and one messenger from B meet in the valley and give each other a set time?

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

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

pls get patreon and premium memberships and no cemmercials thnx

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.

Initially, I completely misread the title.

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

I know that this video is not about military tactics, but it would be extremely easy, I feel, to coordinate that attack.

Theoretically quantum entanglement, more specifically quantum computing does in fact solve this problem. For reference, research the two slits photon phenomena.

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.

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

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

Now, can you do one that explains why idempotency is pronounced like that? I've always read it as i-dem-potency

An interesting follow up would be the Byzantine general's problem - what if there were multiple generals that could back stab each other?

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

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

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."

The solution is to use flags as long distance communication

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

OMG look at all those IBM PCs!!

...tcp

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.

google already does for free what dashlane charges for.

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

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.

Huh?

"A single human error is never the root cause" A single human error: I'm about to end this man's whole career

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.

A lot of FUD in the intro, when this problem is not affecting people in the real world hardly at all anymore.

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.

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

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

even thieves can't avoid a traceable digital fingerprint....just a logical fact.

The actual same thing happens to me

But they don't know that we know they know!

Just go around the castle and talk to them

obviously war drums or bag pipes.

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.

Am I the only one that got an ad for that same company?

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.

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.

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...

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.

Suggest recipes for Tom to cook tbh

Brexit

These comments are excellent, wish I could see them more than once!

These comments are excellent, wish I could see them more than once!

Captain Kirk would have solved the problem.

Figured it out - the general would turn his entire division, including himself into messengers. Crisis averted, you're welcome.

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 🚀🙄

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.

Wrong! there is a solution for this Problem, it's called quantum entanglement.

Couldn't you just have the messengers meet in the middle, shout the time, and then run back quick as they can?

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.

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?

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.

Power to the deliveroo strikers tho

got randomly recommended this video an hour after it came out......... i am now subbed and have been bingeing your videos

why did I watch this so long hahaha

Walk around

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?

Quantum computing

Only drawback to Dashlane is cost. Free as single use, but to sync it is expensive..

Take the long way round, at night?

where do they ever put castles in valleys? I've never seen one, all the ones I've seen are on hilltops

Use Smoke signs

I almost read the title as “The two genders problem” and was about to comment that there is only two genders, not 72 😂

I thought it said the 2 genders problem

not accurate, a castlee would have been built on the highest point :)