Hybrid journal (It can contain Open Access articles) ISSN (Print) 0010-4620 - ISSN (Online) 1460-2067 Published by Oxford University Press[370 journals]

Authors:Chen W; Ling S. Abstract: AbstractCycle embedding in networks is one of the fundamental algorithmic issues in interconnection networks. Biswapped networks are a family of composite interconnection networks, applicable to constructing massive parallel computers owing to their attractive attributes. Specifically, each biswapped network is built by taking 2n copies of some n-node factor network as modules and connecting them in a simple inter-module connectivity rule. In this paper, the problem of embedding cycles of various lengths in a biswapped network is investigated based on a given cycle of length l≥3 in its factor network. We propose a simple method to address the problem. Using the method, one easily constructs cycles of all even lengths ranging from 8 to 2l2, and also cycles of all odd lengths ranging from l+6 to 2l2−1 for l being odd in the biswapped network. Together with the known property that a biswapped network inherits the node-symmetry of its factor network, these results indicate that if an n-node factor network is Hamiltonian, then the biswapped network enjoys 8-node-bipancyclicity, and also (n+5)-node-pancyclicity for n being odd. The basic technique behind our method comes from the observation that a cycle of a given length in the biswapped network can be constructed from two associated combined closed walks in the factor network. By constructing combined closed walks of different lengths in the factor network, we can build cycles of various lengths in the biswapped network. Our technique also can be used for embedding cycles in other composite networks, such as swapped networks and Cartesian product networks. PubDate: 2017-01-23

Authors:Hierons RM; Türker U. Abstract: AbstractThere has been long-standing interest in automatically generating test sequences from a finite state machine (FSM) and more recently this has been extended to the case where there are multiple physically distributed testers and so we are testing from a multi-port FSM. This paper explores the problem of generating a controllable preset distinguishing sequence (PDS) from a multi-port FSM, motivated by the fact that many FSM-based test generation algorithms use PDSs. We prove that it is generally undecidable whether a multi-port FSM has a controllable PDS but provide a class of multi-port FSMs for which the problem is decidable. We also consider the important case where there is an upper bound ℓ on the length of PDSs of interest, proving that controllable PDS existence is PSPACE-hard and in EXPSPACE. In practice the upper bound ℓ is likely to be a polynomial in terms of the size of the multi-port FSM and in this case controllable PDS existence is NP-Complete. PubDate: 2017-01-23

Authors:Shoaran M; Thomo A. Abstract: AbstractWe introduce a general notion of maturity in social networks that is based on the number of triangles between groups/communities. In order to protect individual privacy upon possible release of such information, we propose privacy mechanisms using zero-knowledge privacy (ZKP), a recently proposed privacy scheme that provides stronger protection than differential privacy for social-graph data. We present techniques to compute the parameters required to design ZKP methods and finally evaluate the practicality of the proposed methods. PubDate: 2017-01-23

Authors:Wang S; Wang F. Abstract: AbstractThe independent spanning trees (ISTs) problem is asked to find k spanning trees rooted at a designated vertex r such that, for any vertex v, all paths connecting r and v in k spanning trees are pairwise internally disjoint in the given graph. ISTs have numerous applications in networks such as reliable communication protocols, data broadcasting and secure message distribution. In the past, most of the results focused on constructing k-ISTs on symmetric networks. While the existence of asymmetry makes the k-ISTs problem even harder than its symmetric counterpart, we have derived linear time algorithms for solving 3-ISTs rooted at an arbitrary vertex of recursive transpose-connected 4-cycle-pyramids. PubDate: 2017-01-23

Authors:Di Giacomo E; Didimo W, Liotta G, et al. Abstract: AbstractWe study the problem of computing drawings of planar graphs in sub-quadratic area, by allowing edge crossings. We first prove that sub-quadratic area cannot be achieved if only a constant number of crossings per edge is allowed. More precisely, we show that the same area lower bounds as in the crossing-free case hold for straight-line and poly-line drawings of planar graphs and series-parallel graphs. Motivated by this result, we study straight-line drawings of planar graphs where the number of crossings per edge is not bounded by a constant. In this case, we prove that every planar graph admits a straight-line drawing with sub-quadratic area and sub-linear thickness (the thickness of a drawing is the minimum number of colors that can be assigned to the edges so that each color class induces a planar drawing). We also prove that every partial 2-tree (and hence every series-parallel graph) admits a linear-area straight-line drawing with thickness at most 10. It is worth remarking that a drawing with thickness h−1 is h-quasi planar, i.e. it does not contain h-mutually crossing edges. The main ingredient to prove our results is (c, t)-track layouts, a combinatorial tool that can be represented as a drawing where: (i) each vertex is assigned to one of t horizontal layers (tracks), (ii) no two adjacent vertices are on the same track, (iii) each edge receives one of c colors, so that no two edges of the same color (u, v) and (w, z) cross if u, w are on the same track, and v, z are on the same track. PubDate: 2017-01-23

