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?
$\begingroup$
$\endgroup$
9
-
19$\begingroup$ Who told you humans ever agree on anything other than their disagreements? $\endgroup$– babouCommented Jun 7, 2015 at 22:11
-
7$\begingroup$ The "unsolvability" of the "two generals" 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" them. By the way, I have just answered another question which is closely related to yours. $\endgroup$– hengxinCommented Jun 8, 2015 at 2:19
-
5$\begingroup$ @babou Unfortunately, people (with the same priors) cannot even agree to disagree. $\endgroup$– hengxinCommented Jun 8, 2015 at 2:26
-
3$\begingroup$ Well, it's unsolvable in general. There's still plenty of cases when you can ignore the problems and get away with it - most of human communication relies on this. The major reason it's a significant problem in computer science is pretty much a reason of scale - in any system that already has to be distributed, you're probably getting these issues once in a while, possibly even daily or more. This is a big problem if you rely heavily on correctness, with no self-correcting mechanisms. A closer human analogue is Chinese whispers / telephone - a distributed system without error correction. $\endgroup$– LuaanCommented Jun 8, 2015 at 13:28
-
2$\begingroup$ @AlecTeal I don't know where sure certainty to know about how a good Computer Science question looks like comes from, but in any case: please be nice. Abusing others will not be tolerated here. (removing the not-so-nice parts of your comment) $\endgroup$– RaphaelCommented Jun 9, 2015 at 9:19
|
Show 4 more comments
7 Answers
$\begingroup$
$\endgroup$
5
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.
-
3$\begingroup$ Malice is significant in the practical sense because it limits the degree of certainty that can be achieved. If one assumes interference is the result of random chance factors rather than malevolence, then for any probability p > 0, one may design a protocol such that the probability of erroneous "consensus" will be less than p and the probability of successful consensus will be greater than 1-p. Against an adversary who is malevolent and omniscient, however, such algorithms may be unable to accomplish much. $\endgroup$– supercatCommented Jun 8, 2015 at 15:12
-
3$\begingroup$ @supercat: OK. But my point is just that the two generals problem which concerns the questioner, remains a problem when malice is excluded: the impossibility is a consequence of error, not malice. I would say that ideally the problem should be framed such that the missing messages need not be the consequence of enemy action, we just know that some messages go astray. The Byzantine generals problem explicitly introduces opposing players, though. $\endgroup$ Commented Jun 8, 2015 at 15:19
-
1$\begingroup$ So the two generals should first agree to have coffee together. Then they can plan the battle face-to-face, which gives them a reliable channel! $\endgroup$ Commented Jun 9, 2015 at 12:45
-
2$\begingroup$ @DavidRicherby: indeed, this works extremely well in theatres of war that are well-appointed with coffee shops. Computer scientists very rarely encounter any other terrain, so the real generals are pretty much on their own as far as CS theory is concerned. And existentialist generals have no reliable channel even face-to-face, so they never attack anyone because they can't be sure their allies exist, let alone the enemy. $\endgroup$ Commented Jun 9, 2015 at 12:49
-
$\begingroup$ Since its computer science and you can guess at the channel capacity this answer might be better if it linked to and discussed Shannon's theorem : en.wikipedia.org/wiki/Noisy-channel_coding_theorem $\endgroup$– danielCommented Apr 24, 2017 at 11:33
$\begingroup$
$\endgroup$
3
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.
answered Jun 8, 2015 at 1:00
-
8$\begingroup$ AFAIK, the two generals problem doesn't require a malicious communications channel, just an unreliable one. The concern isn't with messages being corrupted or modified; only with them not being received: en.wikipedia.org/wiki/… $\endgroup$– Ajedi32Commented Jun 8, 2015 at 14:13
-
1$\begingroup$ @Ajedi32, I should make it clearer what I mean - the metaphorical set up has a malicious enemy, the messengers aren't just wandering off, but what this would most immediately equate to is loss of entire messages with no probability model. Given that we don't send messages as atomic entities, the "loss of a message" can be interpreted as loss of bits, loss of packets, etc. The other half is that communication channels have analyzable properties - they may have random noise, but it's in a model-able fashion, which we can provably cope with, then the only other source of loss of information is... $\endgroup$ Commented Jun 9, 2015 at 1:23
-
$\begingroup$ ...actual malicious behaviour, which we can also make noticable. In short the two generals problem gives a hypothetical situation which is unrealistic in its assumptions. Yes would could lose information somewhere, but there isn't (in everyday sensible situations) limitless error. $\endgroup$ Commented Jun 9, 2015 at 1:26
$\begingroup$
$\endgroup$
1
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.)
-
2$\begingroup$ If you look at modern communication, especially in war, great care is taken to pick strategies which do not depend on such problems. When they do depend on such problems, there is almost always some contingency plan in place to deal with it. In the computer science program, we put all of our eggs in one basket, and declare "any one potential failure, no matter how improbable, is too much" $\endgroup$ Commented Jun 8, 2015 at 5:04
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
You can never go from an uncertainty to a certainty. The two generals problem is one where the only action that can be taken (sending a message) is an uncertain one.
If we changed the problems to have certainties then it's solvable. Like if general A had a portal that with 100% certainty a messenger can walk through and be right next to general B instantly. In this scenario, general A sends exactly one message and then rides out to battle at the specified time. No further message sending is required by either of them.
If you're standing right next to another human it's just the simple equivalent of having the portal.
$\begingroup$
$\endgroup$
5
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.
-
2$\begingroup$ Welcome! We're looking for answers that contain some detail and explanation, rather than just brief comments. The idea in your comment has already been discussed in some detail in the existing answers to the question so I don't think you're adding anything at all, here. $\endgroup$ Commented Oct 6, 2015 at 11:39
-
$\begingroup$ My comment is succinct and to the point. The question paraphrased was how do humans agree on anything if we know a problem is unsolvable? My answer is from maths (specifically pi in decimal) that we round off and approximate. $\endgroup$– RajuKCommented Oct 7, 2015 at 2:14
-
$\begingroup$ Your comment is just that: a comment. When you have enough reputation, you'll be able to post comments. Until then, you can only post answers and answers are expected to be more detailed than this, as I already explained. $\endgroup$ Commented Oct 7, 2015 at 6:46
-
$\begingroup$ The question as such is not a comp science question, but a question about human behavior. Hence my answer was to the point. Why was the question not tagged as a non-computer science question and rejected? $\endgroup$– RajuKCommented Oct 8, 2015 at 10:39
-
$\begingroup$ If you believe the question is off-topic, you should flag it and not answer it. Please also note that Stack Exchange sites (even comments on them) are not intended to be discussion boards. $\endgroup$ Commented Oct 8, 2015 at 10:42
$\begingroup$
$\endgroup$
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.
