4
$\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$
3
  • 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$ Oct 7, 2019 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, 2019 at 20:36
  • 4
    $\begingroup$ You explain in your post what's wrong with your idea – "[i]t doesn't solve the problem". $\endgroup$ Oct 7, 2019 at 20:58

4 Answers 4

3
$\begingroup$

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

  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 acknowledgement 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$
4
  • $\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, 2019 at 12:23
  • $\begingroup$ @shade, I edited my answer to elaborate further. $\endgroup$
    – Pelican
    Oct 8, 2019 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, 2019 at 18:04
  • $\begingroup$ This answer is wrong. You are describing how TCP works. In TCP, the receiver never has certainty that the sender knows the receiver received the sent messages. See my answer for further details. In the Two Generals Problem, it is criticial that the receiver knows that the sender knows the receiver recieved the information. This is a stronger guarantee than TCP provides. $\endgroup$ Feb 11 at 12:00
1
$\begingroup$

Here is where you misunderstand the Two Generals Problem:

I will resend the time of attack after time t if I did not get a confirmation.

The Two Generals problem does not allow for retries. That isn't specified as being part of how the system works.

You even said it yourself:

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.

Well, that is the definition of the Two Generals Problem. Both of them have to be certain about all messages being sent and received without any message being lost. (Including the final one.)

You have redefined an alternative message exchange system, essentially the same as to that of TCP, where retries are permitted and used to attempt to transfer information from one place to another.


Here is some more detailed information:

The Two Generals Problem (and the more general case of the Byzantine Generals Problem) is not about answering the question:

  • Can you send a piece of information from one entity to another

Clearly this is possible, and is how TCP works. You keep sending the data or an ack to the data until the sender sees the ack. That way the sender knows the receiver knows the information the sender has. (RETRIES are permitted.)

Instead it is about answering the question:

  • Can two entities exchange a fixed, finite number of messages between each other to agree on a concensus, WITHOUT retrys.

This question is clearly mathematically impossible on an unreliable network because the number of messages exchanged is irrelevant. The problem is both intuitive and obvious: With each message which is exchanged, there is a finite probability of it being lost. The more messages which are exchanged, the higher probability that the sequence will be broken at some point by a message being lost.

I suspect, in terms of information theory, the more messages are successfully exchanged, the higher degree of confidence one has about both systems being "in concensus" however there is also a higher probability of a message being lost at some point in the sequence.

I'm not totally sure on that.

  • In the "TCP case" one system starts with the message x=4. It wants to send that message to another system. All it has to do is repeatedly send x=4 until the other system replies with x=4. Then the sender knows the receiver has the data it sent. The reciever however NEVER knows the sender knows the receiver has the information x=4. It may be able to infer this by the fact that the sender stops sending x=4 for some period of time - but how long should it wait? It might not be that the sender has stopped sending but that all messages are now being lost.

  • In the "Two Generals case" one system starts with the message x=4. It wants to send that message to the receiver, but critically the receiver also wants to know that the sender knows that it knows that x=4. This is different from the above case. If the receiver replies to the sender saying x=4 (ie: I know that x=4 as well) the reply may be lost. This is a mirror image of the original problem, just one step further along a chain of messages. There is a symmetry to the problem, a recursive nature to it, if you will.

Hopefully it is obvious how the two problems differ?

$\endgroup$
1
$\begingroup$

The enemy puts a few dozen highly trained snipers around the generals camp. Anyone leaving looking like a messenger or entering looking like a messenger will be instantly shot.

Sorry, your general will be in the dark.

$\endgroup$
1
  • $\begingroup$ (What is a messaged?)(Edit queue too full) $\endgroup$
    – greybeard
    Feb 12 at 7:36
1
$\begingroup$

Whenever you think you have solved the two generals problem, there is only one thing you need to do to find why your solution is wrong.

Take every step s_1...s_n of your algorithm and treat it as the final step before a permanent network failure.
Does a general end up dead if any step s_i is the final step before total network failure?
Then you haven't solved it.

You say once A receives confirmation he will begin sending some new type of messages instead of the old attack time. Okay so he gets the confirmation. Then a permanent network failure happens. He begins sending that new type of message out but none of them will ever reach B, so B will never be certain enough to attack. Now under your scheme general A rides out to his death alone.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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