Proof Sketches
With high probability, Chord contacts nodes to find a successor in an -node network.
Suppose node wishes to find the successor of key . Let be the predecessor of . We wish to find an upper bound for the number of steps it takes for a message to be routed from to . Node will examine its finger table and route the request to the closest predecessor of that it has. Call this node . If is the entry 's finger table, then both and are at distances between and from along the identifier circle. Hence, the distance between and along this circle is at most . Thus the distance from to is less than the distance from to : the new distance to is at most half the initial distance.
This process of halving the remaining distance repeats itself, so after steps, the distance remaining to is at most ; in particular, after steps, the remaining distance is at most . Because nodes are distributed uniformly at random along the identifier circle, the expected number of nodes falling within an interval of this length is 1, and with high probability, there are fewer than such nodes. Because the message always advances by at least one node, it takes at most steps for a message to traverse this remaining distance. The total expected routing time is thus .
If Chord keeps track of predecessors/successors, then with high probability, if each node has probability of 1/4 of failing, find_successor (see below) and find_predecessor (see below) will return the correct nodes
Simply, the probability that all nodes fail is, which is a low probability; so with high probability at least one of them is alive and the node will have the correct pointer.
Read more about this topic: Chord (peer-to-peer)
Famous quotes containing the words proof and/or sketches:
“The thing with Catholicism, the same as all religions, is that it teaches what should be, which seems rather incorrect. This is “what should be.” Now, if you’re taught to live up to a “what should be” that never existed—only an occult superstition, no proof of this “should be”Mthen you can sit on a jury and indict easily, you can cast the first stone, you can burn Adolf Eichmann, like that!”
—Lenny Bruce (1925–1966)
“Turning one’s novel into a movie script is rather like making a series of sketches for a painting that has long ago been finished and framed.”
—Vladimir Nabokov (1899–1977)