An O(k3·log(n/k)) algorithm for theconsecutive-k-out-of-n:F system

The fastest generally-recognized algorithms for computing the reliability of consecutive-k-out-of-n:F systems require O(n) time, for both the linear and circular systems. The authors' new algorithm requires O(k³·log(n/k)) time. The algorithm can be extended to yield an O(n·max{k³·log(n/k), log(n))} total time procedure for solving the combinatorial problem of counting the number of working states, with w working and n-w failed components, w=1,2,...,n     

An O(n·(log2(n))2) algorithm forcomputing the reliability of k-out-of-n:G and k-to-l-out-of-n:G systems

This paper presents the RAFFT-GFP (Recursively Applied Fast Fourier Transform for Generator Function Products) algorithm as a computationally superior algorithm for expressing and computing the reliability of k-out-of-n:G and k-to-l-out-of-n:G systems using the fast Fourier transform. Originally suggested by Barlow and Heidtmann (1984), generating functions provide a clear, concise method for computing the reliabilities of such systems. By recursively applying the FFT to computing generator function products, the RAFFT-GFP achieves an overall asymptotic computational complexity of O(n·(log₂(n)) ²) for computing system reliability. Algebraic manipulations suggested by Upadhyaya and Pham (1993) are reformulated in the context of generator functions to reduce the number of computations. The number of computations and the CPU time are used to compare the performance of the RAFFT-GFP algorithm to the best found in the literature. Due to larger overheads required, the RAFFT-GFP algorithm is superior for problem sizes larger than about 4000 components, in terms of both computation and CPU time for the examples studied in this paper. Lastly, studies of very large systems with unequal reliabilities indicate that the binomial distribution gives a good approximation for generating function coefficients, allowing algebraic solutions for system reliability     

Reliability evaluation of combined k-out-of-n:F,consecutive-k-out-of-n:F and linear connected-(r, s)-out-of-(m, n):Fsystem structures

Based on a real industrial application, three new system reliability models are proposed: combined k-out-of-n:F and consecutive-k _c-out-of-n:F system; combined k-out-of-m·n:F and linear connected-(r,s)-out-of-(m,n):F system; and combined k-out-of-m·n:F consecutive-k_c-out-of-n:F and linear connected-(r,s)-out-of-(m,n):F system. Reliability evaluation algorithms are provided for these models. The computation times of the algorithms for these models are, respectively: O(n·k), O(k·n·2 ^m·s^m-r+2), O(k·n·(2k_c )^m·s^m-r+1). The algorithms are used for system reliability evaluation of furnace systems. The concept of the combined k-out-of-n:F and 1-dimensional and 2-dimensional consecutive-k-out-of-n:F systems can be extended to other variations of the consecutive-k-out-of-n:F systems, e.g., the consecutive-k-out-of-n:G system and 1-dimensional and 2-dimensional r-within-k-out-of-n:F systems. The concept of Markov chain imbeddable (MIS) systems is another excellent tool that can be used for analysis of such combined system structures     

Efficient algorithms for k-out-of-n andconsecutive-weighted-k-out-of-n:F system

A new reliability model, consecutive-weighted-k-out-of-n:F system, is proposed and an O(n) algorithm is provided to evaluate its reliability. An O(n·min(n,k)) algorithm is also presented for the circular case of this model. The authors design an O(n) parallel algorithm using k processors to compute the reliability of k-out-of-n systems, that achieves linear speedup     

An algorithm for computing the reliability of weighted-k-out-of-nsystems

This paper constructs a new k-out-of-n model, viz, a weighted-k-out-of-n system, which has n components, each with its own positive integer weight (total system weight=w), such that the system is good (failed) if the total weight of good (failed) components is at least k. The reliability of the weighted-k-out-of-n:G system is the complement of the unreliability of a weighted-(w-k+1)-out-of-n:F system. Without loss of generality, the authors discuss the weighted-k-out-of-n:G system only. The k-out-of-n:G system is a special case of the weighted-k-out-of-n:G system wherein the weight of each component is 1. An efficient algorithm is given to evaluate the reliability of the weighted-k-out-of-n:G system. The time complexity of this algorithm is O(n.k)     

An Efficient Algorithm for Computing the Reliability of Consecutive-$k$-Out-Of-$n$:F Systems

