Efficient schemes for constructing reliable computing nodes in d

Details Efficient schemes for constructing reliable computing nodes in d Efficient schemes for constructing reliable computing nodes in d

1995-06-23

1998-05-19

Beausoliel, Jr., Robert W.

Excavating

371 36, G06F 1134

Patent

active

057547572

DESCRIPTION:

BRIEF SUMMARY
BACKGROUND OF THE INVENTION

1. Field of the Invention
The invention relates to a computing node in or for use in a computer processing system and particularly a fail-silent computing node.
2. Description of the Prior Art
It is known that replicating computer processing on different computer microprocessors provides a practical means of constructing computer systems capable of tolerating arbitrary computer processor failures. A computing node is composed of a number of conventional computer processors on which applications are replicated to achieve tolerance to failures. Computing nodes are connected via a network.
Typically, individual hardware components do not inherently fail by becoming silent rather their output is corrupted. For some devices, simple models of their correct behaviour exist and can thus be used as a checking means, eg, memory devices should output exactly the data that was originally input to them. In these cases, faults can easily be identified by the addition to the data of redundant information, eg, parity bits, which can be checked when the data is output. However, for complex devices, for which there is no simple correlation between their inputs and subsequent ouptputs, eg, microprocessors, the easiest error detection method of adding redundancy is to duplicate the device and compare the outputs of the two devices.
In typical existing implementations of a fail-silent node, a plurality of or duplicated microprocessors are closely coupled and run in micro-synchronisation. Each microprocessor is initialised to an identical state and then performs identical actions on identical data for each tick of the system clock. Hence on every clock cycle the data output by the component is identical. The principles underlying the node architectures can be explained by examining FIG. 1 which is a diagrammatic representation of a conventional fail-silent node. Since the data streams to be compared are in exact lock-step, a simple hardware comparator (cmp) can be used to check that the data streams are identical and to prevent any outputs once a discrepancy is detected. Although two replicas are actually running, because they are microsynchronised and compared by the dedicated hardware comparator, the application running is unaware of the replication and the comparisons undertaken. When this fail-silent technique is used, the correct and erroneous message sets sent over the network are distinguished by the fact that the only erroneous messages than can be sent are incomplete correct messages, since the occurrence of a fault during the transmission of a message can stop transmission within one clock tick. Such incomplete messages are easily identified by the receiver since they will contravene the lowest levels of network protocols.
Fail-silent nodes have been used widely, for example, in commercial transaction computer processing systems. Such nodes have been designed with the assistance of specialised comparator hardware and clock circuits. A common (reliable) clock source is used for driving a pair of processors that execute in lock-step, with the outputs compared by a (reliable) comparator; no output is produced, once a disagreement is detected by the comparator. Note that since only two microprocessors are used within a node to check on each other, the fail silent characteristics of a node can be guaranteed only if no more than one microprocessor within a node is faulty.
Intuitively, fail silent behaviour ought to mean that a node never generates an erroneous output, i.e., the node can only either generate correct outputs or remain silent. However, this is impossible to implement in practice since output messages take a finite time to transmit, and a fault may occur leading to an error during the transmission of a message. A definition of fail-silence must include the case where a message receiver rejects such erroneous messages. Thus a two-microprocessor node will be said to exhibit fail-silent behaviour in the following sense: the outputs produced by it (if any) are either valid messages or d

REFERENCES:
patent: 4356546 (1982-10-01), Whiteside et al.
patent: 4914657 (1990-04-01), Walter et al.
patent: 5023779 (1991-06-01), Federico et al.
patent: 5157780 (1992-10-01), Stewart et al.
patent: 5210834 (1993-05-01), Zurawski et al.
patent: 5285381 (1994-02-01), Iskarous et al.
patent: 5423024 (1995-06-01), Cheung
patent: 5428769 (1995-06-01), Glaser et al.

Affiliated with

Also associated with

Rating

Efficient schemes for constructing reliable computing nodes in d does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Efficient schemes for constructing reliable computing nodes in d, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient schemes for constructing reliable computing nodes in d will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1862660