Show simple item record

dc.contributor.authorKarger, David
dc.contributor.authorRuhl, Matthias
dc.contributor.otherTheory of Computation
dc.date.accessioned2005-12-12T23:24:43Z
dc.date.available2005-12-12T23:24:43Z
dc.date.issued2003-07-16
dc.identifier.otherMIT-CSAIL-TR-2003-003
dc.identifier.otherMIT-LCS-TR-911
dc.identifier.urihttp://hdl.handle.net/1721.1/29831
dc.description.abstractLoad balancing is a critical issue for the efficient operation of peer-to-peer networks. We give new protocols for several scenarios, whose provable performance guarantees are within a constant factor of optimal. First, we give an improved version of consistent hashing, a scheme used for item to node assignments in the Chord system. In its original form, it required every network node to operate O(log n) virtual nodes to achieve a balanced load, causing a corresponding increase in space and bandwidth usage. Our protocol eliminates the necessity of virtual nodes while maintaining a balanced load. Improving on related protocols, our scheme allows for the deletion of nodes and admits a simpler analysis, since the assignments do not depend on the history of the network. We then analyze a simple protocol for load sharing by movements of data from higher loaded to lower loaded nodes. This protocol can be extended to preserve the ordering of data items. As an application, we use the last protocol to give an efficient implementation of a distributed data structure for range searches on ordered data.
dc.format.extent5 p.
dc.format.extent8268446 bytes
dc.format.extent349665 bytes
dc.format.mimetypeapplication/postscript
dc.format.mimetypeapplication/pdf
dc.language.isoen_US
dc.relation.ispartofseriesMassachusetts Institute of Technology Computer Science and Artificial Intelligence Laboratory
dc.titleNew Algorithms for Load Balancing in Peer-to-Peer Systems


Files in this item

Thumbnail
Thumbnail

This item appears in the following Collection(s)

Show simple item record