The primary motivation of this research is to develop and investigate parallel preconditioners for linear elliptic partial differential equations. Three preconditioners are studied: block-Jacobi preconditioner (BJ), a two-level tangential preconditioner (D0), and a three-level preconditioner (D1). Performance and scalability on a distributed memory parallel computer are considered. Communication cost and redundancy are explored as well. After experiments and analysis, we find that the three-level preconditioner D1 is the most efficient and scalable parallel preconditioner, compared to BJ and D0. The D1 preconditioner reduces both the number of iterations and computational time substantially. A new hybrid preconditioner is suggested which may combine the best features of D0 and D1. / Master of Science

Disaster recovery is an important aspect to consider when working in distributed systems and cloud environments. How should a system be saved when the physical infrastructure is faced with natural disasters like earthquakes and floods or more technical disasters like power outages and cyber-attacks? This thesis introduces the concept of disaster recovery and the different approaches that can be applied, specifically to a trading platform's matching engine. Experiments with three different kinds of disaster recovery methods are run, namely, Hot, Warm, and Cold, both on a local machine and using AWS cloud. The key performance indicators of these experiments are resource costs like CPU and memory usage, along with the startup time of a site, called Recovery Time Objective (RTO). The results show that the hot method clearly uses more resources during normal operation, followed by the warm site. The cold site which is inactive does not use any resources. Regarding the RTO, the hot site achieves the fastest time followed by the warm site. The cold site is tested with different sizes of states and snapshots, and the results show that a significant improvement of the RTO can gained by using snapshots. The local experiment performs better on all sites compared to running it on the cloud, implying that latency affects the performance substantially. With these findings, businesses should better be able to decide what method would be suitable for their system based on their needs and resources. For systems where maximum uptime is crucial, a hot approach is likely to be most suitable, while for systems where downtime is not as important, a warm or cold approach may be preferred. / <p></p><p></p><p></p>

This thesis presents Caesar, a novel multi-leader Generalized Consensus protocol for geographically replicated systems. Caesar is able to achieve near-perfect availability, provide high performance - low latency and high throughput compared to the existing state-of-the- art, and tolerate replica failures. Recently, a number of state-of-the-art consensus protocols that implement the Generalized Consensus definition have been proposed. However, the major limitation of these existing approaches is the significant performance degradation when application workload produces conflicting requests. Caesar's main goal is to overcome this limitation by changing the way a fast decision is taken: its ordering protocol does not reject a fast decision for a client request if a quorum of nodes reply with different dependency sets for that request. It only switches to a slow decision if there is no chance to agree on the proposed order for that request. Caesar is able to achieve this using a combination of wait condition and logical time stamping. The effectiveness of Caesar is demonstrated through an evaluation study performed on Amazon's EC2 infrastructure using 5 geo-replicated sites. Caesar outperforms other multi-leader (e.g., EPaxos) competitors by as much as 1.7x in presence of 30% conflicting requests, and single-leader (e.g., Multi-Paxos) by as much as 3.5x. The protocol is also resistant to heavy client loads unlike existing protocols. / Master of Science / Today, there exists a plethora of online services (e.g. Facebook, Google) that serve millions of users daily. Usually, each of these services have multiple subcomponents that work cohesively to deliver a rich user experience. One vital component that is prevalent in these services is the one that maintains the shared state. One example of a shared state component is a database, which enables operations on structured data. Such shared states are replicated across multiple server nodes, and even across multiple data centers to guarantee availability, i.e., if a node fails, other nodes can still serve requests on the shared state; low-latency, i.e., placing the copy of the shared state in a datacenter closer to the users will reduce the time required to serve the users; and scalability, i.e., the bottleneck that a single server node cannot serve millions of concurrent requests can be alleviated by having multiple nodes serve users at the same time. These replicated shared states need to be kept consistent i.e. every copy of the shared state must be the same in all the replicated nodes, and maintaining this consistency requires that each of these replicating nodes communicate with each other and reach an agreement on the order in which the operations on the shared data should be applied. In that regard, this thesis proposes Caesar, a consensus protocol with the aforementioned guarantees that will ease the deployment of services that contain a shared state. It addresses the problem of performance degradation in existing approaches when the same part of the shared state are accessed by multiple users that are connected to different server nodes. The effectiveness of Caesar is demonstrated through an evaluation study performed by deploying the protocol on five of Amazon’s data centers around the world. Caesar outperforms the existing state-of-the-art by as much as 3.5x. Caesar is also resistant to heavy client loads unlike existing protocols.

