Search

A new algebraic system, test algebra ($\mathsf{TA}$), is proposed for identifying faults in combinatorial testing for software-as-a-service (SaaS) applications. In the context of cloud computing, SaaS is a new software delivery model, in which mission-critical applications are composed, deployed, and executed on cloud platforms. Testing SaaS applications is challenging because new applications need to be tested once they are composed, and prior to their deployment. A composition of components providing services yields a configuration providing an SaaS application. While individual components in the configuration may have been thoroughly tested, faults still arise due to interactions among the components composed, making the configuration faulty. When there are $k$ components, combinatorial testing algorithms can be used to identify faulty interactions with $t$ or fewer components, for some threshold $2 \leq t \leq k$ on the size of interactions considered. In general, these methods do not identify specific faults, but rather indicate the presence or absence of some faults. To identify specific faults, an adaptive testing regime repeatedly constructs and tests configurations in order to determine, for each interaction of interest, whether it is faulty or not. In order to perform such testing in a loosely coupled distributed environment such as the cloud, it is imperative that testing results can be combined from many different servers. The $\mathsf{TA}$ defines rules to permit results to be combined, and to identify the faulty interactions. Using the $\mathsf{TA}$ , configurations can be tested concurrently on different servers and in any order. The $\mathsf{TA}$ always keeps the high reduction rate of potential faulty configurations in fault location analysis. [ABSTRACT FROM AUTHOR]

We use deterministic and probabilistic methods to analyze the performance of compressed sensing matrices constructed from Hadamard matrices and pairwise balanced designs, previously introduced by a subset of the authors. In this paper, we obtain upper and lower bounds on the sparsity of signals for which our matrices guarantee recovery. These bounds are tight to within a multiplicative factor of at most 4\sqrt 2 . We provide new theoretical results and detailed simulations, which indicate that the construction is competitive with Gaussian random matrices, and that recovery is tolerant to noise. A new recovery algorithm tailored to the construction is also given. [ABSTRACT FROM AUTHOR]

Software behavior depends on many factors. Combinatorial testing (CT) aims to generate small sets of test cases to uncover defects caused by those factors and their interactions. Covering array generation, a discrete optimization problem, is the most popular research area in the field of CT. Particle swarm optimization (PSO), an evolutionary search-based heuristic technique, has succeeded in generating covering arrays that are competitive in size. However, current PSO methods for covering array generation simply round the particle’s position to an integer to handle the discrete search space. Moreover, no guidelines are available to effectively set PSOs parameters for this problem. In this paper, we extend the set-based PSO, an existing discrete PSO (DPSO) method, to covering array generation. Two auxiliary strategies (particle reinitialization and additional evaluation of gbest) are proposed to improve performance, and thus a novel DPSO for covering array generation is developed. Guidelines for parameter settings both for conventional PSO (CPSO) and for DPSO are developed systematically here. Discrete extensions of four existing PSO variants are developed, in order to further investigate the effectiveness of DPSO for covering array generation. Experiments show that CPSO can produce better results using the guidelines for parameter settings, and that DPSO can generate smaller covering arrays than CPSO and other existing evolutionary algorithms. DPSO is a promising improvement on PSO for covering array generation. [ABSTRACT FROM PUBLISHER]

The largest strength of contention-based MAC protocols is simultaneously the largest weakness of their scheduled counterparts: the ability to adapt to changes in network conditions. For scheduling to be competitive in mobile wireless networks, continuous adaptation must be addressed. We propose ATLAS, an Adaptive Topology- and Load-Aware Scheduling protocol to address this problem. In ATLAS, each node employs a random schedule achieving its persistence, the fraction of time a node is permitted to transmit, that is computed in a topology and load dependent manner. A distributed auction (REACT) piggybacks offers and claims onto existing network traffic to compute a lexicographic max-min channel allocation. A node’s persistence p is related to its allocation. Its schedule achieving p is updated where and when needed, without waiting for a frame boundary. We study how ATLAS adapts to controlled changes in topology and load. Our results show that ATLAS adapts to most network changes in less than 0.1s, with about 20 percent relative error, scaling with network size. We further study ATLAS in more dynamic networks showing that it keeps up with changes in topology and load sufficient for TCP to sustain multi-hop flows, a struggle in IEEE 802.11 networks. The stable performance of ATLAS supports the design of higher-layer services that inform, and are informed by, the underlying communication network. [ABSTRACT FROM AUTHOR]

The primary function of the medium access control (MAC) protocol is managing access to the shared communication channel. From the viewpoint of the transmitters, the MAC protocol determines each transmitter's channel occupancy, the fraction of time that it spends transmitting over the channel. In this paper, we define a set of topological persistences that conform to both network topology and traffic load. We employ these persistences as target occupancies for the MAC layer protocol. A centralized algorithm is developed for calculating topological persistences and its correctness is established. A distributed algorithm and implementation are developed that can operate within scheduled and contention-based MAC protocols. In the distributed algorithm, network resources are allocated through auctions at each receiver in which transmitters participate as bidders to converge on the topological allocation. Very low overhead is achieved by piggybacking auction and bidder communication on existing data packets. The practicality of the distributed algorithm is demonstrated in a wireless network via simulation using the ns-2 network simulator. Simulation results show fast convergence to the topological solution and, once operating with topological persistences, improved performance compared to IEEE 802.11 in delay, throughput, and drop rate. [ABSTRACT FROM PUBLISHER]

