This paper continues the authors’ research on scalable distributed data structures. In this work, the authors focus their attention on data availability, and extend their previous proposal, LH*, to provide high availability. An LH* server can be unavailable, in which case access to data becomes impossible; this may not be acceptable for an application.

The paper considers two issues: algorithm performance and high availability. On one side, the proposal applies Reed-Solomon codes with a Galois field (GF) (2¹⁶) for parity calculus. It refines the parity matrix, and introduces the concept of a generic parity matrix. The authors also implement the GF multiplication using logarithms and antilogarithms. In addition, they pay special attention to the efficiency of the communication architecture. Such considerations support improving the performance of the algorithm. On the other side, the paper proposes the use of parity records, which are invisible to applications, and provide high availability for the application. The architecture considers a set of LH*_RS servers that are contacted by the application only through the LH*_RS clients. Such clients are localized in the application node. Clients are responsible for data search or storage over the network. Applications ask the clients for data.

There is another important component in the architecture: the coordinator. The paper describes the operation of such a coordinator to provide high-availability updating, insertion, and deletion of data in the system, and bucket split and merging. The paper also describes how the coordinator performs the above operations to derive recovery responsibilities for the LH*_RS clients and servers; this avoids the coordinator being a hot spot in the system. According to paper, the coordinator is k-replicated. However, the resolution of coordinator failure is not clearly explained.

The paper provides some interesting evaluations of the proposal, which support the conclusion that the authors have proposed a new highly available scalable distributed data structure that can be applied in current systems (including peer-to-peer networks, replication systems, and databases).