DIKUL - logo
E-viri
Celotno besedilo
Recenzirano Odprti dostop
  • Explicit Low-Bandwidth Eval...
    Kiah, Han Mao; Kim, Wilton; Kruglik, Stanislav; Ling, San; Wang, Huaxiong

    IEEE transactions on information theory, 2024-Aug., Letnik: 70, Številka: 8
    Journal Article

    Motivated by applications in distributed storage, distributed computing, and homomorphic secret sharing, we study communication-efficient schemes for computing linear combinations of coded symbols. Specifically, we design low-bandwidth schemes that evaluate the weighted sum of <inline-formula> <tex-math notation="LaTeX">\ell </tex-math></inline-formula> coded symbols in a codeword <inline-formula> <tex-math notation="LaTeX">\pmb {c}\in \mathbb {F}^{n} </tex-math></inline-formula>, when we are given access to d of the remaining components in <inline-formula> <tex-math notation="LaTeX">\pmb {c} </tex-math></inline-formula>. Formally, suppose that <inline-formula> <tex-math notation="LaTeX">\mathbb {F} </tex-math></inline-formula> is a field extension of <inline-formula> <tex-math notation="LaTeX">\mathbb {B} </tex-math></inline-formula> of degree t. Let <inline-formula> <tex-math notation="LaTeX">\pmb {c} </tex-math></inline-formula> be a codeword in a Reed-Solomon code of dimension k and our task is to compute the weighted sum of <inline-formula> <tex-math notation="LaTeX">\ell </tex-math></inline-formula> coded symbols. In this paper, for some <inline-formula> <tex-math notation="LaTeX">s\lt t </tex-math></inline-formula>, we provide an explicit scheme that performs this task by downloading <inline-formula> <tex-math notation="LaTeX">d(t-s) </tex-math></inline-formula> sub-symbols in <inline-formula> <tex-math notation="LaTeX">\mathbb {B} </tex-math></inline-formula> from d available nodes, whenever <inline-formula> <tex-math notation="LaTeX">d\ge \ell |\mathbb {B}|^{s}-\ell +k </tex-math></inline-formula>. In many cases, our scheme outperforms previous schemes in the literature. Furthermore, we provide a characterization of evaluation schemes for general linear codes. Then in the special case of Reed-Solomon codes, we use this characterization to derive a lower bound for the evaluation bandwidth.