Logic unit operable under the byzantine algorithm, computer...

Details Logic unit operable under the byzantine algorithm, computer... Logic unit operable under the byzantine algorithm, computer...

2000-05-05

2003-05-20

Iqbal, Nadeem (Department: 2184)

Error detection/correction and fault detection/recovery

Data processing system error or fault handling

Reliability and availability

C714S011000, C714S003000

Reexamination Certificate

active

06567927

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
This present invention may relate to a logic unit for the configuration of an architecture that is simultaneous-as-to-time and operable under the Byzantine algorithm and that tolerates a plurality F of faults, with a plurality of inputs for in-reading of data into registers of a set of registers and a plurality of outputs for out-reading of data from the registers, whereby each output is adapted to be connected with an input of a further logic unit. Furthermore, the present invention may relate to a computer unit with such logic unit, as well as to the fault tolerant assembly of at least 3F+1 logic units or computer units. Finally, the present invention may relates also to a method of operating a fault tolerant assembly with at least 3F+1 of such logic units or computer units with F+1 data distributing cycles.
2. Background Information
Fault tolerant computers of this type are known, for example, from German Patent No. 44 01 168 C2. They operate under the Byzantine algorithm as described in German Patent No. 44 01 168 C2, as well as in the paper by Leslie Lamport, Robert Shostak, and Marshall Pease, entitled “The Byzantine Generals Problem”, ACM Transaction on Programming Languages and Systems (TOPLAS), Volume 4, Number 3, July 1982, pages 382-401. The Byzantine algorithm is comprised essentially of a redundant data processing with a plurality of computer units operating in parallel which under this algorithm distribute data, in a manner which will be explained in greater detail below, and compare the data. Fault tolerant computers of this type are comprised of an assembly of 3F+1 computer units RE
1
to RE(3F+1). Such computer units are, for example, for F=1, in accordance with
FIG. 5
, connected to one another in such a manner so that each computer unit can directly exchange data with any other computer unit. By distribution into F+1 distribution cycles and verification of these data under the Byzantine algorithm, a fault-containing computer unit can hereby be recognized and deactivated, whereby the unaffected computer units continue to operate with valid data.
Each computer unit contains, for this purpose, one data storage DS
1
to DS(3F+1). To make the basic problematic which is the base of the invention more clearly understood, the circuitry and procedures in such fault tolerant computers, on the basis of
FIGS. 5
,
5
a
,
5
b
and
5
c
of this application, will be briefly described for F=1, for example.
FIG. 5
of this application shows how, via process signal lines
1
,
2
,
3
,
4
,
5
, process signals are passed to each computer unit RE
1
, RE
2
, RE
3
, RE
4
. Further data lines
6
,
7
,
8
,
9
,
10
,
11
connect each computer unit with respectively one other computer unit. Each of these data lines
6
-
11
is comprised in detail of bi-directional connections for data and for deactivating signals and providing of clock pulse signals. The lines
1
to
11
shown in
FIG. 5
are to be found in corresponding manner in the
FIGS. 5
a
,
5
b
and
5
c
, but without reference numerals.
Each one of the four computer units RE
1
to RE
4
has a process interface PSS and a monitoring logic ÜL, as well as an application specific processor AP. The data storages DS
1
to DS
4
are part of the monitoring logic ÜL and serve for storing of in-read process data.
The original data produced in the computer unit or, respectively, data d
1
to d
4
in-read by a process interface PSS are initially taken up in the respectively associated data storages DS
1
to DS
4
, in accordance with
FIG. 5
a.
Subsequently, each computer unit transfers, in a first data distribution cycle in accordance with
FIG. 5
b
, its original data d
1
to d
4
to each other computer unit, into the associated data storage. At the conclusion of this distribution cycle, thus, each data storage contains, in accordance with
FIG. 5
a
, the in-read, inherent data d
1
; d
2
; d
3
; d
4
, as well as the d
1
/RE
1
; d
2
/RE
2
; d
3
/RE
3
; d
4
/RE
4
identified data, respectively, of the other computer units.
In a second data distribution cycle in accordance with
FIG. 5
c
, each computer unit then transfers all data obtained according to
FIG. 5
b
into the data storages of those two computer units which did not already obtain data in the original condition in accordance with
FIG. 5
a
. Thus, at the conclusion of this distribution cycle, each data storage DS
1
, DS
2
, DS
3
and DS
4
contains its own or inherent data in accordance with
FIG. 5
a
as well as, respectively, three blocks of data DB
1
, DB
2
and DB
3
, whereby the original data di are contained in a transferred block of data of the three other computer units, respectively, from another one of the three computer units REi.
The evaluation is then carried out in each computer unit respectively through a first comparison of the three data within each block of data for bitwise identity, and in a second comparison of the blocks of data DB
1
to DB
3
among one another, as well as with the respective original data in accordance with
FIG. 5
a
, for identity, whereby congruent (i.e., bit-identical) and quasi-congruent identity (i.e., identity within a tolerance range) can be differentiated. When through the subsequent evaluation of the results of comparison, by means of the known Byzantine algorithm, a fault-containing computer unit is identified, the computer unit then produces and transfers a deactivating signal to the computer unit identified as being fault-containing. When this computer unit receives from all three other computer units a deactivating signal, this computer unit is deactivated.
Known computer units or assemblies formed therefrom in accordance with German Patent No. 44 01 168 C2 have, however, the disadvantage that due to the differing contents of the data storages (compare
FIG. 5
c
of this application), as well as the distribution and the comparison of the data on a logical plane or data stream at a level or plane above the individual data, there is required for each computer unit an individual data evaluation, which leads thereto so that known computer units or, respectively, assemblies configured thereof operate rather slowly, since the transfer and evaluation of the sets of data or data sentences require a high computing effort.
OBJECT OF THE INVENTION
One possible object of the present invention may be to provide a fault tolerant assembly of individual logic units or, respectively, computer units, these units per se, as well as a method of operating the assembly, being described above in this application, and which, respectively, operate essentially faster and essentially more reliably.
SUMMARY OF THE INVENTION
One possible embodiment of the present invention preferably teaches that this possible object can be accomplished with a logic unit of the type mentioned above in this application which is characterized thereby in that the registers are coupled with—each connected with one output—the inputs and outputs, and that each register is capable of being in-read and out-read, independently of the position of the logic unit within the assembly, by means of a position-invariant relative identification.
Furthermore, at least one possible embodiment of the present invention preferably teaches a computer unit with such a logic unit, as well as teaching a fault tolerant assembly of at least 3F+1 identically configured ones of such logic units or, respectively, computer units, whereby the inputs and outputs of the logic units or, respectively, computer units, are connected with one another, such that corresponding registers of various logic units or, respectively, computer units comprise data of like relative identification of the origin and of the transmitting computer unit.
Finally, at least one possible embodiment of the present invention preferably teaches a method of operating an assembly in accordance with the invention with at least 3F+1 logic units or computer units according to the invention, wherein F is the amount of

Affiliated with

Also associated with

Rating

Logic unit operable under the byzantine algorithm, computer... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Logic unit operable under the byzantine algorithm, computer..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Logic unit operable under the byzantine algorithm, computer... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3007531