The presence of computer technologies in our daily life is growing by leaps and bounds. One of the recent trends is the use of mobile technologies and cloud services for supporting everyday tasks and the sharing of information between users. The field of education is not absent from these developments and many organizations are adopting Information and Communication Technologies (ICT) in various ways for supporting teaching and learning. The field of Mobile Learning (M-Learning) offers new opportunities for carrying out collaborative educational activities in a variety of settings and situations. The use of mobile technologies for enhancing collaboration provides new opportunities but at the same time new challenges emerge. One of those challenges is discussed in this thesis and it con- cerns with uncertainties related to the dynamic aspects that characterized outdoor M-Learning activities. The existence of these uncertainties force software developers to make assumptions in their developments. However, these uncertainties are the cause of risks that may affect the required outcomes for M-Learning activities. Mitigations mechanisms can be developed and included to reduce the risks’ impact during the different phases of development. However, uncertainties which are present at runtime require adaptation mechanisms to mitigate the resulting risks. This thesis analyzes the current state of the art in self-adaptation in Technology-Enhanced Learning (TEL) and M-Learning. The results of an extensive literature survey in the field and the outcomes of the Geometry Mobile (GEM) research project are reported. A list of uncertainties in collaborative M-Learning activities and the associated risks that threaten the critical QoS outcomes for collaboration are identified and discussed. A detailed elaboration addressing mitigation mechanisms to cope with these problems is elaborated and presented. The results of these efforts provide valuable insights and the basis towards the design of a multi-agent self-adaptive architecture for multiple concerns that is illustrated with a prototype implementation. The proposed conceptual architecture is an initial cornerstone towards the creation of a decentralized distributed self-adaptive system for multiple concerns to guarantee collaboration in M-Learning.

This project investigated how NoSQL databases can be used together with a logical layer, instead of a relational database with separated backend logic, to search for products with customer specific constraints in an e-commerce scenario. The motivation behind moving from a relational database was the scalability issues and increased read latencies experienced as the data increased. The work resulted in a framework called Cauldron that uses pipelines a sequence of execution steps to expose its data stored in an in-memory key-value store and a document database. Cauldron uses write replication between distributed instances to increase read throughput at the cost of write latency. A product database with customer specific constraints was implemented using Cauldron to compare it against an existing solution based on a relational database. The new product database can serve search queries 10 times faster in the general case and up to 25 times faster in extreme cases compared to the existing solution. / Projektet undersökte hur NoSQL databaser tillsammans med ett logiskt lager, istället för en relationsdatabas med separat backend logik, kan användas för att söka på produkter med kundunika restriktioner. Motivationen till att byta ut relationsdatabasen berodde på skalbarhetsproblem och långsammare svarstider när datamängden ökade. Arbetet resulterade i ett ramverk vid namn Cauldron som använder pipelines sammankopplade logiska steg för att exponera sin data från en minnesbunden nyckel-värde-databas och en dokumentdatabas. Cauldron använder replikering mellan distribuerade instanser för att öka läsgenomstömmningen på bekostnad av högre skrivlatenser. En produktdatabas med kundunika restriktioner implementerades med hjälp av Cauldron för att jämföra den mot en befintlig lösning baserad på en relationsdatabas. Den nya databasen kan besvara sökförfrågningar 10 gånger snabbare i normalfallen och upp till 25 gånger snabbare i extremfallen jämfört med den befintliga lösningen.

