5 ms·
This is probably naive but if we already know Alice and Bob will win by both retreating, can't we simply say that if there is no acknowledgement by a pre agreed
by mcny 8y ago
This is probably naive but if we already know Alice and Bob will win by both retreating, can't we simply say that if there is no acknowledgement by a pre agreed timeout, it means we both retreat?
- _nalply 8y agoThe crux lies in the word «pre agreed» since this involves communication.
- oh_sigh 8y agoAny symbolic communication required pre-agreement as well(that is, Alice sending her intent in Chinese won't matter if Bob only speaks Swahili)
- nannal 8y agoI think the real crux of the issue was the pre-agreement to use the enemy generals postal system as a means of distributing vital information.
- IggleSniggle 8y agoThe way I first heard this problem, the messages are sent via carrier pidgeon over Eve’s army, and sometimes enemy soldiers shoot down the pigeons.
- foota 8y agoYou can "fix" this loophole by adding a criteria that you eventually capture the city.
- another-one-off 8y agoSo, always attack? But if we don't know that the other army is in position, and if Eve burns every message, then the problem is clearly unsolvable.
- Fnoord 8y agoYes, either start with always attack, or always retreat. Another (practical) solution could be to spoof a message, making it appear as if from Eve. Some kind of steganography might work as well (or alternative forms of communication such as pigeons or smoke signals). And if all communications between Alice and Bob is discarded, this would worry either one of them to send a personal messenger who is human. This person could be captured and tortured, sure. But if they get "burned" as well, that'd be an act of war. Plus, if they are able to predetermine that if they don't hear from each other after X time, they attack after X + Y time (e.g. 3 months and 1 month [to prepare]) then the problem can be solved. If they cannot create a clear way of predetermined action based on actions then they'll always retreat. Actually now that I gave it some further thought this "two general problem" can be observed in the cold war as well via (the nuclear threat of both parties). The nuclear threat from both sides created an equilibrium akin to what could happen in the described situation.
- cyphar 8y agoThe point of the Two Generals problem is that it's impossible to solve. No matter how many acknowledgements you send or receive over a lossy medium you can never be sure that both parties will agree on whether to attack. It's a fairly infamous restriction on distributed system design. Working distributed systems have to work around this (and other) restrictions that are implicit to the properties of a distributed system. So TCP still works perfectly fine even though a perfect version of TCP (that didn't have timeouts) would be mathematically impossible to implement.
- ikeboy 8y agoOk. Say timeout is one hour. Alice sends message to Bob saying attack. Bob acknowledges, Alice receives message at T+:10 minutes. Alice acknowledges, but Eve drops Alice's acknowledgement. Now, as far as Alice is concerned, both Alice and Bob acknowledged. However, Bob never got Alice's acknowledgement, so he won't attack.