Test response compaction for integrated circuits (ICs) with scan-based design-for-testability (DFT) support in the presence of unknown logic values (Xs) is investigated from a combinatorial viewpoint. The theoretical foundations of X-codes, employed in an X-tolerant compaction technique called X-compact, are examined. Through the formulation of a combinatorial model of X-compact, novel design techniques are developed for X-codes to detect a specified maximum number of errors in the presence of a specified maximum number of unknown logic values, while requiring only small fan-out. The special class of X-codes that results leads to an avoidance problem for configurations in combinatorial designs. General design methods and nonconstructive existence theorems to estimate the compaction ratio of an optimal X-compactor are also derived. [ABSTRACT FROM AUTHOR]

Topology-transparent scheduling for mobile wireless ad hoc networks has been treated as a theoretical curiosity. This paper makes two contributions towards its practical deployment: 1) We generalize the combinatorial requirement on the schedules and show that the solution is a cover-free family. As a result, a much wider number and variety of constructions for schedules exist to match network conditions. 2) In simulation, we closely match the theoretical bound on expected throughput. The bound was derived assuming acknowledgments are available immediately. We use rateless forward error correction (RFEC) as an acknowledgment scheme with minimal computational overhead. Since the wireless medium is inherently unreliable, RFEC also offers some measure of automatic adaptation to channel load. These contributions renew interest in topology-transparent scheduling when delay is a principal objective. [ABSTRACT FROM AUTHOR]

Medium access control for multihop wireless sensor networks (WSNs) must be energy efficient because the battery-operated nodes are not practical to recharge. We give constructions for ternary schedules in which each node is in one of three states: transmitting, receiving, or asleep. For each hop (vi, vj), communication is effective only when vi is transmitting, vj is receiving, and no other node in proximity of vj is also transmitting. Since sensor nodes are prone to failure, the schedules should be independent of the detailed topology while supporting spatial reuse. We use arc-decompositions of the complete λ-fold directed graph Kn into directed complete bipartite subgraphs Ka,b as a model for ternary scheduling in WSNs. We associate the vertices of Kn with the nodes of the WSN, and occurrences of Ka,b s (blocks) in the decomposition with time slots in the schedule. A block with out-vertices A and in-vertices B corresponds to a slot in which the a nodes in A are transmitting, the b in B are receiving, and all others are asleep. Such a decomposition of λKn guarantees that every ordered pair of nodes in the WSN can communicate in λ time slots. [ABSTRACT FROM AUTHOR]

We formulate a combinatorial model of impulse radio sequences (IRSs) to study sequence or signal design for ultra-wideband (UWB) radio with unmodulated lime hopping. Using this combinatorial model for IRSs, we develop necessary and sufficient conditions for the existence of IRSs. Several novel constructions for IRSs with optimal correlation properties are given. The constructions involve the Welch construction for Costas arrays, a quadratic polynomial construction over finite fields, recursive techniques for optical orthogonal codes, and combinatorial design techniques using perfect Mendelsohn designs (PMDs). [ABSTRACT FROM AUTHOR]

Studies the combinatorial and computational constructions for difference triangle sets having small scopes. Combinatorial asymptotics for difference triangle sets; Algorithms for constructing difference triangle sets; Conclusions.

Presents distance renormalization which generalizes the reliability renormalization algorithm for bounding probabilistic distances in bi-directional probabilistic weighted networks. Mechanism based on non-planar duality for using the algorithm to bound probabilistic maxflow and mean maxflow; Undirected to directed transformation.

The dynamic behavior of executing programs is a significant factor in the performance of virtual memory computer systems. Program restructuring attempts to improve the behavior of programs by reorganizing their object code to account for the characteristics of the virtual memory environment. A significant component of the restructuring process involves a restructuring graph. An analysis of restructuring graphs of typical programs found edge weights to be distributed in a Bradford-Zipf fashion, implying that a large fraction of total edge weight is concentrated in relatively few edges. This empirical observation can be used to improve the clustering phase of program restructuring, by limiting consideration to edges of large weight. We consider the effect of this improved clustering in the restructuring process by examining various means of restructuring some typical programs. In our experiments, 95 percent of the total edge value is typically accounted for by 50-60 percent of the edges. For naive clustering algorithms, clustering time is therefore typically halved; for more sophisticated methods, more substantial savings result. Finally, clustering with 95 percent of total edge value typically results in only a small decay in performance measures such as number of page faults and aver- age working set size. [ABSTRACT FROM AUTHOR]

Using cyclotomic numbers, a simple construction is presented for frequency-hopping (FH) sequences having optimal autocorrelation with respect to the well-known Lempel-Greenberger bound. Some optimal families of FH sequences are constructed. The simplicity of this technique makes it attractive for practical use. [ABSTRACT FROM AUTHOR]

We develop a connection between permutation arrays that are used in powerline communication and well-studied combinatorial objects, mutually orthogonal latin squares (MOLS). From this connection, many new results on permutation arrays can be obtained. [ABSTRACT FROM AUTHOR]

Deterministic construction of measurement matrices for compressive sensing can be effected by first constructing a relatively small matrix explicitly, and then inflating it using a column replacement technique to form a large measurement matrix that supports at least the same level of sparsity. In particular, using easily developed null space conditions for \ell_0- and \ell_1-recoverability, properties of the pattern matrix used to select columns lead to well-studied matrices, separating and distributing hash families. Two-stage compression and recovery techniques are developed that employ more computationally intensive \ell_0-recoverability for small matrices and simpler \ell_1-recoverability for one larger matrix; this can reduce the number of measurements required. [ABSTRACT FROM PUBLISHER]