Testing the reliability of an application usually requires a good usage model that accurately captures the likely sequences of inputs that the application will receive from the environment. The models being used in the literature are mostly based on Markov chains. They are used to generate test cases that are statistically close to what the applica-tion is expected to receive when in production. In this thesis, we propose a model for reli-ability testing that is created directly from the log file of a web application. Our proposed model is also based on Markov chains and has two components: one component, based on a modified tree, captures the most frequent behaviors, while the other component is another Markov chain that captures infrequent behaviors. The result is a statistically cor-rect model that shows clearly what most users do on the site. The thesis also presents an evaluation method for estimating the accuracy of vari-ous reliability-testing usage models. The method is based on comparison between ob-served users’ traces and traces inferred from the usage model. Our method gauges the accuracy of the reliability-testing usage model by calculating the sum of goodness-of-fit values of each traces and scaling the result between 0 and 1. Finally, we present an experimental study on the log of a real web site and discuss the way to use proposed usage model to generate test sequences, as well as strength and weakness of the model for reliability testing.

This dissertation focuses on reexamining traditional management problems that emerge in service systems where customers or jobs queue for service. In particular, we investigate how a manger should make maintenance and routing decisions in settings where there is a departure from traditional modeling assumptions. In many cases, the performance evaluation of a management problems has, at its heart, a complex, infinite Markov chain which must be solved before any optimization can begin. Unfortunately, most Markov chains are not analytically tractable. In the first essay, we address the solution of infinite state Markov chains. We focus on class M Markov chains, a broad class of chains which is representative of a wide array of problems arising in the management of computer, service, and manufacturing systems where queueing parameters change over time according to a restricted stochastic pattern. We develop a new method, called Clearing Analysis on Phases, for the limiting probability distribution of such chains in exact closed form. In the second essay, we apply the CAP method to answer the question of how a manager should maintain a system in a setting where an online customer-facing service is vulnerable to persistent malware infections. These infections can cause performance degradation and facilitate data theft, both of which have monetary repercussions. Infections can go undetected and can only be removed by a timeconsuming cleanup procedure, which takes the service offline and causes all existing jobs to be discarded without service. In particular, we provide recommendations for when (and in response to what events) a manager should initiate cleanup procedures by solving an infinite state maintenance problem. We quantify the efficiency of various cleanup (maintenance) policies by proposing a revenue model which incorporates both delay-based pricing and data theft costs. In the third essay, we examine queueing systems in call centers and answer the question of a how a manager should route customers to strategic staff who choose their own service rates in response to workload incentives. We address this problem using game theoretic techniques. In particular, we introduce a utility model where the servers choose their service rate in order to maximize a tradeoff between an “effort cost” and a “value of idleness.” We find that relaxing the classical assumption that all servers work at a fixed rate renders traditional routing policies inadequate. Our approach allows us to recommend novel routing policies that are both fair for the staff and efficient for the customers. In the fourth essay we look at web server farms and answer the question of how jobs should be immediately routed to computer servers in a setting where some jobs are more valuable or more important than others. Such settings arise when some jobs are generated by users who are paying for a premium service. We address how a manager should incorporate information about a job’s value when making routing decisions in order to minimize expected value-weighted response times. The heterogeneity in job values greatly the dimensionality of this problem. Via a combination of exact analysis, asymptotic analysis, and simulation, we are able to deduce many unexpected results regarding routing.

We give an architecture of a storage system consisting of a storage medium made of unreliable memory elements and an error correction circuit made of a combination of noisy and noiseless logic gates that is capable of retaining the stored information with the lower probability of error than a storage system with a correction circuit made completely of noiseless logic gates. Our correction circuit is based on the iterative decoding of low-density parity check codes, and uses the positive effect of errors in logic gates to correct errors in memory elements. In the spirit of Marcus Tullius Cicero's Clavus clavo eicitur (one nail drives out another), the proposed storage system operates on the principle: error errore eicitur-one error drives out another. The randomness that is present in the logic gates makes these classes of decoders superior to their noiseless counterparts. Moreover, random perturbations do not require any additional computational resources as they are inherent to unreliable hardware itself. To utilize the benefits of logic gate failures, our correction circuit relies on two key novelties: a mixture of reliable and unreliable gates and decoder rewinding. We present a method based on absorbing Markov chains for the probability of error analysis, and explain how the randomness in the variable and check node update function helps a decoder to escape to local minima associated with trapping sets.

