2
$\begingroup$

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:

  • 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 case, General A can send the message:

  • 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.
  • I will not send any other communication until I've received your confirmation.

That way, General A can be sure that General B received the plan, when he gets the confirmation and General B can be sure General A received the confirmation when General A sending messages about something else.

So, what is wrong with my approach?

$\endgroup$
  • 1
    $\begingroup$ "...and General B can be sure General A received the confirmation when General A sending messages about something else.". Not sure if I understood, but what happens if General A has nothing else to send? You would still have a scenario where you need to account the probability that General A has something else to send, wouldn't? $\endgroup$ – Victor Hugo Oct 7 '19 at 20:25
  • $\begingroup$ Yes. That's just a special case where a 100% certainty for both can be reached. The main thing i don't understand is why sending confirmation forth and back is the way to handle this problem. $\endgroup$ – Shade Oct 7 '19 at 20:36
  • 3
    $\begingroup$ You explain in your post what's wrong with your idea – "[i]t doesn't solve the problem". $\endgroup$ – Yuval Filmus Oct 7 '19 at 20:58
2
$\begingroup$

New answer

After thinking some more and searching around for a bit I beleive 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 acked. 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

  1. The sender did not receive an acknowledgement so it sends the same message again.
  2. The receiver notices that the same message is being sent again so it sends the same acknowledgement it sent previously for this message.
  3. 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

  1. General A did not receive an acknwoledgement so he sends the same message again.
  2. General B notices that the same message is being sent again so he sends the same confirmation he sent previously for this message.
  3. 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.

$\endgroup$
  • $\begingroup$ The Special Case is just something additional and not the main approach. My thought when reading the "practical approach" on Wikipedia was That's crude. Some time later, I had the idea for my approach. So, I began to start looking for the name of this approach but wasn't able to find it. So, I assumed there has to be a flaw as otherwise, somebody else would've come up with it. The special case came later when looking into it deeper and deeper to find the flaw in my approach. $\endgroup$ – Shade Oct 8 '19 at 12:23
  • $\begingroup$ @shade, I edited my answer to elaborate further. $\endgroup$ – Pelican Oct 8 '19 at 16:41
  • $\begingroup$ Thanks. So, I was too focused on the two generals problem in order to search for the implementation... $\endgroup$ – Shade Oct 8 '19 at 18:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.