Byzantine resilient fault tolerant shared memory data processing system

Claim 2

A fault tolerant data processing system for providing single fault Byzantine resilience, said system comprising: a plurality of fault containment regions each region including at least one processing element; a shared memory, each fault containment region further including a portion of said shared memory, the shared memory portion in each fault containment region providing communication with the shared memory portions of each other said fault containment region; each shared memory portion in a fault containment region including encoding means responsive to a data byte from the processor in said fault containment region for encoding said data byte into a plurality of data byte symbols representing said data byte, a selected number of said data byte symbols being usable to reconstruct said data byte; storage means for storing encoded data byte symbols in said shared memory portion; transmitting means for transmitting encoded data byte symbols to one or more of the other shared memory portions in other fault containment regions; receiving means for receiving encoded data byte symbols from one or more of said other shared memory portions; and decoding means responsive to data byte symbols for decoding said symbols to reconstruct a data byte represented thereby.

Claim 3

A fault tolerant data processing system in accordance with claim 1 wherein said system includes four fault containment regions each having a memory quadrant of said shared memory and wherein said encoding means responds to a data byte for encoding said data byte into four data byte symbols, any three of which are usable to reconstruct said data byte, said system performing a data byte write operation when a data byte is supplied from a processing element of one of said fault containment regions wherein the encoding means of the shared memory quadrant of said one fault containment region responds to said data byte to encode said data byte into four data byte symbols, N O , N 1 , N 2 and N 3 ; the storage means of the shared memory quadrant of said one fault containment region stores the N 0 data byte symbol and the transmitting means of the shared memory quadrant transmits the N 1 , N 2 and N 3 data byte symbols to different ones of the other three shared memory quadrants the other ones of said fault containment regions, respectively; and the receiving means of each of said other three shared memory quadrants receives its respective data byte symbol and stores said received data byte symbol in its storage means.

Claim 4

A fault tolerant data processing system in accordance with claim 2 for providing a data byte read operation when a data byte symbol N o of a data word to be read is supplied from a source shared memory quadrant of one of said fault containment region wherein the transmitting means of the shared memory quadrant of said one fault containment region transmits said data byte symbol N o to each of the other three shared memory quadrants of the other fault containment regions; the receiving means of each of said other three shared memory quadrants receive said data byte symbol N o and the transmitting means thereof re-transmits said received data byte symbol N 0 to the shared memory quadrants of all of said fault containment regions; the receiving means of each shared memory quadrant receives the data byte symbols N 0 from each of said other three memory quadrants, respectively, and supplies said received data byte symbols to its voter means for providing a voted N o data byte symbol output therefrom; the transmitting means of said other three shared memory quadrants transmits the data byte symbols N 1 , N 2 and N 3 , respectively, representing the data byte to be read, to all said shared memory quadrants. each shared memory quadrant supplying the data byte symbols N 1 , N 2 , N 3 received from said other three memory quadrants and the voted N 0 data byte symbol from its voter means to its decoding means for decoding the voted N 0 data byte symbol and the received data byte symbols N 1 , N 2 and N 3 to reconstruct therefrom the data byte read from said shared memory.

Claim 5

A fault tolerant data processing system in accordance with claim 3 wherein the transmitting of the data byte symbol N 0 from the source shared memory quadrant to all of said shared memory quadrants and the transmitting of the shared data byte symbols N 1 , N 2 and N 3 from said other three shared memory quadrants to all said shared memory quadrants are performed simultaneously.

Claim 6

A fault tolerant data processing system in accordance with claims 1, 2, 3 or 4 and further including memory error detection and correction means for sequentially scanning memory locations in the shared memory portions of said shared memory and connecting transient errors at said locations; and means for periodically actuating said memory error detection and correction means.

Claim 7

A fault tolerant data processing system in accordance with claim 5 and further including means for regulating the periodic actuation of said memory error detection and correction means.

Claim 8

A fault tolerant data processing system in accordance with claim 6 wherein said regulating means includes fault tolerant clock means for controlling the timing of the operation of said system in accordance with a selected fault tolerant clock cycle; means for counting the number of fault tolerant clock cycles following the completion of a sequential scanning of said memory locations by said error detection and correction means; and means for actuating said error detection and correction means to begin a subsequent sequential scanning of said memory locations after a specified number of fault tolerant clock cycles have been counted by said counting means.