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)

One solution

One solution I found out, which is actually used today by many alarm transmitters and safety systems. To use the generals metaphor, we will still talk about attacking:

Define a action X that will happen. Lets say "Attack the city"

Decide the precision of the action, such as how accurate the action must be performed to be successful. Say we need to be accurate within 30 minutes, which means that if general A army attack 2:30 and general B army attack 3:00 or 2:00 it will be successful, but more dispersion, eg 1:59 or 3:01 for army B = unsuccessful attack. That's "precision = 30"

Decide a number of messages that should be safety-sent to avoid a unnecessary attack because one messenger tripped and fell down a chasm or something. Lets say "safety = 3"

Now decide a interval such as ([safety]x[interval])+[transmission time] less than [precision] AND [interval] must be larger than 2x[transmission time] + a safety margin if a message just arrives late. In this example, lets say transmission time = 3 min, so we select interval = 8 minutes.

The simplest rule here is that the general A is transmitter and transmits with interval times, the B just replies immediately. If a general does not see a message in [interval] time, he should just retransmit is last message.

Each message must have a counter that is increased unless the message is a resent message. Eg, if you waited [interval] time without hearing from the other general, resend the same message you just sent. Else you increase the counter and send a new message. Each message should also contain a unique counter so late message can be separated from recent resends, since late messages should be ignored aswell. But the attacker delaying a messenger should be kept out of scope here.

If a party received a message with a counter value of X, and receives another message with same or lower counter value, it should not update its "last message received" value. When its time to attack, the parties simply cease communication.

Now its just for the generals to start communicate.

Lets take a example: (first is always transmission time - pay attention to this, second is transmitter, third is receive time. fourth is if message arrived, five is message counter)

First is a example of a single capture/failure that should not lead to a attack.

T+00 A T+03 Y 1

T+03 B T+06 Y 2

T+08 A T+11 Y 3

T+11 B T+14 Y 4

T+16 A T+NN N 5 (single lost message)

T+19 B T+22 Y 4 (A will ignore this message since it bears a counter value already used)

T+24 A T+27 Y 5 (no attack since B did get all messages within precision)

T+27 B T+30 Y 6 (No attack since A did get all messages within precision).

Second is a example of a malicious attacker who decides to capture all messengers in a specific direction, namely from A to B:

T+00 A T+03 Y 1

T+03 B T+06 Y 2

T+08 A T+11 Y 3 **LA**

T+11 B T+14 Y 4 **LB** (Last message to B: T+11. Last message to A: T+14)

T+16 A T+NN N 5(Capture start here)

T+19 B T+22 Y 4 (A will ignore this message since it bears the same counter value as his received)

T+24 A T+NN N 5

T+27 B T+30 Y 4 (A will ignore this message since it bears the same counter value as his received)

T+32 A T+NN N 5

T+35 B T+38 Y 4 (A will ignore this message since it bears the same counter value as his received)

T+40 A T+NN N 5

T+41: B start attacking the city. (reason: Latest valid message with a unused counter was received T+11 at **LA**)

T+44: A start attacking the city. (reason: Latest valid message with a unused counter was received T+14 at **LB**)

Same applies in the other direction, but the its the general B that will send repeating messages with the same number. In this case, the general A will start attacking, and then B will start attacking 8 minutes later.

Capture of all messengers or the generals decides start attacking (and thus cease communication), will lead to the same fate for the city.

Basically, this messaging system works by a "Don't attack" messages being send regularly until its time to attack.

As I said, this is used by many alarm systems to prevent burglars from cutting the wire or jamming the wireless signal. Simple, the detectors or alarm panels send a "OK" signal. Lack of "OK" signal indicates tamper, which in some systems are same as "alarm".

• NOTE* This messaging system can only be used to reliable transmit a binary signal (1 or 0) per channel, in addition to transmitting unreliable messages.

The binary signal is such that the action taken out when this binary signal triggers, is a action that would be best for the parties to carry out, or worst for a attacker attempting to hinder communication between the parties is. Think it of a carrier wave in a analog system. The carrier wave tells there is a signal present, and the receiver can carry out a specific action (silencing a speaker or something) when the carrier signal is not there.

Sebastiannielsen (talk) 18:14, 5 November 2014 (UTC)

