8 ms·
Two Generals and Time Machines
- oh_sigh 8y agoA much easier but pathological proof is simply that Eve burns all messages and therefore Alice and Bob can never communicate a single bit to each other.
- mcny 8y agoThis 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.
- Veedrac 8y agoYou misunderstand the Two Generals problem, which is that regardless of how many messages Eve burns, the two generals can never be certain of shared knowledge.
- malisper 8y agoNormally in the two generals problem you assume that if you send a message repeatedly for an indefinite amount of time it will eventually be delivered. This assumption makes the problem the author described possible, but the actual two generals problem is still impossible. See my explanation here: https://news.ycombinator.com/item?id=17536337 https://news.ycombinator.com/item?id=17536337
- xchaotic 8y agoFor such generic statement of the problem, it's certainly unsolvable. But with encryption, timeouts and defaults it can be - as seen by many the distributed systems on the Internet
- craigsmansion 8y ago> with encryption. That has been accounted for. " [Eve] does not, however, get to open the enveloped message." > timeouts and defaults it can be These time-outs and defaults would have to be negotiated between the generals over the postal system and wouldn't help them. > as seen by many the distributed systems on the Internet Those would have implemented a form of fault-tolerance for the more general "Byzantine Generals Problem."
- quikoa 8y agoTimeouts and defaults can be considered as part of the algorithm. The problem is that you may be unable to determine a reasonable timeout beforehand. The timeout as a practical solution is also described under 'engineering approaches': https://en.wikipedia.org/wiki/Two_Generals'_Problem#Engineering_approaches https://en.wikipedia.org/wiki/Two_Generals'_Problem#Engineer...
- ColinWright 8y agoI cannot reconcile your claim with my understanding of the formal proof. We are asking for a guaranteed consensus, perhaps you are merely asking for arbitrarily high probability of consensus. Can you point me at an algorithm that guarantees consensus? Your claim seems to be at odds with the formal proof in the article. I particular, the article already allows for encryption, timeouts, and defaults. So I can't see how you are right, and would appreciate some additional information as to why you think the article is wrong.
- tonyg 8y agoThe whole point of the problem is that you're not allowed to use timeouts and stuff to get a work around. Adding timeouts etc fundamentally changes the situation. The distributed systems on the Internet you see do not solve the problem - they work around it, basically by adding failure modes not present in the original.
- 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
- pron 8y agoI see this annoying mistake everywhere, but it's important to point out in the context of computer science (more so than in mathematics) because it relates to one of its core components: in the context of logic and proofs, "formal" does not mean precise or mathematical (and certainly not official), but rather mechanical. A formal description is one with a precise syntax and semantics, whose truth can (at least in principle) be judged directly from its form. A formal proof is one carried out through pure syntactic (i.e., formal, in the sense of "pertaining to form") manipulation, and does not rely on any informal arguments, namely ones that do not appear in the form. As a rule of thumb, if you could replace the word "formal" with "mechanical" and your sentence would still be true, then you can use the word formal (this is the case, say, with formal software verification, which is simply mechanical software verification, or formal proofs in a proof assistant, that are mechanical proofs). So, a formal description is one that could be directly mechanically interpreted by a simple computer program as written, and a formal proof is one that could be mechanically checked. If this is not the case -- use the word "precise" (or "mathematical" if you prefer). It's both simpler and more accurate. As the description given here makes heavy use of natural language that is not easily interpretable by a computer, it is not formal, and since the proof makes use of a notion of a time machine, as well as others, not given a formal definition, it is very much informal, even if sufficiently precise to be acceptable as a mathematical proof.
- mlevental 8y agowelcome to writing? i don't understand this kind of pedantry: it is very clear from context that is not going to be a formal spec or formal proof and therefore the word formal here is being used informally... or just ya know according to its conventional understanding. did you really get to the end of article before you realized this wasn't going to be about formal proofs/specs?
- tofof 8y agoDid you really get to the end of the first paragraph before you decided this wasn't going to be about formal proofs/specs? "It will then formalize the Two Generals' Problem and formally prove the impossibility."
- ikeboy 8y ago>With the help of my time machine, I'll switch Alice's input from 1 to 0. This execution, E k + 1 , is indistinguishable to E k for Alice, so she still outputs 1, as does Bob. Next, I'll switch Bob's input to 0. Again, this execution, E k + 2 , is indistinguishable to the previous execution, E k + 1 , for Bob, so both Bob and Alice output 1. This is wrong. Alice and Bob should be switched.
- Aardwolf 8y agoI assume they must meet to discuss the algorithm beforehand. So they could choose as algorithm: never attack (Even if they cannot meet beforehand, the above is a strategy they can figure out on their own assuming the other is also choosing an optimal solution. Never attack is better than always attack because it doesn't depend on timing) Then they need no communication yet know what to do and what the other does. So problem is solvable, and something is wrong in the proof? Or alternatively I missed something in the problem statement preventing the above.
- sidedishes 8y agoI had the same confusion until I read the proof, though maybe I missed something earlier too. This corresponds to the validity condition in the last section. Both generals start with either 0 or 1, and the condition is that if both started with 0 (i.e., initially wanted to individually retreat), they should both output 0. Likewise for 1. The thing about Eve deciding which value the generals start with may also be confusing; a better way to think of it is that 'no matter what both generals start with, this validity condition holds'.
- pimmen 8y agoThe problem could be formulated better, basically it's about reaching consensus about what the state is right now through a lossy medium. Your suggestion is to have a default, which is a good idea, but it doesn't really solve the problem if you want both processes to react to the state (there's an opportunity for an attack now, let's attack). What also makes it unsolvable is that you do not want to endanger more messengers than necessary, i.e you don't want to send the another messenger with a message already sent. It's impossible to always know whether or not the receiver really did get the last message.
- tyleo 8y agoWhile I have not seen this problem before, I agree that a better formulation would have been helpful in thinking about it. For example, I (and it looks like some others in the thread) got caught up on the idea that Eve should just burn all of the messages and obviously you couldn't have consensus. This is because the article says Eve has the ability to burn all of the messages. I think it would be better stated as something like, "Bob/Alice is sending a messenger past the enemy to the other and the messenger may or may not be caught by Eve and killed." Or maybe I am still misunderstanding?
- gcb0 8y agoisn't the two generals solved by encryption/signature and already used on tcp et al?
- detaro 8y agoIt already assumes private communication and doesn't involve an attacker reading the messages, so no. FTA: > Eve receives every message and decides whether she wants to deliver the message or burn the message. She does not, however, get to open the enveloped message.
- draw_down 8y agoIt’s interesting to see a proof of the problem, but I’m more interested in how people deal with it practically.
- dsr_ 8y agoMost of the time, people deal with this by noting that the network sometimes has problems and expecting success anyway. This is guaranteed to fail eventually, but if you can characterize the likelihood of dropping messages, you can set up agreed-upon sequences to improve the probability of eventual cooperation -- but you can never guarantee it. For example: you can put checksums or hashes on your message to help detect corruption. You can put sequence numbers on your messages to help detect message loss. You can run an isochronous stream of very short messages to help decide on a base error rate, or to increase the likelihood of detecting a major loss. You can set up N different networks and hope that they don't all have losses at the same time. All of these techniques help identify and remediate some degree of message loss, but cannot guarantee to solve it given a cantankerous enough -- or evil enough -- message killer.
- FrozenVoid 8y agoCould this be solved by sending lots of messages to synchronize between the two parties. Even if most messages are lost, its possible to have a state where you have both the same goal: if both receive the same message they sent they're on the same page. A sends "Attack?Send your plan" B sends "Retreat,Send your plan" A sends "Retreat,Send your plan" B sends "Retreat,Send your plan" A sends "Retreat,Send your plan" B sends "Retreat,Send your plan"
- humbledrone 8y agoEve could defeat this strategy by dropping all messages.
- nevi-me 8y agoI had a similar comment re. eventual consistency; and I think this is a case of eventual consistency. I think it doesn't work because the problem becomes "when to retreat". It actually introduces a third state (attack; retreat; do nothing), where I might retreat today, and you do nothing. Out of interest, if you set a time/date on when to retreat, how would the message look like, and how would you define confirmation for both parties?
- FrozenVoid 8y agoContinuous synchronization is a solved problem: https://en.wikipedia.org/wiki/Network_Time_Protocol https://en.wikipedia.org/wiki/Network_Time_Protocol
- 8y ago
- nevi-me 8y agoGiven the Two Generals problem, I wanted to frame "eventual consistency" as the below, (but it doesn't work): Alice sends a message saying "Attack on XX:XX on the nth day", and sends that message each day, with nth changing to (n - days)th. If the network (Eve) is lossy, it means she doesn't automatically burn all messages, so eventually, Bob will receive Alice's message. Bob then responds with the same message back to Alice, until Alice receives it. I initially thought this would work, but the extra round-trip from Bob to Alice makes it a problem. I suppose with a long enough 'n', one only needs 2 round-trips, but with a state beyond {0;1}, it's probably impossible to reach "eventual consistency"
- zzzcpan 8y agoReaching consensus is the definition of strong consistency. Eventual consistency would be something like: "Alice: I don't care when Bob attacks, as long as he attacks sometime in the future."
- nevi-me 8y agoSomeone pointed out that the 2 generals problem wasn't stated correctly on the post, the Wikipedia article invalidates my thinking entirely [0]. So, I agree re. strong consistency; as the problem was about that, and not eventual consistency. https://en.m.wikipedia.org/wiki/Two_Generals'_Problem https://en.m.wikipedia.org/wiki/Two_Generals'_Problem
- spooneybarger 8y agoThe article incorrectly defines the two generals problem. The problem states that the two generals have decided to attack but need to coordinate on when. Failure to attack at the same time will result in defeat. Full details are available on Wikipedia: https://en.m.wikipedia.org/wiki/Two_Generals'_Problem https://en.m.wikipedia.org/wiki/Two_Generals'_Problem
- wool_gather 8y agoDoes the semantics of the message matter to the fundamental problem? What's the difference between coordinating a time and coordinating an action? Notice that in either case, you're assuming the other component.
- malisper 8y agoDeciding between a time and an action does matter. The big difference is when deciding on an action, each general only needs to eventually learn the action to take. When learning a time, each general needs to know the time to attack and they need to need to know the other general knows the time to attack before the time to attack has arrived. Here's a more thorough explanation: Normally for the two generals problem, you assume if you retry a message indefinitely, the message will eventually be delivered. If this isn't the case, the problem is trivially impossible. If every message is dropped, the two generals cannot communicate with each other at all. With this assumption, deciding on an action eventually becomes possible. Let's say the two generals strategy is the following. Each general individually decides to attack or retreat, then communicates their plan to the other general. If both general's agree they will execute that plan. Otherwise they will both retreat. To execute this strategy, the generals can use a protocol like TCP. Each general repeatedly sends their plan to the other general until they receive an acknowledgement. Whenever a general receives a plan from the other general they send an acknowledgement, even if they have acknowledgement before. Based on the assumption above, if the first general keeps sending their plan, the second general will eventually receive it. When this happens the second general sends an acknowledgment. If the acknowledgement gets dropped, this cycle repeats. This is because the first general keeps sending the plan and the second general acknowledges it every time they receive it. Since the second general repeatedly sends the acknowledgement indefinitely, the first general will eventually receive it. Since both generals eventually receive the acknowledgement from the other general, using this algorithm will eventually finish. This algorithm allows the generals to eventually agree an action. To see why the algorithm doesn't work for deciding on a time to attack, you can notice that in the above algorithm that each general never actually learns when both general's agree on an action. If a general doesn't know if the other general knows the plan, they cannot attack. If one general learns they are going to attack at 2pm, but the other general hasn't yet learned the time to attack, the first general will attack at 2pm, but the second general won't. Not only do you have to decide on a time, but each general needs to know that the other general has agreed with the time. Doing this is impossible. The proof from Wikipedia looks something like the following. If the two generals eventually reach a point where they both know that "we will attack at 2pm" and "both generals know to attack at 2pm", there must have been some specific message where that statement became true. Without loss of generality, let's say that message was a message sent from the first general to the second. If that message was dropped, everything appears the same to the first general, but not to the second. The first general is now thinking "both generals will attack at 2pm", but the other general doesn't think that yet. This means that its impossible to construct any algorithm that works.
- catchmeifyoucan 8y agoWhat if you said that Bob and Alice have an agreement to send letters every 2 minutes (taking turns one after another). If Eve were to drop a message, Bob or Alice would know that the message was discarded because the next sent message would not arrive in that 2-minute frame. Therefore, they do not update their state. If a state change is requested by either party, if and only if, simultaneous/consecutive messages go through (a total time of 4 minutes: one send and acknowledge) - states are updated: except the catch is that the send note contains the future time both Alice and Bob need to perform the update - which is constant in this entire exchange.