Two Generals Problems - What's wrong with my approach?

Question

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?

Answer 1

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.

Answer 2

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?

Answer 3

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.

Answer 4

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.