Highly dynamic and complex computing systems are increasingly needed and are relied upon in daily life. One such system is the dynamic network, particularly in communication, in which it has widespread applications, such as: Internet, peer-to-peer networks, mobile networks and wireless networks. Dynamic networks consist of nodes and edges whose operating status may change over time; the edges may be unreliable and operate intermittently. Message-passing in such networks is inherently difficult and reasoning about the behaviour of message-passing algorithms is also difficult and hard to analyse. Their behaviour and correctness are hard to formulate and establish. To undertake formal reasoning about such systems, abstract models are essential in order to separate the general reasoning about message routing and the updating of routing tables from the details of how these are implemented in particular networks. This thesis proposes a new approach to modelling and reasoning about dynamic networks as follows. It develops a series of abstract models which makes it possible to focus on the correctness of routing methods. It models the dynamic network as a “demonic” process which runs concurrently with routing updates and message-passing, to express dynamic networks as concurrent systems. This allows the use of temporal logic and fairness constraints to reason about dynamic networks. To do so, it introduces a modal logic and formulates concepts of fairness which capture network properties. The correctness of dynamic networks means that under certain conditions, all messages will eventually be delivered. Formulating networks as concurrent systems means can establish the correctness for networks that never cease to change. Modelling at that one level of abstraction means being able to prove the properties of networks independently of the mechanisms in actual networks. Therefore, it provides “a factorisation” of proofs of correctness for actual dynamic networks. The models are implemented as multi-threaded programs, and then adopted an experimental runtime verification tool called RULER to test whether model instances satisfy the modal correctness for message delivery.

In this dissertation, we study self-adjusting algorithms for large-scale distributed systems. Self-adjusting algorithms enable distributed systems to adjust their properties dynamically as the input pattern changes. Self-adjustment is an attractive tool as it has the potential to significantly improve the performance of distributed systems, especially when the input patterns are skewed. We start with a distributed self-adjusting algorithm for skip graphs that minimizes the average routing costs between arbitrary communication pairs by performing topological adaptation to the communication pattern. Our algorithm is fully decentralized, conforms to the CONGEST model (i.e. uses O(log n) bit messages), and requires O(log n) bits of memory for each node, where n is the total number of nodes. Upon each communication request, our algorithm first establishes communication by using the standard skip graph routing, and then locally and partially reconstructs the skip graph topology to perform topological adaptation. We propose a computational model for such algorithms, as well as a yardstick (working set property) to evaluate them. Our working set property can also be used to evaluate self-adjusting algorithms for other graph classes where multiple tree-like subgraphs overlap (e.g. hypercube networks). We derive a lower bound of the amortized routing cost for any algorithm that follows our model and serves an unknown sequence of communication requests. We show that the routing cost of our algorithm is at most a constant factor more than the amortized routing cost of any algorithm conforming to our computational model. We also show that the expected transformation cost for our algorithm is at most a logarithmic factor more than the amortized routing cost of any algorithm conforming to our computational model. As a follow-up work, we present a distributed self-adjusting algorithm (referred to as DyHypes) for topological adaption in hypercubic networks. One of the major differences between hypercubic networks and skip graphs is that hypercubic networks are more rigid in structure than that of skip graphs. This property of hypercubic networks makes self-adjustment significantly different compared to skip graphs. Upon a communication between an arbitrary pair of nodes, DyHypes transforms the network to place frequently communicating nodes closer to each other to maximize communication efficiency, and uses randomization in the transformation process to speed up the transformation and reduce message complexity. We show that, as compared to DSG, DyHypes reduces the transformation cost by a factor of O(log n), where n is the number of nodes involved in the transformation. Moreover, despite achieving faster transformation with lower message complexity, the combined cost (routing and transformation) of DyHypes is at most a log log n factor more than that of any algorithm that conforms to the computational model adopted for this work. Similar to DSG, DyHypes is fully decentralized, conforms to the CONGEST model, and requires O(log n) bits of memory for each node, where N is the total number of nodes. Finally, we present a novel distributed load balancing algorithm called Meezan to address the load imbalance among large-scale networked cache servers. Modern web services rely on a network of distributed cache servers to efficiently deliver content to users. Load imbalance among cache servers can substantially degrade content delivery performance. Due to the skewed and dynamic nature of real-world workloads, cache servers that serve viral content experience higher load as compared to other cache servers. Our algorithm Meezan replicates popular objects to mitigate skewness and adjusts hash space boundaries in response to load dynamics in a novel way. Our theoretical analysis shows that Meezan achieves near perfect load balancing for a wide range of operating parameters. Our trace driven simulations shows that Meezan reduces load imbalance by up to 52% as compared to prior solutions.

