A computationally efficient technique for transient analysis of repairable Markovian systems

A technique to design efficient methods using a combination of explicit (non-stiff) and implicit (stiff) ODE methods for numerical transient analysis of repairable Markovian systems is proposed. Repairable systems give rise to stiff Markov chains due to extreme disparity between failure rates and repair rates. Our approach is based on the observation that stiff Markov chains are non-stiff for an initial phase of the solution interval. A non-stiff ODE method is used to solve the model for this phase and a stiff ODE method is used to solve the model for the rest of the duration until the end of solution interval. A formal criterion to determine the length of the non-stiff phase is described. A significant outcome of this approach is that the accuracy requirement automatically becomes a part of model stiffness. Two specific methods based on this approach have been implemented. Both the methods use the Runge-Kutta-Fehlberg method as the non-stiff method. One uses the TR-BDF2 method as the stiff method while the other uses an implicit Runge-Kutta method as the stiff method. Numerical results obtained from solving dependability models of a multiprocessor system and an interconnection network are presented. These results show that the methods obtained using this approach are much more efficient than the corresponding stiff methods which have been proposed to solve stiff Markov models.     

Software dependability evaluation based on Markov usage models

A general technique for computing optimal state transition probabilities for software tests, based on a Markov usage model, is developed. The optimization criterion is maximum precision of unbiased dependability estimates derived from the test results. Three different dependability measures are considered: (i) risk, (ii) safety, and (iii) reliability. As input, pre-information on failure probabilities and losses in case of failure related with single operations is used. The optimization itself is done by means of a numerical procedure which is fast because of the convexity of the underlying stochastic optimization problem. The procedure can be improved by the construction of a distribution with a common lower bound on state transition probabilities; this distribution may also be used in the more general context of structural statistical testing of software.     

Composite performance and dependability analysis

Composite performance and dependability analysis is gaining importance in the design of complex, fault-tolerant systems. Markov reward models are most commonly used for this purpose. In this paper, an introduction to Markov reward models including solution techniques and application examples is presented. Extensions of Markov reward models to semi-Markov reward models are also mentioned. A brief discussion of how task completion time models and models of queues with breakdowns and repairs relate to Markov reward models is also given.     

On the use of MTBDDs for performability analysis and verification of stochastic systems

This paper describes how to employ multi-terminal binary decision diagrams (MTBDDs) for the construction and analysis of a general class of models that exhibit stochastic, probabilistic and non-deterministic behaviour. It is shown how the notorious problem of state space explosion can be circumvented by compositionally constructing symbolic (i.e. MTBDD-based) representations of complex systems from small-scale components. We emphasise, however, that compactness of the representation can only be achieved if heuristics are applied with insight into the structure of the system under investigation. We report on our experiences concerning compact representation, performance analysis and verification of performability properties.     

Two methods for computing bounds for the distribution of cumulative reward for large Markov models

Degradable fault-tolerant systems can be evaluated using rewarded continuous-time Markov chain (CTMC) models. In that context, a useful measure to consider is the distribution of the cumulative reward over a time interval [0,t]. All currently available numerical methods for computing that measure tend to be very expensive when the product of the maximum output rate of the CTMC model and t is large and, in that case, their application is limited to CTMC models of moderate size. In this paper, we develop two methods for computing bounds for the cumulative reward distribution of CTMC models with reward rates associated with states: BT/RT (Bounding Transformation/Regenerative Transformation) and BT/BRT (Bounding Transformation/Bounding Regenerative Transformation). The methods require the selection of a regenerative state, are numerically stable and compute the bounds with well-controlled error. For a class of rewarded CTMC models, class , and a particular, natural selection for the regenerative state the BT/BRT method allows us to trade off bound tightness with computational cost and will provide bounds at a moderate computational cost in many cases of interest. For a class of models, class , slightly wider than class , and a particular, natural selection for the regenerative state, the BT/RT method will yield tighter bounds at a higher computational cost. Under additional conditions, the bounds obtained using the less expensive version of BT/BRT and BT/RT seem to be tight for any value of t or not small values of t, depending on the initial probability distribution of the model. Class and class models with these additional conditions include both exact and bounding typical failure/repair performability models of fault-tolerant systems with exponential failure and repair time distributions and repair in every state with failed components and a reward rate structure which is a non-increasing function of the collection of failed components. We illustrate both the applicability and the performance of the methods using a large CTMC performability example of a fault-tolerant multiprocessor system.     

