Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2011-04-19
2011-04-19
Alphonse, Fritz (Department: 2112)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S759000, C714S784000
Reexamination Certificate
active
07930611
ABSTRACT:
A multiple protection group (MPG) erasure-resilient coding method for constructing MPG codes for encoding and decoding data. The MPG codes constructed herein protect data chunks of data in multiple protection groups and subgroups. In general, the MPG erasure-resilient codes are constructed by locating data chunks into multiple protection groups and assigning at least one parity chunk to each protection group. Basic MPG codes are constructed from existing Maximum Distance Separable (MDS) codes by splitting at least some of the parity chunks into local parities for each of the multiple protection groups and projecting local parities onto each of the groups. Generalized MPG codes have a Maximally Recoverable property that can be used to determine whether an erasure pattern is recoverable or unrecoverable. Generalized MPG codes can recover any erasure pattern that is recoverable.
REFERENCES:
patent: 4769818 (1988-09-01), Mortimer
patent: 6687860 (2004-02-01), Iijima et al.
patent: 6851082 (2005-02-01), Corbett
patent: 6877128 (2005-04-01), Boyer et al.
patent: 6920599 (2005-07-01), Kuwamura
patent: 6968479 (2005-11-01), Wyatt et al.
patent: 7003714 (2006-02-01), Sundaram et al.
patent: 7103824 (2006-09-01), Halford
patent: 7219289 (2007-05-01), Dickson
patent: 7484158 (2009-01-01), Sharon et al.
patent: 7519898 (2009-04-01), Narayanan et al.
patent: 7627715 (2009-12-01), Corbett
patent: 7647546 (2010-01-01), Lee et al.
patent: 2004/0128587 (2004-07-01), Kenchammana-Hosekote et al.
patent: 2004/0158791 (2004-08-01), Sawaguchi
patent: 2006/0107135 (2006-05-01), Corbett
patent: 2007/0011302 (2007-01-01), Groner
patent: 2008/0069242 (2008-03-01), Xu et al.
patent: 2008/0168329 (2008-07-01), Han et al.
Adya, A., W. J. Bolosky, M. Castro, R. Chaiken, G. Cermak, J. R. Douceur, J. Howell, J. R. Lorch, M. Theimer, R. P. Wattenhofer, Farsite: Federated, available, and reliable storage for an incompletely trusted environment, 5th OSDI, Dec. 2002.
Aguilera, M. K., R. Janakiraman, L. Xu, Using erasure codes efficiently for storage in a distributed system, Int'l Conf. on Dependable Sys. and Networks, Jun. 2005, pp. 336-345.
Berrou, C., A. Glavieux, P. Thitimajshima, Near Shannon limit error-correcting coding and decoding: Turbo-codes, IEEE Int'l Conf. on Communications, May 1993, vol. 2, pp. 1064-1070.
Blaum, M., J. Brady, J. Bruck, J. Menon, Evenodd: An efficient scheme for tolerating double disk failures in RAID architectures, IEEE Transactions on Comp., Feb. 1995, pp. 192-202, vol. 44, No. 2.
Byers, J. W., M. Luby, M. Mitzenmacher, and A. Rege, A digital fountain approach to reliable distribution of bulk data, Comp. Comm.—Review, 1998, pp. 56-67, vol. 28, No. 4.
Cachin, C., S. Tessaro, Optimal resilience for erasure-coded Byzantine distributed storage, Proc. of the Int'l Conf. on Dependable Sys. and Networks (DSN'06), 2006, pp. 115-124.
Chou, P. A., Y. Wu, and K. Jain, Practical network coding, Proc. of 41st Annual Allerton Conf. on Comm., Control, and Computing, Oct. 2003.
Chun, B.-G., F. Dabek, A. Haeberlen, H. Weatherspoon, M. F. Kaashoek, J. Kubiatowicz, and R. Morris, Efficient replica maintenance for distributed storage systems, Proc. of the 3rd Symposium on Networked Systems Design and Implementation, May 2006, San Jose, CA.
Cooley, J. A., J. L. Mineweaser, L. D. Servi, E. T. Tsung, Software-based erasure codes for scalable distributed storage, Proc. of the 20th IEEE/11th NASA Goddard Conf. on Mass Storage Sys. and Tech. (MSS'03), 2003, pp. 157-164.
Corbett, P., B. English, A. Goel, T. Grcanac, S. Kleiman, J. Leong, S. Sankar, Row-Diagonal Parity for Double Disk Failure Correction, Proc. of the 3rd USENIX Conf. on File and Storage Technologies, 2004, pp. 1-14, San Francisco, CA.
Dabek, F., M. F. Kaashoek, D. Karger, R. Morris, and I. Stoica, Wide-area cooperative storage with CFS, Proc. of the 18th ACM Symposium on Operating Systems Principles, Oct. 2001, pp. 202-215.
Dimakis, A. G., V. Prabhakaran, K. Ramchandran, Decentralized erasure codes for distributed networked storage, IEEE/ACM Transactions on Networking, Jun. 2006, vol. 14, pp. 2809-2816.
Dimakis, A. G., P. B. Godfrey, M. J. Wainwright, K. Ramchandran, Network coding for distributed storage systems, 26th IEEE Int'l Conf. on Comp. Comm., May 2007, pp. 2000-2008.
Druschel, P. and A. Rowstron, PAST: A large-scale persistent peer-to-peer storage utility, Proc. of the Eight IEEE Workshop on Hot Topics in Operating Systems (HotOSVIII), Schoss Elmau, Germany, May 2001.
Freundlich, S., D. Burshtein, S. Litsyn, Approximately lower triangular ensembles of LDPC codes with linear encoding complexity, IEEE Transactions on Info. Theory, Apr. 2007, vol. 53, No. 4, pp. 1484-1494.
Ghemawat, S., H. Gobioff, and S.-T. Leung, The Google file system, Proc. of ACM SOSP, Oct. 2003, pp. 96-108.
Hafner, J. L., HoVer erasure codes for disk arrays, Int'l Conf. on Dependable Sys. and Networks (DSN'06), 2006, pp. 217-226.
Hafner, J. L., V. Deenadhayalan, K. K. Rao, J. A. Tomlin, Matrix methods for lost data reconstruction in erasure codes, 4th USENIX Conf. on File and Storage Tech. (FAST '05), 2005, p. 183-196, San Francosco, CA.
Hellerstein, L., G. Gibson, R. Karp, R. Katz, and D. Patterson, Coding techniques for handling failures in large disk arrays, Algorithmica, 1994, vol. 2, No. 3, pp. 182-208.
Huang, C., L. Xu, STAR: An efficient coding scheme for correcting triple storage node failures, Proc. 4th USENIX Conf. on File and Storage Techn, pp. 197-210.
Huang, C., C. Minghua, J. Li, Pyramid codes: Flexible schemes to trade space for access efficiency in reliable data storage systems, Sixth IEEE Int'l Symposium on Network Computing and Applications, Jul. 12-14, 2007, pp. 79-86.
Kamra, A., V. Misra, J. Feldman, D. Rubenstein, Growth codes: maximizing sensor network data persistence, Proc. of the 2006 Conf. on Applications, Tech., Architectures, and Protocols for Comp. Comm., 2006, pp. 255-266, Pisa, Italy.
Kubiatowicz, J., D. Bindel, Y. Chen, S. Czerwinski, P. Eaton, D. Geels, R. Gummadi, S. Rhea, H. Weatherspoon, W. Weimer, C. Wells, and B. Zhao, OceanStore: An architecture for global-scale persistent storage, Proc. of the 9th Int'l Conf. on Architectural Support for Programming Languages and Operating Systems, Nov. 2000, pp. 190-201.
Lentmaier, M., and K. S. Ziganfirov, Iterative decoding of generalized low-density parity-check codes, Proc. of IEEE Int'l Symposium on Information Theory, 1998, p. 149.
Plank, J. S., M. G. Thomason, A practical analysis of low-density parity-check erasure codes for wide-area storage applications, Int'l Conf. on Dependable Systems and Networks, Jun. 28-Jul. 1, 2004, pp. 115-124.
Richter, G., S. Stiglmayr, M. Bossert, Optimized asymptotic puncturing distributions for different LDPC code constructions, IEEE Int'l Symposium on Information Theory, Jul. 2006, pp. 831-835.
Xu, L., Hydra: A platform for survivable and secure data storage systems, Proc. of the 2005 ACM Workshop on Storage Security and Survivability, 2005, pp. 108-114.
Xu, L., and J. Bruck, X-Code: MDS array codes with optimal encoding, IEEE Trans. on Information Theory, Jan. 1999, vol. 45, No. 1, pp. 272-276.
Yue, G., L. Ping, X. Wang, Low-rate generalized low-density parity-check codes with hadamard constraints, Proc. Int'l Symposium on Information Theory, Sep. 4-9, 2005, pp. 1377-1381.
Co-pending U.S. Appl. No. 11/684,589, filed Mar. 9, 2007.
Xu et al., Variable shortened-and-punctured Reed-Solomon codes for packet loss protection, Sep. 2002, IEEE Transactions on Broadcasting, vol. 48, No. 3, pp. 237-245.
Rizk, Samir Wadie, U.S. Appl. No. 11/684,589, U.S. Office Action, Jun. 28, 2010.
Chen Minghua
Huang Cheng
Li Jin
Alphonse Fritz
Fischer Craig S.
Lyon & Harr L.L.P.
Microsoft Corporation
LandOfFree
Erasure-resilient codes having multiple protection groups does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Erasure-resilient codes having multiple protection groups, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Erasure-resilient codes having multiple protection groups will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2708170