LH*RSP2P: a scalable distributed data structure for P2P environment

LH*RSP2P is a Scalable Distributed Data Structure (SDDS) designed for P2P applications. It stores and processes data on SDDS peer nodes. Each node is both an SDDS client and, actually or potentially, an SDDS server with application or parity data. The scheme improves on LH*RS. The basic difference is that now key-based queries require at most one forwarding message, instead of possibly two for LH*RS. This property makes LH*RSP2P the fastest P2P or SDDS addressing scheme. The scan operation now also takes at most two rounds. LH*RSP2P parity management reuses the LH*RS Reed Salomon erasure correction scheme to deal efficiently with churn. The file supports unavailability or withdrawal of up to any k ≥ 1 peers, where k is a parameter that can scale dynamically. We discuss the LH*RSP2P design, implementation issues and variants, as well as related work