Ganesan, Prasanna and Bawa, Mayank (2003) Distributed Balanced Tables: Not Making a Hash of it all. Technical Report. Stanford.
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||http://infolab.stanford.edu/peers/|
|Deposited By:||Import Account|
|Deposited On:||25 Nov 2003 16:00|
|Last Modified:||24 Dec 2008 09:47|
Available Versions of this Item
- Distributed Balanced Tables: Not Making a Hash of it all. (deposited 25 Nov 2003 16:00) [Currently Displayed]
Repository Staff Only: item control page