Numerical solution of non-linear elliptic boundary-value problems by isomorphic iterative methods

New implicit iterative methods are presented for the efficient numerical solution of non-linear elliptic boundary-value problems. Isomorphic iterative schemes in conjunction with preconditioning techniques are used for solving non-linear elliptic equations in two and three-space dimensions. The application of the derived methods on characteristic 2D and 3D non-linear boundary-value problems is discussed and numerical results are given.     

Noise tolerant iterative learning control for a class of continuous-time systems

The paper proposes a noise tolerant iterative learning control (ILC) for a class of linear continuous-time systems, which achieves high-precision tracking for uncertain plants by iteration of trials in the presence of heavy measurement noise. The robustness against measurement noise is achieved through (i) projection of continuous-time I/O signals onto a finite-dimensional parameter space, (ii) using error data of all past iterations via an integral operation in the learning law and (iii) noise reduction by H² optimization subject to a specified convergence speed of the ILC.     

Reward model solution methods with impulse and rate rewards: an algorithm and numerical results

Reward models have become an important method for specifying performability models for many types of systems. Many methods have been proposed for solving reward models, but no method has proven itself to be applicable over all system classes and sizes. Furthermore, specification of reward models has usually been done at the state level, which can be extremely cumbersome for realistic models. We describe a method to specify reward models as stochastic activity networks (SANs) with impulse and rate rewards, and a method by which to solve these models via uniformization. The method is an extension of one proposed by de Souza e Silva and Gail in which impulse and rate rewards are specified at the SAN level, and solved in a single model. Furthermore, we propose a new technique for discarding paths in the uniformized process whose contribution to the reward variable is minimal, which greatly reduces the time and space required for a solution. A bound is calculated on the error introduced by this discarding, and its effectiveness is illustrated through the study of the performability and availability of a degradable multi-processor system.     

A method for calculating successive approximate solutions for a class of block banded M/G/1 type Markovian models

This paper presents an efficient equilibrium solution algorithm for a class of infinite block banded M/G/1 type Markov chains. By re-blocking the states, these are a class of the so-called quasi-birth-and-death (QBD) type chains. The proposed algorithm is not based on an iterative approach, so that the exact solution can be computed in a known finite number of steps. The key point on which the algorithm is based is the identification of a linear dependence among variables. This dependence is expressed in terms of a companion matrix. The equilibrium solution of the Markov chain is obtained operating on this matrix.

An attractive feature of the algorithm is that it allows the computation of a succession of approximate solutions with growing accuracy, until the exact solution is obtained in a finite number of steps. The class of block-banded M/G/1 type Markov chains we consider requires that the lower diagonal block is invertible and that the chain is ergodic. However, many models arising from telecommunication systems satisfy this restriction. Results for a case study show that the proposed algorithm is efficient and quite accurate, even when providing approximate solutions.     

Numerical fixed grid methods for differential inclusions

Summary Numerical methods for initial value problems for differential inclusions usually require a discretization of time as well as of the set valued right hand side. In this paper, two numerical fixed grid methods for the approximation of the full solution set are proposed and analyzed. Convergence results are proved which show the combined influence of time and (phase) space discretization. Supported by CRC 701 “Spectral Analysis and Topological Methods in Mathematics”.     

一类离散时间非齐次马尔可夫跳跃系统最优控制

本文研究了一类离散时间非齐次马尔可夫跳跃线性系统的线型二次高斯(linear quadratic Gaussian,LQG)问题,其中系统模态转移概率矩阵随时间随机变化,其变化特性由一高阶马尔可夫链描述.对于该系统的LQG问题,文中首先给出了线性最优滤波器,得到最优状态估计;其次,验证分离定理成立,并利用利用动态规划方法设计了系统最优控制器;最后,数值仿真结果验证了所设计控制器的有效性.     

Convergence conditions for iterative methods seeking multi-component solitary waves with prescribed quadratic conserved quantities

