Failed disk recovery in double erasure RAID arrays

Reliability is a major concern in the design of large disk arrays. In this paper, we examine the effect of encountering more failures than that for which the RAID array was initially designed. Erasure codes are incorporated to enable system recovery from a specified number of disk erasures, and strive beyond that threshold to recover the system as frequently, and as thoroughly, as is possible. Erasure codes for tolerating two disk failures are examined. For these double erasure codes, we establish a correspondence between system operation and acyclicity of its graph model. For the most compact double erasure code, the full 2-code, this underlies an efficient algorithm for the computation of system operation probability (all disks operating or recoverable).When the system has failed, some disks are nonetheless recoverable. We extend the graph model to determine the probability that d disks have failed, a of which are recoverable by solving one linear equation, b of which are further recoverable by solving systems of linear equations, and d−a−b of which cannot be recovered. These statistics are efficiently calculated for the full 2-code by developing a three variable ordinary generating function whose coefficients give the specified values. Finally, examples are given to illustrate the probability that an individual disk can be recovered, even when the system is in a failed state.     

A note on preconditioned GMRES for solving singular linear systems

For solving a singular linear system Ax=b by GMRES, it is shown in the literature that if A is range-symmetric, then GMRES converges safely to a solution. In this paper we consider preconditioned GMRES for solving a singular linear system, we construct preconditioners by so-called proper splittings, which can ensure that the coefficient matrix of the preconditioned system is range-symmetric.     

Analysis of preemptive loss priority queues with preemption distance

In a queueing system with preemptive loss priority discipline, customers disappear from the system immediately when their service is preempted by the arrival of another customer with higher priority. Such a system can model a case in which old requests of low priority are not worthy of deferred service. This paper is concerned with preemptive loss priority queues in which customers of each priority class arrive in a Poisson process and have general service time distribution. The strict preemption in the existing model is extended by allowing the preemption distance parameterd such that arriving customers of only class 1 throughp — d can preempt the service of a customer of classp. We obtain closed-form expressions for the mean waiting time, sojourn time, and queue size from their distributions for each class, together with numerical examples. We also consider similar systems with server vacations.     

Robust Optimisation with Normal Vectors on Critical Manifolds of Disturbance-Induced Stability Loss

Dynamic systems that are subject to fast disturbances, parametrised by a disturbance vector d, undergo bifurcations for some values of the disturbance d. In this work we specifically examine those bifurcations which give rise to system trajectories that leave the domain of attraction of a desired system state. We derive equations which describe the manifold of bifurcation values (that is the manifold of disturbances d which cause the system trajectory to abandon the desired domain of attraction) and the corresponding normal vectors. The system of equations can then be used to find the smallest critical disturbance in physical, biological or other systems, or to robustly optimise design parameters of an engineered system.     

On the numerical solution of certain boundary control problems for vibrating media in one space-dimension

This paper is concerned with the numerical solution of control problems which consist of minimizing certain quadratic functionals depending on control functions in L ₂[0,1] for some given time T > 0 and bounded with respect to the maximum norm. These control functions act upon the boundary conditions of a vibrating system in one space-dimension which is governed by a wave equation of spatial order 2n They are to be chosen in such a way that a given initial state of vibration at time zero is transferred into the state of rest. This requirement can be expressed by an infinite system of moment equations to be satisfied by the control functions

The control problem is approximated by replacing this infinite system by finitely many, say N, equations (truncation) and by choosing piecewise constant functions as controls (discretization). The resulting problem is a quadratic optimization problem which is solved very efficiently by a multiplier method

Convergence of the solutions of the approximating problems to the solution of the control problem, as N tends to infinity and the discretization is infinitely refined, is shown under mild assumptions. Numerical results are presented for a vibrating beam     

Special tight frames

Special vector systems, in which every element is the preceding element multiplied by a unitary matrix U, are introduced. Necessary and sufficient conditions for such a system to be a tight frame are obtained (Theorem 1). Examples illustrating the necessity of every condition are given. The theorem is applied to the Mercedes-Benz frame. Let P denote the matrix composed of orthonormal eigenvectors of U. A new system of vectors in which every element equals the corresponding element of the initial system multiplied by P* is considered. It is proved that this system is a generalized harmonic frame if and only if the assumptions of Theorem 1 hold. This result is applied to show how to transform the Mercedes-Benz frame into a generalized harmonic frame.     