That's fail-deadly design, it's also a keystone of nuclear deterrence ("if you cannot radio the President or anyone else, your submarine is to kill everyone"). The trouble with this is that the "catastrophic loss if both generals do not attack together" in the Two Generals setup is the equivalent of "if the alarm is tripped but there is no burglar, your house is automatically burgled." This does not tend to be a problem in the construction of actual burglar alarms. Herr Gruber (talk) 09:03, 28 December 2014 (UTC)

Actually, the catastrophic loss is prevented by executing the protocol in dual-direction. Most alarm transmitters do execute the protocol in one-direction only, same with submarines (if you cannot radio the president, fire the nuclear bomb). But in this case, you send a confirmation message for each valid transmit, so even if only 1 direction of the communication is severed, the "carrier wave" is severed in both directions, causing the both generals to attack at the same time.

There is actually alarm transmitters that DO execute the protocol in dual direction, and will sound the siren in addition to summoning guard/cop response if the communication line between the guard company and the alarm panel is severed.

It does not need to be fail-deadly design, the important thing is that the action carried out is the best in a given situation. Lets say the signal is to keep a emergency door locked, then you program the signal to actually open the door if the emergency door loses contact with its controller. Another example is a radio controlled flight machine that safely lands if it loses dual-direction communication with the operator. But in the war case, you have malicious entities that might capture the messenger, thus your default must be "attack the city" if no communication. The cease of the signal is the signal to attack.

The important thing here is the precision. If its important that both general attack the city the exact same second, then you must send messengers like each 1/3 to get a enough fail-safe system. But wars are not that precise, in most cases it does not matter if they arrive with a devitation of ~10 minutes, thus theres room to wait for responses.

Sebastiannielsen (talk) 20:13, 21 March 2015 (UTC)

The problem here is that the start point occurs with no authentication: in other words, with the communication line not transmitting. You're trying to establish a communication line between the alarm sensor and the control box because you've suddenly found yourself in a position where you need it switched on; one of you is at the sensor, one is at the control box, neither of you know how the alarm works, and you can't communicate using anything other than the alarm itself; there's a light you can flash at each end, but you don't know if it's flashing because of the other person, because of someone else entirely, or just at random, and you don't know if every flash you send is received. You have agreed to turn the alarm on, but you have not agreed how you will determine it actually is on at both ends, or is even functioning at all. If you stop and the alarm is not on, magic burglars will appear and rob you, and you will both be held responsible.

Your example would require the two generals have an unbroken stream of messengers you know to be authentic already in existence to be the equivalent of the unbroken signal and an existing plan of attack if the line is broken: of course it's easy to solve then, because you've already solved it before you started. In this scenario you are trying to create the protocol in question using an initially unreliable line of communication; you can't start out with a set of rules already established for the scenario (otherwise the easiest solution would be for the two generals to have an existing contingency plan for being separated, which would require no messengers at all). As a result every message you receive may be false, including the first one.

Like I said, this is just a fact of any imprecise means of communication, including speaking face to face; you cannot absolutely confirm the person you are talking to has heard you unless they acknowledge it, in which case they do not know if you heard them, and so on. If both speakers believe they will die if they do not confirm what the other said, they will be confirming back and forth forever since neither could be sufficiently sure that they would want to be the one to cease communication. Herr Gruber (talk) 10:07, 5 April 2015 (UTC)

Apostrophe

The name of this page and problem, to my mind, should have no apostrophe. Yes the problem certainly is a problem for the Generals and it's their problem, but the name of the problem they are having is the "Two Generals Problem".

Does anyone have a citation which can settle this? Quirkie (talk) 18:45, 24 April 2008 (UTC)

It is a problem that 2 Generals have. It is their problem. It belongs to them both. Two Generals' Problem. You could also phrase it as "the problem of 2 Generals", but that's just the same thing with the words moved round. "The problem that 2 Generals had" would imply 2 real Generals. It's fine as it is, it works, it's OK. You could pick nits in either direction, but the current way is valid. It's only an apostrophe. 188.29.165.189 (talk) 21:58, 23 March 2014 (UTC)

Well, you could also see it as "the problem involving two generals" without the apostrophe. After all, the two generals in the problem aren't real and so can't possess anything. Herr Gruber (talk) 20:35, 1 May 2015 (UTC)

Purported solution (wrong)

This thought experiment is solved here: http://www.reddit.com/r/wikipedia/comments/am11y/the_two_generals_problem_is_a_thought_experiment/c0iaqag —Preceding unsigned comment added by 24.62.203.6 (talk) 12:32, 6 January 2010 (UTC)