Estudos têm mostrado que nem sempre indivíduos maximizam seus ganhos. Quando confrontados a uma sequência binária, cuja recompensa aparece mais em uma das alternativas, ao invés de perseverarem no lado de maior aparecimento, os voluntários adultos escolhem um lado tantas vezes quanto esse lado apresente a recompensa. Foi relatado, entretanto, que crianças perseverariam no lado mais freqüente, maximizando. Estudos relatam a possibilidade de adultos não perseverarem, porque procurariam padrões na sequência; procurou-se realizar quatro experimentos com sequências sem e com padrões (cadeias de Markov), de modo que se pudesse observar e comparar as estratégias de decisão das faixas etárias para padrão ou sem ele. Os resultados mostraram que existe uma tendência à perseveração, com o envelhecimento, e não o contrário, em detrimento da possibilidade de assimilar padrões. Eles também mostram que a assimilação de padrões se desenvolve gradualmente e decai com o envelhecimento, invalidando a ideia de que a não-maximização seja apenas fruto da busca por padrões. / Studies have shown subjects dont maximize their profits all the time. When confronted with binary sequences, with rewards that show up more in one alternative than another, adult volunteers choose one side as the number of rewards the side shows; instead of maximizing in the side that shows more rewards. However, it was related children maximize. Studies assert to the possibility that adults dont maximize because they are searching for a pattern in the sequence. Four experiments were made with sequences with and without a pattern, so that we could observe and compare the decision making strategies between ages for patterns and non-patterns. Results show a tendency to maximization with aging and not the contrary, how was related, and to the detriment of pattern assimilation possibilities; also results show the pattern finding develops gradually with growth and worse with aging. In this way, searching for patterns cant be the only explanation for the non-maximization behavior.

Neste trabalho foi elaborada uma estrutura de modelos probabilísticos simples que pudessem descrever o processo de tomada de decisão de agentes humanos que são confrontados com a tarefa de prever elementos de uma sequência aleatória gerada por uma cadeia de Markov de memória L. Essa estrutura partiu de uma abordagem bayesiana em que o agente infere uma distribuição de probabilidades a partir de uma série de observações da sequência e de suas próprias respostas, considerando que o agente tenha uma memória de tamanho K. Como resultado da abordagem bayesiana, o agente adota uma estratégia ótima que consiste na perseveração na alternativa mais provável dado o histórico das últimas tentativas; por conta disso e de observações experimentais de que humanos tendem a adotar nesse tipo de problema estratégias sub-ótimas, por exemplo a de pareamento de probabilidades (probability matching), foram desenvolvidas variações sobre esse modelo que tentassem descrever mais de perto o comportamento adotado por humanos. Nesse sentido, foram adotadas as variáveis de troca de resposta (possível ação tomada pelo agente) e de recompensa (possível resultado da ação) na formulação do modelo e foram adicionados parâmetros, inspirados em modelos de ação dopaminérgica, que permitissem um desvio da estratégia ótima resultante da abordagem bayesiana. Os modelos construídos nessa estrutura foram simulados computacionalmente para diversos valores dos parâmetros, incluindo as memórias K e L do agente e da cadeia de Markov, respectivamente. Através de análises de correlação, esses resultados foram comparados aos dados experimentais, de um grupo de pesquisa do Instituto de Ciências Biomédicas da USP, referentes a tarefas de tomada de decisão envolvendo pessoas de diversas faixas etárias (de 3 a 73 anos) e cadeias de Markov de memórias 0, 1 e 2. Nessa comparação, concluiu-se que as diferenças entre grupos etários no experimento podem ser explicadas em nossa modelagem através da variação da memória K do agente crianças de até 5 anos mostram um limite K = 1, e as de até 12 anos mostram um limite K = 2 e da variação de um parâmetro de reforço de aprendizado dependendo do grupo e da situação de decisão à qual os indivíduos eram expostos, o valor ajustado desse parâmetro variou de 10% para baixo até 30% para cima do seu valor original de acordo com a abordagem bayesiana. / In this work we developed a simple probabilistic modeling framework that could describe the process of decision making in human agents that are presented with the task of predicting elements of a random sequence generated by a Markov chain with memory L. Such framework arised from a Bayesian approach in which the agent infers a probability distribution from a series of observations on the sequence and on its own answers, and considers that the agent\'s memory has length K. As a result of the Bayesian approach, the agent adopts an optimal strategy that consists in perseveration of the most likely alternative given the history of the last few trials; because of that and of experimental evidence that humans tend, in such kinds of problems, to adopt suboptimal strategies such as probability matching, variations on that model were developed in an attempt to have a closer description of the behavior adopted by humans. In that sense, the `shift\' (possible action taken by the agent on its response) and `reward\' (possible result of the action) variables were adopted in the formulation of the model, and parameters inspired by models of dopaminergic action were added to allow deviation from the optimal strategy that resulted from the Bayesian approach. The models developed in that framework were computationally simulated for many values of the parameters, including the agent\'s and the Markov chain\'s memory lengths K and L respectively. Through correlation analysis these results were compared to experimental data, from a research group from the Biomedical Science Institute at USP, regarding decision making tasks that involved people of various ages (3 to 73 years old) and Markov chains of orders 0, 1 and 2. In this comparison it was concluded that the differences between age groups in the experiment can be explained in our modeling through variation of the agent\'s memory length K children up to 5 years old exhibited a limitation of K = 1, and those up to 12 years old were limited to K = 2 and through variation of a learning reinforcement parameter depending on the group and the decision situation to which the candidates were exposed, the fitted value for that parameter ranged from 10% below to 30% above its original value according to the Bayesian approach.