Statistical analysis of network data is an active field of study, in which researchers inves- tigate graph-theoretic concepts and various probability models that explain the behaviour of real networks. This thesis attempts to combine two of these concepts: an exponential random graph and a centrality index. Exponential random graphs comprise the most useful class of probability models for network data. These models often require the assumption of a complex dependence structure, which creates certain difficulties in the estimation of unknown model parameters. However, in the context of dynamic networks the exponential random graph model provides the opportunity to incorporate a complex network structure such as centrality without the usual drawbacks associated with parameter estimation. The thesis employs this idea by proposing probability models that are equivalent to the logistic regression models and that can be used to explain behaviour of both static and dynamic networks.

Statistical analysis of network data is an active field of study, in which researchers inves- tigate graph-theoretic concepts and various probability models that explain the behaviour of real networks. This thesis attempts to combine two of these concepts: an exponential random graph and a centrality index. Exponential random graphs comprise the most useful class of probability models for network data. These models often require the assumption of a complex dependence structure, which creates certain difficulties in the estimation of unknown model parameters. However, in the context of dynamic networks the exponential random graph model provides the opportunity to incorporate a complex network structure such as centrality without the usual drawbacks associated with parameter estimation. The thesis employs this idea by proposing probability models that are equivalent to the logistic regression models and that can be used to explain behaviour of both static and dynamic networks.

