The study on the longest stretch of consecutive successes in \random" trials dates back to 1916 when the German philosopher Karl Marbe wrote a paper concerning the longest stretch of consecutive births of children of the same sex as appearing in the birth register of a Bavarian town. The result was actually used by parents to \predict" the sex of their children. The longest stretch of same-sex births during that time in 200 thousand birth registrations was actually 17 t log2(200 103): During the past century, the research of longest stretch of consecutive successes (longest runs) has found applications in various areas, especially in the theory of reliability. The aim of this thesis is to study large deviations on longest runs in the setting of Markov chains. More precisely, we establish a general large deviation principle for the longest success run in a two-state (success or failure) Markov chain. Our tool is based on a recent result regarding a general large deviation for the longest success run in Bernoulli trails. It turns out that the main ingredient in the proof is to implement several global and local estimates of the cumulative distribution function of the longest success run.

The Birnbaum importance (BI) is a well-known measure that evaluates the relative contribution of components to system reliability. It has been successfully applied to tackling some reliability problems. This dissertation investigates two topics related to the BI in the reliability field: the patterns of component BIs and the BI-based heuristics and meta-heuristics for solving the component assignment problem (CAP).There exist certain patterns of component BIs (i.e., the relative order of the BI values to the individual components) for linear consecutive-k-out-of-n (Lin/Con/k/n) systems when all components have the same reliability p. This study summarizes and annotates the existing BI patterns for Lin/Con/k/n systems, proves new BI patterns conditioned on the value of p, disproves some patterns that were conjectured or claimed in the literature, and makes new conjectures based on comprehensive computational tests and analysis. More importantly, this study defines a concept of segment in Lin/Con/k/n systems for analyzing the BI patterns, and investigates the relationship between the BI and the common component reliability p and the relationship between the BI and the system size n. One can then use these relationships to further understand the proved, disproved, and conjectured BI patterns.The CAP is to find the optimal assignment of n available components to n positions in a system such that the system reliability is maximized. The ordering of component BIs has been successfully used to design heuristics for the CAP. This study proposes five new BI-based heuristics and discusses their corresponding properties. Based on comprehensive numerical experiments, a BI-based two-stage approach (BITA) is proposed for solving the CAP with each stage using different BI-based heuristics. The two-stage approach is much more efficient and capable to generate solutions of higher quality than the GAMS/CoinBonmin solver and a randomization method.This dissertation then presents a meta-heuristic, i.e., a BI-based genetic local search (BIGLS) algorithm, for the CAP in which a BI-based local search is embedded into the genetic algorithm. Comprehensive numerical experiments show the robustness and effectiveness of the BIGLS algorithm and especially its advantages over the BITA in terms of solution quality.

Due to great effort from mathematicians, physicists and computer scientists, network science has attained rapid development during the past decades. However, because of the complexity, most researches in this area are conducted only based upon experiments and simulations, it is critical to do research based on theoretical results so as to gain more insight on how the structure of a network affects the security. This dissertation introduces some stochastic and statistical models on certain networks and uses a k-out-of-n tolerant structure to characterize both logically and physically the behavior of nodes. Based upon these models, we draw several illuminating results in the following two aspects, which are consistent with what computer scientists have observed in either practical situations or experimental studies. Suppose that the node in a P2P network loses the designed function or service when some of its neighbors are disconnected. By studying the isolation probability and the durable time of a single user, we prove that the network with the user's lifetime having more NWUE-ness is more resilient in the sense of having a smaller probability to be isolated by neighbors and longer time to be online without being interrupted. Meanwhile, some preservation properties are also studied for the durable time of a network. Additionally, in order to apply the model in practice, both graphical and nonparametric statistical methods are developed and are employed to a real data set. On the other hand, a stochastic model is introduced to investigate the security of network systems based on their vulnerability graph abstractions. A node loses its designed function when certain number of its neighbors are compromised in the sense of being taken over by the malicious codes or the hacker. The attack compromises some nodes, and the victimized nodes become accomplices. We derived an equation to solve the probability for a node to be compromised in a network. Since this equation has no explicit solution, we also established new lower and upper bounds for the probability. The two models proposed herewith generalize existing models in the literature, the corresponding theoretical results effectively improve those known results and hence carry an insight on designing a more secure system and enhancing the security of an existing system.

