Coding In Paradise

Found a great page that describes several distributed hashtable systems that are attempting to achieve O(1) lookup for DHTs; this is important because decreasing latency in DHTs makes them more viable for replacing DNS and acting as a general P2P substrate. Here is an example from the page: CS 615: Disributed hash tables (structured O(1)).: "The key idea is that a lookup time better than O(log n) can be achieved at the cost of increased storage and traffic overhead. The system presented in this paper achieves the O(1) lookup performance at the cost of roughly O(sqrt(n)) storage per node, less than 2MB in an experimental system of 100 thousand nodes storing 10 million files used in the tests......A high-churn scenario was also tested, half of the nodes were randomly chosen to fail. It appeared that queries would only fail if the home node failed, which indicates that the system is still able to efficiently route messages in such situation."