Distributed Balanced Tables: Not Making a Hash of it all

Abstract

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.

Available Versions of this Item

• Distributed Balanced Tables: Not Making a Hash of it all. (deposited 25 Nov 2003 16:00) [Currently Displayed]
  • Online Balancing of Range-Partitioned Data with Applications to Peer-to-Peer Systems. (deposited 11 Mar 2004 16:00)
  • Online Balancing of Range-Partitioned Data with Applications to Peer-to-Peer Systems. (deposited 12 Jul 2004 17:00)