That solution should work, provided an infinite amount of time and messengers is allowed. Of course, so long as there is a finite probability of capture, and a finite number of messengers there will always be a finite chance that all will be intercepted. In this sense, the fact that the solution is unsolvable is trivial. 150.203.179.56 (talk) 07:07, 9 June 2015 (UTC)

Is this really unsolvable? Elsewhere, this paper is cited as proof that the Byzantine Generals Problem has been solved. I won't edit the actual page until others chime in. — Preceding unsigned comment added by 68.105.115.235 (talk) 23:31, 28 July 2016 (UTC)

Proof section

I fixed the proof to cover a more general case. Obviously, since real-world protocols can be nondeterministic and variable length, the more general proof is needed — I find it surprising that most of the references you see about this problem don't mention this at all. --DavidHopwood 16:15, 31 August 2007 (UTC)

I feel that the second half of the [deterministic, fixed-length] proof section is not a very good explanation. -- isionous 09:16, 9 December 2006 (UTC)

Any concrete suggestion for how to improve it? --DavidHopwood 04:26, 15 November 2007 (UTC)

I am not familiar with the practices on cited proofs vs. original research in this kind of Wikipedia articles. Nevertheless, there is no citation in the proof section so I am not sure how closely it follows the original article. Because of this, the suggestion here may be on either the proof writing on the page (in which case I am suggesting modifications) or comment to the original article (in which case no modifications should be done, but I would like to hear your comments).

The current deterministic proof essentially starts with "suppose there is a sequence of a fixed number of messages, one or more successfully delivered and one or more not." Next we go on with "Consider the last such message that was successfully delivered. If that last message had not been successfully delivered, then one general at least (presumably the receiver) would decide not to attack."

I do not think this is true, it could very well be the case that both generals are already convinced and we are doing redundant messaging. We could counter this argument by following text format:

"suppose there is a sequence of a fixed number of messages, one or more successfully delivered and one or more not. Now we can find a corresponding sequence with similar features but also with minimal amount of delivered messages. That is because if a sequence is not minimal, you can get one by changing one or more delivered messages to undelivered ones. The assumption is that there should be a shared certainty for both generals to attack.

Consider the last message of the sequence that was successfully delivered. If that last message had not been successfully delivered, from the viewpoint of the sender, the sequence of messages sent and delivered is exactly the same as it would have been. Since the protocol is deterministic, the general sending that last message will still decide to attack. Otherwise the sequence would not be minimal. On the other hand, the other general will not attack, otherwise the sequence would, again, not be minimal.

We've now created a situation where the suggested protocol leads one general to attack and the other not to attack - contradicting the assumption that the protocol was a solution to the problem."

Or am I understanding something wrong? --Misna (talk) 11:21, 3 July 2016 (UTC)

No you're completely correct.

Here's the original statement and proof (from the appendix of Some constraints and trade-offs in the design of network communications):

Note that the needs of both parties are quite reasonable. They simply want to reach a state where
(1) The original message (i.e., the plan of action) is successfully delivered, and
(2) Both parties know that they are in mutual agreement that (i) occurred.
Fact The sequence cannot terminate successfully.
Proof
(a) Clearly the sequence contains at least one message of importance.
(b) Assume that it is possible to reach the desired state after a finite sequence of messages. Then there must exist a number n > 1 such that n is the length of the shortest sequence which gets us to this state. Since this is the shortest sequence, the last message in it is important: if the n'th message gets lost, the desired state cannot be reached. The sender of the n'th message must receive acknowledgment.
This means that the sequence is at least of length n + 1. The assumption is contradicted and the sequence cannot be finite.
Note also that the sequence is infinite even when none of the messages are actually lost.

Notice the explicit use of the shortest sequence of messages, as in your suggested correction.

Daira Hopwood ⚥ (talk) 12:28, 17 November 2017 (UTC)

I do not understand why the citation is needed - this is just a proof. Even if you have a determined list of confirmations needed, you can never be sure that the last message has been received. The person who is not sure the message is received is the sender - the person who might not attack in the eyes of the sender is the intended receiver. If this last message is not delivered (and you cannot be sure it was delivered), this would cause the receiver to not attack, and the sender to attack, leading to the attack failing. Is the proof provided not clear enough? is that the issue at hand?

Emperorhaplo (talk) 22:21, 17 December 2017 (UTC)

