2 ms·
(Note: this is based on the informal description of the problem in the article and on Wikipedia, not the formal model given in the article) What is consensus [
by tzs 8y ago
(Note: this is based on the informal description of the problem in the article and on Wikipedia, not the formal model given in the article)
What is consensus [1]?
As oh_sign noted in an earlier comment here, if Eve blocks all messages there is obviously no way to achieve consensus, so if there are no constraints on Eve's ability to interfere this is a trivial problem, so I'm going to assume that Eve is not able to block everything.
Suppose each general does this:
1. Generate a random 128 bit integer, P.
2. Decide the action they are going to take, A (attack or retreat).
3. Repeatedly send the message: "I will do A with priority P". (To be clear, P is only generated once. That single P is used in all messages).
4. They take action A unless they receive a message from the other general that states a different action, A', AND the other general's message has a lower P. In that case, they take action A'.
Without loss of generality, assume Alice has the lower P.
With the above procedure, as long as a single message from Alice to Bob makes it through, the generals will take the same action, which will be the action Alice picked.
Although they take the same action, only Bob knows that they are going to do so. He knows this because since a message from Alice got through to him, he knows she has a lower P so will stick with her original action regardless of whether or not his messages got through, and he will match her action because he knows she has a lower P.
Is that consensus, or to count as consensus do they both have to know before they act that they will be taking the same action?
Let's say that they do both have to know. Modify the above procedure so that if a general finds out they have the higher P, they change the message they are repeatedly sending to "I will do action A', following your lead", where A' is the action from the other general's message.
With this modified procedure, if Eve lets one message through from Alice, and after that lets one message through from Bob, then (1) the two generals take the same action, (2) Bob knows they will be taking the same action, and (3) Alice knows they will be taking the same action.
Is that now consensus? They are taking the same action and they both know they are doing so. Furthermore Alice knows that Bob knows. Bob, however, does not know that Alice knows. Do we need not only agreement, but each knowing that there is agreement, and knowing that they each know, and knowing that they each know that they each know, ad infinitum?
[1] Are consensus problems usually stated in terms of agreements between generals because the definition of consensus is literally, at least in Oxford, "A general agreement"?
- zzzcpan 8y ago> They take action A unless they receive a message from the other general The missing piece in your algorithm is how long do they wait to receive a message from each other and how they can know that it's long enough? If they don't wait long enough they will not receive a message and will make wrong assumptions about the other general, will not reach consensus and will take each their own action. To fix this each has to wait as long as it takes to receive a message from the other general and know about this (which in itself requires more messages). But what if one of the generals dies in the meantime and stops sending messages? Or what if both Bob and Alice got the same random integer? There are other issues too. But the important thing is it's all about time. You can always wait out uncertainty, but of course you won't be able to make progress waiting.
- y4mi 8y ago> I'm going to assume that Eve is not able to block everything. This problem keeps coming up in distributes systems and sadly, a full breakdown of internal communication is also possible. I.e. internet routing works, switch for lan/cluster communication broke.
- Veedrac 8y agoIf you know that at least one message from Alice goes through, and Alice says "do this with priority 0", then yes, you can solve the problem. The issue here is different to what you are modelling; imagine this payoff table for A B attacks B holds A attacks +1 -∞ A holds 0 0 The question is, knowing nothing about the reliability of the connection, is possible to have a strategy that has a positive expectation? B is only going to attack if they are absolutely certain you will, and vice-versa. The issue with your strategy is that even if Eve never interfered with the connection once, Alice does not know that, so will hold.