Two Generals Problem

This is a thought experiment designed to help us understand a very basic problem in distributed systems.

Scenario

There are three cities named A, B, and C. Both City B and City C's generals want to attack City A, but City A is well-defended enough that neither City B nor City C can win an invasion against City A on their own.

The smart generals in Cities B and C come up with a plan. They think that if they both attack City A at the same time, they will be able to take it down.

Both generals agree to do their own reconnaissance and send a messenger when they find the best time to attack.

The forest between City B and City C is also connected to City A. When City A hears about this plan, it sends people to stop any messengers going through the forest to stop them from carrying out their plan.

This means that it's possible that City C will never get a message sent by City B, and the same is true for City B.

Our challenge is to come up with a way for both cities to agree on when to attack City A.

Solutions

Solution 1

City B knows that City A might catch its messenger, so it sends more than one, hoping that one of them will get through. Then, City B attacks City A without hearing back from City A, hoping that at least one of its messengers would have reached City C.

But there's a good chance that City A will catch all the messengers, and City B will lose because City C never got the message.

Solution 2

What if City B waited until it heard back from City C that it got the message before attacking? So, City B won't have to fight a battle it can't win, right?

City B might not be fighting a losing battle, but City C might be, since the messenger sent by City C to confirm the invasion date could be caught by City A, and City C has no way of knowing if their confirmation got through.

Is this practical?

Sure, and it happens more often than you think.

Imagine we are building an online shop and want to connect it to a Payment Service.

Customer, Online Shop, and Payment Service must all agree on a common message ( Money Charged ).

It's possible that the money was charged to the customer, but when the payment service tried to tell you, the message got lost. This is a problem because money is taken from the customer but our Online Shop doesn't know it.

If this really happens, how do online shops work?

In real life, there are reconciliation systems that track these types of extra money movement and delay your refunds unlike our thought experiment where there was no scope of fixing things later.

If you've ever had a problem with Amazon or Swiggy where your payment went through but your order wasn't placed, even if Swiggy didn't know about it right away and couldn't place your order, it eventually learned about it and processed your refund, and you'd have received your money back.

There's nothing we can do to keep messages from getting lost, but we can figure out what went wrong and fix it later.