Sep 2007, Volume 1 Issue 3
    

  • Select all
  • Search an unsorted database with quantum mechanics
    LONG Guilu, LIU Yang
    2007, 1(3): 247-271. https://doi.org/10.1007/s11704-007-0026-z
    Download PDF
    In this article, we review quantum search algorithms for unsorted database search problem. Unsorted database search is a very important problem in science and technology. In a quantum computer, a marked state can be found with very high probability using the Grover's algorithm, or exactly with the Long algorithm. We review the Grover algorithm and related generalizations. In particular, we review the phase matching conditions in quantum search algorithm. Several issues that may cause confusion about the quantum search algorithm are also clarified.
  • An overview of the haplotype problems and algorithms
    ZHAO Yuzhong, XU Yun, ZHANG Qiangfeng, CHEN Guoliang
    2007, 1(3): 272-282. https://doi.org/10.1007/s11704-007-0027-y
    Download PDF
    A single nucleotide polymorphism (SNP), as the most common form of genetic variation, has been widely studied to help analyze the possible association between diseases and genomes. To gain more information, SNPs on a single chromosome are usually studied together, which constitute a haplotype. Gaining haplotypes from biological experiments is usually very costly and time-consuming, which causes people to develop efficient methods to determine haplotypes from the computational angle. Many problems and algorithms about haplotypes have been proposed to reduce the cost of studies of disease association. In general, four categories of problems are widely researched: the haplotype assembly problem, the haplotype inference problem, the haplotype block partition problem, and the haplotype tagging SNP selection problem. The former two problems have been well reviewed by many researchers, whereas the latter two have not been comprehensively surveyed to our knowledge. In this paper, we try to make a detailed introduction to the four problems, especially the latter two.
  • Well limit behaviors of term rewriting systems
    MA Shilong, XU Ke, SUI Yuefei
    2007, 1(3): 283-296. https://doi.org/10.1007/s11704-007-0028-x
    Download PDF
    The limit behaviors of computations have not been fully explored. It is necessary to consider such limit behaviors when we consider the properties of infinite objects in computer science, such as infinite logic programs, the symbolic solutions of infinite polynomial equations. Usually, we can use finite objects to approximate infinite objects, and we should know what kinds of infinite objects are approximable and how to approximate them effectively. A sequence {Rk: k∈ω} of term rewriting systems has the well limit behavior if under the condition that the sequence has the set-theoretic limit or the distance-based limit, the sequence {Th(Rk): k∈ω} of corresponding theoretic closures of Rk has the set-theoretic or distance-based limit, and limk →∞ Th(Rk) is equal to the theoretic closure of the limit of {Rk: k∈ω}. Two kinds of limits of term rewriting systems are considered: one is based on the set-theoretic limit, the other is on the distance-based limit. It is proved that given a sequence {Rk: k∈ω} of term rewriting systems Rk, if there is a well-founded ordering ? on terms such that every Rk is ? -well-founded, and the set-theoretic limit of {Rk: k∈ω} exists, then {Rk: k∈ω} has the well limit behavior; and if (1) there is a well-founded ordering ? on terms such that every Rk is ? -well-founded, (2) there is a distance d on terms which is closed under substitutions and contexts and (3) {Rk: k∈ω} is Cauchy under d then {Rk: k∈ω} has the well limit behavior. The results are used to approximate the least Herbrand models of infinite Horn logic programs and real Horn logic programs, and the solutions and Gröbner bases of (infinite) sets of real polynomials by sequences of (finite) sets of rational polynomials. two.
  • A pointer logic and certifying compiler
    CHEN Yiyun, GE Lin, HUA Baojian, LI Zhaopeng, LIU Cheng, WANG Zhifang
    2007, 1(3): 297-312. https://doi.org/10.1007/s11704-007-0029-9
    Download PDF
    Proof-Carrying Code brings two big challenges to the research field of programming languages. One is to seek more expressive logics or type systems to specify or reason about the properties of low-level or high-level programs. The other is to study the technology of certifying compilation in which the compiler generates proofs for programs with annotations. This paper presents our progress in the above two aspects. A pointer logic was designed for PointerC (a C-like programming language) in our research. As an extension of Hoare logic, our pointer logic expresses the change of pointer information for each statement in its inference rules to support program verification. Meanwhile, based on the ideas from CAP (Certified Assembly Programming) and SCAP (Stack-based Certified Assembly Programming), a reasoning framework was built to verify the properties of object code in a Hoare style. And a certifying compiler prototype for PointerC was implemented based on this framework. The main contribution of this paper is the design of the pointer logic and the implementation of the certifying compiler prototype. In our certifying compiler, the source language contains rich pointer types and operations and also supports dynamic storage allocation and deallocation.
  • Research on dynamic update transaction for Java classes
    ZHANG Shi, HUANG Linpeng
    2007, 1(3): 313-321. https://doi.org/10.1007/s11704-007-0030-3
    Download PDF
    Dynamic software updating is critical for many systems that must provide continuous service. In addition, the Java language is gaining increasing popularity in developing distributed systems. Most previous works on updating are concerned with safely updating one class every time. It has many limitations on updating classes, such as not allowing deleting methods invoked in other classes. In this paper, the update transaction is purposed to dynamically update the class set, and some of its properties are discussed, such as atomicity, consistency, isolation, and durability (ACID). Then the property of type-safety is proven formally. In order to update without changing the Java Virtual Machine (JVM) and the Java programming language, this paper proposes a new implementation method. The method makes use of the Java class loading mechanism and reflection mechanism. We also present how to design an updatable Java program and a Java updating program. At the end of the paper, an experiment is made for analysis.
  • Requirement emergence computation of networked software
    HE Keqing, LIANG Peng, PENG Rong, LI Bing, LIU Jing
    2007, 1(3): 322-328. https://doi.org/10.1007/s11704-007-0031-2
    Download PDF
    Emergence Computation has become a hot topic in the research of complex systems in recent years. With the substantial increase in scale and complexity of network-based information systems, the uncertain user requirements from the Internet and personalized application requirement result in the frequent change for the software requirement. Meanwhile, the software system with non self-possessed resource become more and more complex. Furthermore, the interaction and cooperation requirement between software units and running environment in service computing increase the complexity of software systems. The software systems with complex system characteristics are developing into the Networked Software  with characteristics of change-on-demand and change-with-cooperation. The concepts programming , compiling  and running  of software in common sense are extended from desktop  to network . The core issue of software engineering is moving to the requirement engineering, which becomes the research focus of complex system software engineering. In this paper, we present the software network view based on complex system theory, and the concept of networked software and networked requirement. We propose the challenge problem in the research of emergence computation of networked software requirement. A hierarchical & cooperative unified requirement modeling framework URF (Unified Requirement Framework) and related RGPS (Role, Goal, Process and Service) meta-models are proposed. Five scales and the evolutionary growth mechanism in requirement emergence computation of networked software are given with focus on user-dominant and domain-oriented requirement, and the rules and predictability in requirement emergence computation are analyzed. A case study in the application of networked e-Business with evolutionary growth based on State design pattern is presented in the end.
  • Performance analysis of a dependable scheduling strategy based on a fault-tolerant grid model
    WANG Yuanzhuo, LIN Chuang, YANG Yang, SHAN Zhiguang
    2007, 1(3): 329-337. https://doi.org/10.1007/s11704-007-0032-1
    Download PDF
    The grid provides an integrated computer platform composed of differentiated and distributed systems. These resources are dynamic and heterogeneous. In this paper, a novel fault-tolerant grid-scheduling model is presented based on Stochastic Petri Nets (SPN) to assure the heterogeneity and dynamism of the grid system. Also, a new grid-scheduling strategy, the dependable strategy for the shortest expected accomplishing time (DSEAT), is put forward, in which the dependability factor is introduced in the task-dispatching strategy. In the end, the performance of the scheduling strategy based on the fault-tolerant grid-scheduling model is analyzed by an software package, named SPNP. The numerical results show that dynamic resources will increase the response time for all classes of tasks in differing degrees. Compared with shortest expected accomplishing time (SEAT) strategy, the DSEAT strategy can reduce the negative effects of dynamic and autonomic resources to some extent so as to guarantee a high quality of service (QoS).
  • An optimal replication strategy for data grid systems
    JIANG Jianjin, YANG Guangwen
    2007, 1(3): 338-348. https://doi.org/10.1007/s11704-007-0033-0
    Download PDF
    Data access latency is an important metric of system performance in data grid. By means of efficient replication strategy, the amount of data transferred in a wide area network will decrease, and the average access latency of data will decrease ultimately. The motivation of our research is to solve the optimized replica distribution problem in a data grid; that is, the system should utilize many replicas for every data with storage constraints to minimize the average access latency of data. This paper proposes a model of replication strategy in federated data grid and gives the optimized solution. The analysis results and simulation results show that the optimized replication strategy proposed in this paper is superior to LRU caching strategy, uniform replication strategy, proportional replication strategy and square root replication strategy in terms of wide area network bandwidth requirement and in the average access latency of data.
  • High TPO/TCO for data storage: policy, algorithm and early practice
    ZENG Lingfang, FENG Dan, JIANG Hong
    2007, 1(3): 349-360. https://doi.org/10.1007/s11704-007-0034-z
    Download PDF
    Today, the data storage industry faces a rapidly growing volume of data. Adding more primary disk capacity to manage data growth is a costly and non-sustainable strategy. Before investing in new capacity, data managers should rationalize their existing storage infrastructure to maximize the use of existing capacity. There is a growing need for achieving a high ratio of Total Performance of Ownership (TPO) to Total Cost of Ownership (TCO), or TPO/TCO. The storage infrastructure can be made more efficient by assessing data usages, eliminating unnecessary data copies, moving less critical data to less expensive disk devices and repurposing allocated but unused capacity. Optimizing existing storage assets can reduce storage costs by delaying or eliminating the need for new primary capacity to manage information growth. In this paper, we apply the notion of information lifecycle management (ILM) to achieve the above improved efficiencies and optimizations. By balancing data value and storage requirements, we aim to reduce the storage system s dependence on expensive high- performance disk devices and lower its cost per online gigabyte, thus resulting in a higher TPO/TCO.
  • A hierarchical model for structure learning based on the physiological characteristics of neurons
    WEI Hui
    2007, 1(3): 361-372. https://doi.org/10.1007/s11704-007-0035-y
    Download PDF
    Almost all applications of Artificial Neural Networks (ANNs) depend mainly on their memory ability. The characteristics of typical ANN models are fixed connections, with evolved weights, globalized representations, and globalized optimizations, all based on a mathematical approach. This makes those models to be deficient in robustness, efficiency of learning, capacity, anti-jamming between training sets, and correlativity of samples, etc. In this paper, we attempt to address these problems by adopting the characteristics of biological neurons in morphology and signal processing. A hierarchical neural network was designed and realized to implement structure learning and representations based on connected structures. The basic characteristics of this model are localized and random connections, field limitations of neuron fan-in and fan-out, dynamic behavior of neurons, and samples represented through different sub-circuits of neurons specialized into different response patterns. At the end of this paper, some important aspects of error correction, capacity, learning efficiency, and soundness of structural representation are analyzed theoretically. This paper has demonstrated the feasibility and advantages of structure learning and representation. This model can serve as a fundamental element of cognitive systems such as perception and associative memory.