Essa dissertação propõe um conjunto de experimentos de simulação em sistemas sujeitos a dois modos de falha com vistas à otimização de confiabilidade. Para tanto, propõe a modelagem analítica e otimização via Algoritmo Genético em sistemas série-paralelo com múltipla escolha de componentes. A ocorrência de falhas em produtos e serviços pode gerar descontentamento aos clientes e até riscos à sua segurança. Em muitos casos práticos, sistemas constituídos por componentes que apresentam dois modos de falha (ou seja, que podem falhar no modo aberto ou curto) são caracterizados por elevada complexidade matemática e analítica para mensuração de sua confiabilidade e estabelecimento de arranjos ótimos. O objetivo da modelagem de estruturas com foco na otimização de confiabilidade consiste em determinar o arranjo que proporciona níveis mais elevados de confiabilidade, ao passo que problemas de alocação de redundância visam à seleção de componentes e níveis apropriados de redundância que maximizem a confiabilidade ou minimizem os custos do sistema frente a restrições de projeto. São estudados os sistemas série-paralelo k-out-of-n (em que qualquer combinação de k dentre n componentes devem operar devidamente). Esse trabalho inova ao apresentar sistemas série-paralelo l-out-of-m, onde a falha de até l dentre m subsistemas não ocasiona falha no sistema geral. Os métodos apresentados fornecem uma contribuição ao estudo de confiabilidade em sistemas com dois modos de falha. / This dissertation proposes a set of simulation experiments in series-parallel systems subject to two failure modes with a view to reliability optimization. Therefore, proposes analytical modeling and optimization by the genetic algorithms in k-out-of-n series-parallel systems and l-out-of-m series-parallel systems, with multiple choice of components. When it comes to products and services, functional errors can lead disgruntlement by customers and even security risks. In many practical cases, systems consisting of two failure modes components (ie, they can fail in open or short mode) rely on highly mathematical and analytical complexity for reliability estimation and establishment of optimal arrangements. The goal of structural modeling focused on reliability optimization is to determine the design that provides the highest reliability levels, while the redundancy allocation problem involves selecting components and appropriate levels of redundancy that either maximize reliability or minimize system costs against design constraints. The k-out-of-n series-parallel structure (any combination of k among n components must operate properly) are studied and this work innovates by presenting l-out-of-m series-parallel systems, where failure of up to l within m subsystems does not cause a overall system failure. The methods presented contribute to the study of reliability in systems with two modes of failure.

Essa dissertação propõe um conjunto de experimentos de simulação em sistemas sujeitos a dois modos de falha com vistas à otimização de confiabilidade. Para tanto, propõe a modelagem analítica e otimização via Algoritmo Genético em sistemas série-paralelo com múltipla escolha de componentes. A ocorrência de falhas em produtos e serviços pode gerar descontentamento aos clientes e até riscos à sua segurança. Em muitos casos práticos, sistemas constituídos por componentes que apresentam dois modos de falha (ou seja, que podem falhar no modo aberto ou curto) são caracterizados por elevada complexidade matemática e analítica para mensuração de sua confiabilidade e estabelecimento de arranjos ótimos. O objetivo da modelagem de estruturas com foco na otimização de confiabilidade consiste em determinar o arranjo que proporciona níveis mais elevados de confiabilidade, ao passo que problemas de alocação de redundância visam à seleção de componentes e níveis apropriados de redundância que maximizem a confiabilidade ou minimizem os custos do sistema frente a restrições de projeto. São estudados os sistemas série-paralelo k-out-of-n (em que qualquer combinação de k dentre n componentes devem operar devidamente). Esse trabalho inova ao apresentar sistemas série-paralelo l-out-of-m, onde a falha de até l dentre m subsistemas não ocasiona falha no sistema geral. Os métodos apresentados fornecem uma contribuição ao estudo de confiabilidade em sistemas com dois modos de falha. / This dissertation proposes a set of simulation experiments in series-parallel systems subject to two failure modes with a view to reliability optimization. Therefore, proposes analytical modeling and optimization by the genetic algorithms in k-out-of-n series-parallel systems and l-out-of-m series-parallel systems, with multiple choice of components. When it comes to products and services, functional errors can lead disgruntlement by customers and even security risks. In many practical cases, systems consisting of two failure modes components (ie, they can fail in open or short mode) rely on highly mathematical and analytical complexity for reliability estimation and establishment of optimal arrangements. The goal of structural modeling focused on reliability optimization is to determine the design that provides the highest reliability levels, while the redundancy allocation problem involves selecting components and appropriate levels of redundancy that either maximize reliability or minimize system costs against design constraints. The k-out-of-n series-parallel structure (any combination of k among n components must operate properly) are studied and this work innovates by presenting l-out-of-m series-parallel systems, where failure of up to l within m subsystems does not cause a overall system failure. The methods presented contribute to the study of reliability in systems with two modes of failure.

