Making Chord Robust to Byzantine Attacks

摘要: Chord is a distributed hash table (DHT) that requires only O(log n) links per node and performs searches with latency message cost n), where n the number of peers in network. assumes all nodes behave according to protocol. We give variant which robust high probability for any time period during which: 1) there are always at least z total network some integer z; 2) never more than (1/4–e)z Byzantine fixed e > 0; 3) peer insertion deletion events no zk tunable parameter k. assume an adversary controlling IP-addresses locations they join carefully selected by this adversary. Our notion robustness rather strong we not guarantee can be performed but also enforce set “proper behavior” such as contributing new material, etc. In comparison Chord, resources required polylogarithmic factor greater communication, messaging, linking costs.