We obtain linearized (i.e., non-global) convergence conditions for iterative methods that seek solitary waves with prescribed values of quadratic conserved quantities of multi-component Hamiltonian nonlinear wave equations. These conditions extend the ones found for single-component solitary waves in a recent publication by Yang and the present author. We also show that, and why, these convergence conditions coincide with dynamical stability conditions for ground-state solitary waves.Notably, our analysis applies regardless of whether the number of quadratic conserved quantities, s, equals or is less than the number of equations, S. To illustrate the situation when s < S, we use one of our iterative methods to find ground-state solitary waves in spin-1 Bose-Einstein condensates in a magnetic field (s = 2, S = 3).     

Mixing logics and rewards for the component-oriented specification of performance measures

Formal notations for system performance modeling need to be equipped with suitable notations for specifying performance measures. These companion notations have been traditionally based on reward structures and, more recently, on temporal logics. In this paper we propose an approach that combines logics and rewards, together with a definition mechanism that allows performance measures to be specified in a component-oriented way, thus facilitating the task for non-experts. The resulting Measure Specification Language (MSL) is interpreted both on action-labeled continuous-time Markov chains and on stochastic process algebras. The latter interpretation provides a compositional framework for performance-sensitive model manipulations and emphasizes the increased expressiveness with respect to traditional reward structures for implicit-state modeling notations.     

Markov models for digraph panel data: Monte Carlo-based derivative estimation

A parametric, continuous-time Markov model for digraph panel data is considered. The parameter is estimated by the method of moments. A convenient method for estimating the variance-covariance matrix of the moment estimator relies on the delta method, requiring the Jacobian matrix—that is, the matrix of partial derivatives—of the estimating function. The Jacobian matrix was estimated hitherto by Monte Carlo methods based on finite differences. Three new Monte Carlo estimators of the Jacobian matrix are proposed, which are related to the likelihood ratio/score function method of derivative estimation and have theoretical and practical advantages compared to the finite differences method. Some light is shed on the practical performance of the methods by applying them in a situation where the true Jacobian matrix is known and in a situation where the true Jacobian matrix is unknown.     

Spectral expansion solution for a class of Markov models: application and comparison with the matrix-geometric method

Many two-dimensional Markov models whose state space is a semi-infinite strip (i.e. finite in one dimension and infinite in the other) can be solved efficiently by means of spectral expansion. This method and its application are described in the context of an M/M//N queue with general breakdowns and repairs. The results of experiments aimed at evaluating the relative merits of the spectral expansion and the matrix-geometric solutions are also presented.     

Introducing a new Cryptologia series: Sources and methods for cryptologic history

Abstract

The idea for a regular column in Cryptologia devoted to a discussion of sources and methods came from recurring discussion among the three of us about the future of cryptologic history and a desire to encourage others to do research and writing in the field. We are all retired from the National Security Agency (two of us from the Center for Cryptologic History (CCH) and one from the Office of Strategy, Policy, and Plans). Each of us continues to research and write on cryptologic subjects. This article summarizes our sense of the state of the field and outlines the topics for future articles in this series.     

An efficient preconditioned iterative solver for solving a coupled fluid structure interaction problem

Modelling the interaction of an acoustic field in a fluid and an elastic structure submerged in the fluid leads to a system of complex linear equations with a complicated sparsity structure and, for higher wavenumbers and adequate modelling, the systems are very large. Direct methods are not practical. Preconditioned iterative methods, which are suitable for single operator equations, are not immediately applicable to the coupled case. This article proposes a block diagonal preconditioner of the sparse approximate inverse (SPAI) type that can accelerate the convergence of Krylov iterative solvers for the coupled system. Moreover, the proposed preconditioner can properly and implicitly scale the coupled matrix. Some numerical results are presented to demonstrate the effectiveness of the new method.     

A multi-server queueing model with retrial connection arrivals as a model for optimisation of the traffic control

We consider a multi-server queueing model with a finite buffer and requests arriving in connections. The number of requests in a connection is random and unknown at the connection initiation instant. Requests, which belong to the connection, arrive in accordance with a Poisson process. Admission of connections to the system is regulated by means of so-called tokens. The pool of tokens is finite. If a connection arrives and there are no tokens available, it leaves the system forever or joins the orbit and retries for access later on. The steady-state distribution of the system is analysed. The problem of the throughput maximisation under the constraint that the request loss probability does not exceed a predefined value is numerically solved. The effect of the retrial intensity, correlation and variation in the arrival process and the probability to leave the system if tokens are not available is numerically highlighted.