Rafig YAGUBOGLU SAMEDOV, Pamukkale University, TURKEY

Mustafa TEMIZ, Pamukkale University, TURKEY

Two types of faults are considered in the Redundant Computer Control Systems (RCCS): Non-Byzantine and Byzantine. The Non-Byzantine (Byzantine) faults cause the faulty computer to behave in a fixed (different) manner relative to the normally operating computers. This paper analyses the regular features of the fault types in RCCS.

Let N be the total number of computers in the RCCS, k - the number of faulty computers and m - the number of the communication rounds between computers. In order to counteract k Non-Byzantine faults, N? k+1 computers and m=k rounds are required. However, k Byzantine faults are counteracted by N? 3k+1 computers together with m = k+1 rounds [1]. Consequently, the Byzantine faults require more soft- and hardware and processing time and lead the RCCS to fail for N? 3. This situation is unacceptable in highly responsive hard real-time system.

Suppose that the computer n (n=1, 2, ..., N) in the RCCS consists of the Central Processor (CP), Input Processor (IP) and Output Processor (OP). The CP controls the computational process, computes its own computational result (CR) and executes the fault-tolerant procedure on the basis of CRs of all computers in RCCS. The IP consists of the receivers which receive CRs from the other computers. On the other hand, the OP consists of the transmitters which transmit CRs to the other computers. The computational process executed in RCCS is periodically interrupted at the check-points by the execution of the fault-tolerant procedure. At the check-points, m communication rounds between computers are realized to exchange CRs.

We have made a certain assumption on the fault appearances. Only one fault can appear in the RCCS between any two check-points (the probability of the appearance of another fault is negligibly small).

Computer nth can employ the following interface structures:

1. Serial receipt in the time-sharing mode (one receiver receives CRs from the other computers during (N-1) tact);

2. Parallel receipt ((N-1) receivers receive CRs from the other

computers during one tact);

3. Parallel transmission in the broadcast mode (one transmitter transmits CR to the other computers by one bus during one tact);

4. Parallel transmission ((N-1) transmitters transmit CR to the other computers by (N-1) buses during one tact);

5. Serial transmission in the time-sharing mode (one transmitter transmits CR to the other computers by one bus during (N-1) tact).

Let us analyze the regular features between the interface structures and the fault types.

a) Fault occurs in the IP (the CP and OP are non-faulty).

The faulty IP receives the incorrect CRs from other computers in the first and second rounds. The non-faulty OP transmits both the same and correct CR of CP of computer nth in the first round and both the same and incorrect CRs (which were received by IP in first round) in the second round to the other computers.

b) Fault occurs in the CP (the IP and OP are non-faulty).

CR of the CP of computer nth will be incorrect. Non-faulty IP receives the same and correct CRs from other computers in the first and second rounds. Non-faulty OP transmits both the same and incorrect CR in the first round and both the same and correct CRs in the second round.

c) Fault occurs in the OP (the CP and IP are non-faulty).

In structure (3), the faulty OP transmits the same and incorrect CR of the CP of computer nth in the first round and CRs (which were received by IP in the first round) in the second round to other computers. In (4), the part of transmitters of the OP is non-faulty and the other part is faulty. In (5), the OP can change the transmitted CRs in each tact.

As a result, if the communication between computers in the RCCS is realized by using one of the interface structures (1), (2) for receiving and (3) for transmitting, only the Non-Byzantine faults can appear. If the structures (4), (5) are used for transmitting, the Non-Byzantine and Byzantine faults can appear in RCCS.

REFERENCE

1. Mamedli, E. M., Samedov, R. Ya., and Sobolev, N. A. “A Method For Localization of Byzantine And Non-Byzantine Faults”, J. Automation   and Remote Control, Vol. 53, Iss 5, pp 734-744, 1992.