Stanford InfoLab Publication Server

A Distributed Ordered Dictionary with (1+epsilon) Load Balance

Babcock, Brian and Ganesan, Prasanna (2004) A Distributed Ordered Dictionary with (1+epsilon) Load Balance. Technical Report. Stanford.




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.

Item Type:Techreport (Technical Report)
Related URLs:Project Homepage
ID Code:656
Deposited By:Import Account
Deposited On:31 Jul 2004 17:00
Last Modified:23 Dec 2008 08:40

Download statistics

Repository Staff Only: item control page