Uma forma de se reduzir o custo (em termos tanto de área de chip quanto de consumo de energia) de algoritmos de processamento de sinais é empregar aritmética de ponto fixo, usando o menor número de bits possível para se representar as variáveis e coeficientes necessários. Com isso, consegue-se reduzir a complexidade do hardware, levando a economias de energia e de área de chip em circuitos dedicados. A escolha do nível de quantização a que cada variável deve ser submetida depende de se conhecer o efeito da quantização de cada variável nas saídas do sistema, o que pode ser conseguido através de simulações (em geral lentas) ou por métodos analíticos. Este documento propõe avanços a uma nova metodologia de análise de algoritmos para processamento digital de sinais implementados em aritmética de ponto fixo, usando modelos baseados em cadeias de Markov. As contribuições desta dissertação são as seguintes: Filtros IIR de primeira e de segunda ordem são analisados via cadeia de Markov, pressupondo que a entrada possui uma função densidade de probabilidade conhecida. O modelo é desenvolvido de forma geral, de forma que pode ser considerada uma função de densidade de probabilidade qualquer. A saída dos filtros é usada para definir os estados da cadeia. O modelo via cadeia de Markov para o coeficiente do algoritmo LMS unidimensional é estendido para entrada correlacionada. Nesse caso, os estados passam a ser descritos em termos do coeficiente e do da entrada anterior. Um exemplo assumido função de densidade de probabilidade de entrada gaussiana para o filtro adaptativo é apresentado. / The implementation cost of signal processing algorithms may be reduced by using fixed-point arithmetic with the smallest possible word-length for each variable or parameter. This allows the designer to reduce hardware complexity, leading to economy of energy and chip area in dedicated circuits. The choice of word-length depends on the determination of the effect at the output of the quantization of each variable, which may be obtained through simulations (generally slow) or through analytical methods. This document proposes new advances to a new analysis method for digital signal processing algorithms implemented in fixed-point arithmetic, based on Markov chain models. Our contributions are the following: A Markov chain model is used to study first and second order IIR filters for an known input density probability function. The model is general and can be applied for any probability function. We use the output of the filters to define the states of the Markov chain. The unidimensional LMS Markov chain model is extended to correlated input. The states are defined by a pair considering the coefficient and the previous input and an example assuming Gaussian-distributed input is presented.

Grande parte do sucesso do Google provêm do algoritmo Page Rank, que avalia quantitativamente a importância de cada página na web. Esta ordenação é obtida através do vetor estacionário de uma matriz estocástica específica, utilizando o Método das Potências. A velocidade de convergência deste método será avaliada em detalhe, já que se trata de uma resposta imediata da pesquisa do usuário. Afim de entender as diferentes situações que o modelo pode enfrentar, diversas simulações são apresentadas neste trabalho. Em particular, estamos interessados nos fatores que influenciam a velocidade de convergência. Para tanto, o número de páginas total e de cada conjunto fechado, bem como o número de conjuntos fechados e de nós pendentes foram estudados. / Great part of Google\'s success comes from the Page Rank algorithm, wich quantitatively evaluates the importance of each page on the web. This sort is achieved through a specific stochastic matrix stationary vector, using the Power Method. The convergency speed of this method will be evaluated in details, since this is a imediate response for the user search. In order to understand the diferent situations the model can confront, several simulations are shown in this work. In particular, we are interested in the factors which influences the convergency speed. For that, the total and inside each closed set number of pages and also the closed sets and dangling nodes numbers were studied.

