Stanford InfoLab Publication Server

Distributed Balanced Tables: Not Making a Hash of it all

Ganesan, Prasanna and Bawa, Mayank (2003) Distributed Balanced Tables: Not Making a Hash of it all. Technical Report. Stanford.

WarningThere is a more recent version of this item available.



DHTs implement a distributed dictionary, supporting key insertion, deletion and lookup. They use hashing to (a) enable efficient dictionary operations, and (b) achieve storage balance across the participant nodes. Hashing can be inappropriate for both problems, as it (a) destroys data ordering, thus making sequential key access and range queries expensive, and (b) fails to provide storage balance when keys are not unique. We propose generalizing DHTs to create Distributed Balanced Tables (DBTs), which eliminate the above two problems. To solve problem (a), we discuss how DHT routing structures can be adapted for use in DBTs, while preserving the costs of the standard dictionary operations and supporting efficient range queries. To solve problem (b), we describe an efficient algorithm that guarantees storage balance, even against an adversarial insertion and deletion of keys.

Item Type:Techreport (Technical Report)
Subjects:Computer Science > Distributed Systems
Related URLs:Project Homepage
ID Code:623
Deposited By:Import Account
Deposited On:25 Nov 2003 16:00
Last Modified:24 Dec 2008 09:47

Download statistics

Repository Staff Only: item control page