Essa dissertação propõe um conjunto de experimentos de simulação em sistemas sujeitos a dois modos de falha com vistas à otimização de confiabilidade. Para tanto, propõe a modelagem analítica e otimização via Algoritmo Genético em sistemas série-paralelo com múltipla escolha de componentes. A ocorrência de falhas em produtos e serviços pode gerar descontentamento aos clientes e até riscos à sua segurança. Em muitos casos práticos, sistemas constituídos por componentes que apresentam dois modos de falha (ou seja, que podem falhar no modo aberto ou curto) são caracterizados por elevada complexidade matemática e analítica para mensuração de sua confiabilidade e estabelecimento de arranjos ótimos. O objetivo da modelagem de estruturas com foco na otimização de confiabilidade consiste em determinar o arranjo que proporciona níveis mais elevados de confiabilidade, ao passo que problemas de alocação de redundância visam à seleção de componentes e níveis apropriados de redundância que maximizem a confiabilidade ou minimizem os custos do sistema frente a restrições de projeto. São estudados os sistemas série-paralelo k-out-of-n (em que qualquer combinação de k dentre n componentes devem operar devidamente). Esse trabalho inova ao apresentar sistemas série-paralelo l-out-of-m, onde a falha de até l dentre m subsistemas não ocasiona falha no sistema geral. Os métodos apresentados fornecem uma contribuição ao estudo de confiabilidade em sistemas com dois modos de falha. / This dissertation proposes a set of simulation experiments in series-parallel systems subject to two failure modes with a view to reliability optimization. Therefore, proposes analytical modeling and optimization by the genetic algorithms in k-out-of-n series-parallel systems and l-out-of-m series-parallel systems, with multiple choice of components. When it comes to products and services, functional errors can lead disgruntlement by customers and even security risks. In many practical cases, systems consisting of two failure modes components (ie, they can fail in open or short mode) rely on highly mathematical and analytical complexity for reliability estimation and establishment of optimal arrangements. The goal of structural modeling focused on reliability optimization is to determine the design that provides the highest reliability levels, while the redundancy allocation problem involves selecting components and appropriate levels of redundancy that either maximize reliability or minimize system costs against design constraints. The k-out-of-n series-parallel structure (any combination of k among n components must operate properly) are studied and this work innovates by presenting l-out-of-m series-parallel systems, where failure of up to l within m subsystems does not cause a overall system failure. The methods presented contribute to the study of reliability in systems with two modes of failure.

Reliability is the probability that a system doesn’t fail in a time interval. A weighted-k-out-of-n system is a system of nodes with weights, where the total weight of all operational nodes must be at least equal to the value k for the system to be operational. Although previous studies have brought forward some quantification models for reliability in such systems, there is a lack of research in the comparison of these methods. There is also a lack of research in how to best scale these types of systems. This thesis thus investigates optimal methods of quantifying the reliability of weighted-k-out-of-n systems, and latterly discusses optimal methods of scaling them. Some methods of quantifying reliability of such systems are designed and/or implemented from prior theory, and compared in terms of time complexity and accuracy. Of these models the Higashiyama algorithm, a Monte Carlo simulation and a brute force enumeration method proves to be successful. Experiments are conducted in which the scaling factors of adding nodes, adding weights, decreasing k and increasing individual node reliability are tested. Results show that adding nodes generally has the best impact on reliability, but that it also varies on the real-life implementation of the system. Some correlations between minimal paths and reliability are also studied, and a pattern was seen of how optimal minimal paths led to optimal reliability. / Robusthet är sannolikheten att ett system inte slutar fungera i ett tidsintervall. Ett viktat-k-av-n-system är ett system av noder med vikter, där den totala vikten av alla fungerande noder måste vara minst lika med värdet k för att systemet ska fungera. Trots att tidigare studier har lyft fram några modeller för beräkning av robusthet i sådana system, finns det en brist på forskning i jämförelse av dessa metoder. Det finns även en brist på forskning i hur sådana system skalas på bästa sätt. Därför undersöker detta projekt optimala metoder för att mäta robustheten i viktade-k-av-n-system, och diskuterar sedan optimala metoder för att skala dessa. Detta projekt undersöker robusthet i viktade-k-av-n-system, specifikt i termer av kvantifiering och skalning. Några metoder för att kvantifiera robusthet i sådana system designas och/eller implementeras från tidigare teori, av vilka Higashiyama algoritmen, en Monte Carlo simulering och en “brute force" metod är användbara. Experiment utförs där faktorer för skalning, det vill säga att lägga till noder, lägga till vikter, sänka k, och öka robustheten hos individuella noder testas. Resultat visar att tilläggning av noder har generellt bäst påverkan på robusthet, men att det beror på hur den verkliga implementationen av systemet ser ut. Några korrelationer mellan minimala vägar och robusthet studeras också, och ett mönster syns där optimala minimala vägar leder till optimal robusthet.