LH*RS P2P: A Scalable Distributed Data Structure for P2P Environment

The concept of a Scalable Distributed Data Structure (SDDS) appeared in 1993. It was intended for multicomputers and more specifically for networks of interconnected workstations. Some SDDS nodes are clients, interfacing to applications. Others are servers storing data in buckets and addressed only by the clients. The data are either application data or the parity data for a high-availability SDDS such as LHRS. Overloaded servers split, migrating data to new servers to make the file scalable. The first SDDS was the now popular LH schema that exists in several variants and implementations. A key search in LH needs at most two forwarding messages (hops) to find the correct server, regardless of the size of the file.