Random linear coding approach to distributed data storage

Details Random linear coding approach to distributed data storage Random linear coding approach to distributed data storage

2004-12-30

2011-10-25

Chan, Wing (Department: 2441)

Electrical computers and digital processing systems: multicomput

Remote data accessing

Reexamination Certificate

active

08046426

ABSTRACT:
A method and computer program product for providing a random linear coding approach to distributed data storage is presented. A file is broken into a plurality of pieces. For every peer (peer means storage-location with limited storage space), the number of coded-pieces the peer can store is determined. Each of the coded-piece is determined by taking random linear combination of all the pieces of the entire file. The associate code-vector is stored for every coded-piece. The file is retrieved by collecting code-vectors and the coded-pieces from the peers and viewing the collected code-vectors as a matrix. When a dimension of the matrix is equal to the number of pieces of the file, the file is recovered using the collection of code vectors in the matrix.

REFERENCES:
patent: 5924060 (1999-07-01), Brandenburg
patent: 6370389 (2002-04-01), Isomursu et al.
patent: 7174385 (2007-02-01), Li
patent: 2002/0147645 (2002-10-01), Alao et al.
patent: 2004/0054807 (2004-03-01), Harvey et al.
patent: 2004/0215516 (2004-10-01), Denoon et al.
patent: 2004/0249972 (2004-12-01), White et al.
patent: 2005/0152391 (2005-07-01), Effros et al.
patent: 2005/0283537 (2005-12-01), Li et al.
patent: 2006/0007947 (2006-01-01), Li et al.
patent: 2006/0053209 (2006-03-01), Li
patent: 2006/0069800 (2006-03-01), Li
patent: 2006/0075063 (2006-04-01), Grosse et al.
patent: 2006/0080454 (2006-04-01), Li
patent: 2006/0146791 (2006-07-01), Deb et al.
patent: 2006/0218222 (2006-09-01), Brahmbhatt et al.
patent: 2007/0130360 (2007-06-01), Li
patent: 2007/0130361 (2007-06-01), Li
patent: 2007/0294422 (2007-12-01), Zuckerman et al.
Deb, S. et al., Algebraic Gossip: A Network Coding Approach to Optimal Multiple Rumor Mongering. Submitted to IEEE Transactions on Information Theory, Apr. 2004. pp. 1-10.
Acedanski, S. et al., How Good is Random Linear Coding Based Distributed Networked Storage?, 2005, Proceedings of the 2005 International Symposium on Network Coding, pp. 1-6.
Deb S. et al., Data Harvesting: A Random Coding Approach to Rapid Dissemination and Efficient Storage of Data, 2005, Proceedings of the 2005 International Symposium on Network Coding, pp. 1-12.
Ho, T. et al., The Benefits of Coding over Routing in a Randomized Setting, 2003, Proceedings of the 2003 IEEE International Symposium on Information Theory, pp. 442-447.
Ho, T. et al., Network Coding from a Network Flow Perspective, 2003, Proceedings of the 2003 IEEE International Symposium on Information Theory, pp. 441-446.
Ho, T. et al., On Randomized Network Coding, 2003, In Proceedings of 41st Annual Allerton Conference on Communication, Control, and Computing, pp. 1-10.
Koetter R. et al., An Algebraic Approach to Network Coding, Oct. 2003, IEEE/ACM Transactions on Networking, vol. 11, Issue 5, pp. 782-795.
Koetter R. et al., Beyond Routing: An Algebraic Approach to Network Coding, 2002, INFOCOM 2002, Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies, vol. 1, pp. 122-130.
Li S-Y. et al., Linear Network Coding, Feb. 2003, IEEE Transactions on Information Theory, vol. 49, Issue 2, pp. 371-381.
Qiu D. et al., Modeling and performance analysis of BitTorrent-like peer-to-peer networks, 2004, SIGCOMM '04 Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, ACM, pp. 367-377.
Shrader B. et al., On Packet Lengths and Overhead for Random Linear Coding Over the Erasure Channel, 2007, Proceeding IWCMC '07 Proceedings of the 2007 international conference on Wireless communications and mobile computing, ACM, pp. 314-318.
Rudolf Ahlswede, et al., “Network Information Flow”, IEEE Transactions on Information Theory, vol. 46, No. 4, Jul. 2000, pp. 1204-1216.
Ashwinder Ahluwalia, et al., “On the Complexity and Distributed Construction of Energy-Efficient Broadcast Trees in Static Ad Hoc Wireless Networks”, In Proceedings. 2002 Conference on Information Sciences and Systems (CISS 2002), Mar. 2002, pp. 807-813.
Ning Cai, et al., “Secure Network Coding”, In Proceedings. 2002 IEEE International Symposium on Information Theory, Jun. 30-Jul. 5, 2002, p. 323.
Philip A. Chou, et al., “Practical Network Coding”, In Proceedings. 41stAnnual Allerton Conference on Communication, Control and Computing, Oct. 2003, pp. 40-49.
Alan Demers, et al., “Epidemic Algorithms for Replicated Database Maintenance”, In Proc. ACM Symposium on Principles of Distributed Computing, 1987, pp. 1-12.
Michelle Effros, “Distortion-Rate Bounds for Fixed-and Variable-Rate Multiresolution Source Codes”, IEEE Transactions on Information Theory, vol. 45, No. 6, Sep. 1999, pp. 1887-1910.
Tracey Ho, et al., “On Randomized Network Coding”, In Proc. 41stAnnual Allerton Conference on Communication, Control and Computing, Oct. 2003, pp. 11-20.
Tracey Ho, et al., “Byzantine Modification Detection in Multicast Networks Using Randomized Network Coding”, ISIT 2004, Chicago, USA, Jun. 27-Jul. 2, 2004, p. 144.
Tracey Ho, et al., “The Benefits of Coding Over Routing in a Randomized Setting”, ISIT 2003, Yokohama, Japan, Jun. 29-Jul. 4, 2003, p. 442.
R. Karp, et al., “Randomized Rumor Spreading”, In Proc. Foundations of Computer Science, 2000. pp. 565-574.
David Kempe, et al., “Protocols and Impossibility Results for Gossip-Based Communication Mechanisms”, In Proc. 43rdIEEE Symposium on Foundations of Computer Science, 2002. pp. 471-480.
Ralf Koetter, et al., “An Algebraic Approach to Network Coding”, IEEE/ACM Transactions on Networking, vol. 11, No. 5, Oct. 2003. pp. 782-795.
Kadaba Bharath-Kumar, et al., “Routing to Multiple Destinations in Computer Networks”, IEEE Transactions on Communications, vol. Com-31, No. 3, Mar. 1983, pp. 343-351.
April Rasala Lehman, et al., “Complexity Classification of Network Information Flow Problems”, In Proc. 41stAnnual Allerton Conference on Communication, Control and Computing, Oct. 2003, pp. 9-10.
Muriel Medard, et al., “On Coding for Non-Multicast Networks”, In Proc. 41stAnnual Allerton Conference on Communication, Control and Computing, Oct. 2003, pp. 21-29.
S. Ramanathan, “Multicast Tree Generation in Networks With Asymmetric Links”, IEEE/ACM Transactions on Networking, vol. 4, No. 4, Aug. 1996, pp. 558-568.
Tim Roughgarden, et al., “How Bad Is Selfish Routing?”, Journal of the ACM, vol. 49, No. 2, Mar. 2002, pp. 236-259.
Scott Shenker, et al., “Pricing in Computer Networks: Reshaping the Research Agenda”, Telecommunications Policy, vol. 20, No. 3, 1996, pp. 183-201.
Hanif D. Sherali, et al., “Recovery of Primal Solutions When Using Subgradient Optimization Methods to Solve Lagrangian Duals of Linear Programs”, Operations Research Letters 19 (1996), pp. 105-113.
Luhua Song, et al., “Zero-Error Network Coding for Acyclic Networks”, IEEE Transactions on Information Theory, vol. 49, No. 12, Dec. 2003, pp. 3129-3139.
Shuo-Yen Robert Li, et al, “Linear Network Coding”, IEEE Transactions on Information Theory, vol. 49, No. 2, Feb. 2003, pp. 371-381.
Jeffrey E. Wieselthier, et al., “Energy-Aware Wireless Networking with Directional Antennas: The Case of Session-Based Broadcasting and Multicasting”, IEEE Trans. on Mobile Computing, vol. 1, No. 3, Jul.-Sep. 2002, pp. 176-191.
Jeffrey E. Wieselthier, et al., “Energy-Efficient Broadcast and Multicast Trees in Wireless Networks”, Mobile Networks and Applications 7, 2002, pp. 481-492.
Raymond W. Yeung, “Multilevel Diversity Coding with Distortion”, IEEE Transactions on Information Theory, vol. 41, No. 2, Mar. 1995, pp. 412-422.

Affiliated with

Also associated with

Rating

Random linear coding approach to distributed data storage does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Random linear coding approach to distributed data storage, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Random linear coding approach to distributed data storage will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4261275