Wikipedia

Two Generals' Problem: Difference between revisions

Browse history interactively
← Previous editNext edit →
Content deleted Content added
VisualWikitext
→For nondeterministic and variable-length protocols: Delete reference to a book that, according to its Google Books reviews, is just a copy-paste of Wikipedia. That obviously makes the reference circular. Someone should probably actually check the proof. <snark>Or would that violate WP:NOR?</snark>
Tags: references removed Mobile edit Mobile web edit
→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)
Line 34:
 
===For nondeterministic and variable-length protocols===
A nondeterministic protocol with a potentially variable message count can be compared to aan edge-labeled finite [[tree (graph theory)|tree]], where each leaf or branch (node) in the tree represents an explored example up to a specified point. A protocol that terminates before sending any messages is represented by a tree containing only a root node. The edges from a node to each child are labeled with the messages sent in order to reach the child state. Leaf nodes represent points at which the protocol terminates.
 
Suppose there exists a nondeterministic protocol ''P'' which solves the problemTwo Generals' Problem. Then, by a similar argument to the one used for fixed-length deterministic exampleprotocols inabove, ''P' '' must also solve the previousTwo sectionGenerals' Problem, where athe deterministictree protocolrepresenting can''P' be'' is obtained from thethat non-deterministicfor one''P'' by removing all leaf nodes, and the deterministicedges protocolleading must then also solve theto problemthem.▼
The roots of this tree are labeled with the possible starting messages, and the branch nodes stemming from these roots are labeled with the possible next messages. Leaf nodes represent examples which end after sending the last message. A protocol that terminates before sending any messages is represented by a null tree.
 
Since the nondeterministic protocol''P'' is finite, it then follows that the protocol representedthat byterminates thebefore sending emptyany treemessages would solve the problem. ClearlyBut thisclearly isit notdoes possiblenot. Therefore a nondeterministic protocol which solves the problem cannot exist.▼
▲Suppose there exists a nondeterministic protocol which solves the problem. Then, by a similar argument to the deterministic example in the previous section, where a deterministic protocol can be obtained from the non-deterministic one by removing all leaf nodes, the deterministic protocol must then also solve the problem.
 
▲Since the nondeterministic protocol is finite, it then follows that the protocol represented by the empty tree would solve the problem. Clearly this is not possible. Therefore a nondeterministic protocol which solves the problem cannot exist.
 
===Proof by symmetry===
Retrieved from "https://en.wikipedia.org/wiki/Two_Generals%27_Problem"