Achieving one-hop DHT lookup and strong stabilization by passing tokens

Recent research has demonstrated that if network churn is not excessively high, it becomes entirely reasonable for a distributed hash table (DHT) to store a global lookup table at every node to achieve one-hop lookup. We present a novel algorithm for maintaining global lookup state in a DHT with a Chord-like circular address space. In our DHT, events are disseminated with a parallelized token-passing algorithm using dynamically-constructed dissemination trees rooted at the source of the events. We show that we are able to achieve good one- and two-hop routing performance at a modest cost in bandwidth. Furthermore, our scheme is bandwidth-adaptive, and automatically detects and repairs global address space inconsistencies.