22:
247:
1407:
The classical way to recover from failures in storage systems was to use replication. However, replication incurs significant overhead in terms of wasted bytes. Therefore, increasingly large storage systems, such as those used in data centers use erasure-coded storage. The most common form of erasure
1047:
Note that Alice cannot encode her telephone number in just one err-mail, because it contains six characters, and that the maximum length of one err-mail message is five characters. If she sent her phone number in pieces, asking Bob to acknowledge receipt of each piece, at least four messages would
225:
While technically RAID can be seen as a kind of erasure code, "RAID" is generally applied to an array attached to a single host computer (which is a single point of failure), while "erasure coding" generally implies multiple hosts, sometimes called a
1376:
symbol message into a practically infinite encoded form, i.e., they can generate an arbitrary amount of redundancy symbols that can all be used for error correction. Receivers can start decoding after they have received slightly more than
1387:
address the issue of rebuilding (also called repairing) lost encoded fragments from existing encoded fragments. This issue occurs in distributed storage systems where communication to maintain encoded redundancy is a problem.
1470:, 10 MB of user data is divided into ten 1MB blocks. Then, four additional 1 MB parity blocks are created to provide redundancy. This can tolerate up to 4 concurrent failures. The storage overhead here is 14/10 = 1.4X.
1480:
Initially, erasure codes were used to reduce the cost of storing "cold" (rarely-accessed) data efficiently; but erasure codes can also be used to improve performance serving "hot" (more-frequently-accessed) data.
2120:
is a near optimal extension to Luigi Rizzo's work that uses band matrices. Many parameters can be set, like the size of the width of the band and size of the finite field. It also successfully exploits the large
1473:
In the case of a fully replicated system, the 10 MB of user data will have to be replicated 4 times to tolerate up to 4 concurrent failures. The storage overhead in that case will be 50/10 = 5 times.
1484:
RAID N+M divides data blocks across N+M drives, and can recover all the data when any M drives fail. In particular, RAID 7.3 refers to triple-parity RAID, and can recover all the data when any 3 drives fail.
1152: − 1 'on the fly', i.e., distribute the workload evenly between transmission of the symbols. If the receiver wants to do his calculations 'on the fly', he can construct a new polynomial
644:
464:
529:
673: = 2, redundancy symbols may be created by sampling different points along the line between the two original symbols. This is pictured with a simple example, called err-mail:
384:
1903:
1008:
778:
834:
265:
2022:
Dimakis, Alexandros G.; Godfrey, P. Brighten; Wu, Yunnan; Wainwright, Martin J.; Ramchandran, Kannan (September 2010). "Network Coding for
Distributed Storage Systems".
904:
869:
1779:
556:
1048:
have to be sent anyway (two from Alice, and two acknowledgments from Bob). So the erasure code in this example, which requires five messages, is quite economical.
1477:
This gives an idea of the lower storage overhead of erasure-coded storage compared to full replication and thus the attraction in today's storage systems.
1023:
912:
211:
As of 2023, modern data storage systems can be designed to tolerate the complete failure of a few disks without data loss, using one of 3 approaches:
1940:
1396:
Erasure coding is now standard practice for reliable data storage. In particular, various implementations of Reed-Solomon erasure coding are used by
1853:
227:
2128:
1993:
1051:
This example is a little bit contrived. For truly generic erasure codes that work over any data set, we would need something other than the
304:
code word symbols are sufficient to recover the original message (i.e., they have optimal reception efficiency). Optimal erasure codes are
1769:. The third Sino-French Workshop on Information and Communication Technologies, SIFWICT 2015, Jun 2015, Nantes, France. ffhal-01162047f
1907:
1044:(5)) he has received. Bob can perform this procedure using any two err-mails, so the erasure code in this example has a rate of 40%.
1412:, an advanced mathematics formula used to enable regeneration of missing data from pieces of known data, called parity blocks. In a (
1409:
1358:
trade correction capabilities for computational complexity: practical algorithms can encode and decode with linear time complexity.
283:
105:
233:
Compared to block-level RAID systems, object storage erasure coding has some significant differences that make it more resilient.
1828:
1133: − 1). The receiver can now also use polynomial interpolation to recover the lost packets, provided he receives
1604:
305:
1507:
43:
564:
2137:
Developed in 1996, was the first use of FEC "Forward Error correction" on the
Internet. It was first used commercially to *
1660:
86:
201:
39:
58:
2077:
2111:
396:
65:
1556:
32:
1742:
1544:
476:
2108:
is a Free
Software library implementing Reed-Solomon and Cauchy erasure code techniques with SIMD optimisations.
1983:
1616:
1068:
337:
130:
72:
1593:
1585:
2154:
2041:
1633:
170:
1589:
1309:
54:
1931:. 2016. p. 2: section "Abstract". p. 9: section "Systematic codes". p. 12: section "Regenerating codes".
1598:
1539:
133:(FEC) code under the assumption of bit erasures (rather than bit errors), which transforms a message of
1928:
1714:
1384:
945:
715:
783:
2046:
1091:
197:
1625:(differs in that the original secret is encrypted and obscured until the decode quorum is reached)
1141:
is less than 2, where b is the number of bits in a symbol, then multiple polynomials can be used.
2122:
2059:
2031:
1317:
697:
Instead of asking Bob to acknowledge the messages she sends, Alice devises the following scheme.
1022:
911:
1354:
symbols to recover the message (where ε>0). Reducing ε can be done at the cost of CPU time.
1989:
1685:
1628:
874:
839:
1580:
2051:
534:
2125:
size of modern CPUs. How it compares to the near optimal codes mentioned above is unknown.
1324:
230:(RAIS). The erasure code allows operations to continue when any one of those hosts stops.
190:
79:
1588:, an MDS code outperforming Reed–Solomon in the maximal number of redundant packets, see
1018:
are the two parts of the telephone number. Now suppose Bob receives "D=777" and "E=851".
1622:
1336:
1272:
and evaluate it to find the lost packets. So both the sender and the receiver require
2148:
2063:
2009:
1519:
1502:
1397:
1361:
680:
676:
196:
There are many different erasure coding schemes. The most popular erasure codes are
122:
1534:
1524:
1313:
1072:
1404:
built into Linux, Microsoft Azure, Facebook cold storage, and
Backblaze Vaults.
205:
186:
21:
1969:
930:(5), and then transmits three redundant messages: "C=703", "D=777" and "E=851".
1803:
1571:
317:
2081:
2055:
141:
symbols such that the original message can be recovered from a subset of the
1766:
558:, is erased, it can be easily recovered by summing the remaining variables:
158:
2138:
1086:, but usually a power of 2. The sender numbers the data symbols from 0 to
2139:
stream live video of Sir Arthur C. Clarke in Sri Lanka to UIUC in
Indiana
1566:
1529:
1780:"Understanding IBM Spectrum Scale Erasure Code Edition fault tolerance"
1765:
Dimitri Pertin, Alexandre van Kempen, Benoît
Parrein, Nicolas Normand.
1448:) chunks are available, one can recover the entire data. This means a (
531:
is now consistent with regard to the checksum. If one of these values,
1953:
1877:
1829:"Erasure coding vs Raid as a data protection method | Computer Weekly"
1401:
649:
1982:
Xia, Mingyuan; Saxena, Mohit; Blaum, Mario; Pease, David A. (2015).
1575:
1028:
Bob can reconstruct Alice's phone number by computing the values of
2036:
1661:"RAID vs. Erasure Coding. What's the Difference? | Blog | Xinnor"
2117:
1970:"Backblaze Open-sources Reed-Solomon Erasure Coding Source Code"
1560:
1493:
Here are some examples of implementations of the various codes:
1467:
1268:) can be calculated. So we have enough data points to construct
652:
is a widely-used application of the parity check erasure code.
173:. The recovery algorithm expects that it is known which of the
169:
denotes the number of symbols required for recovery, is called
240:
15:
1466:
In RS (10, 4) code, which is used in
Facebook for their
2078:"home [Erasure Coding for Distributed Storage Wiki]"
709:= 629, and sends 2 messages – "A=555" and "B=629" – to Bob.
1929:"Erasure Coding for Big-data Systems: Theory and Practice"
1090: − 1 and sends them. He then constructs a
2114:
by Luigi Rizzo describes optimal erasure correction codes
683:
using err-mail. Err-mail works just like e-mail, except
2105:
261:
1804:"Object Storage Erasure Coding vs. Block Storage RAID"
1331:
symbols can be found copied, unencoded, as one of the
639:{\displaystyle v_{e}=-\sum _{i=1,i\neq e}^{k+1}v_{i}.}
1904:"Why erasure coding is the future of data resiliency"
948:
877:
842:
786:
718:
567:
537:
479:
399:
340:
2131:
for regenerating codes and rebuilding erasure codes.
1665:
The
Fastest and Most Reliable Software RAID | Xinnor
1236:
has been received successfully. Secondly, if symbol
1067:
The linear construction above can be generalized to
2134:
1436:. The coding is done such that as long as at least
256:
may be too technical for most readers to understand
46:. Unsourced material may be challenged and removed.
1854:"Erasure Code: RAID As It Should Be – Huawei BLOG"
1002:
898:
863:
828:
772:
701:She breaks her telephone number up into two parts
638:
550:
523:
458:
378:
1392:Applications of erasure coding in storage systems
296:Optimal erasure codes have the property that any
1424:data blocks, called "chunks", are encoded into (
1071:. Additionally, points are now computed over a
679:wants to send her telephone number (555629) to
137:symbols into a longer message (code word) with
1514:Near optimal fountain (rateless erasure) codes
1432:) chunks. The total set of chunks comprises a
690:Messages longer than 5 characters are illegal.
459:{\displaystyle v_{k+1}=-\sum _{i=1}^{k}v_{i}.}
1335:message symbols. (Erasure codes that support
386:, a checksum is computed and appended to the
8:
494:
480:
355:
341:
693:It is very expensive (similar to air-mail).
524:{\displaystyle \{v_{i}\}_{1\leq i\leq k+1}}
1941:"Erasure Encoding—Practice and Principles"
1923:
1921:
1919:
1917:
2045:
2035:
1964:
1962:
947:
876:
841:
785:
717:
627:
611:
588:
572:
566:
542:
536:
497:
487:
478:
447:
437:
426:
404:
398:
379:{\displaystyle \{v_{i}\}_{1\leq i\leq k}}
358:
348:
339:
284:Learn how and when to remove this message
268:, without removing the technical details.
118:Code added to allow recovery of lost data
106:Learn how and when to remove this message
1902:Bhaskaran, Dinesh Kumar (July 6, 2018).
1655:
1653:
1651:
1649:
1456:) RS-encoded storage can tolerate up to
2112:Software FEC in computer communications
2024:IEEE Transactions on Information Theory
1715:"RAID vs Erasure Coding vs Replication"
1645:
322:Parity check is the special case where
1137:symbols successfully. If the order of
228:Redundant Array of Inexpensive Servers
2135:ECIP "Erasure Code Internet Protocol"
1985:A Tale of Two Erasure Codes in {HDFS}
1736:
1734:
1708:
1706:
1312:, with code words constructed over a
1244:has been received successfully, then
687:About half of all the mail gets lost.
266:make it understandable to non-experts
7:
1767:"Comparison of RAID-6 Erasure Codes"
1300:) space for operating 'on the fly'.
44:adding citations to reliable sources
2129:Coding for Distributed Storage wiki
1686:"Ceph.io — Erasure Coding in Ceph"
1408:coding used in storage systems is
712:She constructs a linear function,
14:
1586:Erasure Resilient Systematic Code
1323:Most practical erasure codes are
1144:The sender can construct symbols
1003:{\displaystyle f(i)=a+(b-a)(i-1)}
773:{\displaystyle f(i)=a+(b-a)(i-1)}
2010:""Triple-parity RAID and beyond"
1021:
910:
829:{\displaystyle f(i)=555+74(i-1)}
306:maximum distance separable codes
245:
20:
1605:maximum distance separable code
1308:This process is implemented by
1078:First we choose a finite field
185:Erasure coding was invented by
31:needs additional citations for
1508:Low-density parity-check codes
1339:never use a systematic code).
1180:was received successfully and
997:
985:
982:
970:
958:
952:
887:
881:
852:
846:
823:
811:
796:
790:
767:
755:
752:
740:
728:
722:
330: + 1. From a set of
1:
202:Low-density parity-check code
2080:. 2017-07-31. Archived from
1327:-- each one of the original
1188:) = 0 when symbol
1852:Kruth, Peter (2023-10-04).
1713:Lee, Brandon (2023-12-26).
934:Bob knows that the form of
2171:
1497:Near optimal erasure codes
1420:) RS code, a given set of
1370:near-optimal erasure codes
1368:) are notable examples of
1356:Near-optimal erasure codes
1348:Near-optimal erasure codes
1343:Near-optimal erasure codes
1228:) = 0 if symbol
1196:was not received. Now let
1113:) is equal to data symbol
315:
1743:"RAID Vs. Erasure Coding"
1350:require (1 + ε)
1304:Real world implementation
669:In the simple case where
2056:10.1109/TIT.2010.2054295
1747:www.networkcomputing.com
1617:Forward error correction
1220:). Firstly we know that
1069:polynomial interpolation
918:She computes the values
899:{\displaystyle f(2)=629}
864:{\displaystyle f(1)=555}
131:forward error correction
1372:. They can transform a
1288:)) operations and only
1082:with order of at least
656:Polynomial oversampling
1634:Binary erasure channel
1410:Reed-Solomon (RS) code
1366:rateless erasure codes
1004:
900:
865:
830:
774:
640:
622:
552:
525:
473: + 1 values
460:
442:
380:
145:symbols. The fraction
1551:Optimal erasure codes
1092:(Lagrange) polynomial
1005:
901:
866:
831:
775:
641:
584:
553:
551:{\displaystyle v_{e}}
526:
461:
422:
381:
237:Optimal erasure codes
1988:. pp. 213–226.
1954:"Erasure Coding 101"
1878:"Erasure Coding 101"
1260:) −
1212:) −
946:
875:
840:
784:
716:
565:
535:
477:
397:
338:
171:reception efficiency
40:improve this article
1594:RS(9,2) with 3 bits
1590:RS(4,2) with 2 bits
1296: −
1284: −
661:Example: Err-mail (
198:Reed-Solomon coding
1910:on August 7, 2020.
1833:ComputerWeekly.com
1599:Regenerating Codes
1581:Reed–Solomon codes
1385:Regenerating codes
1318:Vandermonde matrix
1310:Reed–Solomon codes
1000:
896:
861:
826:
770:
636:
548:
521:
456:
376:
204:(LDPC codes), and
177:symbols are lost.
1995:978-1-931971-20-1
1629:Spelling alphabet
1381:encoded symbols.
1036:from the values (
294:
293:
286:
116:
115:
108:
90:
2162:
2093:
2092:
2090:
2089:
2074:
2068:
2067:
2049:
2039:
2030:(9): 4539–4551.
2019:
2013:
2008:Adam Leventhal.
2006:
2000:
1999:
1979:
1973:
1966:
1957:
1950:
1944:
1938:
1932:
1927:Rashmi Vinayak.
1925:
1912:
1911:
1906:. Archived from
1899:
1893:
1892:
1890:
1889:
1874:
1868:
1867:
1865:
1864:
1849:
1843:
1842:
1840:
1839:
1825:
1819:
1818:
1816:
1815:
1800:
1794:
1793:
1791:
1790:
1776:
1770:
1763:
1757:
1756:
1754:
1753:
1738:
1729:
1728:
1726:
1725:
1710:
1701:
1700:
1698:
1697:
1682:
1676:
1675:
1673:
1672:
1657:
1563:storage systems.
1545:Triangular codes
1325:systematic codes
1192: <
1117:. He then sends
1025:
1009:
1007:
1006:
1001:
914:
905:
903:
902:
897:
870:
868:
867:
862:
835:
833:
832:
827:
779:
777:
776:
771:
645:
643:
642:
637:
632:
631:
621:
610:
577:
576:
557:
555:
554:
549:
547:
546:
530:
528:
527:
522:
520:
519:
492:
491:
465:
463:
462:
457:
452:
451:
441:
436:
415:
414:
385:
383:
382:
377:
375:
374:
353:
352:
289:
282:
278:
275:
269:
249:
248:
241:
111:
104:
100:
97:
91:
89:
48:
24:
16:
2170:
2169:
2165:
2164:
2163:
2161:
2160:
2159:
2145:
2144:
2102:
2097:
2096:
2087:
2085:
2076:
2075:
2071:
2047:10.1.1.117.6892
2021:
2020:
2016:
2007:
2003:
1996:
1981:
1980:
1976:
1967:
1960:
1951:
1947:
1939:
1935:
1926:
1915:
1901:
1900:
1896:
1887:
1885:
1876:
1875:
1871:
1862:
1860:
1858:web.archive.org
1851:
1850:
1846:
1837:
1835:
1827:
1826:
1822:
1813:
1811:
1802:
1801:
1797:
1788:
1786:
1778:
1777:
1773:
1764:
1760:
1751:
1749:
1741:O'Reilly, Jim.
1740:
1739:
1732:
1723:
1721:
1712:
1711:
1704:
1695:
1693:
1684:
1683:
1679:
1670:
1668:
1659:
1658:
1647:
1642:
1613:
1553:
1516:
1499:
1491:
1394:
1364:(also known as
1345:
1306:
1065:
944:
943:
873:
872:
838:
837:
782:
781:
780:, in this case
714:
713:
667:
665: = 2)
658:
623:
568:
563:
562:
538:
533:
532:
493:
483:
475:
474:
443:
400:
395:
394:
390:source values:
354:
344:
336:
335:
320:
314:
290:
279:
273:
270:
262:help improve it
259:
250:
246:
239:
191:Gustave Solomon
183:
161:. The fraction
119:
112:
101:
95:
92:
49:
47:
37:
25:
12:
11:
5:
2168:
2166:
2158:
2157:
2147:
2146:
2143:
2142:
2132:
2126:
2115:
2109:
2101:
2100:External links
2098:
2095:
2094:
2069:
2014:
2001:
1994:
1974:
1958:
1945:
1933:
1913:
1894:
1869:
1844:
1820:
1795:
1771:
1758:
1730:
1702:
1677:
1644:
1643:
1641:
1638:
1637:
1636:
1631:
1626:
1623:Secret sharing
1620:
1612:
1609:
1608:
1607:
1601:
1596:
1583:
1578:
1569:
1564:
1552:
1549:
1548:
1547:
1542:
1537:
1532:
1527:
1522:
1515:
1512:
1511:
1510:
1505:
1498:
1495:
1490:
1487:
1393:
1390:
1362:Fountain codes
1344:
1341:
1337:secret sharing
1305:
1302:
1252:) =
1064:
1061:
999:
996:
993:
990:
987:
984:
981:
978:
975:
972:
969:
966:
963:
960:
957:
954:
951:
932:
931:
908:
907:
895:
892:
889:
886:
883:
880:
860:
857:
854:
851:
848:
845:
825:
822:
819:
816:
813:
810:
807:
804:
801:
798:
795:
792:
789:
769:
766:
763:
760:
757:
754:
751:
748:
745:
742:
739:
736:
733:
730:
727:
724:
721:
710:
695:
694:
691:
688:
666:
659:
657:
654:
647:
646:
635:
630:
626:
620:
617:
614:
609:
606:
603:
600:
597:
594:
591:
587:
583:
580:
575:
571:
545:
541:
518:
515:
512:
509:
506:
503:
500:
496:
490:
486:
482:
467:
466:
455:
450:
446:
440:
435:
432:
429:
425:
421:
418:
413:
410:
407:
403:
373:
370:
367:
364:
361:
357:
351:
347:
343:
313:
310:
292:
291:
253:
251:
244:
238:
235:
223:
222:
221:Erasure Coding
219:
216:
182:
179:
157:is called the
117:
114:
113:
55:"Erasure code"
28:
26:
19:
13:
10:
9:
6:
4:
3:
2:
2167:
2156:
2155:Coding theory
2153:
2152:
2150:
2140:
2136:
2133:
2130:
2127:
2124:
2119:
2116:
2113:
2110:
2107:
2104:
2103:
2099:
2084:on 2017-07-31
2083:
2079:
2073:
2070:
2065:
2061:
2057:
2053:
2048:
2043:
2038:
2033:
2029:
2025:
2018:
2015:
2011:
2005:
2002:
1997:
1991:
1987:
1986:
1978:
1975:
1971:
1968:Brian Beach.
1965:
1963:
1959:
1955:
1952:Matt Sarrel.
1949:
1946:
1942:
1937:
1934:
1930:
1924:
1922:
1920:
1918:
1914:
1909:
1905:
1898:
1895:
1883:
1879:
1873:
1870:
1859:
1855:
1848:
1845:
1834:
1830:
1824:
1821:
1809:
1805:
1799:
1796:
1785:
1781:
1775:
1772:
1768:
1762:
1759:
1748:
1744:
1737:
1735:
1731:
1720:
1716:
1709:
1707:
1703:
1691:
1687:
1681:
1678:
1666:
1662:
1656:
1654:
1652:
1650:
1646:
1639:
1635:
1632:
1630:
1627:
1624:
1621:
1618:
1615:
1614:
1610:
1606:
1602:
1600:
1597:
1595:
1591:
1587:
1584:
1582:
1579:
1577:
1573:
1570:
1568:
1565:
1562:
1558:
1555:
1554:
1550:
1546:
1543:
1541:
1540:Network Codes
1538:
1536:
1533:
1531:
1528:
1526:
1523:
1521:
1520:Fountain code
1518:
1517:
1513:
1509:
1506:
1504:
1503:Tornado codes
1501:
1500:
1496:
1494:
1488:
1486:
1482:
1478:
1475:
1471:
1469:
1465:
1461:
1459:
1455:
1451:
1447:
1444: +
1443:
1439:
1435:
1431:
1428: +
1427:
1423:
1419:
1415:
1411:
1405:
1403:
1399:
1398:Apache Hadoop
1391:
1389:
1386:
1382:
1380:
1375:
1371:
1367:
1363:
1359:
1357:
1353:
1349:
1342:
1340:
1338:
1334:
1330:
1326:
1321:
1319:
1315:
1311:
1303:
1301:
1299:
1295:
1291:
1287:
1283:
1279:
1275:
1271:
1267:
1263:
1259:
1255:
1251:
1247:
1243:
1240: ≥
1239:
1235:
1231:
1227:
1223:
1219:
1215:
1211:
1207:
1203:
1199:
1195:
1191:
1187:
1183:
1179:
1175:
1171:
1167:
1163:
1159:
1155:
1151:
1147:
1142:
1140:
1136:
1132:
1128:
1124:
1120:
1116:
1112:
1108:
1104:
1100:
1096:
1093:
1089:
1085:
1081:
1076:
1074:
1070:
1062:
1060:
1058:
1054:
1049:
1045:
1043:
1039:
1035:
1031:
1026:
1024:
1019:
1017:
1013:
994:
991:
988:
979:
976:
973:
967:
964:
961:
955:
949:
941:
937:
929:
925:
921:
917:
916:
915:
913:
893:
890:
884:
878:
858:
855:
849:
843:
820:
817:
814:
808:
805:
802:
799:
793:
787:
764:
761:
758:
749:
746:
743:
737:
734:
731:
725:
719:
711:
708:
704:
700:
699:
698:
692:
689:
686:
685:
684:
682:
678:
674:
672:
664:
660:
655:
653:
651:
633:
628:
624:
618:
615:
612:
607:
604:
601:
598:
595:
592:
589:
585:
581:
578:
573:
569:
561:
560:
559:
543:
539:
516:
513:
510:
507:
504:
501:
498:
488:
484:
472:
453:
448:
444:
438:
433:
430:
427:
423:
419:
416:
411:
408:
405:
401:
393:
392:
391:
389:
371:
368:
365:
362:
359:
349:
345:
333:
329:
325:
319:
311:
309:
308:(MDS codes).
307:
303:
299:
288:
285:
277:
267:
263:
257:
254:This section
252:
243:
242:
236:
234:
231:
229:
220:
217:
214:
213:
212:
209:
207:
203:
199:
194:
192:
188:
180:
178:
176:
172:
168:
164:
160:
156:
152:
149: =
148:
144:
140:
136:
132:
128:
124:
123:coding theory
110:
107:
99:
88:
85:
81:
78:
74:
71:
67:
64:
60:
57: –
56:
52:
51:Find sources:
45:
41:
35:
34:
29:This article
27:
23:
18:
17:
2086:. Retrieved
2082:the original
2072:
2027:
2023:
2017:
2004:
1984:
1977:
1948:
1936:
1908:the original
1897:
1886:. Retrieved
1884:. 2022-04-25
1881:
1872:
1861:. Retrieved
1857:
1847:
1836:. Retrieved
1832:
1823:
1812:. Retrieved
1810:. 2021-07-27
1807:
1798:
1787:. Retrieved
1783:
1774:
1761:
1750:. Retrieved
1746:
1722:. Retrieved
1718:
1694:. Retrieved
1692:. 2014-04-07
1689:
1680:
1669:. Retrieved
1667:. 2023-09-03
1664:
1535:Raptor codes
1525:Online codes
1492:
1483:
1479:
1476:
1472:
1463:
1462:
1457:
1453:
1449:
1445:
1441:
1437:
1433:
1429:
1425:
1421:
1417:
1413:
1406:
1395:
1383:
1378:
1373:
1369:
1365:
1360:
1355:
1351:
1347:
1346:
1332:
1328:
1322:
1314:finite field
1307:
1297:
1293:
1289:
1285:
1281:
1277:
1273:
1269:
1265:
1261:
1257:
1253:
1249:
1245:
1241:
1237:
1233:
1229:
1225:
1221:
1217:
1213:
1209:
1205:
1201:
1197:
1193:
1189:
1185:
1181:
1177:
1173:
1172:) if symbol
1169:
1165:
1161:
1157:
1156:, such that
1153:
1149:
1145:
1143:
1138:
1134:
1130:
1126:
1122:
1118:
1114:
1110:
1106:
1102:
1098:
1094:
1087:
1083:
1079:
1077:
1073:finite field
1066:
1063:General case
1056:
1052:
1050:
1046:
1041:
1037:
1033:
1029:
1027:
1020:
1015:
1011:
939:
935:
933:
927:
923:
919:
909:
836:, such that
706:
702:
696:
675:
670:
668:
662:
648:
470:
468:
387:
331:
327:
323:
321:
312:Parity check
301:
297:
295:
280:
271:
255:
232:
224:
210:
195:
184:
174:
166:
162:
154:
150:
146:
142:
138:
134:
127:erasure code
126:
120:
102:
93:
83:
76:
69:
62:
50:
38:Please help
33:verification
30:
1784:www.ibm.com
1460:failures.
1101:) of order
469:The set of
300:out of the
274:August 2023
215:Replication
206:Turbo codes
187:Irving Reed
96:August 2023
2088:2023-08-20
2037:cs/0702015
1888:2024-09-18
1882:MinIO Blog
1863:2024-09-18
1838:2024-09-18
1814:2024-09-18
1808:MinIO Blog
1789:2024-09-18
1752:2024-09-18
1724:2024-09-18
1696:2024-09-18
1671:2024-09-18
1640:References
1603:any other
1572:Tahoe-LAFS
1559:: used in
1105:such that
318:Parity bit
316:See also:
66:newspapers
2064:260559901
2042:CiteSeerX
1574:includes
1059:) given.
992:−
977:−
926:(4), and
818:−
762:−
747:−
605:≠
586:∑
582:−
508:≤
502:≤
424:∑
420:−
369:≤
363:≤
193:in 1960.
159:code rate
2149:Category
2123:register
2106:Jerasure
1719:BDRSuite
1611:See also
1567:Parchive
1530:LT codes
1489:Examples
1464:Example:
1440:out of (
1316:using a
1125:), ...,
1040:(4) and
1010:, where
165:, where
2012:. 2009.
1972:. 2015.
1956:. 2022.
1943:. 2016.
1690:ceph.io
1452:,
1416:,
705:= 555,
334:values
326:=
324:n
260:Please
181:History
80:scholar
2118:Feclib
2062:
2044:
1992:
1619:codes.
1557:Parity
1434:stripe
1402:RAID-6
1400:, the
650:RAID 5
82:
75:
68:
61:
53:
2060:S2CID
2032:arXiv
1232:<
1176:<
942:) is
922:(3),
677:Alice
129:is a
125:, an
87:JSTOR
73:books
1990:ISBN
1576:zfec
1561:RAID
1468:HDFS
1204:) =
1164:) =
1032:and
1014:and
871:and
218:RAID
189:and
163:k’/k
59:news
2052:doi
1592:or
1148:to
894:629
859:555
803:555
681:Bob
264:to
121:In
42:by
2151::
2058:.
2050:.
2040:.
2028:56
2026:.
1961:^
1916:^
1880:.
1856:.
1831:.
1806:.
1782:.
1745:.
1733:^
1717:.
1705:^
1688:.
1663:.
1648:^
1320:.
1075:.
809:74
208:.
200:,
167:k’
2141:.
2091:.
2066:.
2054::
2034::
1998:.
1891:.
1866:.
1841:.
1817:.
1792:.
1755:.
1727:.
1699:.
1674:.
1458:m
1454:m
1450:k
1446:m
1442:k
1438:k
1430:m
1426:k
1422:k
1418:m
1414:k
1379:k
1374:k
1352:k
1333:n
1329:k
1298:k
1294:n
1292:(
1290:O
1286:k
1282:n
1280:(
1278:n
1276:(
1274:O
1270:r
1266:i
1264:(
1262:q
1258:i
1256:(
1254:p
1250:i
1248:(
1246:r
1242:k
1238:i
1234:k
1230:i
1226:i
1224:(
1222:r
1218:i
1216:(
1214:q
1210:i
1208:(
1206:p
1202:i
1200:(
1198:r
1194:k
1190:i
1186:i
1184:(
1182:q
1178:k
1174:i
1170:i
1168:(
1166:p
1162:i
1160:(
1158:q
1154:q
1150:n
1146:k
1139:F
1135:k
1131:n
1129:(
1127:p
1123:k
1121:(
1119:p
1115:i
1111:i
1109:(
1107:p
1103:k
1099:x
1097:(
1095:p
1088:k
1084:n
1080:F
1057:i
1055:(
1053:f
1042:f
1038:f
1034:b
1030:a
1016:b
1012:a
998:)
995:1
989:i
986:(
983:)
980:a
974:b
971:(
968:+
965:a
962:=
959:)
956:i
953:(
950:f
940:k
938:(
936:f
928:f
924:f
920:f
906:.
891:=
888:)
885:2
882:(
879:f
856:=
853:)
850:1
847:(
844:f
824:)
821:1
815:i
812:(
806:+
800:=
797:)
794:i
791:(
788:f
768:)
765:1
759:i
756:(
753:)
750:a
744:b
741:(
738:+
735:a
732:=
729:)
726:i
723:(
720:f
707:b
703:a
671:k
663:k
634:.
629:i
625:v
619:1
616:+
613:k
608:e
602:i
599:,
596:1
593:=
590:i
579:=
574:e
570:v
544:e
540:v
517:1
514:+
511:k
505:i
499:1
495:}
489:i
485:v
481:{
471:k
454:.
449:i
445:v
439:k
434:1
431:=
428:i
417:=
412:1
409:+
406:k
402:v
388:k
372:k
366:i
360:1
356:}
350:i
346:v
342:{
332:k
328:k
302:n
298:k
287:)
281:(
276:)
272:(
258:.
175:n
155:n
153:/
151:k
147:r
143:n
139:n
135:k
109:)
103:(
98:)
94:(
84:·
77:·
70:·
63:·
36:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.