Reliable array of distributed computing nodes

• US 6,128,277 A
• Filed: 12/02/1999
• Issued: 10/03/2000
• Est. Priority Date: 10/01/1997
• Status: Expired due to Term

• Current Assignee: California Institute of Technology
• Original Assignee: California Institute of Technology
• Inventors: Riedel, Marcus David Daniel, LeMahieu, Paul, Fan, Chenggong, Bohossian, Vasken, Xu, Lihao, Bruck, Joshua
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): VINCENT, DAVID ROBERT
• Application Number:
  US09/453,312
• Time in Patent Office: 306 Days
• Field of Search: 370/254, 370/216, 370/221, 370/225, 370/227, 370/242, 370/244, 711/114, 711/117, 711/170
• US Class Current: 370/221
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 2211/1028 Distributed, i.e. distributed RAID systems with parity

Abstract

A system which uses redundant storage and redundant communication to provide a robust distributed server system.

Claims

1. A method of using an error correcting code, comprising:

storing raw information and redundant information indicating the error correcting code into a plurality of information nodes;

determining a parameter indicating usability of said information nodes;

reading said raw information from said plurality of nodes if said parameter indicates that said plurality of nodes are usable, and reading both said raw data and said redundant data from less than said plurality of nodes if said parameter indicates that at least a portion of said plurality of nodes are less than usable.

2. A coding method for an array of nodes, comprising:

forming an array of information, by forming each column of the array representing information from a node,

forming a raw portion of each column including raw information indicating data,

forming a redundant information indicating redundancy information, said redundancy information indicating information about other nodes besides said each node, as taken along an envelope of a specified shape that obtains information from said other node.

3. A coding method as in claim 2, wherein said envelope is a diagonal which is extended to other nodes beyond edges of said array.

4. A method of forming a redundantly-coded network formed from a plurality of nodes, comprising:

mapping each node to a column of an array;

forming two rows of redundant information from said columns of the array, and placing said two rows into said columns, to form a resultant array of N by N including N-2 by N information symbols, and 2 by N redundant information symbols, said parity symbols being constructed according to;

##EQU3## where I=0, 1, . . . , n-1, and (x)_n =X mod n.