Taishi NAKASHIMA Satoshi FUJITA
This paper proposes a consistency maintenance scheme for P2P file sharing systems. The basic idea of the proposed scheme is to construct a static tree for each shared file to efficiently propagate the update information to all replica peers. The link to the root of the trees is acquired by referring to a Chord ring which stores the mapping from the set of shared files to the set of tree roots. The performance of the scheme is evaluated by simulation. The simulation result indicates that: 1) it reduces the number of messages in the Li's scheme by 54%, 2) it reduces the propagation delay of the scheme by more than 10%, and 3) the increase of the delay due to peer churns is effectively bounded provided that the percentage of leaving peers is less than 40%.
We consider single and multiple attacker scenarios in guessing and obtain bounds on various success parameters in terms of Renyi entropies. We also obtain a new derivation of the union bound.
You Sung KANG Dong-Jo PARK Daniel W. ENGELS Dooho CHOI
We present a dynamic key generation method, KeyQ, for establishing shared secret keys in EPCglobal Generation 2 (Gen2) compliant systems. Widespread adoption of Gen2 technologies has increased the need for protecting communications in these systems. The highly constrained resources on Gen2 tags limit the usability of traditional key distribution techniques. Dynamic key generation provides a secure method to protect communications with limited key distribution requirements. Our KeyQ method dynamically generates fresh secret keys based on the Gen2 adaptive Q algorithm. We show that the KeyQ method generates fresh and unique secret keys that cannot be predicted with probability greater than 10-250 when the number of tags exceeds 100.
Takumi HASEGAWA Tadashi TSUBONE
We consider an improved control method based on the Stability Transformation Method. Stability Transformation Method detects unknown and unstable periodic orbits of chaotic dynamical systems. Based on the approach to realize the Stability Transformation Method in real systems, we have proposed a control method which can stabilize unknown and unstable periodic orbits embedded in chaotic attractors. However, setting of the control parameters of the control system has remained as unsolved issue. When the dynamics of a target system are unknown, the control parameters have to be set by trial and error. In this paper, we improve the control method with the automatic adjustment function of the control parameters. We show an example of stabilizing unstable periodic orbits of the 3-dimensional hysteresis chaos generator by using the proposed control method. Some results are confirmed by laboratory measurements. The results imply that any unknown and unstable periodic orbits can be stabilized by using the proposed method, if the target chaos system is reduced to 1-dimensional return map.
This note presents a new approach for the robustness of Hurwitz polynomials under coefficient perturbation. The s-domain Hurwitz polynomial is transformed to the z-domain polynomial by the bilinear transformation. Then an approach based on the Rouché theorem introduced in the literature is applied to compute a crude bound for the allowable coefficient variation such that the perturbed polynomial maintains the Hurwitz stability property. Three methods to obtain improved bounds are also suggested. The results of this note are computationally more efficient than the existing direct s-domain approaches especially for polynomials of higher degree. Furthermore examples indicate that the exact bound for the coefficient variation can be obtained in some cases.
A new theorem is proposed on BIBO (Bounded Input Bounded Output) stability of a general feedback amplifier circuit formulated by BIBO operators. The proposed theorem holds for both linear and nonlinear BIBO operators. The meaning of this theorem is clarified by applying it to continuous-time linear cases.
Jun ISHII Hiroyuki MAEOMICHI Akihiro TSUTSUI Ikuo YODA
This paper propose a novel method for obtaining statistical results such as averages, variances, and correlations without leaking any raw data values from data-holders by using multiple pseudonyms. At present, to obtain statistical results using a large amount of data, we need to collect all data in the same storage device. However, gathering real-world data that were generated by different people is not easy because they often contain private information. The authors split the roles of servers into publishing pseudonyms and collecting answers. Splitting these roles, different entities can more easily join as pseudonym servers than in previous secure multi-party computation methods and there is less chance of collusion between servers. Thus, our method enables data holders to protect themselves against malicious attacks from data users. We also estimated a typical problem that occurred with our method and added a pseudonym availability confirmation protocol to prevent the problem. We report our evaluation of the effectiveness of our method through implementation and experimentation and discuss how we incorporated the WebSocket protocol and MySQL Memoty Storage Engine to remove the bottleneck and improve the implementation style. Finally, we explain how our method can obtain averages, variances, and correlation from 5000 data holders within 50 seconds.
This letter introduces a new reference frame to improve the performance of motion estimation and compensation in video coding, based on a video stabilization technique. The proposed method synthesizes the new reference frame from the previous frame in a way that the new reference and current frames have the same camera orientations. The overhead data for each frame to transmit from an encoder to a decoder is only three rotational angles along the x, y, and z axes. Since the new reference and current frames have the same camera orientations, the proposed method significantly improves the performance of motion estimation and compensation for video sequences having dynamic camera motion by up to 0.98 dB with negligible overhead data.
Hoaison NGUYEN Yasuo TAN Yoichi SHINODA
At present, vast numbers of information resources are available on the Internet. However, one emerging issue is how to search and exploit these information resources in an efficient and flexible manner with high scalability. In this study, we focused our attention on the design of a distributed hash table (DHT)-based search system that supports efficient scalable multi-attribute queries of information resources in a distributed manner. Our proposed system, named D-AVTree, is built on top of a ring-based DHT, which partitions a one-dimensional key space across nodes in the system. It utilizes a descriptive naming scheme, which names each resource using an attribute-value (AV) tree, and the resource names are mapped to d-bit keys in order to distribute the resource information to responsible nodes based on a DHT routing algorithm. Our mapping scheme maps each AV branch of a resource name to a d-bit key where AV branches that share a subsequence of AV pairs are mapped to a continuous portion of the key space. Therefore, our mapping scheme ensures that the number of resources distributed to a node is small and it facilitates efficient multi-attribute queries by querying only a small number of nodes. Further, the scheme has good compatibility with key-based load balancing algorithms for DHT-based networks. Our system can achieve both efficiency and a good degree of load balancing even when the distribution of AV pairs in the resource names is skewed. Our simulation results demonstrated the efficiency of our solution in terms of the distribution cost, query hit ratio, and the degree of load balancing compared with conventional approaches.
We design a full-order observer for discrete-time linear time-invariant systems with constant output delays. The observer design is based on the output delay model expressed by a two-dimensional state variable, with discrete-time and space independent variables. Employing a discrete-time state transformation, we construct an explicit strict Lyapunov function that enables us to prove the global exponential stability of the full-order observer error system with an explicit estimate of the exponential decay rate. The numerical example demonstrates the design of the full-order observer and illustrates the validity of the exponential stability.
In-Joong KIM Kyu-Young WHANG Hyuk-Yoon KWON
A top-k keyword query in relational databases returns k trees of tuples — where the tuples containing the query keywords are connected via primary key-foreign key relationships — in the order of relevance to the query. Existing works are classified into two categories: 1) the schema-based approach and 2) the schema-free approach. We focus on the former utilizing database schema information for more effective ranking of the query results. Ranking measures used in existing works can be classified into two categories: 1) the size of the tree (i.e., the syntactic score) and 2) ranking measures, such as TF-IDF, borrowed from the information retrieval field. However, these measures do not take into account semantic relevancy among relations containing the tuples in the query results. In this paper, we propose a new ranking method that ranks the query results by utilizing semantic relevancy among relations containing the tuples at the schema level. First, we propose a structure of semantically strongly related relations, which we call the strongly related tree (SRT). An SRT is a tree that maximally connects relations based on the lossless join property. Next, we propose a new ranking method, SRT-Rank, that ranks the query results by a new scoring function augmenting existing ones with the concept of the SRT. SRT-Rank is the first research effort that applies semantic relevancy among relations to ranking the results of keyword queries. To show the effectiveness of SRT-Rank, we perform experiments on synthetic and real datasets by augmenting the representative existing methods with SRT-Rank. Experimental results show that, compared with existing methods, SRT-Rank improves performance in terms of four quality measures — the mean normalized discounted cumulative gain (nDCG), the number of queries whose top-1 result is relevant to the query, the mean reciprocal rank, and the mean average precision — by up to 46.9%, 160.0%, 61.7%, and 63.8%, respectively. In addition, we show that the query performance of SRT-Rank is comparable to or better than those of existing methods.
Chuang WANG Zunchao LI Cheng LUO Lijuan ZHAO Yefei ZHANG Feng LIANG
A novel auto-tuning digital DC--DC converter is presented. In order to reduce the recovery time and undershoot, the auto-tuning control combines LnL, conventional PID and a predictive PID with a configurable predictive coefficient. A switch module is used to select an algorithm from the three control algorithms, according to the difference between the error signal and the two initially predefined thresholds. The detection and control logic is designed for both window delay line ADC and $Sigma Delta$ DPWM to correct the delay deviation. When the output of the converter exceeds the quantization range, the digital output of ADC is set at 0 or 1, and the delay line stops working to reduce power consumption. Theoretical analysis and simulations in the CSMC CMOS 0.5,$mu$m process are carried out to verify the proposed DC--DC converter. It is found that the converter achieves a power efficiency of more than 90% at heavy load, and reduces the recovery time and undershoot.
Young-Woong KO Min-Ja KIM Jeong-Gun LEE Chuck YOO
In this paper, we propose a new user-level file system to support block relocation by modifying the file allocation table without actual data copying. The key idea of the proposed system is to provide the block insertion and deletion function for file manipulation. This approach can be used very effectively for block-aligned file modification applications such as a compress utility and a TAR archival system. To show the usefulness of the proposed file system, we adapted the new functionality to TAR application by modifying TAR file to support an efficient sub-file management scheme. Experiment results show that the proposed system can significantly reduce the file I/O overhead and improve the I/O performance of a file system.
Wei CHOON TAY Eng LEONG TAN Ding YU HEH
This paper presents a fundamental locally one-dimensional (FLOD) method for 3-D thermal simulation. We first propose a locally one-dimensional (LOD) method for heat transfer equation within general inhomogeneous media. The proposed LOD method is then cast into compact form and formulated into the FLOD method with operator-free right-hand-side (RHS), which leads to computationally efficient update equations. Memory storage requirements and boundary conditions for both FLOD and LOD methods are detailed and compared. Stability analysis by means of analyzing the eigenvalues of amplification matrix substantiates the stability of the FLOD method. Additionally, the potential instability of the Douglas Gunn (DG) alternating-direction-implicit (ADI) method for inhomogeneous media is demonstrated. Numerical experiments justify the gain achieved in the overall efficiency for FLOD over LOD, DG-ADI and explicit methods. Furthermore, the relative maximum error of the FLOD method illustrates good trade-off between accuracy and efficiency.
Ahmad Iqbal Hakim SUHAIMI Yuichi GOTO Jingde CHENG
Information Security Management Systems (ISMSs) play important roles in helping organizations to manage their information securely. However, establishing, managing, and maintaining ISMSs is not an easy task for most organizations because an ISMS has many participants and tasks, and requires many kinds of documents. Therefore, organizations with ISMSs demand tools that can support them to perform all tasks in ISMS lifecycle processes consistently and continuously. To realize such support tools, a database system that manages ISO/IEC 27000 series, which are international standards for ISMSs, and ISMS documents, which are the products of tasks in ISMS lifecycle processes, is indispensable. The database system should manage data of the standards and documents for all available versions and translations, relationship among the standards and documents, authorization to access the standards and documents, and metadata of the standards and documents. No such database system has existed until now. This paper presents an information security management database system (ISMDS) that manages ISO/IEC 27000 series and ISMS documents. ISMDS is a meta-database system that manages several databases of standards and documents. ISMDS is used by participants in ISMS as well as tools supporting the participants to perform tasks in ISMS lifecycle processes. The users or tools can retrieve data from all versions and translations of the standards and documents. The paper also presents some use cases to show the effectiveness of ISMDS.
An-Sheng CHAO Cheng-Wu LIN Hsin-Wen TING Soon-Jyh CHANG
The proposed stimulus design for linearity test is embedded in a differential successive approximation register analog-to-digital converter (SAR ADC), i.e. a design for testability (DFT). The proposed DFT is compatible to the pattern generator (PG) and output response analyzer (ORA) with the cost of 12.4-% area of the SAR ADC. The 10-bit SAR ADC prototype is verified in a 0.18-µm CMOS technology and the measured differential nonlinearity (DNL) error is between -0.386 and 0.281 LSB at 1-MS/s.
In this paper, we show a connection between #P and computing the (real) value of the high order derivative at the origin. Consider, as a problem instance, an integer b and a sufficiently often differentiable function F(x) that is given as a string. Then we consider computing the value F(b)(0) of the b-th derivative of F(x) at the origin. By showing a polynomial as an example, we show that we have FP = #P if we can compute log 2F(b)(0) up to certain precision. The previous statement holds even if F(x) is limited to a function that is analytic at any x ∈ R. It implies the hardness of computing the b-th value of a number sequence from the closed form of its generating function.
This paper proposes a new approach to defining and expressing algorithms: the notion of task logical algorithms. This notion allows the user to define an algorithm for a task T as a set of agents who can collectively perform T. This notion considerably simplifies the algorithm development process and can be seen as an integration of the sequential pseudocode and logical algorithms. This observation requires some changes to algorithm development process. We propose a two-step approach: the first step is to define an algorithm for a task T via a set of agents that can collectively perform T. The second step is to translate these agents into (higher-order) computability logic.
Takako NAKATANI Shozo HORI Keiichi KATAMINE Michio TSUDA Toshihiko TSUMAKI
The success of any project can be affected by requirements changes. Requirements elicitation is a series of activities of adding, deleting, and modifying requirements. We refer to the completion of requirements elicitation of a software component as requirements maturation. When the requirements of each component have reached the 100% maturation point, no requirement will come to the component. This does not mean that a requirements analyst (RA) will reject the addition of requirements, but simply, that the additional requirements will not come to the project. Our motivation is to provide measurements by which an RA can estimate one of the maturation periods: the early, middle, or late period of the project. We will proceed by introducing the requirements maturation efficiency (RME). The RME of the requirements represents how quickly the requirements of a component reach 100% maturation. Then, we will estimate the requirements maturation period for every component by applying the RME. We assume that the RME is derived from its accessibility from an RA to the requirements source and the stability of the requirements. We model accessibility as the number of information flows from the source of the requirements to the RA, and further, model stability with the requirements maturation index (RMI). According to the multiple regression analysis of a case, we are able to get an equation on RME derived from these two factors with a significant level of 5%. We evaluated the result by comparing it to another case, and then discuss the effectiveness of the measurements.
With the development of global navigation satellite systems (GNSS), the interference among global navigation satellite systems, known as the radio frequency compatibility problem, has become a matter of great concern to system providers and user communities. The acceptable compatibility threshold should be determined in the radio frequency compatibility assessment process. However, there is no common standard for the acceptable threshold in the radio frequency compatibility assessment. This paper firstly introduces the comprehensive radio frequency compatibility methodology combining the spectral separation coefficient (SSC) and code tracking spectral sensitivity coefficient (CT_SSC). Then, a method for determination of the acceptable compatibility threshold is proposed. The proposed method considers the receiver processing phase including acquisition, code and carrier tracking and data demodulation. Simulations accounting for the interference effects are carried out at each time step and every place on earth. The simulations mainly consider the signals of GPS, Galileo and BeiDou Navigation Satellite System (BDS) in the L1 band. Results show that all of the sole systems are compatible with other GNSS systems with respect to a special receiver configuration used in the simulations.