I came here because I'm struggling to understand why a logical proof has a [citation required] in the middle of it? The statement is logically valid and doesn't appear to require further evidence. [NB: It may be the whole section that needs citation, I offer no opinion there - but the specific placement is definitely wrong]

BFT and Level of knowledge

However it's true that both generals will never have ssame knowlege it is not true, that they cannot establish common time of attack and be sure that other will do the same.

Let's consider two actors and message flow

A -> B MSG B -> A ACK A -> B ACK2 B -> A ACK3 A -> B ACK4 B -> A ACK5 A KNOWS that ACK4 WAS successfully delivered and therefore that B is certain that A knows about succesful delivery of ACK2 A -> B ACK6 B KNOWS that ACK5 WAS successfully delivered and therefore that A is Certain About sucesful delivery of ACK2

In other words, If any side Send or recieves ACK6 they can proceed on knowledge in MSG

So they can reach consensus. The trick is that there is bigger than zero probability that it will never happend and they will not attack.

But they can be certain that if they attack they will be successful — Preceding unsigned comment added by 2A02:A318:8263:D980:151:590D:2E2D:E08C (talk) 09:01, 11 December 2018 (UTC)

How do they know that ACK6 was received ShiberToast (talk) 06:44, 12 February 2020 (UTC)

Grammatical Error in Title

The following discussion is closed. Please do not modify it. Subsequent comments should be made on the appropriate discussion page. No further edits should be made to this discussion.

---

In the title, the apostrophe in the word generals' should be between the l and s, not after the s. I moved the article to Two General's Problem ,someone reverted the move and called the reason not a good reason, so can we reach a consensus here about whether the page should be moved? ShiberToast (talk) 17:23, 11 February 2020 (UTC)

The title should probably be "Two Generals Problem", with no apostrophe, because it's a problem involving two generals. It could conceivably be "Two Generals' Problem" because it's a problem that the two generals collectively have. But an apostrophe between l and s doesn't make sense -- "general's problem" would be a problem belonging to one general, and there are two of them. 195.219.22.180 (talk) 11:58, 12 February 2020 (UTC)

@ShiberToast: Please stop warring over this. You are wrong. The long-standing title is grammatically correct.

The "problem" is "possessed" by "two generals". Therefpre the possessive plural applies. This means the apostrophe goes after the "s", not before (that would be a problem belonging to "one general")

It should not, either be unapostrophised. ——SN54129 12:23, 12 February 2020 (UTC)

You've written a very forceful reply, @Serial Number 54129:. I can't see that ShiberToast was warring over anything, just correcting bad grammar that the site should not promote to readers. The correct English is Two Generals' Problem. Please have a read up on grammar if you disagree. When this title is corrected, I hope you will not just war in disagreement.ToaneeM (talk) 13:02, 12 February 2020 (UTC)

@ToaneeM: I now feel like being even more forceful  :) the reason the title is currently correct is because I keep having to correct it. What you say is true: Two Generals' Problem is correct. But ShiberToast has now moved the page to the incorrect Two General's Problem twice ([1],[2]). ——SN54129 13:06, 12 February 2020 (UTC)

Ah, I've got the editors and the suggestions mixed up and backed the wrong horse - sincere apologies, @Serial Number 54129: :-) You are indeed the correct one, the title is correct again and I hope @ShiberToast: can have a read up on this grammar and see that it's correct. Thanks.ToaneeM (talk) 13:47, 12 February 2020 (UTC) (written earlier, failed to save)

At a pinch "Two Generals problem" without a possessive apostrophe would be all right. The existing, and grammatically correct "Generals'" is better. The illiterate "Two General's" would be idiotic. Tim riley talk 13:14, 12 February 2020 (UTC)

Conclusion: I am an idiot that forgot how plurals work, dismissed ShiberToast (talk) 17:47, 12 February 2020 (UTC)

The discussion above is closed. Please do not modify it. Subsequent comments should be made on the appropriate discussion page. No further edits should be made to this discussion.

(edit conflict) Don't torture yourself, ShiberToast, that's our job.;)

There's a fascinating lack of agreement in the literature about whether or not to apostrophize. This respectable book, for instance, omits it. A conflict-avoiding solution would be to rename the article Coordinated attack problem. Who am I kidding? That's not how Wikipedia works. Favonian (talk) 17:56, 12 February 2020 (UTC)