Two General Problem
Problem Statement
Lets say that you are leading an army. You need to co-ordinate an attack on the enemy with a friend, situated at the opposite end.
The only way to communicate with the friend and vice versa is through a spy who would need to cross the “Enemy Area”.
How would you co-ordinate with the other army to attack at a precise time?It is important that the attack happens simultaneously, as the enemy is powerful enough to win individual armies, but not when fighting both armies.
Solution?
One plausible solution would be to send a spy mentioning the time of attack. Here, it doesn’t matter if the enemy gets to know the time of attack, what matters is that both armies attack together.
So say, the spy leaves. Now there are 2 outcomes, he gets caught or he reaches your friend.
In both the cases, you are not sure of whether your friend knows about the attack time, so in order to make sure, you had asked the spy to send a return spy to inform you about the successful message receiving.
Your Spy -> Caught (You are not sure whether to attack or not)
Your Spy -> Reaches Friend’s Place -> Friend’s spy -> Caught (You are still not sure whether to attack or not)
Your Spy -> Reaches Friend’s Place -> Friend’s spy -> Reaches You (Your friend doesn’t know whether his spy reached you and hence now he is unsure of the attack)
Your Spy -> Reaches Friend’s Place -> Friend’s spy -> Reaches You -> Your Spy -> Caught (Your friend doesn’t know whether his spy reached you and hence now he is unsure of the attack)
Your Spy -> Reaches Friend’s Place -> Friend’s spy -> Reaches You -> Your Spy -> Reaches Friend’s Place (You don’t know whether your spy reached the friend’s place and hence now you are unsure of the attack)
Extrapolating, this can continue forever without reaching a consensus on the attack.
Internet and Two General Problem
Why does this problem statement feature in Computer Science?
This problem statement is the basis of lot of solutions on which the internet is made up of.
When a data packet travel’s from the host computer to the destination computer, it crosses multiple routers. How then does the host computer know of the successful transmission of the data?
Or let us say that we want consistency (one master, one slave), how does the master and slave co-ordinate for consistent writes.
Or let us say we do not want the enemy to know about the time of attack (data security).
This challenge would exist whenever we want to co-ordinate an action between multiple systems.
Possible Solutions
The base of each solution is idempotency. You could possibly have multiple spies with the same data, the receiver needs to ensure to treat them as one.
Or in case of different messages, there needs to be a resolution mechanism to know which one is the correct message e.g. in a distributed system, when there are multiple writes to the same key. Each write is idempotent independently, but at a system level, which write is to be considered.
Each problem has different solutions on the basis of cost and implementation challenges.
Below are few examples.
Data Transmission
For transmitting a data packet, the solution is to have multiple routes, so when an acknowledgement isn’t received or multiple acknowledgment aren’t received via a route, change the route so as to increase probability.
The internet is a web of routes, where each router checks for the headers of the data packet, to identify the destination path and directs the packet to the next router.
In case when the acknowledgment is not received within specific time, the packet is retried or sent via a different route.
When an acknowledgment is received, the sender stops retrying. In this way there is no need of multiple trips.
Your spy -> Caught (You are unsure)
Your Spy -> Reaches Friend’s Place -> Friend’s spy -> Caught (You are still not sure whether to attack or not)
Your Spy -> Reaches Friend’s Place -> Friend’s spy -> Reaches You (You are sure to attack)
There are chances that the destination has received the data but sender hasn’t received the acknowledgment. This is solved by using different routes and retries, wherein the underlying assumption is enough retries will eventually make systems consistent.
System Design and the problem statement
The Two General Problem is applicable in all system designs. It is when consistency is needed across distributed systems.
When multiple systems have to be on the same values.
What is your take on the problem? In which shape have you ever come across the 2 General Problem?
