Load balancing and locality in range-queriable data structures

James Aspnes, Jonathan Kirsch, and Arvind Krishnamurthy. Load balancing and locality in range-queriable data structures. Twenty-Third ACM Symposium on Principles of Distributed Computing, July 2004, pp. 115–124.

Abstract

We describe a load-balancing mechanism for assigning elements to servers in a distributed data structure that supports range queries. The mechanism ensures both load-balancing with respect to an arbitrary load measure specified by the user and geographical locality, assigning elements with similar keys to the same server. Though our mechanism is specifically designed to improve the performance of skip graphs, it can be adapted to provide deterministic, locality-preserving load-balancing to any distributed data structure that orders machines in a ring or line.

BibTeX

Download
@inproceedings(AspnesKK2004,
title="Load balancing and locality in range-queriable data structures",
author="James Aspnes and Jonathan Kirsch and Arvind Krishnamurthy",
booktitle="Twenty-Third ACM Symposium on Principles of Distributed Computing",
month=jul,
year=2004,
pages={115--124}
)

Consolidated BibTeX file
Return to James Aspnes's publications
Return to James Aspnes's home page