This paper develops an algorithm based on the Modular Approach to solve singly constrained separable discrete optimization problems (Nonlinear Knapsack Problems). The Modular Approach uses fathoming and integration techniques repeatedly. The fathoming reduces the decision space of variables. The integration reduces the number of variables in the problem by combining several variables into one variable. Computational experiments for "hard" test problems with up to 1000 variables are provided. Each variable has up to 1000 integer values.

Classification of the new and used bills using the spectral patterns of raw time-series acoustic data (observation data) poses some difficulty. This is the fact that the observation data include not only a bill sound, but also some motor sound and noise by a transaction machine. We have already reported the method using adaptive digital filters (ADFs) to eliminate the motor sound and noise. In this paper, we propose an advanced technique to eliminate it by the neural networks (NNs). Only a bill sound is extracted from observation data using prediction ability of the NNs. Classification processing of the new and used bills is performed by using the spectral data obtained from the result of the ADFs and the NNs. Effectiveness of the proposed method using the NNs is illustrated in comparison with former results using ADFs.

In a multisystem data sharing environment (MDSE), the computing nodes are locally coupled via a high-speed network and share a common database at the disk level. To reduce the amount of expensive and slow disk I/O, each node caches database pages in its main memory buffer. This paper focuses on the MDSE that uses record-level locking as a concurrency control. While the record-level locking can guarantee higher concurrency than page-level locking, it may result in heavy message traffic. In this paper, we first propose a cache coherency scheme that can reduce the message traffic in the standard locking. Then the scheme is extended to the context where lock caching and lock de-escalation are adopted. Using a distributed database simulation model, we evaluate the performance of the proposed schemes under a wide variety of database workloads.

In a mobile computing environment, in which communication channels are limited and have low-bandwidths, mobile transactions are long-lived and frequently disconnected with their wireless network in processing. Such peculiarities of mobile transactions make existing transaction scheduling schemes inadequate and raise new challenging research problems. In this paper, we propose a new scheduling scheme called OTS/MT (Optimistic Timestamp Scheme for Mobile Transactions) for mobile transaction scheduling. OTS/MT is based on an optimistic approach that is suitable for low data contention, and prevents indefinite postponement and cascading delay which are major drawbacks of the existing optimistic concurrency control scheme and the timestamp ordering scheme. In addition, the OTS/MT algorithm is inherently a deadlock-free scheduling scheme. In order to schedule mobile transactions, OTS/MT postpones the detection of conflict between mobile transactions until transaction commit time to improve the performance deterioration of TO. In this paper, we attempt to show that this application of optimism to TO is justified by way of simulation.

Epsilon serializability (ESR) was proposed to relax serializability constraints by allowing transactions to execute with a limited amount of inconsistency (ε-spec). Divergence control algorithms, viewed as extensions of concurrency control algorithms, enable read-only transactions to complete if their inconsistencies do not exceed ε-spec. This paper studies the performance of two-phase locking divergence control (2PLDC) and optimistic divergence control (ODC) algorithms. We develop a central part of the ESR transaction processing system that runs with 2PLDC and ODC. We applied a comprehensive centralized database simulation model to measure the performance. Evaluations are conducted with multi-class workloads where on-line update transactions and long-duration queries progress under various ε-spec. Our results demonstrate that significant performance enhancements are achieved with a non-zero tolerable inconsistency. With sufficient ε-spec and limited system resources, both algorithms result in comparable performance. However, with low resource contention, ODC performs significantly better than 2PLDC. Furthermore, in the range of small ε-spec, the queries committed by ODC have more accurate results than those committed by 2PLDC.

The advent of high-speed networks with quality of service guarantees, will enable the deployment of data-server distributed systems over wide-area networks. Most implementations of data-server systems have been over local area networks. Thus it is important, in this context, to study the performance of existing distributed data management protocols in the new networking environment, identify the performance bottlenecks and develop protocols that are capable of taking advantage of the high speed networking technology. In this paper, we examine and compare the scalability of the server-based two-phase locking protocol (s-2PL), and the group two-phase locking protocol (g-2PL). The s-2PL protocol is the most widely used concurrency control protocol, while the g-2PL protocol is an optimized version of the s-2PL protocol, tailored for high-speed wide-area network environments. The g-2PL protocol reduces the effect of the network latency by message grouping, client-end caching and data migration. Detailed simulation results indicate that g-2PL indeed scales better than s-2PL. For example, upto 28% improvement in response time is reported.

This paper introduces a material management system for newspapers that was developed for The Yomiuri Shimbun. Material transferred to the system is stored in a material database and sent to terminals located in the related sections. The material can be processed effectively just by checking information on the terminals. Special requirements for this system will be discussed first in the paper, then problem-solving will be explored.

