Non-transitive connectivity and DHTs

摘要: The most basic functionality of a distributed hash table, or DHT, is to partition key space across the set nodes in system such that all agree on partitioning. For example, Chord DHT assigns each node random identifier from integers modulo 2160 and maps whose immediately follows it. thus said implement successor relation, so long as network knows its predecessor space, any can compute which keys are mapped onto An implicit assumption other protocols able communicate with other, yet we know this unfounded practice. We say three hosts, A, B, C, exhibit non-transitivity if A B but cannot C. As show Section 2, 2.3% pairs PlanetLab transient periods they through third node. These occur for many reasons, including link failures, BGP routing updates, ISP peering disputes (e.g., [13]). Such underlying problematic DHTs. Consider example illustrated Figure 1. Identifiers increase left, proper k. If unable will believe C successor. Upon receiving lookup request k, return requester. requester then tries insert document associated k at would refuse, since according view it not responsible While may seem contrived, fact quite common. pair adjacent identifiers 300-node (independently) has 0.1% chance being communicate, expect there 1−0.999300≈ 26% some be time. However, both have 0.9992 precedes them both.