2004 · 99 citations · 15 references
ComputingComputer ScienceComputer SystemsData StructuresDatabasesDistributed SystemsData LocalityDistributed ComputingDistributed Data ProcessingDistributed Database ArchitectureQuery ProcessingRange SearchingDistributed Data StructuresKeysLoad Balancing For Data AccessLoad Balancing ModelsRange QueriesRange Query Data StructuresRange Query SupportRange Selection Queries
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.
15
Ion Stoica, Robert Morris, David R. Karger et al. · 2001 · 9.7K citations
A scalable content-addressable network
Sylvia Ratnasamy, Paul Francis, Mark Handley et al. · 2001 · 6.4K citations · Full text
Consistent hashing and random trees
David R. Karger, Eric Lehman, Tom Leighton et al. · 1997 · 2K citations