| Available via | http://dbpubs.stanford.edu/pub/2004-18 |
| Previous version | 2003-71 |
|
Submitted on |
12th of March 2004 |
|
Author |
Ganesan, Prasanna; Bawa, Mayank; Garcia-Molina, Hector |
|
Title |
Online Balancing of Range-Partitioned Data with Applications to Peer-to-Peer Systems |
|
Date of publication |
March 2004 |
|
Number of pages |
13 |
|
Language |
English |
|
Project |
Peers |
|
Type |
Technical Report |
|
Subject group |
Distributed Systems |
|
Abstract |
We consider the problem of horizontally partitioning a dynamic relation across a large number of disks/nodes by the use of range partitioning. Such partitioning is often desirable in large-scale parallel databases, as well as in peer-to-peer (P2P) systems. As tuples are inserted and deleted, the partitions may need to be adjusted, and data moved, in order to achieve storage balance across the participant disks/nodes. We propose efficient, asymptotically optimal algorithms that ensure storage balance at all times, even against an adversarial insertion and deletion of tuples. We combine the above algorithms with distributed routing structures to architect a P2P system that supports efficient range queries, while simultaneously guaranteeing storage balance. |
| Fulltext source |
Postscript (ps, ps.gz, ps.zip)
PDF (pdf, pdf.gz, pdf.zip)
| Management of the document by | siroker@db.stanford.edu
| |