“EpiChord: Parallelizing the Chord Lookup Algorithm with Reactive Routing State Management” by Ben Leong, Barbara Liskov, and Erik D. Demaine. In 12th International Conference on Networks (ICON), (Singapore), Nov. 2004.
EpiChord is a DHT lookup algorithm that demonstrates that we can remove the O(log n)-state-per-node restriction on some existing DHT topologies to achieve signif{}icantly 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(log n)-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 pathlengths 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 over a range of lookup workloads.
BibTeX entry:
@inproceedings{leong04epichord,
author = {Ben Leong and Barbara Liskov and Erik D. Demaine},
title = {EpiChord: Parallelizing the Chord Lookup Algorithm with
Reactive Routing State Management},
booktitle = {12th International Conference on Networks (ICON)},
address = {Singapore},
month = nov,
year = {2004}
}
Programming Methodology Group