Many algorithms for computing the reliability of linear or circular consecutive-k-out-of-n:F systems appeared in this Transactions. The best complexity estimate obtained for solving this problem is O(k³ log(n/k)) operations in the case of i.i.d. components. Using fast algorithms for computing a selected term of a linear recurrence with constant coefficients, we provide an algorithm having arithmetic complexity O(k log (k) log(log(k)) log(n)+k^omega) where 2相似文献   

Optimal design of k-out-of-n:G subsystems subjected to imperfect fault-coverage

Systems subjected to imperfect fault-coverage may fail even prior to the exhaustion of spares due to uncovered component failures. This paper presents optimal cost-effective design policies for k-out-of-n:G subsystems subjected to imperfect fault-coverage. It is assumed that there exists a k-out-of-n:G subsystem in a nonseries-parallel system and, except for this subsystem, the redundancy configurations of all other subsystems are fixed. This paper also presents optimal design polices which maximize overall system reliability. As a special case, results are presented for k-out-of-n:G systems subjected to imperfect fault-coverage. Examples then demonstrate how to apply the main results of this paper to find the optimal configurations of all subsystems simultaneously. In this paper, we show that the optimal n which maximizes system reliability is always less than or equal to the n which maximizes the reliability of the subsystem itself. Similarly, if the failure cost is the same, then the optimal n which minimizes the average system cost is always less than or equal to the n which minimizes the average cost of the subsystem. It is also shown that if the subsystem being analyzed is in series with the rest of the system, then the optimal n which maximizes subsystem reliability can also maximize the system reliability. The computational procedure of the proposed algorithms is illustrated through the examples.     

Energy-Optimal Distributed Algorithms for Minimum Spanning Trees

Traditionally, the performance of distributed algorithms has been measured in terms of time and message complexity.Message complexity concerns the number of messages transmitted over all the edges during the course of the algorithm. However, in energy-constrained ad hoc wireless networks (e.g., sensor networks), energy is a critical factor in measuring the efficiency of a distributed algorithm. Transmitting a message between two nodes has an associated cost (energy) and moreover this cost can depend on the two nodes (e.g., the distance between them among other things). Thus in addition to the time and message complexity, it is important to consider energy complexity that accounts for the total energy associated with the messages exchanged among the nodes in a distributed algorithm. This paper addresses the minimum spanning tree (MST) problem, a fundamental problem in distributed computing and communication networks. We study energy-efficient distributed algorithms for the Euclidean MST problem assuming random distribution of nodes. We show a non-trivial lower bound of ω(log n) on the energy complexity of any distributed MST algorithm. We then give an energy-optimal distributed algorithm that constructs an optimal MST with energy complexity O(log n) on average and O(log n log log n) with high probability. This is an improvement over the previous best known bound on the average energy complexity of ?(log2 n). Our energy-optimal algorithm exploits a novel property of the giant component of sparse random geometric graphs. All of the above results assume that nodes do not know their geometric coordinates. If the nodes know their own coordinates, then we give an algorithm with O(1) energy complexity (which is the best possible) that gives an O(1) approximation to the MST.     

Reliability optimization of series-parallel systems using a genetic algorithm

A problem-specific genetic algorithm (GA) is developed and demonstrated to analyze series-parallel systems and to determine the optimal design configuration when there are multiple component choices available for each of several k-out-of-n:G subsystems. The problem is to select components and redundancy-levels to optimize some objective function, given system-level constraints on reliability, cost, and/or weight. Previous formulations of the problem have implicit restrictions concerning the type of redundancy allowed, the number of available component choices, and whether mixing of components is allowed. GA is a robust evolutionary optimization search technique with very few restrictions concerning the type or size of the design problem. The solution approach was to solve the dual of a nonlinear optimization problem by using a dynamic penalty function. GA performs very well on two types of problems: (1) redundancy allocation originally proposed by Fyffe, Hines, Lee, and (2) randomly generated problem with more complex k-out-of-n:G configurations.     

基于“反体存储器”概念的分类器：SORTER

