Talk:Two Generals' Problem/Archive 1

Archive 1

Redirect

Could a search for "two army problem", which seems to be a common name for the same thing, be redirected here?

Is already done. Mathmo ^Talk 09:00, 12 February 2007 (UTC)

Categories

Why is thes in the TOC category? What about something related to networks? -Weedrat 06:43, 10 May 2007 (UTC)

Null syncronization

Depending on the precise nature of the problem, it may be possible to coordinate the attack by sending no messages. There is rumor that the Germans used a similar coordination system where enemy locations & hotspots were transmitted but nothing else. There was a standard "canned" protocol for attack times, etc. —Preceding unsigned comment added by 12.117.131.10 (talk) 15:18, 14 September 2007 (UTC)

That requires an already agreed-upon time. If you complicate the problem so that the generals need to exchange information that wasn't available beforehand, such as they discover that the town has four gates, and they need to coordinate which gates to attack, you're back to the same problem. As a military problem, this is mostly just a story (but not always -- it comes up in small scale during the confusion of a battle, the wrong message might be acknowledged, etc). In the real world problems for which this problem is a metaphor, there's always a piece missing that wasn't known beforehand, such as transaction data that needs to be committed. 67.98.226.13 20:59, 20 September 2007 (UTC)

Solution

Isn't this a solution to this problem? The leader sends this message: "The attack begins 1 year from today at noon if both of us know that both of us have received at least 1 message, including this one. Only send a message after you have received a message. If you send a message and you don't get a response, send another message until you eventually get a response. We will send messages back and forth. If you know that I have received at least 1 reply, then you are ordered to attack. If I know that you have received at least 1 message, including this one, then I will attack. Obviously, to know that you have received at least 1 message, you must send me a reply, otherwise I will not know that you have received a message. In turn, in order for me to know that you have received at least 1 message, you must send me a response. Reply to me until you have received at least one response. The only way the attack will occur, is if both of us know that each of us have received at least 1 message. And the only way that will happen, is if each of us have received 3 or more messages, because by that time it is obvious that both of us will have received at least 1 message. Therefore, keep sending messages until you have received 3 messages." —Preceding unsigned comment added by Oiarbovnb (talk • contribs) 19:26, 29 July 2008 (UTC)

This doesn't work, because it's possible that one general will have received 3 messages and the other only 2, so that only one will attack. Dcoetzee 19:39, 29 July 2008 (UTC)

Chinese Generals problem

I have deleted this term which is not mentioned in the refs given as an alternate. According to this ref the term is a generalisation of the Byzantine generals problem, not this one. SpinningSpark 20:16, 31 July 2008 (UTC)

Illustration

Recent edit removed "fortified" from "'fortified' city". I think "fortified" shouldn't have been removed, since it helps illustrate how important the generals decision will be —Preceding unsigned comment added by 66.90.147.7 (talk) 04:36, 14 May 2009 (UTC)

Um, I added fortified, I didn't delete it. So thanks for your approval, please learn to use the edit history properly. By the way, I disagree that "grievous losses" should have been changed to "total devastation" is cheap imagery and unencyclopedic.

Also please sign your posts with four ~'s 67.244.76.211 (talk) 04:40, 14 May 2009 (UTC)

Counterexample

"It quickly becomes evident that no matter how many [...]". I don't agree. Counterexample:

• General 1: "Message 1a: Time for attack: Monday, 09:00 GMT. I will only attack if I know you have received this message."
• General 2: "Message 1b: Message 1a received. Attack scheduled for Monday, 09:00 GMT. I will only attack if I know you have received this message."
• General 1: "Message 2a: Message 1b received."
• General 2: "Message 2b: Messages 1a and 2a received. I will attack."
• General 1: "Message 3a: Messages 1b and 2b received. I will attack, too."
• General 2: "Message 3b: Messages 1a, 2a and 3a received."
• General 1: "Message 4a: Messages 1b, 2b and 3b received. On an off-topic note: Your muscles are really hot."
• General 2: "Message 4b: Messages 1a, 2a, 3a and 4a received. You have great muscles, too, but I hope you don't make any advances to me with this."
• General 1: "Message 5a: Messages 1b, 2b, 3b and 4b received. I never would. You know, I'm married."