Die wachsende Anzahl an Robotikanwendungen, in denen mehrere Roboter ein gemeinsames Ziel verfolgen, erfordert eine gesonderte Betrachtung der Interaktion zwischen diesen Robotern mit Bezug auf den damit entstehenden Datenaustausch. Dieser muss hierbei effizient betrieben werden und die Sicherheit des gesamt Systems gewährleisten. Diese Masterarbeit stellt eine Simulationsumgebung vor, welche anhand von Testszenarien und Austauschstrategien Roboterkonstellationen prüft und Messergebnisse ausliefert. Zu Beginn der Arbeit werden drei Datenaustauschverfahren betrachtet und anschließend Publikationen vorgestellt, in denen Datenaustausch betrieben wird und Simulatoren für die Nutzbarkeit der Simulationsumgebung untersucht. Die anschließenden Kapitel behandeln das Konzept und die Implementierung der Testumgebung erläutert, wobei Roboter aus einer Menge von Hardware Komponenten und Zielen beschrieben werden. Der Aufbau des Experiments umfasst die verschiedenen Umgebungen, Testszenarien und Roboterkonfiguration. Der Aufbau beschreibt die Grundlage für die Auswertung der Testergebnisse.

The Internet of Things is a recent computing paradigm, de- fined by networks of highly connected things – sensors, actuators and smart objects – communicating across networks of homes, buildings, vehicles, and even people. The Internet of Things brings with it a host of new problems, from managing security on constrained devices to processing never before seen amounts of data. While cloud computing might be able to keep up with current data processing and computational demands, it is unclear whether it can be extended to the requirements brought forth by Internet of Things. Fog computing provides an architectural solution to address some of these problems by providing a layer of intermediary nodes within what is called an edge network, separating the local object networks and the Cloud. These edge nodes provide interoperability, real-time interaction, routing, and, if necessary, computational delegation to the Cloud. This paper attempts to evaluate Go, a distributed systems language developed by Google, in the context of requirements set forth by Fog computing. Similar methodologies of previous literature are simulated and benchmarked against in order to assess the viability of Go in the edge nodes of Fog computing architecture.

El objetivo de esta Tesis es el análisis para la gestión de entornos virtuales de manera eficiente. En este sentido, se realizó una optimización sobre el middleware de planificación en forma dinámica sobre entornos de computación Grid, siendo la meta a alcanzar la asignación y utilización óptima de recursos para la ejecución coordinada de tareas. Se investigó en particular la interacción entre servicios Grid y la problemática de la distribución de tareas en meta-organizaciones con requerimientos de calidad de servicio no trivial, estableciendo una relación entre la distribución de tareas y las necesidades locales pertenecientes a organizaciones virtuales. La idea tuvo origen en el estudio de laboratorios virtuales y remotos para la creación de espacios virtuales. En muchas organizaciones públicas y de investigación se dispone de gran cantidad de recursos, pero estos no siempre se encuentran accesibles, debido a la distancia geográfica, o no se dispone de la capacidad de interconectarlos para lograr un fin común. El concepto de espacio virtual introduce una capa de abstracción sobre estos recursos logrando independencia de ubicación y la interactividad entre dispositivos heterogéneos, logrando de esta manera hacer uso eficiente de los medios disponibles. Durante el desarrollo se ha experimentado y logrado la implementación de un entorno para la generación de espacios virtuales. Se ha definido la infraestructura, se implementaron dos tipos de laboratorios y se ha propuesto una optimización para lograr el máximo aprovechamiento en un entorno para aplicaciones paralelas. Actualmente estos conceptos han evolucionando y algunas de las ideas publicadas se han implementado en prototipos funcionales para infraestructuras comerciales, si bien aún se encuentra en investigación la planificación sobre centros de cómputos para miles de equipos.

