EpiChord: parallelizing the chord lookup algorithm with reactive routing state management
Ben Leong, Barbara H. Liskov, Erik D. Demaine · 2005
EpiChord is a DHT lookup algorithm that demonstrates that we can remove the O(logn)-state-per-node restriction on existing DHT topologies to achieve significantly better lookup performance and resilience using a novel reactive routing state maintenance strategy that amortizes network maintenance costs into existing lookups and by issuing parallel queries. Our technique allows us to design a new class of unlimited-state-per-node DHTs that is able to adapt naturally to a wide range of lookup workloads. EpiChord is able to achieve O(1)-hop lookup performance under lookup-intensive workloads and at least O(logn)-hop lookup performance under churn-intensive workloads even in the worst case (though it is expected to perform better on average). Our simulations show that our approach can reduce both lookup latencies and path lengths by a factor of 3 by issuing only 3 queries asynchronously in parallel per lookup. Furthermore, we show that we are able to achieve this result with minimal additional communication overhead and the number of messages generated per lookup is in general no more than that for the corresponding sequential chord lookup algorithm.