Hiroyoshi MATSUI Michiko INOUE Toshimitsu MASUZAWA Hideo FUJIWARA
We investigate possibility of fault-tolerant and self-stabilizing protocols (ftss protocols) using an unreliable failure detector. Our main contribution is (1) to newly introduce k-accuracy of an unreliable failure detector, (2) to show that k-accuracy of a failure detector is necessary for any ftss k-group consensus protocol, and (3) to present three ftss k-group consensus protocols using a k-accurate and weakly complete failure detector under the read/write daemon on complete networks and on (n-k+1)-connected networks, and under the central daemon on complete networks.
Kwame Osei BOATENG Hiroshi TAKAHASHI Yuzo TAKAMATSU
In this paper, we consider the design for testability of a multiplier based on the modified Booth Algorithm. First, we present a basic array implementation of the multiplier. Next, we introduce testability considerations to derive two C-testable designs. The first of the designs is C-testable under the single stuck-at fault model (SAF) with 10 test patterns. And, the second is C-testable under the cell fault model (CFM) with 33 test patterns.
Masami SHISHIBORI Kazuaki ANDO Yuuichirou KASHIWAGI Jun-ichi AOE
Natural language interface systems can accept more unrestricted queries from users than other systems, however it is impossible to understand erroneous sentences which include the syntax errors, unknown words and misspelling. In order to realize the superior natural language interface, the automatic error correction for erroneous sentences is one of problems to be solved. The method to apply the LR parsing strategies is one of the famous approaches as the robust error recovery scheme. This method is able to obtain a high correction accuracy, however it takes a great deal of time to parse the sentence, such that it becomes a very important task to improve the time-cost. In this paper, we propose the method to improve the time efficiency, keeping the correction accuracy of the traditional method. This method makes use of a new parsing table that denotes the states to be transited after accepting each symbol. By using this table, the symbol which is allocated just after the error position can be utilized for selecting correction symbols, as a result, the number of candidates produced on the correction process is reduced, and fast system can be realized. The experiment results, using 1,050 sentences including error characters, show that this method can correct error points 69 times faster than the traditional method, also keep the same correction accuracy as the traditional method.
Hideaki MATSUE Masahiro UMEHIRA Takehiro MURASE
The ATM Wireless Access (AWA) System allows portable terminals such as notebook PCs to provide up to 10Mbits/s to each user. AWA will be one of the last hops of the fiber system; it seamlessly provides wireless terminals with most of the services available in the fiber system. A prototype is developed to confirm system realization and the technical feasibility of the radio transmission rate of 80 Mbit/s, the highest yet reported in wireless access systems, by employing ATM technology to support multimedia communication with different communication quality requirements. The prototype uses TDMA as the multiple access method. This paper proposes the system concept and technical issues of the AWA system. The design and performance of the AWA prototype are clarified. It is confirmed that the target performance of the prototype can be achieved and technical issues are feasible.
Goro YAMAUCHI Kenichi TAKAI Hiroyuki SAITO
We developed a new water repellent coating consisting of PTFE particles dispersed in PVDF resin. This coating exhibited a contact angle of 150 degrees. By ice accreting test, the intensity of reflected microwave on the water-repellent coated plate did not decrease, whereas that on uncoated one decreased.
Shin ARAHIRA Yukio KATOH Daisuke KUNIMATSU Yoh OGAWA
A 160 GHz colliding-pulse mode-locked laser diode (CPM-LD) was stabilized by injection of a stable master laser pulse train repeated at a 16th-subharmonic-frequency (9.873 GHz) of the CPM-LD's mode-locking frequency. Synchroscan steak camera measurements revealed a clear pulse train with 16-times repetition frequency of the master laser pulse train for the stabilized CPM-LD output, indicating that CPM-LD output was synchronized to the master laser and that the timing jitter was also reduced. The timing jitter of the stabilized CPM-LD was quantitatively evaluated by an all-optical down converting technique using the nonlinearity of optical fiber. This technique is simple and has a wider bandwidth in comparison to a conventional technique, making it possible to accurately measure the phase noise of ultrafast optical pulse train when its repetition frequency exceeds 100 GHz. The electrical power spectra measurements indicated that the CPM-LD's mode-locking frequency was exactly locked by the injection of the master laser pulse train and that the timing jitter decreased as the injection power increased. The timing jitter was reduced from 2.2 ps in free running operation to 0.26 ps at an injection power of 57 mW, comparable to that of the master laser (0.21 ps).
Chunhee WOO Daehyun LEE Hagbae KIM
When a failure or upset occurring in a controller computer induces a task failure durable for a substantial period, system dynamics apparently deviates from its desirable sample paths, and loses its stability in an extreme case for the period to exceed the hard deadline in a real-time control system. In the paper, we propose an algorithm to combine the deadlines of all elementary tasks (derived formerly by our work) executed in several operation modes with multi-sampling periods. This results in computing the hard deadline of the entire system through modifying task-state equations to capture the effects of task failures and inter-correlations among tasks.
In a client-server system, when LRU or its variant buffer replacement strategy is used on both the client and the server, the cache performance on the server side is very poor mainly because of pages duplicated in both systems. This paper introduces a server buffer replacement strategy which uses a replaced page-id than a request page-id, for the primary information for its operations. The importance of the corresponding pages in the server cache is decided according to the replaced page-ids that are delivered from clients to the server, so that locations of the pages are altered. Consequently, if a client uses LRU as its buffer replacement strategy, then the server cache is seen by the client as a long virtual client LRU cache extended to the server. Since the replaced page-id is only sent to the server by piggybacking whenever a new page fetch request is sent, the operation to deliver the replaced page-id is simple and induces a minimal overhead. We show that the proposed strategy reveals good performance characteristics in diverse situations, such as single and multiple clients, as well as with various access patterns.
Hiroyuki KAMATA Yohei UMEZAWA Masamichi DOBASHI Tetsuro ENDO Yoshihisa ISHIDA
This paper proposes a private communication system with chaos using fixed-point digital computation. When fixed-point computation is adopted, chaotic properties of the modulated signal should be checked carefully as well as calculation error problems (especially, overflow problems). In this paper, we propose a novel chaos modem system for private communications including a chaotic neuron type nonlinearity, an unstable digital filter and an overflow function. We demonstrate that the modulated signal reveals hyperchaotic property within 10,000 data point fixed-point computation, and evaluate the security of this system in view of the sensitivity of coefficients for demodulation.
While the secure concurrency controllers (SCCs) in multilevel secure database systems (MLS/DBMSs) synchronize transactions cleared at different security levels, they must consider the problem of covert channel. We propose a new SCC, named Verified Order-based secure concurrency controller (VO) that founds on multiversion database. VO maintains elaborated information about ordering relationships among transactions in a way of actively investigating and renewing the ordering relationships whenever it receives operations. With the elaborated information, it becomes capable of aborting transactions selectively whose non-interfered executions definitely violate one-copy serializability and providing more recent data versions to read requests than the other multiversion-based SCCs. Therefore, it comes to reduce the abort ratio and provide data versions of improved trustworthiness to transactions. By virtue of the elaborated information, moreover, VO is able to distinguish worthful versions and worthful transactions from worthless ones, so that it is capable lightening the burdens of maintaining multiple versions and accumulated transaction ordering relationships. For the aborts that are inevitable for preserving one-copy serializability, VO achieves security by deriving the conflicts to occur between transactions that have been cleared at the same security level.
Asynchronous, distributed, decision-making (ADDM) systems constitute a special class of distributed problems and are characterized as large, complex systems wherein the principal elements are the geographically-dispersed entities that communicate among themselves, asynchronously, through message passing and are permitted autonomy in local decision-making. A fundamental property of ADDM systems is stability that refers to their behavior under representative perturbations to their operating environments, given that such systems are intended to be real, complex, and to some extent, mission critical systems, and are subject to unexpected changes in their operating conditions. ADDM systems are closely related to autonomous decentralized systems (ADS) in the principal elements, the difference being that the characteristics and boundaries of ADDM systems are defined rigorously. This paper introduces the concept of stability in ADDM systems and proposes an intuitive yet practical and usable definition that is inspired by those used in Control Systems and Physics. A comprehensive stability analysis on an accurate simulation model will provide the necessary assurance, with a high level of confidence, that the system will perform adequately. An ADDM system is defined as a stable system if it returns to a steady-state in finite time, following perturbation, provided that it is initiated in a steady-state. Equilibrium or steady-state is defined through placing bounds on the measured error in the system. Where the final steady-state is equivalent to the initial one, a system is referred to as strongly stable. If the final steady-state is potentially worse then the initial one, a system is deemed marginally stable. When a system fails to return to steady-state following the perturbation, it is unstable. The perturbations are classified as either changes in the input pattern or changes in one or more environmental characteristics of the system such as hardware failures. Thus, the key elements in the study of stability include steady-state, perturbations, and stability. Since the development of rigorous analytical models for most ADDM systems is difficult, if not impossible, the definitions of the key elements, proposed in this paper, constitute a general framework to investigate stability. For a given ADDM system, the definitions are based on the performance indices that must be judiciously identified by the system architect and are likely to be unique. While a comprehensive study of all possible perturbations is too complex and time consuming, this paper focuses on a key subset of perturbations that are important and are likely to occur with greater frequency. To facilitate the understanding of stability in representative real-world systems, this paper reports the analysis of two basic manifestations of ADDM systems that have been reported in the literature --(i) a decentralized military command and control problem, MFAD, and (ii) a novel distributed algorithm with soft reservation for efficient scheduling and congestion mitigation in railway networks, RYNSORD. Stability analysis of MFAD and RYNSORD yields key stable and unstable conditions.
A new elliptic curve scalar multiplication algorithm is proposed. The algorithm offers about twice the throughput of some conventional OEF-base algorithms because it combines the Frobenius map with the table reference method based on base-φ expansion. Furthermore, since this algorithm suits conventional computational units such as 16, 32 and 64 bits, its base field Fpm is expected to enhance elliptic curve operation efficiency more than Fq (q is a prime) or F2n.
Toshimitsu MASUZAWA Michiko INOUE
Distributed computation has attracted considerable attention and large-scale distributed systems have been designed and developed. A distributed system inherently has possibility of fault tolerance because of its redundancy. Thus, a great deal of investigation has been made to design fault-tolerant distributed algorithms. This paper introduces two promising paradigms, self-stabilization and wait-freedom, for designing fault-tolerant distributed algorithms and discusses some subjects important from the point of view of algorithm engineering.
Janson NAIBORHU Kiyotaka SHIMIZU
We study the problem of stabilizing a general nonlinear control system globally based on direct gradient descent control which is a dynamic feedback control law. The direct gradient descent control and the general nonlinear control system (original system) form a new system (extended system). Under an appropriate assumption we can make the extended system become globally asymptotically stable if its unforced system is stable in the sense of Lyapunov.
Teruyuki MIYAJIMA Fumihito BAISHO Kazuo YAMANAKA Kazuhiko NAKAMURA Masahiro AGU
A new phasor model of neural networks is proposed in which the state of each neuron possibly takes the value at the origin as well as on the unit circle. A stability property of equilibria is studied in association with the energy landscape. It is shown that a simple condition guarantees an equilibrium to be asymptotically stable.
Frank and Zadaff had proposed a class of polyphase orthogonal sequences. Now the sequences are called "Frank sequences. " Suehiro has proposed a modulation method for Frank sequences. For example, the number of 4-phase orthogonal sequences of period 16 is 32 by Suehiro's method, on the other hand, the number of 4-phase Frank sequences of period 16 is 2. In this paper, the modulation method is expanded again and we prove that the sequences obtained by the proposed method are polyphase orthogonal sequences. Furhtermore, we prove that the number of N-phase orthogonal sequences of period N2 obtained by the proposed method is NN-2(N-1)!. As a result of the proposed expansion, the number of 4-phase orthogonal sequences of period 16 is 96.
Thermal stability of anisotropic and isotropic Co alloy thin-film media is investigated. The orientation ratio of CoCrTa(Pt)/Cr media was controlled by the mechanical texture of the NiP/Al substrates. Bulk magnetic properties, delta M curves and time decay of magnetization in the circumferential and radial directions were measured. The maximum magnetic viscosity coefficient calculated from the time decay of magnetization in the circumferential direction was higher than that in the radial direction for a mechanically textured sample, while it was similar in both directions for a non-textured sample. The magnetic viscosity coefficient in the circumferential direction is smaller than that in the radial direction when the reverse field is in the range of the demagnetization field for thin-film recording media. This implies that an anisotropic sample (namely, a sample with a high orientation ratio) will be more thermally stable when it is not exposed to a large external magnetic field.
As many research works are based on some previous results, my paper, namely The Integrated Scheduling and Allocation of High-Level Test Synthesis, makes use of some techniques by T. Kim. However, I did not state explicitly that some parts of my work are based on Kim's approach although I have referred to his paper. I would like to express my deep apology to Kim for not having emphasized Kim's contribution to my work. But my intention was not to steal Kim's ideas. I would like to emphasize the following difference.
I would like to draw the attention of the editorial board of IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences and its readers to a recent paper, Tianruo Yang, "The integrated scheduling and allocation of high-level test synthesis," vol. E82-A, no. 1, January 1999, pp. 145-158. (Here we call this paper the Yang's paper. ) Yang did not give the correct information about the originality of the paper. I will point out that the writings (and the idea accordingly) of section 6 of Yang's paper came from papers [1] and [2].
Yoshiyuki SHINKAWA Masao J. MATSUMOTO
Adaptability evaluation of software systems is one of the key concerns in both software engineering and requirements engineering. In this paper, we present a formal and systematic approach to evaluate adaptability of software systems to requirements in enterprise business applications. Our approach consists of three major parts, that is, the common modeling method for both business realms and software realms, functional adaptability evaluation between the models with Σ algebra and behavioral adaptability evaluation with process algebra. By our approach, one can rigorously and uniquely determine whether a software system is adaptable to the requirements, either totally or partially. A sample application from an order processing is illustrated to show how this approach is effective in solving the adaptability evolution problem.