Made available in DSpace on 2014-06-12T15:52:19Z (GMT). No. of bitstreams: 2 arquivo3230_1.pdf: 3857855 bytes, checksum: 68166824b668991a7746113795017a33 (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2010 / Universidade Federal de Campina Grande / Nos últimos anos diversas tecnologias foram desenvolvidas com o objetivo de facilitar a interação entre os usuários e seus dispositivos e melhorar a comunicação entre eles, necessitando da interoperabilidade entre essas tecnologias e, consequentemente, a necessidade de uma nova infraestrutura de rede que permita uma melhor adaptação aos novos requisitos criados por esta diversidade de tecnologias. O modelo de comunicação entre redes também está sendo modificado, uma vez que é esperado que elas sejam criadas dinamicamente para facilitar a utilização da rede pelos usuários e permitir que diversas operações sejam realizadas automaticamente (endereçamento, descoberta de serviços, etc.). Essas redes devem estar presentes em diversos cenários de comunicação e um dos seus principais desafios é permitir que diversos tipos de tecnologias cooperem em ambientes com alto dinamismo e heterogeneidade. Estas redes têm como objetivo interconectar diferentes tecnologias e domínios oferecendo uma comunicação que aparente ser homogêneo para os seus usuários. Para a criação dessas futuras redes dinâmicas pontos chaves são a interconexão e a cooperação entre as tecnologias envolvidas, o que exige o desenvolvimento de soluções para garantir que novos requisitos sejam suportados. Para permitir que novos requisitos sejam corretamente suportados, um conjunto de mecanismos para controlar a descoberta automática de recursos e realizar a sua configuração é proposto, permitindo que redes sejam criadas e adaptadas de maneira completamente automática. Também é proposto um mecanismo de negociação de políticas inter-domínio responsável por descobrir e negociar novos recursos que dever ser usados pelas redes, o que traz um novo modelo de comunicação baseado na criação oportunista de redes e ao mesmo tempo permite a criação de novos acordos de comunicação entre domínios administrativos de maneira dinâmica e sem a intervenção dos usuários ou dos administradores das redes

This dissertation is the compilation of two major innovations that rely on a common technique known as multidimensional scaling (MDS). MDS is a dimension-reduction method that takes high-dimensional data and creates low-dimensional versions. Project 1: Visualizations are useful when learning from high-dimensional data. However, visualizations, just as any data summary, can be misleading when they do not incorporate measures of uncertainty; e.g., uncertainty from the data or the dimension reduction algorithm used to create the visual display. We incorporate uncertainty into visualizations created by a weighted version of MDS called WMDS. Uncertainty exists in these visualizations on the variable weights, the coordinates of the display, and the fit of WMDS. We quantify these uncertainties using Bayesian models in a method we call Informative Probabilistic WMDS (IP-WMDS). Visually, we display estimated uncertainty in the form of color and ellipses, and practically, these uncertainties reflect trust in WMDS. Our results show that these displays of uncertainty highlight different aspects of the visualization, which can help inform analysts. Project 2: Analysis of network data has emerged as an active research area in statistics. Much of the focus of ongoing research has been on static networks that represent a single snapshot or aggregated historical data unchanging over time. However, most networks result from temporally-evolving systems that exhibit intrinsic dynamic behavior. Monitoring such temporally-varying networks to detect anomalous changes has applications in both social and physical sciences. In this work, we simulate data from models that rely on MDS, and we perform an evaluation study of the use of summary statistics for anomaly detection by incorporating principles from statistical process monitoring. In contrast to most previous studies, we deliberately incorporate temporal auto-correlation in our study. Other considerations in our comprehensive assessment include types and duration of anomaly, model type, and sparsity in temporally-evolving networks. We conclude that the use of summary statistics can be valuable tools for network monitoring and often perform better than more involved techniques. / Doctor of Philosophy / In this work, two main ideas in data visualization and anomaly detection in dynamic networks are further explored. For both ideas, a connecting theme is extensions of a method called Multidimensional Scaling (MDS). MDS is a dimension-reduction method that takes high-dimensional data (all $p$ dimensions) and creates a low-dimensional projection of the data. That is, relationships in a dataset with presumably a large number of dimensions or variables can be summarized into a lower number of, e.g., two, dimensions. For a given data, an analyst could use a scatterplot to observe the relationship between 2 variables initially. Then, by coloring points, changing the size of the points, or using different shapes for the points, perhaps another 3 to 4 more variables (in total around 7 variables) may be shown in the scatterplot. An advantage of MDS (or any dimension-reduction technique) is that relationships among the data can be viewed easily in a scatterplot regardless of the number of variables in the data. The interpretation of any MDS plot is that observations that are close together are relatively more similar than observations that are farther apart, i.e., proximity in the scatterplot indicates relative similarity. In the first project, we use a weighted version of MDS called Weighted Multidimensional Scaling (WMDS) where weights, which indicate a sense of importance, are placed on the variables of the data. The problem with any WMDS plot is that inaccuracies of the method are not included in the plot. For example, is an observation that appears to be an outlier, really an outlier? An analyst cannot confirm this without further context. Thus, we created a model to calculate, visualize, and interpret such inaccuracy or uncertainty in WMDS plots. Such modeling efforts help analysts facilitate exploratory data analysis. In the second project, the theme of MDS is extended to an application with dynamic networks. Dynamic networks are multiple snapshots of pairwise interactions (represented as edges) among a set of nodes (observations). Over time, changes may appear in some of the snapshots. We aim to detect such changes using a process monitoring approach on dynamic networks. Statistical monitoring approaches determine thresholds for in-control or expected behavior that are calculated from data with no signal. Then, the in-control thresholds are used to monitor newly collected data. We applied this approach on dynamic network data, and we utilized a detailed simulation study to better understand the performance of such monitoring. For the simulation study, data are generated from dynamic network models that use MDS. We found that monitoring summary statistics of the network were quite effective on data generated from these models. Thus, simple tools may be used as a first step to anomaly detection in dynamic networks.

No description available.

No description available.

Different types of shocks, or the treatment of one of the players in a specific network, may influence not only the future performance of themselves but also affect their network connections. It is crucial to explore the behaviour of the whole network in response to such an event. This paper focuses on the cases of endogenously formed shock. The logic used in the peer effect literature is adopted to develop the dynamic model and accounts for the endogeneity of the shock. The model allows us to predict the endogenous part of the shock and use the remaining unexpected component to estimate the effect of the shock on the changes in the performance of network connections. The identification conditions for effect are derived, and the consistent estimation procedure is proposed. / Series: Department of Economics Working Paper Series

Diagnosticar os elementos que influenciam a atuação organizacional é um passo essencial para trabalhar o desempenho em mercados cada vez mais competitivos. Dentre esses elementos, a produção, a demanda, os recursos financeiros, entre outros, são variáveis que devem sempre equacionar o ritmo e a intensidade das relações intra e interorganizacionais. O processo de planejamento de vendas e operações (S&OP) vai ao encontro dessa necessidade, porventura tática, de balancear as competências e forças internas (e.g. capacidades de produção, P&D, etc.) com as externas, (e.g. oportunidades de negócio, comportamento de demanda, etc.) nas Organizações. Com base nesse contexto procura-se desenvolver um modelo de referência baseado no EKD, para estruturar a execução do planejamento de vendas e operações (S&OP) utilizando os conceitos de redes dinâmicas (formação de redes), em um ambiente empresarial que emprega vários sistemas produtivos para atuar no mercado. / Diagnose the elements that influence the organizational acting is the essential step to work the performance in competitive market. Among these elements, the production, the demand, the financial resources, and others, are variables that must have always equating the rhythm and intensity of intra and Interorganizational interaction. The process of Sales and Operations Planning (S&OP) is in the line with this necessity, possibly tactic, of competent and internal forces balance (e.g. production capacity, R&D, etc.) with the external (e.g. business opportunities, demand behavior, etc) in the organizations. Based on that context, the present work aims to develop a EKD\'s reference model for Sales & Operations Planning (S&OP) with dynamic networks concepts in an empresarial environment that uses a diversity of production systems.