In this paper we study a classical firing squad synchronization problem on a model of fault-tolerant cellular automata that have possibly some defective cells. Several fault-tolerant time-efficient synchronization algorithms are developed based on a simple freezing-thawing technique. It is shown that, under some constraints on the distribution of defective cells, any cellular array of length n with p defective cell segments can be synchronized in 2n - 2 + p steps.

Fast algorithms for computing the running type-I discrete sine transform (DST-I) and type-III discrete sine transform (DST-III) are proposed. The algorithms are based on a recursive relationship between three subsequent local discrete sine spectra. The computational complexity of the algorithms is compared with that of fast DST-I and DST-III algorithms. Fast inverse algorithms for signal processing in the running discrete sine transform domains are also proposed.

The capabilities of reliable computations in one-dimensional cellular automata are investigated by means of the Early Bird Problem. The problem is typical for situations in massively parallel systems where a global behavior must be achieved by only local interactions between the single elements. The cells that cause the misoperations are assumed to behave as follows. They run a self-diagnosis before the actual computation once. The result is stored locally such that the working state of a cell becomes visible to its neighbors. A non-working (defective) cell cannot modify information but is able to transmit it unchanged with unit speed. We present an O(n log (n) log (n))-time fault-tolerant solution of the Early Bird Problem.

The number and location of the inventory centers play an important role in the material distribution process since residents and inventory centers may be in dispersed regions. In this paper, we view the problem of finding the better locations for the inventory centers as an optimization problem, and propose a nested genetic algorithm (NGA) approach to design an optimal material distribution system. We demonstrate the feasibility of the proposed approach by numerical experiments.

The IP routing lookup problem is equivalent to finding the longest prefix of a packet's destination address in a routing table. It is a challenging problem to design a high performance IP routing lookup architecture, because of increasing traffic, higher link speed, frequent updates and increasing routing table size. At first, increasing traffic and higher link speed require that the IP routing can be executed at wire speed. Secondly, frequent routing table updates require that the insertion and deletion operations should be simple and low delay. At last, increasing routing table size hopes that less memory is used in order to reduce cost. Although many schemes to achieve fast lookup exist, less attention is paid on the latter two factors. This paper proposed a novel pipelined IP routing lookup architecture using selective binary search on hash table organized by prefix lengths. The evaluation results show that it can perform IP lookup operations at a maximum rate of one lookup per cycle. The hash operation ratio for one lookup can be reduced to about 1%, less than two hash operations are needed for one table update and only 512 kbytes SRAM is needed for a routing table with about 43000 prefixes. It proves to have higher performance than the existing schemes.

An Ad Hoc network is a collection of wireless mobile nodes dynamically forming a temporary network without the use of any existing network infrastructure or centralized administration. The choice of medium access is difficult in Ad Hoc networks due to the time-varying network topology and the lack of centralized control. In this paper, we propose a novel multichannel schedule-based Medium Access Control (MAC) protocol for Ad Hoc networks named Multichannel Reservation Protocol for TDMA-based networks (MRPT). MRPT ensures collision free in successfully reserved data links, even when hidden terminals exist. The reservation of MRPT is based a control channel and in order to improve throughput we propose Four-Phase-Two-Division (FPTD) as a media access scheme of the control channel for broadcasting control or reservation messages. In FPTD, the collision can be solved rapidly with an efficient backoff algorithm which results in that system block is avoided in case of high traffic. In this paper, we also present the throughput performance of MRPT, which shows a high value and no system block even in case of high traffic load.

A "based" plane triangulation is a plane triangulation with one designated edge on the outer face. In this paper we give a simple algorithm to generate all biconnected based plane triangulations having exactly n vertices and with the maximum degree exactly D. The algorithm uses O(n) space and generates such triangulations in O(1) time per triangulation without duplications.

We present a learning algorithm of the Hopfield neural network for minimizing edge crossings in linear drawings of nonplanar graphs. The proposed algorithm uses the Hopfield neural network to get a local optimal number of edge crossings, and adjusts the balance between terms of the energy function to make the network escape from the local optimal number of edge crossings. The proposed algorithm is tested on a variety of graphs including some "real word" instances of interconnection networks. The proposed learning algorithm is compared with some existing algorithms. The experimental results indicate that the proposed algorithm yields optimal or near-optimal solutions and outperforms the compared algorithms.

