| Available via | http://dbpubs.stanford.edu/pub/2003-71 |
| Next version(s) |
2004-35, 2004-18 |
|
Submitted on |
26th of November 2003 |
|
Author |
Ganesan, Prasanna; Bawa, Mayank |
|
Title |
Distributed Balanced Tables: Not Making a Hash of it all |
|
Date of publication |
2003 |
|
Published in |
Technical Report |
|
Citation |
Ganesan, Prasanna; Bawa, Mayank. Distributed Balanced Tables: Not Making a Hash of it all, Technical Report |
|
Number of pages |
5 |
|
Language |
English |
|
Project |
Peers |
|
Type |
Technical Report |
|
Subject group |
Distributed Systems |
|
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. |
| Fulltext source |
Postscript (ps, ps.gz, ps.zip)
PDF (pdf, pdf.gz, pdf.zip)
| Management of the document by | siroker@db.stanford.edu
| |