In an effort to make more spectrum available, recent initiatives by the FCC let mobile providers offer spot service of their licensed spectrum to secondary users, hence paving the way to dynamic secondary spectrum markets. This dissertation investigates secondary spectrum markets under different regulatory regimes by identifying profitability conditions and possible competitive outcomes in an oligopoly model. We consider pricing in a market where multiple providers compete for secondary demand. First, we analyze the market outcomes when providers adopt a coordinated access policy, where, besides pricing, a provider can elect to apply admission control on secondary users based on the state of its network. We next consider a competition when providers implement an uncoordinated access policy (i.e., no admission control). Through our analysis, we identify profitability conditions and fundamental price thresholds, including break-even and market sharing prices. We prove that regardless of the specific form of the secondary demand function, competition under coordinated access always leads to a price war outcome. In contrast, under uncoordinated access, market sharing becomes a viable market outcome if the intervals of prices for which the providers are willing to share the market overlap. We then turn our attention to how a network provider use carrier (spectrum) aggregation in order to lower its break-even price and gain an edge over its competition. To this end, we determine the optimal (minimum) level of carrier aggregation that a smaller provider needs. Under a quality-driven (QD) regime, we establish an efficient way of numerically calculating the optimal carrier aggregation and derive scaling laws. We extend the results to delay-related metrics and show their applications to profitable pricing in secondary spectrum markets. Finally, we consider the problem of profitability over a spatial topology, where identifying system behavior suffers from the curse of dimensionality. Hence, we propose an approximation model that captures system behavior to the first-order and provide an expression to calculate the break-even price at each network location and provide simulation results for accuracy comparison. All of our results hold for general forms of demand, thus avoid restricting assumptions of customer preferences and the valuation of the spectrum.

Este trabalho divide-se em três partes. Na primeira parte fazemos uma breve descrição de cadeias de Markov a tempo discreto e tempo contínuo. Na segunda parte, seguindo o artigo [5], introduzimos o formalismo termodinâmico no espaço de Bernoulli com símbolos dados em um espaço métrico compacto, generalizando a teoria usual onde o espaço de estados é finito. Após, seguindo o artigo [1], introduziremos uma versão do Operador de Ruelle para cadeias de Markov a tempo contínuo. Ainda, a partir de uma função V que funcionará como uma perturbação, definiremos um operador de Ruelle modificado e, para este operador, mostraremos a existência de uma auto-função e uma auto-medida. / This work is divided in three parts. In the first one, we give a brief description of Markov chains in both discrete time and continuous time. In the second one, following the article [5], we introduce the thermodynamic formalism in the Bernoulli space with symbols in a compact metric space, generalizing the usual theory, where the space of states is finite. Then, following the article [1], we will introduce a version of Ruelle Opemtor for Markov chains in continuous time. Also, using a V function, which will be seen as a perturbation, we will define a modified Ruelle operator and, for this operator, we will show the existence of a eigenfunction and a eigenmeasure.

A etiquetagem morfossintática envolve atribuir às palavras de uma sentença suas classes morfossintáticas de acordo com os contextos em que elas aparecem. Cadeias de Markov de Tamanho Variável (VLMCs, do inglês \"Variable-Length Markov Chains\") oferecem uma forma de modelar contextos maiores que trigramas sem sofrer demais com a esparsidade de dados e a complexidade do espaço de estados. Mesmo assim, duas palavras do português apresentam um alto grau de ambiguidade: \'que\' e \'a\'. O número de erros na etiquetagem dessas palavras corresponde a um quarto do total de erros cometidos por um etiquetador baseado em VLMCs. Além disso, essas palavras parecem apresentar dois diferentes tipos de ambiguidade: um dependendo de contexto não local e outro de contexto direito. Exploramos maneiras de expandir o modelo baseado em VLMCs através do uso de diferentes modelos e métodos, a fim de atacar esses problemas. As abordagens mostraram variado grau de sucesso, com um método em particular (aprendizado guiado) se mostrando capaz de resolver boa parte da ambiguidade de \'a\'. Discutimos razões para isso acontecer. Com relação a \'que\', ao longo desta tese propusemos e testamos diversos métodos de aprendizado de informação contextual para tentar desambiguá-lo. Mostramos como, em todos eles, o nível de ambiguidade de \'que\' permanece praticamente constante. / Part-of-speech tagging involves assigning to words in a sentence their part-of-speech class based on the contexts they appear in. Variable-Length Markov Chains (VLMCs) offer a way of modeling contexts longer than trigrams without suffering too much from data sparsity and state space complexity. Even so, two words in Portuguese show a high degree of ambiguity: \'que\' and \'a\'. The number of errors tagging these words corresponds to a quarter of the total errors made by a VLMC-based tagger. Moreover, these words seem to show two different types of ambiguity: one depending on non-local context and one on right context. We searched ways of expanding the VLMC-based model with a number of different models and methods in order to tackle these issues. The approaches showed variable degrees of success, with one particular method (Guided Learning) solving much of the ambiguity of \'a\'. We explore reasons why this happened. Rega rding \'que\', throughout this thesis we propose and test various methods for learning contextual information in order to try to disambiguate it. We show how, in all of them, the level of ambiguity shown by \'que\' remains practically c onstant.