At this point in time, it does not matter whether message 5a is actually delivered or not (except for General 2 maybe feeling a bit awkward during the attack, if he won't have gotten a reply to message 4b by then :). --boarders paradise (talk) 04:42, 20 May 2009 (UTC)

This doesn't work. There are many ways it can break down. When General 1 receives message 1b, he will attack Because he knows that General 2 has received message 1a. But General 2 will only attack if he receives message 2a. So General 1 attacks and General 2 does not, and they lose the battle. This counter-example doesn't work because there's always a finite change that messages 2a and onwards are lost, while messages 1a and 1b get through. So while this is a sensible strategy in that it has a couple of degrees of error-checking, reducing the probability that only one general attacks, it's still totally possible to happen and doesn't resolve the problem. 140.184.21.115 (talk) 16:55, 17 June 2010 (UTC)

If you are a notable mathematician, please link to where you have published this important work so we can mention it in the article. If not, try thinking about it a bit harder. SpinningSpark 06:54, 20 May 2009 (UTC)

A single counterexample is sufficient for countering the article's two proofs that this problem has not a single solution, no matter if the counterexample stems from a "notable" person or not. I sincerely wanted to contribute to this Wikipedia page and as I find that the article's claims are wrong I posted this message here. I'm familiar with Wikipedia's policies (no original research), that's precisely why I would have never posted this content on the article's page but started a discussion instead. (I did an extensive research on the Internet, but there are only a few pages discussing the issue and most of them even have a wrong take on the problem, thinking they are dealing with a probability issue. I've thought about it as hard as I can and I think the counterexample is valid. --boarders paradise (talk) 14:44, 20 May 2009 (UTC)

Well you are absolutely right on one thing, original research should not go in the article. That means that even if we were all to agree that your counterexample was valid, without a reliable source it cannot go in the article. That has nothing to do with how notable you are, (or not), and my apologies for the sarcastic comment on those lines above. If there is no source to discuss, then this thread is in danger of breaking another rule (the one about not using talk pages as forums) and I suggest asking a question at the Reference Desk instead, or if you want to harass me in particular, on my talk page. But at the risk of breaking the rule myself, you have gone wrong at line 4. SpinningSpark 18:28, 21 May 2009 (UTC)

Message 1a betrays a logical fallacy in the "counter" example. It is not enough for General 1 to know that General 2 received Message 1a. More formally, knowing that General 2 received Message 1a does not imply that General 2 will attack. Without knowing that General 2 will attack, General 1 cannot decide to attack for fear of "disastrous failure". Therefore, General 1 cannot (correctly) initiate the protocol with Message 1a, and your entire "counter" example is moot. If this does not already convince you, consider the following contradiction within your own proposed protocol. Message 1b assures General 1 that Message 1a was received. Therefore, at this point in the protocol and according to his promise in Message 1a, he decides to attack. Deciding to attack implies that General 1 knows that General 2 has also decided to attack (it would be disastrous otherwise). However, General 2 is waiting for a confirmation of delivery of message 1b, and is clearly undecided, which is a contradiction. I could go on to further expose other issues I see with your "counter" example, but I hope I've already convinced you. SchighSchagh (talk) 06:38, 19 February 2011 (UTC)

Best Possible Solution?

Acknowledging that it is impossible to coordinate an attack with 100% accuracy and that apparently they will be stuck there forever, General A sends a messenger with instructions to count the paces it takes to cross the valley on a route through both friendly and enemy territory that takes an unknown number of paces but takes 30 minutes distance with a verbal message to General B that the attack will occur at a time 30 minutes before the total number of paces in minutes. If General A receives a message in 60 minutes from a messenger who only has instructions to describe the number of paces it took to reach him, he will know when to attack. If a confirmation reply is received in 60 minutes, the attack will commence. If no response is received in 60 minutes, a new message will be sent with instructions that the attack will occur 90 minutes before the total number of paces it takes to get there in minutes until a reply is received. This way, the time of the attack can not be known until the message is ready to be delivered, and the distance cannot be known by the enemy because part of the distance is over the hill. If the enemy attempts to check the number of paces it takes to cross the distance they would have no way of knowing the information they have is correct without ALSO facing the Two General's Problem or bringing the identity of the scout into play, and if that were allowed, then the same rules must apply to the messenger. If no message is received by General B, he will not attack or reply, if no message is received by General A, he will assume that no messages were received by General B and will not know the time of the attack and wont be killed in the failed attack, so it's a win-win situation for General A and gives some insurance. Is there a better solution?--Hoyt596 (talk) 06:32, 23 May 2011 (UTC)

Wow. Amazing. But you could've made your point more succintly by simply stating that you're an idiot. That way i wouldn't have had to read this drivel of yours and lose yet another bit of faith in Humanity. — Preceding unsigned comment added by 79.168.131.203 (talk) 18:10, 18 June 2011 (UTC)

Tampering

To expand on the thought problem, one might consider how the defenders could intercept the messenger(s) and tamper with the system. Sending back a false confirmation or changing the time for example to would result in the catastrophic outcome for the attackers. A man-in-the-middle attack basically. Depending on the scenario (siege, for example) the winning outcome could either be postponing the attack or destruction of 1 (or both) attacking armies. 74.37.238.57 (talk) 11:25, 25 August 2010 (UTC)

Man-in-the-middle exploits only work if nobody's aware of the man in the middle. In this scenario, the defender has no way of knowing if the messages are in some sort of code, intended for him to intercept in order to mislead him, or are not just garbage sent to confuse him. As a casual example, one general sends the message 'The enemy cannot be beaten. He has two great towers and 30 strong groups of men. We must retreat.' The defender passes this on. Both generals attack at 2:30 that afternoon.

The defender has the same problem the attackers do in that he is unable to authenticate anything completely. Herr Gruber (talk) 12:00, 9 March 2013 (UTC)

fireworks?

Maybe it isn't in the spirit of the problem, but why not just incorporate the use fireworks? Only the first message needs to be hidden. The enemy can see the confirmation message because they don't know what the confirmation means. —Preceding unsigned comment added by 80.203.36.250 (talk) 21:52, 13 September 2007 (UTC)

for the same reason that you can't just call in an artillery strike, because that isn't the point. —Preceding unsigned comment added by 129.46.148.92 (talk) 23:05, 13 September 2007 (UTC)

i think a smoke signal would work well also.

Or lighting up a big fire —Preceding unsigned comment added by 194.114.240.52 (talk) 08:23, 19 August 2008 (UTC)

The spirit of the problem is the entire point. The 2 Generals don't really exist, and they haven't been waiting to attack since 1975. If they had they could just use the many types of radio available to modern armed forces. It'd be a pretty useless General who couldn't think of signal fires for himself.

But in this hypothetical universe the communication can only be by messenger, which in real life represents a network cable or somesuch. It's a hypothetical universe where only the armies, the generals, and the town exist. It's a metaphor. It's meant to be easier to think about than talking about packets and Shannon's theory and things. Like all metaphors, if you don't stick to the point, it's meaningless. 188.29.165.177 (talk) 00:00, 6 February 2014 (UTC)

increased probability

Similar in vein to sending x number of messengers with the hope that one would get through - I believe the most ideal solution would be for the first general to send messengers at regular intervals (say one every five minutes) until the second general sends an acknowledgement back. The first general knows the second general has received his message when he gets the message back, and the second general knows the first general has received the acknowledgement when he stops getting messengers arriving with the original message. Of course, it could be possible for every messenger in one or both directions to be stopped at any stage, but there is no 100% foolproof solution, this is just a suggestion for the most efficient close approximation. 94.15.182.90 (talk) 16:31, 26 November 2013 (UTC)

Wouldn't work, cos when the second general receives no more messengers, he doesn't know if that's because the first has stopped sending them, or if they're all being killed. So he can't know if Gen 1 has received his acknowledgement. And without the acknowledgement, G1 doesn't know if G2 got the first message, and therefore won't attack. So G2 can't know if G1 is ready to attack or not. No insult, but I'd be surprised if a problem that the world's greatest mathematicians have decided is unsolvable, turned out to be solved by some guy on Wikipedia. 188.29.165.177 (talk) 00:30, 6 February 2014 (UTC)

Think of it in terms of email instead; in an exchange between two people, the last person who sent one cannot know if their mail has been received until they get a reply of some kind. Therefore, the confirmation simply switches who is uncertain about the receipt of their message over, endlessly.

The Two Generals' problem is generally about the impossibility of certainty in any imperfect method of communication; you could even apply it to not knowing if someone you're actually talking to heard the last thing you said without them replying, in which case they won't be sure you heard them, and so on. The example seems flawed simply because every method of communication available to humans is flawed in precisely the same way. Herr Gruber (talk) 15:23, 18 March 2014 (UTC)