A web community is a set of web pages that provide resources on a specific topic. Various methods for finding web communities based on link analysis have been proposed in the literature. The method proposed in this paper is based on the method using the maximum flow algorithm proposed in. Our objective of using the maximum flow algorithm is to extract a subgraph which can be recognized as a good web community in the context of the quantity and the quality. This paper first discusses the features of the maximum flow algorithm based method. The previously proposed approach has a problem that a certain graph structure containing noises (i.e., irrelevant pages) is always extracted. This problem is mainly caused by edge capacities assigned a constant value. This paper proposes an assignment of variable edge capacities that are based on hub and authority scores obtained from HITS calculation. To examine the effects of our proposed method, we performed experiments using a Japanese archive crawled in February 2002. Our experimental results demonstrate that our proposed method removes noise pages caused by constant edge capacities and improves the quality of web communities.

Self-stabilization is a theoretical framework of non-masking fault-tolerant distributed algorithms. In this paper, we investigate the Steiner tree problem in distributed systems, and propose a self-stabilizing heuristic solution to the problem. Our algorithm is constructed by four layered modules (sub-algorithms): construction of a shortest path forest, transformation of the network, construction of a minimum spanning tree, and pruning unnecessary links and processes. Competitiveness is 2(1-1/l), where l is the number of leaves of optimal solution.

In this paper, we consider the problem of constructing a multicast tree in the star graph under the single-port communication model. Unlike previous studies for constructing space-efficient multicast trees, we adopt the completion time of each multicast as the objective function to be minimized. In particular, we study a special case of the problem in which all destination vertices are immediate neighbors of the source vertex, and propose a multicast scheme for the star graph of dimension n in 1.3125log2 n + O(log log n) time units. This running time is at most 1.3125 times of that of an optimal scheme.

Group mutual exclusion is an interesting generalization of the mutual exclusion problem. This problem was introduced by Joung, and some algorithms for the problem have been proposed by incorporating mutual exclusion algorithms. Group mutual exclusion occurs naturally in a situation where a resource can be shared by processes of the same group, but not by processes of a different group. It is also called the congenial talking philosophers problem. In this paper we propose two algorithms based on ticket orders for the group mutual exclusion problem on the asynchronous shared memory model. These algorithms are some modifications of the Bakery algorithm. They satisfy lockout freedom and a high degree of concurrency performance. Each of these algorithms uses single-writer shared variables together with two multi-writer shared variables that are never concurrently written. One of these algorithms has another desirable property, called smooth admission. By this property, during the period that the resource is occupied by the leader (called the chair), a process wishing to join the same group as the leader's group can be granted use of the resource in constant time.

Nearly 1/f processes are known as important stochastic models for scale invariant data analysis in a number of fields. In this paper, two parameter estimation methods of nearly 1/f processes based on wavelets are proposed. The conventional method based on wavelet transform with EM algorithm does not give the reliable parameter estimation value when the data length is short. Moreover, the precise parameter value is not estimated when the spectrum gap exists in 1/f processes. First, in order to improve the accuracy of the estimation when the data length is short, a parameter estimation method based on wavelet transform with complementary sampling is proposed. Next, in order to reduce the effect of spectrum gap, a parameter estimation method based on wavelet packet with EM algorithm is proposed. Simulation results are given to verify the effectiveness of the proposed methods.

This paper examines the properties of the greatest subsolution for linear equations in the max-plus algebra. The greatest subsolution is a relaxed solution of the linear equations, and gives a unified and reasonable solution whether there exists a strict solution or not. Accordingly, it forms part of a key algorithm for deriving a control law in the field of controller design, and some effective controllers based on the greatest subsolution have been proposed. However, there remain several issues to be discussed regarding the properties of the greatest subsolution. Hence, the main focus of this paper is on the following fundamental properties: 1) Formulation as an optimization problem, 2) Uniqueness of the greatest subsolution, 3) Necessary and sufficient condition for the correspondence of the greatest subsolution with the strict solution. These results could provide flexibility of the controller design based on the greatest subsolution, and facilitate the performance evaluation of the controller. Finally, the uniqueness of the strict solution of the linear equations is examined, and it is confirmed through illustrative examples.

