principleMinor
Two Generals Problems - What's wrong with my approach?
Viewed 0 times
generalswhatwithtwowrongproblemsapproach
Problem
Some time ago, I've come across the Two Generals Problem and that it cannot be resolved. Now, recently, I've had an idea how to approach it. IMHO, it is a very obvious way to handle it but I haven't found this way to handle it anywhere and therefore assume my idea is flawed but I can't find the error.
The approach I've found online (from Wikipedia):
A pragmatic approach to dealing with the Two Generals' Problem is to use schemes that accept the uncertainty of the communications channel and not attempt to eliminate it, but rather mitigate it to an acceptable degree. For example, the first general could send 100 messengers, anticipating that the probability of all being captured is low. With this approach the first general will attack no matter what, and the second general will attack if any message is received.
This seems very crude and the chance of a non-delivery stays at $(1-p)^c$.
My Approach
General A sends a message to General B when to attack. The message contains the following information:
That way, General A can be sure General B got the message when he gets the confirmation. General B can be $(1 - p)^{m \cdot c}$ sure that it passed after not getting the time of attack again, where
It does not solve the problem that General B can't be 100% sure that General A received the confirmation but after some time, he can be very certain.
Special Case
Now, if we were to change the scenario slightly, we can reach a 100% certainty for both:
Assume both Generals do not only communicate in order to synchronize the attack but also for other purposes. In that cas
The approach I've found online (from Wikipedia):
A pragmatic approach to dealing with the Two Generals' Problem is to use schemes that accept the uncertainty of the communications channel and not attempt to eliminate it, but rather mitigate it to an acceptable degree. For example, the first general could send 100 messengers, anticipating that the probability of all being captured is low. With this approach the first general will attack no matter what, and the second general will attack if any message is received.
This seems very crude and the chance of a non-delivery stays at $(1-p)^c$.
My Approach
General A sends a message to General B when to attack. The message contains the following information:
- Attack at time $T$.
- Send confirmation of receival.
- I will not confirm your confirmation.
- I will resend the time of attack after time $t$ if I did not get a confirmation.
That way, General A can be sure General B got the message when he gets the confirmation. General B can be $(1 - p)^{m \cdot c}$ sure that it passed after not getting the time of attack again, where
- $p$ := probability the confirmation passed
- $m$ := multiple of time $t$ that has passed.
- $c$ := count of messages sent per time unit (one of the solutions I've come across is to send a lot of messages at the same time).
It does not solve the problem that General B can't be 100% sure that General A received the confirmation but after some time, he can be very certain.
Special Case
Now, if we were to change the scenario slightly, we can reach a 100% certainty for both:
Assume both Generals do not only communicate in order to synchronize the attack but also for other purposes. In that cas
Solution
New answer
After thinking some more and searching around for a bit I believe both of your approaches are already implemented in TCP, as can be seen here:
[...] Acknowledgements (ACKs) are sent with a sequence number by the receiver of data to tell the sender that data has been received to the specified byte. [...]
Reliability is achieved by the sender detecting lost data and retransmitting it. TCP uses two primary techniques to identify loss. Retransmission timeout (abbreviated as RTO) and duplicate cumulative acknowledgements (DupAcks).
Timeout-based retransmission
Whenever a packet is sent, the sender sets a timer that is a conservative estimate of when that packet will be ack'ed. If the sender does not receive an ACK by then, it transmits that packet again. [...]
Dupack-based retransmission
If a single packet (say packet 100) in a stream is lost, then [...] the receiver acknowledges packet 99 again on the receipt of another data packet. [...] if the sender receives three duplicate acknowledgements, it retransmits the last unacknowledged packet. [...]
Retransmission timeout
Retransmission timeout is similar to your first approach: if general A did not receive the confirmation, he will send the same message again.
Duplicate cumulative acknowledgements
First we need to understand the steps taken in each algorithm.
TCP
Your special case
We can see that both algorithms are the same, except for their terminology. So there isn't any problem with your approaches.
Old, wrong answer
The problem with your Special Case approach is that B cannot do anything until new communication is sent. Because this can happen after the attack time has passed, this is not a functional approach.
Translated to real life networking, this means that the message has to sit in the buffer until the next message is received. This is not a usable strategy in most applications.
After thinking some more and searching around for a bit I believe both of your approaches are already implemented in TCP, as can be seen here:
[...] Acknowledgements (ACKs) are sent with a sequence number by the receiver of data to tell the sender that data has been received to the specified byte. [...]
Reliability is achieved by the sender detecting lost data and retransmitting it. TCP uses two primary techniques to identify loss. Retransmission timeout (abbreviated as RTO) and duplicate cumulative acknowledgements (DupAcks).
Timeout-based retransmission
Whenever a packet is sent, the sender sets a timer that is a conservative estimate of when that packet will be ack'ed. If the sender does not receive an ACK by then, it transmits that packet again. [...]
Dupack-based retransmission
If a single packet (say packet 100) in a stream is lost, then [...] the receiver acknowledges packet 99 again on the receipt of another data packet. [...] if the sender receives three duplicate acknowledgements, it retransmits the last unacknowledged packet. [...]
Retransmission timeout
Retransmission timeout is similar to your first approach: if general A did not receive the confirmation, he will send the same message again.
Duplicate cumulative acknowledgements
First we need to understand the steps taken in each algorithm.
TCP
- The sender did not receive an acknowledgement so it sends the same message again.
- The receiver notices that the same message is being sent again so it sends the same acknowledgement it sent previously for this message.
- Only when the sender receives this acknowledgement it will send the next message. Only when the sender sends a new message will the receiver know that the confirmation has been received.
Your special case
- General A did not receive an acknowledgement so he sends the same message again.
- General B notices that the same message is being sent again so he sends the same confirmation he sent previously for this message.
- Only when general A receives this acknowledgement he will send the next message. Only when general A sends a new message will general B know that the confirmation has been received.
We can see that both algorithms are the same, except for their terminology. So there isn't any problem with your approaches.
Old, wrong answer
The problem with your Special Case approach is that B cannot do anything until new communication is sent. Because this can happen after the attack time has passed, this is not a functional approach.
Translated to real life networking, this means that the message has to sit in the buffer until the next message is received. This is not a usable strategy in most applications.
Context
StackExchange Computer Science Q#115570, answer score: 3
Revisions (0)
No revisions yet.