Authors:Sun C; Pan L, Wang Q, et al. Abstract: AbstractNowadays, applications are increasingly deployed as Web services in the globally distributed cloud computing environment. Multiple services are normally composed to fulfill complex functionalities. Business Process Execution Language for Web Services (WS-BPEL) is an XML-based service composition language that is used to define a complex business process by orchestrating multiple services. Compared with traditional applications, WS-BPEL programs pose many new challenges to the quality assurance, especially testing, of service compositions. A number of techniques have been proposed for testing WS-BPEL programs, but only a few studies have been conducted to systematically evaluate the effectiveness of these techniques. Mutation testing has been widely acknowledged as not only a testing method in its own right but also a popular technique for measuring the fault-detection effectiveness of other testing methods. Several previous studies have proposed a family of mutation operators for generating mutants by seeding various faults into WS-BPEL programs. In this study, we conduct a series of empirical studies to evaluate the applicability and effectiveness of various mutation operators for WS-BPEL programs. The experimental results provide insightful and comprehensive guidance for mutation testing of WS-BPEL programs in practice. In particular, our work is the systematic study in the selection of effective mutation operators specifically for WS-BPEL programs. PubDate: 2017-01-23

Authors:Yu J; Han J, Schneider J, et al. Abstract: AbstractThe landscape of modern enterprise IT environments is that a large number of distributed software systems interact and cooperate with each other to support daily business operations. With the prevalence of cloud computing, the level of system connectivity increases further. The large scale of such an environment makes it difficult to test a system's quality attributes such as performance and scalability before it is actually deployed in the production environment. Under the currently dominant iterative and incremental software development paradigm, this difficulty is even more pronounced when the quality attributes of an enterprise system need to be examined and evaluated at early stages but a large part of its operating environment is not available or accessible. In this paper, we present a Coloured Petri nets (CPN) based system behaviour emulation approach and a lightweight emulated testing framework for provisioning a virtual deployment testing environment for an enterprise software system, so that its quality attributes, especially scalability, can be evaluated without physically connecting to the real production environment. It is worth noting that the focus of this work is on the testing environment which enables virtual system deployment and testing, instead of being on the research topic of deployment test. CPN and its associated design and simulation tools have been used and integrated to model and execute the behaviour of those cooperating endpoint systems that an enterprise software system interacts with. We have successfully implemented an industry standard protocol Lightweight Directory Access Protocol in our approach and applied it in testing the scalability of a real-world enterprise application, CA Technologies’ IdentityManager. A thorough in-lab performance study has also been conducted to examine the capacity and scalability of this approach. PubDate: 2017-01-23

Authors:Rextin A; Healy P. Abstract: AbstractIn this paper, we present a dynamic algorithm that checks if a single-source embedded digraph is upward planar in the presence of edge insertions and edge deletions without changing the embedding of the digraph. We show that it can be checked in O(logn) amortized time whether the updated graph is a single-source upward planar digraph with a fixed external face. PubDate: 2017-01-23

Authors:Saez JC; Pousa AA, Rodriíguez-Rodriíguez RR, et al. Abstract: AbstractHardware performance monitoring counters (PMCs) have proven effective in characterizing application performance. Because PMCs can only be accessed directly at the OS privilege level, kernel-level tools must be developed to enable the end-user and userspace programs to access PMCs. A large body of work has demonstrated that the OS can perform effective runtime optimizations in multicore systems by leveraging performance-counter data. Special attention has been paid to optimizations in the OS scheduler. While existing performance monitoring tools greatly simplify the collection of PMC application data from userspace, they do not provide an architecture-agnostic kernel-level mechanism that is capable of exposing high-level PMC metrics to OS components, such as the scheduler. As a result, the implementation of PMC-based OS scheduling schemes is typically tied to specific processor models. To address this shortcoming we present PMCTrack, a novel tool for the Linux kernel that provides a simple architecture-independent mechanism that makes it possible for the OS scheduler to access per-thread PMC data. Despite being an OS-oriented tool, PMCTrack still allows the gathering of monitoring data from userspace, enabling kernel developers to carry out the necessary offline analysis and debugging to assist them during the scheduler design process. In addition, the tool provides both the OS and the user-space PMCTrack components with other insightful metrics available in modern processors and which are not directly exposed as PMCs, such as cache occupancy or energy consumption. This information is also of great value when it comes to analyzing the potential benefits of novel scheduling policies on real systems. In this paper, we analyze different case studies that demonstrate the flexibility, simplicity and powerful features of PMCTrack. PubDate: 2017-01-23

Authors:Pérez A; Sánchez P. Abstract: AbstractNowadays, many software companies have a flagship product that is sold to several customers, but customized to the particular requirements of each one of them. In these cases, Software Product Line Engineering (SPL), whose goal is the effective engineering of software products families, can be helpful. In the last years, several methodologies, techniques, languages and tools for SPL engineering have been released. They aim to improve state-of-the-art technologies, such as object-oriented technologies, regarding SPL engineering. Some years ago, a new programming concept, called partial class, was added to the C# programming language. This concept was considered by some authors as helpful for SPL implementation. Nevertheless, this idea has not been seriously explored until now. In order to fill this gap, this article firstly explores whether C# partial classes are suitable for SPL implementation. Since several pitfalls were found, a solution to overcome them is proposed. This solution is based on a design technique that have been named as the Slicer pattern. Finally, whether this technique provides benefits as compared to current practices are analysed. PubDate: 2017-01-23