本文描述和分析了一个基于反体存储器概念模型的新型分类器（ＳＯＲＴＥＲ）的硬件结构和相应的分类算法。由于不是采用基于比较的分类方法,ＳＯＲＴＥＲ避免了常规分类算法Ｏ（ｎｌｏｇ ｎ）的时间下界。ＳＯＲＴＥＲ仅利用两种基于的读写操作实现数据元素的分类。按存储器访问多次数计算,该算法的复杂度仅为Ｏ（ｎ）。此外,对ＳＯＲＴＥＲ算法稍加修改,就可以实现数据库中的多数运算,其时间的复杂性同样为Ｏ（ｎ）。ＳＯＲＴ     

Maximizing Cooperative Diversity Energy Gain for Wireless Networks

We are concerned with optimally grouping active mobile users in a two-user-based cooperative diversity system to maximize the cooperative diversity energy gain in a radio cell. The optimization problem is formulated as a non-bipartite weighted-matching problem in a static network setting. The weighted-matching problem can be solved using maximum weighted (MW) matching algorithm in polynomial time O(n³). To reduce the implementation and computational complexity, we develop a Worst-Link-First (WLF) matching algorithm, which gives the user with the worse channel condition and the higher energy consumption rate a higher priority to choose its partner. The computational complexity of the proposed WLF algorithm is O(n) while the achieved average energy gain is only slightly lower than that of the optimal maximum weighted- matching algorithm and similar to that of the 1/2-approximation Greedy matching algorithm (with computational complexity of O(n² log n)) for a static-user network. We further investigate the optimal matching problem in mobile networks. By intelligently applying user mobility information in the matching algorithm, high cooperative diversity energy gain with moderate overhead is possible. In mobile networks, the proposed WLF matching algorithm, being less complex than the MW and the Greedy matching algorithms, yields performance characteristics close to those of the MW matching algorithm and better than the Greedy matching algorithm.     

Stochastic ordering results for consecutive k-out-of-n:F systems

A linear (circular) consecutive k-out-of-n:F system is a system of n linearly (circularly) ordered components which fails if and only if at least k consecutive components fail. We use recursive relationships on the reliability of such systems with independent identically distributed components to show that for any fixed k, the lifetime of a (linear or circular) consecutive k-out-of-n:F system is stochastically decreasing in n. This result also holds for linear systems when the components are independent and not necessarily identically distributed, but not in general for circular systems.     

Generalized Access Structure Congestion System

The k-out-of-n secret sharing schemes are effective, reliable, and secure methods to prevent a secret or secrets from being lost, stolen, or corrupted. The circular sequential k-out-of-n congestion (CSknC) system , based upon this type of secret sharing scheme, is presented for reconstructing secret(s) from any k servers among n servers in circular, sequential order. When a server is connected successfully, it will not be reconnected in later rounds until the CSknC system has k distinct, successfully connected servers. An optimal server arrangement in a CSknC system is determined in where n servers have known network connection probabilities for two states, i.e., congested, and successful. In this paper, we present: i) a generalized access structure congestion (GGammaC) system that is based upon the generalized secret sharing scheme, and ii) an efficient connection procedure for the GGammaC system in terms of the minimal number of server connection attempts. The k-out-of-n secret sharing schemes are considered as simple cases of the generalized secret sharing schemes. It implies that the GGammaC system is a more general system than the CSknC system. We established an iterative connection procedure for the new system. Simulation results are used to demonstrate that the iterative connection procedure is more efficient in terms of minimizing the number of connection attempts     

On the rate-distortion performance and computational efficiency ofthe Karhunen-Loeve transform for lossy data compression

We examine the rate-distortion performance and computational complexity of linear transforms for lossy data compression. The goal is to better understand the performance/complexity tradeoffs associated with using the Karhunen-Loeve transform (KLT) and its fast approximations. Since the optimal transform for transform coding is unknown in general, we investigate the performance penalties associated with using the KLT by examining cases where the KLT fails, developing a new transform that corrects the KLT's failures in those examples, and then empirically testing the performance difference between this new transform and the KLT. Experiments demonstrate that while the worst KLT can yield transform coding performance at least 3 dB worse than that of alternative block transforms, the performance penalty associated with using the KLT on real data sets seems to be significantly smaller, giving at most 0.5 dB difference in our experiments. The KLT and its fast variations studied here range in complexity requirements from O(n (2)) to O(n log n) in coding vectors of dimension n. We empirically investigate the rate-distortion performance tradeoffs associated with traversing this range of options. For example, an algorithm with complexity O(n(3/2)) and memory O(n) gives 0.4 dB performance loss relative to the full KLT in our image compression experiments.     