Performance analysis of test scheduling schemes for a multi-access communications network

In this paper, we investigate the performance of two implementable test scheduling schemes for a multi-access communication channel whose components are subject to failure or malfunction. We relate the reliability of the system design, as reflected by system failure rate parameters, and the frequency at which the system (or nodal subsystem) is tested for failure detection, to the underlying key message delay and throughput performance. We derive queue-size distribution results for a discreteGeom ^(X)/D/1 system, representing the operation of the multi-access channel, or of a network node operating as a communications or queueing processor, which is maintained by a periodic or near periodic test scheduling scheme. Explicit formulas are presented for the system behavior as exhibited by the generating functions of the system queue-size distributions. The mean message delay is then calculated. The mean delay (or mean system size/workload performance index) can then be optimized by selecting the proper scheme parameters, under specified system (and component) failure conditions, noting that performing a test at too high a rate leads to inefficient system bandwidth utilization, while if tests are not carried out often enough, excessive message (or task) retransmissions and delays ensue.     

Equilibria of a class of transport equations arising in congestion control

We consider a multi-queue multi-server system with n servers (processors) and m queues. At the system there arrives a stationary and ergodic stream of m different types of requests with service requirements which are served according to the following k-limited head of the line processor sharing discipline: The first k requests at the head of the m queues are served in processor sharing by the n processors, where each request may receive at most the capacity of one processor. By means of sample path analysis and Loynes’ monotonicity method, a stationary and ergodic state process is constructed, and a necessary as well as a sufficient condition for the stability of the m separate queues are given, which are tight within the class of all stationary ergodic inputs. These conditions lead to tight necessary and sufficient conditions for the whole system, also in case of permanent customers, generalizing an earlier result by the authors for the case of n=k=1. This work was supported by a grant from the Siemens AG.     

On algebras of multidimensional probabilities

The probability p(s) of the occurrence of an event pertaining to a physical system which is observed in different states s determines a function p from the set S of states of the system to [0, 1]. The function p is called a multidimensional probability or numerical event. Sets of numerical events which are structured either by partially ordering the functions p and considering orthocomplementation or by introducing operations + and · in order to generalize the notion of Boolean rings representing classical event fields are studied with the goal to relate the algebraic operations + and · to the sum and product of real functions and thus to distinguish between classical and quantum mechanical behaviour of the physical system. Necessary and sufficient conditions for this are derived, as well for the case that the functions p can assume any value between 0 and 1 as for the special cases that the values of p are restricted to two or three different outcomes.     

The Subconstituent Algebra of an Association Scheme (Part II)

This is a continuation of an article from the previous issue. In this section, we determine the structure of a thin, irreducible module for the subconstituent algebra of a P- and Q- polynomial association scheme. Such a module is naturally associated with a Leonard system. The isomorphism class of the module is determined by this Leonard system, which in turn is determined by four parameters: the endpoint, the dual endpoint, the diameter, and an additional parameter f. If the module has sufficiently large dimension, the parameter f takes one of a certain set of values indexed by a bounded integer parameter e.     

The dynamics of marginal equilibria

Suppose F is a real-valued function defined on ^m. The dynamics of the system which is obtained by minimizing F by one (real) component at a time is studied. Two distinct cases arise depending upon whether F is C¹ or not. Thus when F ε C², the dynamical system obtained may be studied in terms of iterations of a C² local diffeomorphism. In particular when F is a Morse function, the system will converge to a minimum of F. However, when F is not C¹, but convex and suitably approximable, then the system exhibits a notion of turbulence which leads to orbits terminating at trapping points. These are not minima of F but are fixed points of the system.     

A new computational approach for stochastic fluid models of multiplexers with heterogeneous sources

In this paper we derive an efficient computational procedure for the system in which fluid is produced byN ₁ on-off sources of type 1,N ₂ on-off sources of type 2 and transferred to a buffer which is serviced by a channel of constant capacity. This is a canonical model for multiservice ATM multiplexing, which is hard to analyze and also of wide interest. This paper's approach to the computation of the buffer overflow probability,G(x) = Pr{buffer content >x}, departs from all prior approaches in that it transforms the computation ofG(x) for a particularx into a recursive construction of an interpolating polynomial. For the particular case of two source types the interpolating polynomial is in two variables. Our main result is the derivation of recursive algorithms for computing the overflow probabilityG(x) and various other performance measures using their respective relations to two-dimensional interpolating polynomials. To make the computational procedure efficient we first derive a new system of equations for the coefficients in the spectral expansion formula forG(x) and then use specific properties of the new system for efficient recursive construction of the polynomials. We also develop an approximate method with low complexity and analyze its accuracy by numerical studies. We computeG(x) for different values ofx, the mean buffer content and the coefficient of the dominant exponential term in the spectral expansion ofG(x). The accuracy of the approximations is reasonable when the buffer utilization characterized by G(0) is more than 10^–2.     

