Title: Making Chord Robust to Byzantine Attacks Location: Building 980, Room 95 (Sandia NM) Brief Abstract: Chord is a distributed hash table (DHT) that requires only O(log n) links per node and performs searches with latency and message cost O(logn), where n is the number of peers in the network. Chord assumes all nodes behave according to protocol. We give a variant of Chord which, for any fixed epsilon>0, is resilient to (1/4-epsilon)z bad nodes joining the network over a time period during which 1) there are always at least z total nodes in the network and 2) the number of peer joins and leaves is no more than z^k for some tunable parameter k. We assume there is an omniscient and computationally unbounded adversary controlling the bad peers and that the IP-addresses of all the bad peers and the locations where they join the network are carefully selected by this adversary. Our notion of resilience is rather strong in that we not only guarantee that searches can be performed but also that we can enforce any set of "proper behavior'' such as contributing new material, etc. In comparison to Chord, the resources required by this new variant are only a polylogarithmic factor greater in communication, messaging, and linking costs. This is joint work with Amos Fiat (U. Tel Aviv), Valerie King (U. Victoria), Maxwell Young (UNM) and Vishal Sanwalani (UNM) and represents work previously published in PODC and ESA. CSRI POC: Cindy Phillips, (505) 845-7296 |