Dynamic balancing of computation and communication load is vital for the execution stability and performance of distributed, parallel simulations deployed on shared, unreliable resources of large-scale environments. High Level Architecture (HLA) based simulations can experience a decrease in performance due to imbalances that are produced initially and/or during run-time. These imbalances are generated by the dynamic load changes of distributed simulations or by unknown, non-managed background processes resulting from the non-dedication of shared resources. Due to the dynamic execution characteristics of elements that compose distributed simulation applications, the computational load and interaction dependencies of each simulation entity change during run-time. These dynamic changes lead to an irregular load and communication distribution, which increases overhead of resources and execution delays. A static partitioning of load is limited to deterministic applications and is incapable of predicting the dynamic changes caused by distributed applications or by external background processes. Due to the relevance in dynamically balancing load for distributed simulations, many balancing approaches have been proposed in order to offer a sub-optimal balancing solution, but they are limited to certain simulation aspects, specific to determined applications, or unaware of HLA-based simulation characteristics. Therefore, schemes for balancing the communication and computational load during the execution of distributed simulations are devised, adopting a hierarchical architecture. First, in order to enable the development of such balancing schemes, a migration technique is also employed to perform reliable and low-latency simulation load transfers. Then, a centralized balancing scheme is designed; this scheme employs local and cluster monitoring mechanisms in order to observe the distributed load changes and identify imbalances, and it uses load reallocation policies to determine a distribution of load and minimize imbalances. As a measure to overcome the drawbacks of this scheme, such as bottlenecks, overheads, global synchronization, and single point of failure, a distributed redistribution algorithm is designed. Extensions of the distributed balancing scheme are also developed to improve the detection of and the reaction to load imbalances. These extensions introduce communication delay detection, migration latency awareness, self-adaptation, and load oscillation prediction in the load redistribution algorithm. Such developed balancing systems successfully improved the use of shared resources and increased distributed simulations' performance.

Stream programming is a paradigm where a program is structured by a set of computational nodes connected by streams. Focusing on data moving between computational nodes via streams, this programming model fits well for applications that process long sequences of data. We call such applications reactive stream programs (RSPs) to distinguish them from stream programs with rather small and finite input data. In stream programming, concurrency is expressed implicitly via communication streams. This helps to reduce the complexity of parallel programming. For this reason, stream programming has gained popularity as a programming model for parallel platforms. However, it is also challenging to analyse and improve the performance without an understanding of the program's internal behaviour. This thesis targets an effi cient execution model for deploying RSPs on parallel platforms. This execution model includes a monitoring framework to understand the internal behaviour of RSPs, scheduling strategies for RSPs on uniform shared-memory platforms; and mapping techniques for deploying RSPs on heterogeneous distributed platforms. The foundation of the execution model is based on a study of the performance of RSPs in terms of throughput and latency. This study includes quantitative formulae for throughput and latency; and the identification of factors that influence these performance metrics. Based on the study of RSP performance, this thesis exploits characteristics of RSPs to derive effective scheduling strategies on uniform shared-memory platforms. Aiming to optimise both throughput and latency, these scheduling strategies are implemented in two heuristic-based schedulers. Both of them are designed to be centralised to provide load balancing for RSPs with dynamic behaviour as well as dynamic structures. The first one uses the notion of positive and negative data demands on each stream to determine the scheduling priorities. This scheduler is independent from the runtime system. The second one requires the runtime system to provide the position information for each computational node in the RSP; and uses that to decide the scheduling priorities. Our experiments show that both schedulers provides similar performance while being significantly better than a reference implementation without dynamic load balancing. Also based on the study of RSP performance, we present in this thesis two new heuristic partitioning algorithms which are used to map RSPs onto heterogeneous distributed platforms. These are Kernighan-Lin Adaptation (KLA) and Congestion Avoidance (CA), where the main objective is to optimise the throughput. This is a multi-parameter optimisation problem where existing graph partitioning algorithms are not applicable. Compared to the generic meta-heuristic Simulated Annealing algorithm, both proposed algorithms achieve equally good or better results. KLA is faster for small benchmarks while slower for large ones. In contrast, CA is always orders of magnitudes faster even for very large benchmarks.