Content deleted Content added
→For nondeterministic and variable-length protocols: Correct the proof. It was broken by this edit: https://en.wikipedia.org/w/index.php?title=Two_Generals%27_Problem&type=revision&diff=681137712&oldid=681129493 , which introduced the completely wrong idea that what we are doing at each step is reducing from a nondeterministic protocol to a deterministic one (as opposed to from one nondetermistic protocol to another) |
two big unsourced sections here |
||
Line 24:
==Proof==
{{unsourced section|date=November 2019}}
===For deterministic protocols with a fixed number of messages===
Because this protocol is [[Deterministic_system|deterministic]], suppose there is a sequence of a fixed number of messages, one or more successfully delivered and one or more not. The assumption is that there should be a ''shared certainty for both generals to attack''.
Line 47:
==Engineering approaches==
{{unsourced section|date=November 2019}}
A pragmatic approach to dealing with the Two Generals' Problem is to use schemes that accept the [[uncertainty]] of the [[communication]]s channel and not attempt to eliminate it, but rather mitigate it to an acceptable degree. For example, the first general could send 100 messengers, anticipating that the probability of all being captured is low. With this approach the first general will attack no matter what, and the second general will attack if any message is received. Alternatively the first general could send a stream of messages and the second general could send acknowledgments to each, with each general feeling more comfortable with every message received. As seen in the proof, however, neither can be certain that the attack will be coordinated. There's no algorithm that they can use (e.g. attack if more than four messages are received) which will be certain to prevent one from attacking without the other. Also, the first general can send a marking on each message saying it is message 1, 2, 3 ... of n. This method will allow the second general to know how reliable the channel is and send an appropriate number of messages back to ensure a high probability of at least one message being received. If the channel can be made to be reliable, then one message will suffice and additional messages do not help. The last is as likely to get lost as the first.
| |||