Performance evaluation of generalized multi-state k-out-of-n systems

The generalized multi-state k-out-of-n:G system model defined by Huang provides more flexibilities for modeling of multi-state systems. However, the performance evaluation algorithm they proposed for such systems is not efficient, and it is applicable only when the k/sub i/ values follow a monotonic pattern. In this paper, we defined the concept of generalized multi-state k-out-of-n:F systems. There is an equivalent generalized multi-state k-out-of-n:G system with respect to each generalized multi-state k-out-of-n:F system, and vice versa. The form of minimal cut vector for generalized multi-state k-out-of-n:F systems is presented. An efficient recursive algorithm based on minimal cut vectors is developed to evaluate the state distributions of a generalized multi-state k-out-of-n:F system. Thus, a generalized multi-state k-out-of-n:G system can first be transformed to the equivalent generalized multi-state k-out-of-n:F system, and then be evaluated using the proposed recursive algorithm. Numerical examples are given to illustrate the effectiveness and efficiencies of the proposed recursive algorithms.     

Generalized multi-state k-out-of-n:G systems

In a binary k-out-of-n:G system, k is the minimum number of components that must work for the system to work. Let 1 represent the working state and 0 the failure state, k then indicates the minimum number of components that must be in state 1 for the system to be in state 1. This paper defines the multi-state k-out-of-n:G system: each component and the system can be in 1 of M+1 possible states: 0, 1, ..., M. In Case I, the system is in state ⩾j iff at least k_j components are in state ⩾j. The value of k_j I 1 can be different for different required minimum system-state level j. Examples illustrate applications of this definition. Algorithms for reliability evaluation of such systems are presented     

平面凸多边形斜支撑线求解的最佳算法

平面凸多边形斜支撑求解是计算几何中诸多问题的一个核心算法。至今，求解该问题的最好算法的时间复杂度为Ｏ（ｎ＋ｍ）。本文在七妙利用凸多边形特殊性质的基础上，给出了一时间复杂度为Ｏ（ｏｌｇ（ｎ＋ｍ）的最佳算法，从而彻底解决了这一问题。     

Optimization Problems in k-out-of-n Systems

A k-out-of-n:G system is an important complex system and is used for mass transit and computer systems. This paper does not discuss the availability, but considers what is the most economical k-out-of-n system when the failure rate of each element is constant. We solve two problems to minimize the mean cost-rate; i) the optimal number of elements and ii) the optimal replacement time before system failure. A numerical example is given.     

An Isochronous Testing Strategy for Hierarchical Adaptive Distributed System-Level Diagnosis

Distributed System-level diagnosis allows the fault-free components of a fault-tolerant distributed system to determine which components of the system are faulty and which are fault-free. The time it takes for nodes running the algorithm to diagnose a new event is called the algorithm's latency. In this paper we present a new distributed system-level diagnosis algorithm which presents a latency of O(log N) testing rounds, for a system of N nodes. A previous hierarchical distributed system-level diagnosis algorithm, Hi-ADSD, presents a latency of O(log ² N) testing rounds. Nodes are grouped in progressively larger logical clusters for the purpose of testing. The algorithm employs an isochronous testing strategy that forces all fault-free nodes to execute tests on clusters of the same size each testing round. This strategy is based on two main principles: a tested node must test its tester in the same round; a node only accepts tests according to a lexical priority order. We present formal proofs that the algorithm's latency is at most 2log N – 1 testing rounds and that the testing strategy of the algorithm leads to the execution of isochronous tests. Simulation results are shown for systems of up to 64 nodes.     

一类多状态连续n中取k(G)系统的可靠性计算

为了计算多状态连续厅中取后（G）系统的可靠性,引入4个定理,将满足引理的多状态系统转换为二元状态系统。分别推导了多状态线形连续k／n（G）系统和环形连续k／n（G）系统的可靠性计算公式。证明了固定k值增加一个新部件,若部件可靠性独立同分布,线形和环形系统可靠性均增加;若部件可靠性独立但不同分布,环形系统存在一个极值,新增加部件可靠性大于这个极值时得到的新系统可靠性增加,反之系统可靠性下降。