If the two generals problem is unsolvable how can we human beings agree on things?
I mean, we communicate everyday and have the same limitations as any communication problem handled by computer science. Why doesn't it affect us?
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
I disagree with other answers that the communication channel needs to be modelled differently. Malice is irrelevant, simple lost messages with any non-zero probability are sufficient to create the two generals problem. e-mail and IM, for example, have a low but not zero chance of dropping messages. Phone calls can suffer interference, so as with the two generals problem you need to somehow confirm whether the other person heard what you said, ad infinitum. And yet I frequently use these channels to make agreements with other people.
What the insoluble "two generals" problem fails to solve, is to get guaranteed common knowledge. In real life we don't require formal common knowledge in order to proceed. Therefore the goal in most practical situations needs to be described differently from the goal in the two generals problem.
We settle for agreement being "sufficiently likely". I might not be willing to attack unless I'm certain you will attack, but I'm willing to walk to the coffee shop to meet you provided that the probability of a communications failure isn't grossly higher than the probability of you failing to arrive due to traffic. Unlike the generals, I'll take a chance on you meeting me.
If you've ever had someone explain something three times to you in different ways when you got it the first time, or ever had someone ask you to confirm something that you've already confirmed twice, then it's because you reached your threshold of "sufficiently likely" before they reached theirs.
Take your pick of psychology, philosophy, or evolutionary biology as the correct realm in which to look for an answer to the next question, why we don't really need a full guarantee of common knowledge :-)
It also relates back to practical problems in computing. For example when we use a single-error-correcting code to "validate" that a symbol in a message has arrived correctly, all we're doing is accepting that the probability of a double-error is negligible for the time being. Then later in the protocol we might have a CRC, to further reduce the probability of undetected error. None of this solves the two generals problem, but it is sufficient for me, my bank and a merchant all to "agree" that a credit card transaction has occurred, with a small probability that we disagree.
Central (pun intended) to the Two Generals problem is a malicious enemy in between. Although this models an unreliable channel, it models it in a way that we normally don't encounter. In the problem, the messages may pass through enemy hands and there's no time constraints, verification, encryption or anything else I haven't thought of.
When we communicate in practice, firstly the channels we use are not expected to be unreliable in this manner. Channels can be noisy, sure, but that's different to being malicious. The probability that a channel that is noisy at the bit level can randomly produced not only a valid message that satisfies whatever error correcting code we're using, but is also valid in that it makes sense to the receiver is very low. We can also use things like public key cryptography to encrypt and/or sign messages, making it harder again to fake a real message. Thirdly a significant chunk of our communication is time sensitive - we actually talk to people so there's no delay in response, in which case we will have to be satisfied that the person we're talking to is the person we're meant to be talking to.
In the majority of cases, we just assume that there's no significant source of error in the messages, and we get away with it. We can imagine a scenario where there really is a malicious man-in-the-middle corrupting the channel, but we come across a couple of things; the public key crypto is still effective, but more importantly the effort and power needed to accurately corrupt a significant enough portion of communication is far beyond what is feasible. If it were not, military signals intelligence would be far more effective than it is (not that it's not effective, it would just be better).
Note that although I have touched on computer/machine mediated communication mostly, the same arguments can be made for interpersonal communication - the sources of noise can't typically fake an entire message, we have correction systems for those that introduce random, low-level noise, and the effort is just not worth it in almost every case for there to be a sufficiently resourced and motivated malicious attacker.
The "unsolvability" of the "Two Generals" problem (or called "Coordinated Attack" problem) is restricted to its context, i.e., in a totally asynchronous distributed system with unreliable, untrusted communication channels. In our daily life, people can "tolerate" such bad situations.
In the book Reasoning about Knowledge; Section 6.1, the authors comment that
The fact that coordinated attack implies common knowledge depends on our requirement that the coordinated attack must be simultaneous. In practice, simultaneity might be too strong a requirement. A protocol that guarantees that the generals attack within a short time of each other may be quite satisfactory.
He further comments that
Nevertheless, even such weaker forms of coordination are unattainable if communication is unreliable.
In our daily life, people can tolerate (and are tolerating) short delays and unreliable channels (as elaborated by @Luke Mathieson). (If you go deeper and ask "how" and "why", then it is probably out of the scope of computer science.)
Because we don't need guaranteed assurance that something will happen when we have sufficient experience that tells us what is likely to happen. For example, let's say that a friend wants to meet up with me. He emails me the time and place, and I respond back with "Sounds great, see you then." I don't need any more information to proceed with meeting him at the specified place and time. Just because I couldn't guarantee that he got my response isn't enough to sway me from acting on my assumptions. My experience tells me that email is fairly reliable, and that if for some reason he didn't get my response, he'll email me again. My experience tells me not to worry about the corner case of my response being silently discarded, and all followup messages from him also being silently discarded. That combination of events just doesn't happen often enough to significantly interfere with my ability to meet people.
If those corner cases (or other issues) did start to happen more often, that would change my experience, and then I'd consider changing my strategy. For example, I might call the person instead of emailing them. Or I might use a calendar website. Or some other option.
As applied to interpersonal communication, I find that the technical issues of the two-generals problem aren't hugely problematic on their own, but can magnify other problems. If I email someone a work request and I don't get a response from them in a reasonable amount of time, what do I do? How long should I hold off before sending a followup message? If I do send a followup message, will they see it as a friendly reminder, or are they going to feel irritated? How should I word the followup message so as not to come across as too presumptuous (because if the network actually dropped the previous message, then this is the first they're hearing from me)?
The nature of these questions all depends on the people and the context involved. There are no guaranteed answers. But again, we don't need guarantees to be successful. All we need are things like introspection, empathy, and the ability to learn from experience. We can discover and develop our own unique strategies -- which may well differ from others -- that enable us to become better communicators over time.
Can you give me the exact value of pi in decimal notation? We humans round-off and approximate when we know the exact value is unsolvable.
The proof only says that it is impossible to design a protocol that reliably solves the problem (i.e. perfectly in every instance).
It doesn't say it is impossible to design a protocol that mostly solves the problem. Humans, being bayesian in nature, are quite good at designing protocols that solve a given problem with some degree of quality and/or some degree of success that is satisfactory in terms of gains and losses in the long run.