Topology Dissemination for Reliable One-Hop Distributed Hash Tables

Abstract

Many distributed hash tables (DHTs) resolve lookups in O(\log n) hops, where n is the number of nodes. One-hop DHTs give lower lookup latencies and lower lookup failure rates. However, it is hard to maintain large, wide-area one-hop topologies. We contribute aecast, a new topology dissemination algorithm for one-hop DHTs. It avoids expensive repair mechanisms and critical points of failure in existing one-hop DHTs. When a node discovers by anti-entropy that it has missed a topology update, it initiates "controlled flooding, sending the update to nodes in the multicast tree that also missed the update. We compare aecast with a widely cited epidemic multicasting algorithm, pbcast, by analysis ..