Distributed Arrays: A P2P Data Structure for Efficient Logical Arrays

Daisuke Fukuchi, Christian Sommer, Yuichi Sei, and Shinichi Honiden
INFOCOM 2009 - 28th IEEE International Conference on Computer Communications (pp. 1458-1466)

Distributed hash tables (DHT) are used for data in P2P environments. However, since most hash functions ignore relations between items, DHTs are not efficient for operations on related items. In this paper, we modify a DHT into a distributed array (DA) that enables efficient operations on logical arrays. The array elements of a DA are placed in a P2P overlay network according to a simple rule such that the load is balanced and the number of messages required to access elements sequentially is reduced. The number of messages required for array operations is much smaller than that for operations on DHTs. We demonstrate this theoretically and experimentally.

@inproceedings{FSSH09,
 author    = {Daisuke Fukuchi 
              and Christian Sommer 
              and Yuichi Sei 
              and Shinichi Honiden},
 title     = {Distributed Arrays: 
              A P2P Data Structure for Efficient Logical Arrays},
 booktitle = {28th IEEE International Conference on 
              Computer Communications, Joint Conference of the 
              IEEE Computer and Communications Societies (INFOCOM)},
 year      = {2009},
 pages     = {1458--1466},
 url       = {http://dx.doi.org/10.1109/INFCOM.2009.5062062},
 doi       = {10.1109/INFCOM.2009.5062062},
}

Official version
Local version (161.8 KB)
Slides (102.5 KB)

Home → Publications → Distributed Arrays: A P2P Data Structure for Efficient Logical Arrays