The distributed program reliability (DPR) is a useful measure for reliability evaluation of distributed systems. In previous methods, a two-mode failure model (working or failed) is assumed for each computing node. However, this assumption is not realistic because data transfer may be possible by way of a computing node even when this node can neither execute programs nor handle its data files. In this paper, we define a new three-mode failure model for representing such a degraded operational state of computing nodes, and present a simple and efficient analysis method based on graph theory. In order to represent the degraded operational state, a given graph expressing a distributed system is augmented by adding new edges and vertices. By traversing this augmented graph, the reliability measure can be computed. Examples show the clear difference between the results of our proposed method and those of the previous ones.

In this paper, we propose a new transaction numbering scheme and a new validation scheme for controlling transactions optimistically in client-server architectural mobile distributed database systems (MDDBSs). In the system, mobile units (MUs) request transaction-related services, e.g., concurrency control, commit process, then the mobile support stations (MSSs) provide the required services. The mobile computing environment makes it very difficult for each MU to assign unique transaction number to transactions since it is allowed to move in communication disconnected states. Besides, validating transactions numbered by the previous transaction numbering scheme could wait indefinitely in the case of data transfer delay. Thus, we propose a new transaction numbering scheme called datatransfer time oriented transaction numbering scheme (DATTO) ,in which we can remove waiting time for validation by determining validation-start time with data-transfer completion time. However, if the previous validation scheme for the static environment is directly applied transactions numbered by DATTO, undesirable results could occur in abnormal cases due to latency on the wireless communication. Thus, we also propose a new validation scheme, called commit-order oriented validation (COOV) ,which is always able to produce correct results by applying backward validation to the abnormal cases.

The fault tolerant computer (FTC) is applied as a communication or database server in the information service and computer aided process control fields. User requires of the FTC are to provide the current level of performance and software transparency needing no additional dedicated program for fault tolerance. To meet these requirements, we propose quadprocessor redundancy (QPR) architecture that combines dualRISC based duplicated CPUs integrating main memories, and duplicated I/O subsystems by using some additional hardware. Duplicated CPUs run under the instruction level synchronization (lock step operation) , and the duplicated I/O subsystems are managed by an operating system. When a fault is detected, the faulty CPU is isolated by hardware. User program is continuously executed by the remaining CPU. We applied the QPR to our UNIX servers, and achieved satisfactory levels of performance.

A new learning algorithm is proposed to enhance fault tolerance ability of the feedforward neural networks. The algorithm focuses on the links (weights) that may cause errors at the output when they are open faults. The relevances of the synaptic weights to the output error (i.e. the sensitivity of the output error to the weight fault) are estimated in each training cycle of the standard backpropagation using the Taylor expansion of the output around fault-free weights. Then the weight giving the maximum relevance is decreased. The approach taken by the algorithm described in this paper is to prevent the weights from having large relevances. The simulation results indicate that the network trained with the proposed algorithm do have significantly better fault tolerance than the network trained with the standard backpropagation algorithm. The simulation results show that the fault tolerance and the generalization abilities are improved.

This paper presents a method of multiple fault diagnosis in sequential circuits by input-sequence pairs having sensitizing input pairs. We, first, introduce an input-sequence pair having sensitizing input pairs to diagnose multiple faults in a sequential circuit represented by a combinational array model. We call such input-sequence pair the sensitizing sequence pair in this paper. Next, we describe a diagnostic method for multiple faults in sequential circuits by the sensitizing sequence pair. From a relation between a sensitizing path generated by a sensitizing sequence pair and a subcircuit, the proposed method deduces the suspected faults for the subcircuits, one by one, based on the responses observed at primary outputs without probing any internal line. Experimental results show that our diagnostic method identifies fault locations within small numbers of suspected faults.

With the scale-down of VLSI chip size and the reduction of switching time of logic gates, crosstalk faults become an important problem in testing of VLSI. For synchronous sequential circuits, the crosstalk pulses on data lines will be considered to be harmless, because they can be invalidated by a clocking phase. However, crosstalk pulses generated on clock lines or reset lines will cause an erroneous operation. In this work, we have analyzed a crosstalk fault scheme, and developed a fault simulator based on the scheme. Throughout this work, we considered the crosstalk fault as unexpected strong capacitive coupling between one data line and one clock line. Since we must consider timing in addition to a logic value, the unit delay model is used in our fault simulation. Our experiments on some benchmark circuits show that fault activation rates and fault detection rates vary widely depending on circuit characteristics. Fault detection rates of up to 80% are obtained from our simulation with test vectors generated at random.

A fault in multi-processing system arbitration circuits result in incorrect arbitration or abnormal operation of the system. A highly reliable system requires dependable arbitration in order to operate properly. Previously, we proposed alternate competing arbitration suitable for highly reliable systems. In this paper, we propose a method for improvement of fault detection and location using additional checkers. This method is effective to maintain reliability of the system.

