J. Rufino, A. Pina, A. Alves, and J. Exposto (Portugal)
Distributed Hash Tables, Distributed Lookup, Evaluation.
We present and evaluate shortcut routing algorithms for
Chord graphs in the hash space, speciﬁcally developed to
accelerate distributed lookups in the Distributed Hash Ta
bles (DHTs) of the Domus framework. The algorithms ex
plore our ﬁndings about the relation of exponential and eu
clidean distances in Chord graphs, in conjunction with the
availability, in each DHT node, of multiple routing tables of
the underlying Chord graph. The outcome are routing deci
sions capable of achieving average distances as low as 40%
of those offered by Chord’s conventional routing method.
Moreover, the supplemental computational effort to take the
shortcut routing decisions is sufﬁciently low to make the al
gorithms useful in a broad set of application scenarios.