Skip to main content
eScholarship
Open Access Publications from the University of California

Scholarly Works (8 results)

  • Article
  • Peer Reviewed
UC Irvine Previously Published Works (2017)
Reed-Solomon (RS) codes are widely used in practical storage systems but their repair bandwidth characterization is still an open problem. RS codes can be viewed as the evaluations of a polynomial over a finite field. Recently, Guruswami and Wootters proposed a repair method for RS codes when the evaluation points are the entire field. Tamo, Ye and Barg achieved the minimum storage regenerating (MSR) bound when the sub-packetization size grows faster than the exponential function of the size of the evaluation points. In this work, we extend these results to accommodate different sizes of the evaluation points. Our schemes provide a flexible tradeoff between the sub-packetization size and the repair bandwidth. In addition, we present a technique for the sub-packetization bound of scalar MSR codes, based on the dimension of some constructed vector space.
    Cover page: A Tradeoff Between the Sub-Packetization Size and the Repair Bandwidth for Reed-Solomon CodeCreative Commons 'BY' version 4.0 license
    • Article
    • Peer Reviewed
    UC Irvine Previously Published Works (2018)
      Cover page: A Tradeoff between the Sub-Packetization Size and the Repair Bandwidth for Reed-Solomon Codes.
      • Article
      • Peer Reviewed
      UC Irvine Previously Published Works (2020)
      We provide a detailed algorithm to repair a single node failure in an (n,k) Reed-Solomon code over GF(2ℓ) with repair bandwidth ℓ/a(n-1)(a-s), for any integers a, s such that a|ℓ, 2a ≥ n + 1, 2s ≤ n-k. We present the constructions of necessary lookup tables for the repair. The storage overhead and the repair complexity of our algorithm are also analyzed. The algorithm can be applied to the (14,10) Reed-Solomon codes over GF(28), which is a modification of the code in Facebook's f4 system, and reaches the lowest repair bandwidth among the existing schemes to the best of our knowledge. The algorithm can be generalized to other codes, including the ones based on Yahoo Object Store and Baidu's Atlas.
        Cover page: Repairing Reed-Solomon Codes Over $GF(2^\ell)$
        • Thesis
        • Peer Reviewed
        UC Irvine Electronic Theses and Dissertations (2021)

        In this dissertation, the constructions and schemes for flexible coding in distributed systems are investigated. Depending on the system parameters, the proposed methods allow adaptive choices of code constructions or data reconstruction schemes that provide desirable cost functions, such as network traffic, complexity, and latency. First, the repair of a node failure for Reed-Solomon (RS) codes, one of the most popular codes used in practical storage systems, is considered. Code constructions and repair schemes that provide a tradeoff between the repair communication cost and the coding complexity are presented. Second, facing the fact that the failures are unpredictable in a distributed system, a framework for flexible codes to achieve the optimal latency of accessing information is proposed. Instead of accessing a fixed number of nodes with a conventional code, a flexible code allows one to recover the entire information from a flexible number of storage nodes, and use all the available nodes efficiently. Constructions for different storage scenarios are proposed. Third, flexible coding in distributed matrix multiplication for failure tolerance is presented to reduce the computing latency. The goal is to allow a master node to efficiently obtain the computation results from a flexible number of available servers. The number of failures is unknown a priori and we provide code constructions that can efficiently make use of the computation results from all available servers. Given the storage capacity of the servers, the computation load optimization problem is analyzed.

          Cover page: Flexible Coding for Distributed Systems
          • Article
          • Peer Reviewed
          UC Irvine Previously Published Works (2019)
            • Article
            UC Irvine Previously Published Works (2021)
            The distributed matrix multiplication problem with an unknown number of stragglers is considered, where the goal is to efficiently and flexibly obtain the product of two massive matrices by distributing the computation across N servers. There are up to N - R stragglers but the exact number is not known a priori. Motivated by reducing the computation load of each server, a flexible solution is proposed to fully utilize the computation capability of available servers. The computing task for each server is separated into several subtasks, constructed based on Entangled Polynomial codes by Yu et al. The final results can be obtained from either a larger number of servers with a smaller amount of computation completed per server or a smaller number of servers with a larger amount of computation completed per server. The required finite field size of the proposed solution is less than 2N. Moreover, the optimal design parameters such as the partitioning of the input matrices is discussed. Our constructions can also be generalized to other settings such as batch distributed matrix multiplication and secure distributed matrix multiplication.
              • Article
              • Peer Reviewed
              UC Irvine Previously Published Works (2023)
              This paper presents flexible storage codes, a class of error-correcting codes that can recover information from a flexible number of storage nodes. As a result, one can make better use of the available storage nodes in the presence of unpredictable node failures and reduce the data access latency. Assume a storage system encodes kℓ information symbols over a finite field F into n nodes, each of size ℓ symbols. The code is parameterized by a set of tuples {(Rj, ℓj) : 1 ≤ j ≤ a}, satisfying ℓ1 < ℓ2 < < ℓa = ℓ and R1 > R2 > > Ra, such that the information symbols can be reconstructed from any Rj nodes, each node accessing ℓj symbols, for any 1 ≤ j ≤ a. In other words, the code allows a flexible number of nodes for decoding to accommodate the variance in the data access time of the nodes. Code constructions are presented for different storage scenarios, including LRC (locally recoverable) codes, PMDS (partial MDS) codes, and MSR (minimum storage regenerating) codes. We analyze the latency of accessing information and perform simulations on Amazon clusters to show the efficiency of the presented codes.
                • Article
                • Peer Reviewed
                UC Irvine Previously Published Works (2022)
                The distributed matrix multiplication problem with an unknown number of stragglers is considered, where the goal is to efficiently and flexibly obtain the product of two massive matrices by distributing the computation across N servers. There are up to N - R stragglers but the exact number is not known a priori. Motivated by reducing the computation load of each server, a flexible solution is proposed to fully utilize the computation capability of available servers. The computing task for each server is separated into several subtasks, constructed based on Entangled Polynomial codes by Yu et al. The final results can be obtained from either a larger number of servers with a smaller amount of computation completed per server or a smaller number of servers with a larger amount of computation completed per server. The required finite field size of the proposed solution is less than 2N. Moreover, the optimal design parameters such as the partitioning of the input matrices are discussed. Our constructions can also be generalized to other settings such as batch distributed matrix multiplication and secure distributed matrix multiplication.
                  Top