This paper presents a strictly time- and communication-optimal distributed sorting algorithm in a line network. A strictly time-optimal distributed sorting algorithm in a line network has already been designed. However, its communication complexity is not strictly optimal and it seems to be difficult to extend it to other problems, such as that related to multiple elements in a process, and also the dynamic sorting problem where the number of elements each process should have as its solution is not the same as that in the initial state. Therefore, the algorithm in this paper was designed by an alternative approach to make it strictly time- and communication-optimal. Moreover, an extension to the dynamic sorting problem is described.

Simple genetic algorithm (SGA) is a population-based optimization method based on the Darwinian natural selection. The theoretical foundations of SGA are the Schema Theorem and the Building Block Hypothesis. Although SGA does well in many applications as an optimization method, it still does not guarantee the convergence of a global optimum in GA-hard problems and deceptive problems. As an alternative schema, therefore, there is a growing interest in a co-evolutionary system where two populations constantly interact and cooperate each other. In this paper we propose a schema co-evolutionary algorithm (SCEA) and show why the SCEA works better than SGA in terms of an extended schema theorem. The experimental analyses using the Walsh-Schema Transform show that the SCEA works well in GA-hard problems including deceptive problems.

In this paper, we describe a technique for optimizing the algebraic method that is applied to higher order differential attack. The higher order differential attack is a well-known attack on block ciphers, in which we derive an attack equation to determine a round key from a property of a higher order differential of a target block cipher. The algebraic method is a linearization of the attack equation and determines the true key by a method such as Gaussian elimination. Our technique is based on linear dependency and can reduce the complexity of that method. We also describe a technique that allows the algebraic method to be used as an attack equation that holds probabilistically. We demonstrate this method by attacking a five-round MISTY1 and show that it needs 221.6 chosen plaintexts and 228.0 encryption times. The computer simulation took about two minutes to complete.

Concurrency in the computing systems using a deadlock avoidance strategy varies largely according to the way that resource usage plan of process is used in testing the possibility of deadlocks. If a detailed resource usage plan of process is to be taken into account, the deadlock avoidance problem is known to be NP-complete. A decomposition model to manage resources is proposed, where process is logically partitioned into a number of segments each of which uses at least one resource. It is shown that one of our deadlock avoidance algorithms achieves the best concurrency among the polynomial-bounded algorithms. We also present a heuristic algorithm that achieves concurrency close to the optimal one. Finally, we analyze concurrency of various algorithms.

In 1999, Boneh et al. proposed the Lattice Factoring Method (LFM) for the integer factoring problem for a composite of the form N = prq by employing the LLL-algorithm. Time complexity of LFM is measured by the number of calls of the LLL-algorithm. In the worst case, the number is 2log p for a certain constant c. In 2001, Uchiyama and Kanayama introduced a novel criterion and provided an improved algorithm which runs (2k-p)/|p-Nr+1| times faster (for certain constants k, Nr+1). In this letter, we note another practical improvement applicable to the original and the improved LFM, which enables to provide about 2 times speed-up.

The baby-step giant-step algorithm, BSGS for short, was proposed by Shanks in order to compute the class number of an imaginary quadratic field. This algorithm is at present known as a very useful tool for computing with respect to finite groups such as the discrete logarithms and counting the number of the elements. Especially, the BSGS is normally made use of counting the rational points on the Jacobian of a hyperelliptic curve over a finite field. Indeed, research on the practical improvement of the BSGS has recently received a lot of attention from a cryptographic viewpoint. In this paper, we explicitly analyze the modified BSGS, which is for non-uniform distributions of the group order, proposed by Blackburn and Teske. More precisely, we refine the Blackburn-Teske algorithm, and also propose a criterion for the decision of the effectiveness of their algorithm; namely, our proposed criterion explicitly shows that what distribution is needed in order that their proposed algorithm is faster than the original BSGS. That is, we for the first time present a necessary and sufficient condition under which the modified BSGS is effective.