【正文】 his means that m erasures are always tolerated. ? Have been around for decades. ? Expensive. J. S. Plank. A tutorial on ReedSolomon coding for faulttolerance in RAIDlike systems. Software – Practiceamp。 Experience, 35(2):189–194,2022. ?2: Will modular arithmetic work? ?NO!!!!! (no multiplicative inverses) ?Instead, you must use Galois Field arithmetic. ReedSolomon Codes ?(n+m) n的范德蒙矩陣 ?基本變換 ?任意兩列可交換 ?任何一列可以乘以一個非 0數(shù) ?任意兩列可做如下變換： Ci=Ci+c*Cj， c非 0 ReedSolomon Performance ? Encoding: O(mn) ? More specifically: mS [ (n1)/BXOR + n/BGFMult ] ? S = Size of a device ? BXOR = Bandwith of XOR (3 GB/s) ? BGFMult = Bandwidth of Multiplication over GF(2w) ?GF(28): 800 MB/s ?GF(216): 150 MB/s ReedSolomon Performance ? Update: O(m) ? More specifically: m+1 XORs and m multiplications. ReedSolomon Performance ? Decoding: O(mn) or O(n3) ? Large devices: dS [ (n1)/BXOR + n/BGFMult ] ? Where d = number of data devices to reconstruct. ? Yes, there’s a matrix to invert, but usually that’s in the noise because dSn n3. ReedSolomon Bottom Line ?Space Efficient: MDS ?Flexible: ?Works for any value of n and m. ?Easy to add/subtract coding devices. ?Publicdomain implementations. ?Slow: ?nway dot product for each coding device. ?GF multiplication slows things down. Cauchy ReedSolomon Codes J. Blomer, M. Kalfane, M. Karpinski, R. Karp, M. Luby, and D. Zuckerman. An XORbased erasureresilient coding scheme. Technical Report TR95048, International Computer Science Institute, August 1995. ?1: Use a Cauchy matrix instead of a Vandermonde matrix: Invert in O(n2). ?2: Use neat projection to convert Galois Field multiplications into XORs. ?Kind of subtle, so we’ll go over it. Cauchy ReedSolomon Codes ?取 GF(2w)中 m+n個不同元素，構(gòu)成X={x1, …, x m}， Y={y1, …, y m} ?Cauchy矩陣：元素 (i, j)為 1/(xi+yj)——GF(2w)上運算 Cauchy ReedSolomon Codes ?例： X={1, 2}， Y={0, 3, 4, 5, 6} Cauchy ReedSolomon Codes Cauchy ReedSolomon Codes ?n、 m固定， w增長， GC的優(yōu)勢明顯 參考文獻(xiàn) ? 參考資料 ? J. S. Plank. Enumeration of optimal and good Cauchy matrices for ReedSolomon coding. Technical Report CS05570, University of Tennessee, December 2022. ? 通信協(xié)議 ——避免重新發(fā)送 ? L. Rizzo. Effective erasure codes for reliable puter munication protocols. ACM SIGCOMM Computer Communication Review, 27(2):24–36, 1997. ? L. Rizzo and L. Vicisano. RMDP: an FECbased reliable multicast protocol for wireless environments. Mobile Computer and Communication Review, 2(2), April 1998. 參考文獻(xiàn) ? 已經(jīng)正在成為 IETF標(biāo)準(zhǔn) ? M. Luby, L. Vicisano, J. Gemmell, L. Rizo, M. Handley, and J. Crowcroft. Forward error correction (FEC) building block. IETF RFC 3452 ( December 2022. ? M. Luby, L. Vicisano, J. Gemmell, L. Rizo, M. Handley, and J. Crowcroft. The use of forward error correction(FEC) in reliable multicast. IETF RFC 3453 ( December 2022. ? 加密 ? C. S. Jutla. Encryption modes with almost free message integrity. Lecture Notes in Computer Science, 2045, 2022. 參考文獻(xiàn) ? 分布式數(shù)據(jù)結(jié)構(gòu) ? W. Litwin and T. Schwarz. Lh*rs: a highavailability scalable distributed data structure using Reed Solomon codes. In Proceedings of the 2022 ACM SIGMOD International Conference on Management of Data, pages 237–248. ACM Press, 2022. ? 降低無線通信能耗 ? P. J. M. Havinga. Energy efficiency of error correction on wireless systems, 1999. ? 廣域網(wǎng)、對等網(wǎng)存儲系統(tǒng) ? J. Kubiatowicz, D. Bindel, Y. Chen, P. Eaton, D. Geels, R. Gummadi, S. Rhea, H. Weatherspoon, W. Weimer, C. Wells, and B. Zhao. Oceanstore: An architecture for globalscale persistent storage. In Proceedings of ACM ASPLOS. ACM, November 2022. 參考文獻(xiàn) ? 用于 cache而不是冗余 ? J. Byers, M. Luby, M. Mitzenmacher, and A. Rege. A digital fountain approach to reliable distribution of bulk data. In ACM SIGCOMM ’98, pages 56–67, Vancouver, August 1998. ? . Byers, M. Luby, and M. Mitzenmacher. Accessing multiple mirror sites in parallel: Using tornado codes to speed up downloads. In IEEE INFOCOM, pages 275–283, New York, NY, March 1999. ? I. T. Rowstron and P. Druschel. Storage management and caching in PAST, a largescale, persistent peertopeer stora