We discuss the security of the improved knapsack cryptosystem that Kobayashi and Kimura have proposed. Two attacking methods for their cryptosystem are proposed; one is the method for obtaining secret keys from public keys by using the continued fraction, and the other is for decrypting the ciphertext without knowing secret keys. We show that their cryptosystem is not secure against these attacks.

Parallel Transaction Processing (TP) systems have great potential to serve the ever-increasing demands for high transaction processing rate. This potential, however, may not be reached due to the data contention and the widely-used two-phase locking (2PL) Concurrency Control (CC) method. In this paper, a distributed locking-based CC policy called LWDC (Local Wait-Depth Control) was proposed for dealing with this problem for the shared-nothing parallel TP system. On the basis of the LWDC policy, an algorithm called LWDCk was designed. Using simulation LWDCk was compared with the 2PL and the base-line Distributed Wait-Depth Limited (DWDL) CC methods. Simulation studies show that the new algorithm offers better system performance than those compared.

We present a new scheduling policy named Value-based Processor Allocation (VPA-k) for scheduling value-based transactions in a multiprocessor real-time database system. The value of a transaction represents the profit the transaction contributes to the system if it is completed before its deadline. Using VPA-k policy, the transactions with higher values are given higher priorities to execute first, while at most k percentage of the total processors are allocated to the urgent transactions dynamically. Through simulation experiments, VPA-k policy is shown to outperform other scheduling policies substantially in both maximizing the totally obtained values and minimizing the number of missed transactions.

S-boxes (vector output Boolean functions) should satisfy cryptographic criteria even if some input bits (say, k bits) are kept constant. However, this kind of security has been studied only for scalar output Boolean functions. SAC (k) is a criterion for scalar output Boolean functions of this type. This paper studies a generalization of SAC (k) to vector output Boolean functions as the first step toward the security of block ciphers against attacks which keep some input bits constant. We first show a close relationship between such Boolean functions and linear error correcting codes. Then we show the existence, bounds and enumeration of vector Boolean functions which satisfy the generalized SAC (k). A design method and examples are also presented.

In this paper we present an algorithm to solve an as-yet untreated knapsack problem, the Multidimensional Multiple-choice Knapsack Problem (MMKP). Since our specific application occurs in the real-time domain, a solution for the MMKP with a small upper bound on the runtime is desirable. Thus, the Lagrange multiplier method is chosen, and a heuristic with a worst-case runtime behavior better than O(n2m) is developed, n being the number of elements and m the number of dimensions. Extensive testing against an exact algorithm based on partial enumeration is used to establish the accuracy and efficiency of the heuristic.

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.

In this paper, we design an optimized compensation transaction (OCT) that implies an important property of location information. The validity of the proposed compensation transaction is illustrated by describing the HLR database systems on the mobile telecommunications system. We found out that both the length and the occurrence percentage of compensation transactions affect reversely the success ratio of other transactions. However, OCT rarely affects the other transactions, because the compensating procedures are performed rapidly. This paper argues that the optimized compensation transaction is very adequate in the mobile telecommunication system where update transactions are issued more frequently than read-only transactions.

We propose an asymmetric neural network which can solve inequality-constrained combinatorial optimization problems that are difficult to solve using symmetric neural networks. In this article, a knapsack problem that is one of such the problem is solved using the proposed network. Additionally, we study condition for obtaining a valid solution. In computer simulations, we show that the condition is correct and that the proposed network produces better solutions than the simple greedy algorithm.

To clarify the stereopsis disturbance in patients with Alzheimer's disease (AD), we analyzed binocular eye movement when subjects shifted their gaze between targets at different depths. Subjects are patients with Alzheimer's disease, Mluti-infarct dementia (MID), or Olivopontocerebellar atrophy (OPCA), and healthy controls. Targets are arranged in two ways: along the median plane and asymmetrically crossing the median plane, at distances from the eyes of 1000 mm and 300 mm. When the targets are switched at the onset of a beep, the subjects shifted their gaze to the lit target. The experiment is conducted in a dimly lit room whose structure is capable of providing good binocular cues for depth. In AD subjects, especially in the subjects whose symptoms are moderate (advanced stage), vergence is limited and the change in the convergence angle is small, unstable, and non-uniform. These results are different from those of other patients (MID) and OPCA) or healthy controls and suggest a disturbance of stereopsis in the parietal lobe where AD patients typically have dysfunctions.

Real-time database systems have the properties of database and real-time systems. This means they must keep timing constraints of transactions as required in real-time systems, and at the same time ensure database consistency as required in database systems. Real-time concurrency control is a general approach for resolving this conflict. In this type of control, a concurrency control technique for database systems is integrated with a task scheduling technique for real-time systems. This paper surveys previous studies on real-time concurrency control and considers future research directions.