The Vlasov-Maxwell-Boltzmann system near Maxwellians

Perhaps the most fundamental model for dynamics of dilute charged particles is described by the Vlasov-Maxwell-Boltzmann system, in which particles interact with themselves through collisions and with their self-consistent electromagnetic field. Despite its importance, no global in time solutions, weak or strong, have been constructed so far. It is shown in this article that any initially smooth, periodic small perturbation of a given global Maxwellian, which preserves the same mass, total momentum and reduced total energy (22), leads to a unique global in time classical solution for such a master system. The construction is based on a recent nonlinear energy method with a new a priori estimate for the dissipation: the linear collision operator L, not its time integration, is positive definite for any solutionf(t,x,v) with small amplitude to the Vlasov-Maxwell-Boltzmann system (8) and (12). As a by-product, such an estimate also yields an exponential decay for the simpler Vlasov-Poisson-Boltzmann system (24).     

Local Well-posedness of Kinetic Chemotaxis Models

We present a general functional analytic setting in which the Cauchy problem for mild solutions of kinetic chemotaxis models is well-posed, locally in time, in general physical dimensions. The models consist of a hyperbolic transport equation that is non-linearly and non-locally coupled to a reaction-diffusion system through kernel operators. Three examples are elaborated throughout the paper in which the latter system is (1) a single linear equation, (2) a FitzHugh-Nagumo system and (3) a piecewise linear approximation thereof. Finally we present a limit argument to obtain results on solutions in L ¹ ∩ L ^∞. Sander C. Hille: This work is supported by PIONIER grant 600-61410 of the Netherlands Organisation for Scientific Research, NWO.     

On instability under small periodic perturbation of two-dimensional hyperbolic systems

Under consideration is a mixed problem for a strictly hyperbolic linear first-order system in the half-strip Π = {(x, t): 0 < x < 1, t > 0} generating a group of unitary operators. In the case of a periodic perturbation a method is proposed for finding the frequencies for which the perturbed system develops parametric resonance. The method is illustrated with a system of two equations.     

Finite-difference methods for solving the reaction-diffusion equations of a simple isothermal chemical system

Numerical methods are proposed for the numerical solution of a system of reaction-diffusion equations, which model chemical wave propagation. The reaction terms in this system of partial differential equations contain nonlinear expressions. Nevertheless, it is seen that the numerical solution is obtained by solving a linear algebraic system at each time step, as opposed to solving a nonlinear algebraic system, which is often required when integrating nonlinear partial differential equations. The development of each numerical method is made in the light of experience gained in solving the system of ordinary differential equations, which model the well-stirred analogue of the chemical system. The first-order numerical methods proposed for the solution of this initialvalue problem are characterized to be implicit. However, in each case it is seen that the numerical solution is obtained explicitly. In a series of numerical experiments, in which the ordinary differential equations are solved first of all, it is seen that the proposed methods have superior stability properties to those of the well-known, first-order, Euler method to which they are compared. Incorporating the proposed methods into the numerical solution of the partial differential equations is seen to lead to two economical and reliable methods, one sequential and one parallel, for solving the travelling-wave problem. © 1994 John Wiley & Sons, Inc.     

Stability of indefinite systems

Absrtract  The paper considers a continuous system

Stratifiable Families of Extremals and Sufficient Conditions for Optimality in Optimal Control Problems

It is shown that, if a parametrized fämily of extremals F can be stratified in a way compatible with the flow map generated by F, then those trajectories of the family which realize the minimal values of the cost in F are indeed optimal in comparison with all trajectories which lie in the region R covered by the trajectories of F. It is not assumed that F is a field covering the state space injectively. As illustration, an optimal synthesis is constructed for a system where the flow of extremals exhibits a simple cusp singularity.