4 ms·

This doesn't explain what is to me the hard part: namely coping with additions and removals of peers, especially unannounced removals of peers.

rco8786 12y ago
From the wiki: "Since the successor (or predecessor) of a node may disappear from the network (because of failure or departure), each node records a whole segment of the circle adjacent to it, i.e. the r nodes preceding it and the r nodes following it. This list results in a high probability that a node is able to correctly locate its successor or predecessor, even if the network in question suffers from a high failure rate." I'm not 100% sure what that means though. Is it that nodes store redundant data to take over the responsibilities of a next door neighbor node going down? If so, what is the data replication strategy. The "failures and replication" section is blank :( I'm also somewhat confused why they are strict about going counterclockwise. If they know if the desired node is higher or lower in the ring, they could easily implement searching in both directions and reduce the average search distance. This maybe doesn't matter because of the exponential jumps in "known" node distances...but it seems that it would be a cheap efficiency gain on some level.
- covi 12y ago
  > Is it that nodes store redundant data to take over the responsibilities of a next door neighbor node going down? In my understanding, this extra-successor scheme has little (or nothing) to do with data redundancy. Instead, it deals with what you can call meta-data redundancy: instead of making a node knowing how to contact one other node, let's make it store more information so that it knows how to contact more nodes (successors). This way, the probability of a node having all neighbors experiencing a failure can be brought low. > I'm also somewhat confused why they are strict about going counterclockwise. If they know if the desired node is higher or lower in the ring, they could easily implement searching in both directions and reduce the average search distance. This maybe doesn't matter because of the exponential jumps in "known" node distances...but it seems that it would be a cheap efficiency gain on some level. I can only speculate that this is because the DHT is usually presented as a logical overlay. So the hops there are logical hops, not necessarily representative of actual network distance.
realcr 12y ago
I was going to write more articles explaining DHTs in more detail, but I can at least write here a short answer. My general belief about dealing with nodes leaving the network is as follows: You just notice at some point that a node doesn't respond, and then you look for a better one. That is because a node leaving the network could be caused by a failure or a user that kills the program. A node leaving the network is an interesting time, because the node doesn't have any incentive to behave well. If a node x wants to join the network, he will first contact a representitive y on the network. y will then search for x inside the DHT, and find the best location. y will then send x that location on the DHT, and x will just join there. You might be wondering how will the links be set up at this point. At the Chord DHT there is an operation called stabilize that is run from time to time. This operation is where every node updates his finger table. It is mentioned in a more detailed fashion in the original article. I didn't deal with those stuff in the article I wrote because I will deal with them in the future, talking about DHT security and stability. EDIT: One thing that people forget from time to time is that DHTs have some hidden assumption that allows them to work. A DHT assumes that things don't change too fast. At least not too fast that individual nodes can not follow. DHTs can deal with a few nodes joining and leaving, but if lots of nodes become offline in one moment, you might face a problem. Thanks for reading.
- sliken 12y ago
  The mainline DHT (bittorrent's Kademlia) is quite resistant to "lots of nodes becoming offline in a moment". Often 5-10M peers are connected, so each peer tracks 180 peers or so. So unless a very large fraction of the DHT is unreachable then you are likely going to be fine. Also even if by some freak chance all 180 of those peers (distributed across the globe) are gone, you'll get incoming queries from the DHT (assuming you were connected long enough to be in their routing table). Once that happens you can start adding peers again. This is the reason that the DHT is pretty resistant to churn. As long as a reasonable fraction of your 180 node routing table is still around in 10-15 minutes (it's often refreshed that often) you can add as many peers as you want. So in practice the DHT is pretty robust compared to other protocols/services.

rco8786 12y ago

From the wiki: "Since the successor (or predecessor) of a node may disappear from the network (because of failure or departure), each node records a whole segment of the circle adjacent to it, i.e. the r nodes preceding it and the r nodes following it. This list results in a high probability that a node is able to correctly locate its successor or predecessor, even if the network in question suffers from a high failure rate." I'm not 100% sure what that means though. Is it that nodes store redundant data to take over the responsibilities of a next door neighbor node going down? If so, what is the data replication strategy. The "failures and replication" section is blank :( I'm also somewhat confused why they are strict about going counterclockwise. If they know if the desired node is higher or lower in the ring, they could easily implement searching in both directions and reduce the average search distance. This maybe doesn't matter because of the exponential jumps in "known" node distances...but it seems that it would be a cheap efficiency gain on some level.

covi 12y ago
> Is it that nodes store redundant data to take over the responsibilities of a next door neighbor node going down? In my understanding, this extra-successor scheme has little (or nothing) to do with data redundancy. Instead, it deals with what you can call meta-data redundancy: instead of making a node knowing how to contact one other node, let's make it store more information so that it knows how to contact more nodes (successors). This way, the probability of a node having all neighbors experiencing a failure can be brought low. > I'm also somewhat confused why they are strict about going counterclockwise. If they know if the desired node is higher or lower in the ring, they could easily implement searching in both directions and reduce the average search distance. This maybe doesn't matter because of the exponential jumps in "known" node distances...but it seems that it would be a cheap efficiency gain on some level. I can only speculate that this is because the DHT is usually presented as a logical overlay. So the hops there are logical hops, not necessarily representative of actual network distance.

realcr 12y ago

I was going to write more articles explaining DHTs in more detail, but I can at least write here a short answer. My general belief about dealing with nodes leaving the network is as follows: You just notice at some point that a node doesn't respond, and then you look for a better one. That is because a node leaving the network could be caused by a failure or a user that kills the program. A node leaving the network is an interesting time, because the node doesn't have any incentive to behave well. If a node x wants to join the network, he will first contact a representitive y on the network. y will then search for x inside the DHT, and find the best location. y will then send x that location on the DHT, and x will just join there. You might be wondering how will the links be set up at this point. At the Chord DHT there is an operation called stabilize that is run from time to time. This operation is where every node updates his finger table. It is mentioned in a more detailed fashion in the original article. I didn't deal with those stuff in the article I wrote because I will deal with them in the future, talking about DHT security and stability. EDIT: One thing that people forget from time to time is that DHTs have some hidden assumption that allows them to work. A DHT assumes that things don't change too fast. At least not too fast that individual nodes can not follow. DHTs can deal with a few nodes joining and leaving, but if lots of nodes become offline in one moment, you might face a problem. Thanks for reading.

sliken 12y ago
The mainline DHT (bittorrent's Kademlia) is quite resistant to "lots of nodes becoming offline in a moment". Often 5-10M peers are connected, so each peer tracks 180 peers or so. So unless a very large fraction of the DHT is unreachable then you are likely going to be fine. Also even if by some freak chance all 180 of those peers (distributed across the globe) are gone, you'll get incoming queries from the DHT (assuming you were connected long enough to be in their routing table). Once that happens you can start adding peers again. This is the reason that the DHT is pretty resistant to churn. As long as a reasonable fraction of your 180 node routing table is still around in 10-15 minutes (it's often refreshed that often) you can add as many peers as you want. So in practice the DHT is pretty robust compared to other protocols/services.