In this paper, we present a first step for developing a method of verifying both safety and correctness of object-oriented design specification. At first, we analyze the discrepancies, which can occur between requirements specification and design specification, to make clear target faults. Then, we propose a new design review method which aims at detecting faults in the design specification by using three kinds of information tables. Here, we assume that component library, standards for safety and design specification obtained from the Booch's object-oriented design method are given. At the beginning, the designers construct a design table based on a design specification, and the verifiers construct a correctness table and a safety table from component library and standards for safety. Then, by comparing the items on three tables, the verifiers review a given design specification and detect faults in it. Finally, using a small example of object-oriented design specification, we show that faults concerning safety or correctness can be detected by the new design review method.

In this paper we propose a method of formal verification of totally self-checking (TSC) properties of combinational circuits using logic function manipulation. We show that the problem of verification of TSC properties can be transformed to a satisfiability problem of decision functions formed from characteristic functions of a circuit's output code words. Then the problem can be solved using binary decision diagrams (BDD). Experimental results show the effectiveness of the proposed method.

In this paper, we discuss the principle of the clumsy painter method proposed for extracting interested regions from image signals automatically. We theoretically clarify the reason why the clumsy painter method is effective so well. We compare its algorithm with the opening operation in mathematical morphology, and prove that the clumsy painter method has the advantage over the opening operation in mathematical morphology on removing uninterested regions from image signals. Simulating these two methods on two simple geometrical models, we show that the extracted redults by the opening operation are included in those by the clumsy painter method.

The Hopfield neural network for optimization problems often falls into local minima. To escape from the local minima, the neuron unit in the neural network is modified to become an oscillatory unit by adding a simple self-feedback circuit. By combining the oscillatory unit with an energy-value extraction circuit, an oscillatory neural network is constructed. The network can repeatedly extract solutions, and can simultaneously evaluate them. In this paper, the network is applied to four NP-complete problems to demonstrate its generality and efficiency. The network can solve each problem and can obtain better solutions than the original Hopfield neural network and simple algorithms.

In this paper, we apply the method of relating learning to hypothesis testing [6] to study average generalization performance of concept learning from noisy random training examples. A striking aspect of the method is that a learning problem with a so-called ill-disposed learning algorithm can equivalently be reduced to a simple one, and for this simple problem, even though a direct and exact calculation of the learning curves might still be impossible, a thorough empirical study can easily be performed. One of the main advantages of using the illdisposed algorithm is that it well models lower quality learning in real situations, and hence the result can provide useful implications as far as reliable generalization is concerned. We provide empirical formulas for the learning curves by simple functions of the noise rate and the sample size from a thorough empirical study, which smoothly incorporates the results from noise-free analysis and are quite accurate and adequate for practical applications when the noise rate is relatively small. The resulting learning curve bounds are directly related to the number of system weights and are not pessimistic in practice, and apply to learning settings not necessarily within the Bayesian framework.

This paper investigates the accepting powers of multi-inkdot two-way alternating pushdown automata (Turing machines) with sublogarithmic space and constant leaf-size. For each k1, and each m0, let weak-ASPACE^m [L(n),k] denote the class of languages accepted by simultaneously weakly L(n) space-bounded and k leaf-bounded m-inkdot two-way alternating Turing machines, and let strong-2APDA^m[L(n),k] denote the class of languages accepted by simultaneously strongly L(n) space-bounded and k leaf-bounded m-inkdot two-way alternating pushdown automata. We show that(1) strong-2APDA^m [log log n,k+1]weak-ASPACE^m[o(log n),k]φfor each k1 and each m1, and(2) strong-2APDA^(m+1) [log log n,k]weak-ASPACE^m[o(log n),k]φfor each k1 and each m0.

In this paper, we show that a parity function with n variables can be computed by a threshold circuit of depth O((log n)/c) and size O((2^clog n)/c), for all 1c [log(n+1)]-1. From this construction, we obtain an O(log n/log log n) upper bound for the depth of polylogarithmic size threshold circuits for parity functions. By using the result of Impagliazzo, Paturi and Saks[5], we also show an Ω (log n/log log n) lower bound for the depth of the threshold circuits. This is an answer to the open question posed in [11].

This paper presents a high-fair bus arbiter for general multiprocessor systems. The arbiter realizes a new bus arbitration protocol which is a modification to the priority scheme specified in the group protocol enabling it to operate effectively on shared-bus multiprocessors to achieve fairness. The modified priority scheme not only guarantees that processors with low priority will gain access to the bus without being completely lock out as might happen during heavy traffic, but also assures that both bus waiting time and utilization on average of each processor closely approximate to other's. Hardware structure for the proposed protocol is also presented; the circuit is also capable of the feature of live insertion of processors from the system.

The response time of adders is mainly determined by the carry propagation delay. This letter deals with a scheme which combines the address addition and decoding together. Although addition is involved in the process, we show that it can be computed without carry propagation. Memory latency is one of the most performance limiting factors. The authors present a new decoder logic named fused add-decoder (FADEC), which performs address addition and decoding in a single process. FADEC can reduce memory latency by eliminating separate address addition cycle.

The storage utilizations of existing similar key search files based on B⁺-tree and extensible hashing were under 70% and should be improved. A similar key search file based on extensible hashing with partial expansion and that on linear hashing with partial expansion are proposed. Computer simulations on about 230 thousand English words show that the storage utilizations of the files with 32 expansive steps are about 97%.