| Available via | http://dbpubs.stanford.edu/pub/2004-39 |
|
Submitted on |
1st of August 2004 |
|
Author |
Babcock, Brian; Ganesan, Prasanna |
|
Title |
A Distributed Ordered Dictionary with (1+epsilon) Load Balance |
|
Date of publication |
2004 |
|
Published in |
Technical Report |
|
Citation |
Babcock, Brian; Ganesan, Prasanna. A Distributed Ordered Dictionary with (1+epsilon) Load Balance, |
|
Number of pages |
3 |
|
Language |
English |
|
Project |
Peers |
|
Type |
Technical Report |
|
Subject group |
Miscellaneous |
|
Abstract |
We consider how to maintain a distributed dictionary over
a set of nodes such that each node stores all the keys in one contiguous range of the (ordered) key domain. Such range-partitioned dictionaries are commonly used in parallel databases as they enable efficient range queries. As keys are inserted and removed from the dictionary, the partitioning needs to be adjusted in order to ensure
storage balance across nodes. We develop an online algorithm that ensures that the asymptotic ratio of storage load between any pair of nodes is at most $(1+\epsilon)$, for any constant $\epsilon >0$,
while ensuring that the amortized cost per key insertion or deletion, measured as the number of keys that are migrated across nodes, is constant. Our algorithm can be extended to work for peer-to-peer systems where
nodes themselves may join and leave the distributed dictionary. |
| Fulltext source |
Postscript (ps, ps.gz, ps.zip)
PDF (pdf, pdf.gz, pdf.zip)
| Management of the document by | siroker@db.stanford.edu
| |