This dissertation presents algorithms for achieving communication in the presence of adversarial attacks in large, decentralized, resource-constrained networks. We consider abstract single-hop communication settings where a set of senders 𝙎 wishes to directly communicate with a set of receivers 𝙍. These results are then extended to provide resource-efficient, multi-hop communication in wireless sensor networks (WSNs), where energy is critically scarce, and peer-to-peer (P2P) networks, where bandwidth and computational power are limited. Our algorithms are provably correct in the face of attacks by a computationally bounded adversary who seeks to disrupt communication between correct participants. The first major result in this dissertation addresses a general scenario involving single-hop communication in a time-slotted network where a single sender in 𝙎 wishes to transmit a message 𝘮 to a single receiver in 𝙍. The two players share a communication channel; however, there exists an adversary who aims to prevent the transmission of 𝘮 by periodically blocking this channel. There are costs to send, receive or block 𝘮 on the channel, and we ask: How much do the two players need to spend relative to the adversary in order to guarantee transmission of the message? This problem abstracts many types of conflict in information networks, and the associated costs represent an expenditure of network resources. We show that it is significantly more costly for the adversary to block 𝘮 than for the two players to achieve communication. Specifically, if the cost to send, receive and block 𝘮 in a slot are fixed constants, and the adversary spends a total of 𝘉 slots to try to block the message, then both the sender and receiver must be active in only O(𝘉ᵠ⁻¹ + 1) slots in expectation to transmit 𝘮, where φ = (1+ √5)/2 is the golden ratio. Surprisingly, this result holds even if (1) the value of 𝘉 is unknown to either player; (2) the adversary knows the algorithms of both players, but not their random bits; and (3) the adversary is able to launch attacks using total knowledge of past actions of both players. Finally, these results are applied to two concrete problems. First, we consider jamming attacks in WSNs and address the fundamental task of propagating 𝘮 from a single device to all others in a WSN in the presence of faults; this is the problem of reliable broadcast. Second, we examine how our algorithms can mitigate application-level distributed denial-of-service attacks in wired client-server scenarios. The second major result deals with a single-hop communication problem where now 𝙎 consists of multiple senders and there is still a single receiver who wishes to obtain a message 𝘮. However, many of the senders (strictly less than half) can be faulty, failing to send 𝘮 or sending incorrect messages. While the majority of the senders possess 𝘮, rather than listening to all of 𝙎 and majority filtering on the received data, we desire an algorithm that allows the single receiver to decide on 𝘮 in a more efficient manner. To investigate this scenario, we define and devise algorithms for a new data streaming problem called the Bad Santa problem which models the selection dilemma faced by the receiver. With our results for the Bad Santa problem, we consider the problem of energy-efficient reliable broadcast. All previous results on reliable broadcast require devices to spend significant time in the energy-expensive receiving state which is a critical problem in WSNs where devices are typically battery powered. In a popular WSN model, we give a reliable broadcast protocol that achieves optimal fault tolerance (i.e., tolerates the maximum number of faults in this WSN model) and improves over previous results by achieving an expected quadratic decrease in the cost to each device. For the case where the number of faults is within a (1-∊)-factor of the optimal fault tolerance, for any constant ∊>0, we give a reliable broadcast protocol that improves further by achieving an expected (roughly) exponential decrease in the cost to each device. The third and final major result of this dissertation addresses single-hop communication where 𝙎 and 𝙍 both consist of multiple peers that need to communicate in an attack-resistant P2P network. There are several analytical results on P2P networks that can tolerate an adversary who controls a large number of peers and uses them to disrupt network functionality. Unfortunately, in such systems, operations such as data retrieval and message sending incur significant communication costs. Here, we employ cryptographic techniques to define two protocols both of which are more efficient than existing solutions. For a network of 𝘯 peers, our first protocol is deterministic with O(log²𝘯) message complexity and our second protocol is randomized with expected O(log 𝘯) message complexity; both improve over all previous results. The hidden constants and setup costs for our protocols are small and no trusted third party is required. Finally, we present an analysis showing that our protocols are practical for deployment under significant churn and adversarial behaviour.

This work describes a programming model and performance model for cycle stealing on the Internet. Cycle stealing is the use of otherwise idle computers to perform work, and promises high performance computing at relatively low cost. The Internet, being the largest pool of potentially idle computers, is an obvious target for cycle stealing. However, computers connected to the Internet are often protected by firewalls, preventing point-to-point communication between them. The fluctuating avail-ability of computers for cycle stealing as they move in and out of an idle state, combined with the restricted communication of the Internet environment, means that programming models and abstractions suitable for programming supercom-puters and clusters are not ideal. Therefore, I have created a programming model for cycle stealing which reflects the types of parallel applications that are suitable for execution using idle computers connected to the Internet. The model is de-signed for use by non-expert parallel programmers, and I will show how it simpli-fies the development of cycle stealing applications, enabling rapid application de-velopment, and straightforward porting of existing sequential applications. This simple to use programming model, combined with the low cost of cycle stealing, improves the accessibility of high performance computing to non-traditional us-ers of supercomputers and clusters. Deployment on the Internet, and the need to navigate through firewalls, suggests a web based framework using common web protocols, web servers and web browsers. Part of this work investigates the feasibility of web based approaches to cycle stealing, from the setup of a cycle stealing system, application development and deployment, and connection of potentially idle computers. I designed and implemented a cycle stealing framework, deployable on the web, to meet expec-tations of performance, reliability, ease of use and safety. Existing cycle stealing frameworks emphasise the need for applications to be de-composed into a set of jobs that execute for a long period, that is, a job should have a computation time sufficient to justify its communication cost. However, there are no tools available for users to determine what an appropriate computa-tion time might be, given a job's data communication requirements. To date, de-ciding the granularity of jobs has been a matter of intuition. Therefore, a user may experience uncertainty as to the benefit of cycle stealing for their particular application, especially if the applications will have relatively short-lived jobs. Based on performance analysis of my framework, I have developed an analytical model and simulator, which can be used to predict, and help to optimise, the per-formance of user applications, and show the feasibility of executing a particular application using the cycle stealing framework.

Ordinary desktop computers continue to obtain ever more resources – in-creased processing power, memory, network speed and bandwidth – yet these resources spend much of their time underutilised. Cycle stealing frameworks harness these resources so they can be used for high-performance computing. Traditionally cycle stealing systems have used client-server based architectures which place significant limits on their ability to scale and the range of applica-tions they can support. By applying a fully decentralised network model to cycle stealing the limits of centralised models can be overcome. Using decentralised networks in this manner presents some difficulties which have not been encountered in their previous uses. Generally decentralised ap-plications do not require any significant fault tolerance guarantees. High-performance computing on the other hand requires very stringent guarantees to ensure correct results are obtained. Unfortunately mechanisms developed for traditional high-performance computing cannot be simply translated because of their reliance on a reliable storage mechanism. In the highly dynamic world of P2P computing this reliable storage is not available. As part of this research a fault tolerance system has been created which provides considerable reliability without the need for a persistent storage. As well as increased scalability, fully decentralised networks offer the ability for volunteers to communicate directly. This ability provides the possibility of supporting applications whose tasks require direct, message passing style communication. Previous cycle stealing systems have only supported embarrassingly parallel applications and applications with limited forms of communication so a new programming model has been developed which can support this style of communication within a cycle stealing context. In this thesis I present a fully decentralised cycle stealing framework. The framework addresses the problems of providing a reliable fault tolerance sys-tem and supporting direct communication between parallel tasks. The thesis includes a programming model for developing cycle stealing applications with direct inter-process communication and methods for optimising object locality on decentralised networks.

Thesis (MScEng)--Stellenbosch University, 2012. / Please refer to full text for abstract.

A crescente complexidade dos programas de computador e o crescimento da carga de trabalho a qual eles são submetidos têm sido tendências recorrentes nos sistemas computacionais, em especial para sistemas distribuídos como aplicações web e sistemas corporativos. O aumento da carga de trabalho gera uma demanda por sistemas que façam melhor uso dos recursos computacionais disponíveis, enquanto a maior complexidade gera uma demanda por sistemas que se preocupem em minimizar o número de erros. Portanto, podem-se identificar dois objetivos a serem perseguidos pelos desenvolvedores de sistemas de software: melhorar o desempenho e aumentar a confiabilidade dos sistemas. A fim de alcançar os objetivos expostos, são desenvolvidos sistemas de monitoramento para automatizar a coleta e análise de dados sobre os sistemas computacionais alvo. O presente trabalho visa contribuir nos seguintes aspectos: na identificação dos dados relevantes para o monitoramento de aplicações distribuídas desenvolvidas para a plataforma Java; e na criação de uma ferramenta de monitoramento de aplicações distribuídas, explorando os novos recursos do JDK 1.5, bem como os recursos já disponíveis em Java, como carga dinâmica de classes e transformação de bytecodes A fim de avaliar a ferramenta proposta foram elaborados três estudos de caso: um utiliza uma aplicação existente sem necessidade de sua adaptação; outro avalia a sobrecarga da ferramenta frente a diferentes parâmetros; e o terceiro avalia o monitoramento de um sistema distribuído. Entende-se que a ferramenta atinge o objetivo de monitoramento de aplicações distribuídas, por meio da incorporação de técnicas e APIs distintas, ao permitir: o monitoramento de uma aplicação distribuída por meio do monitoramento de diversos nodos de tal aplicação concomitantemente; e a visualização das informações coletadas de forma online. Adicionalmente, a coleta simultânea de dados de diferentes nodos de uma aplicação distribuída pode ser útil para a descoberta de relações entre eventos que ocorrem durante a execução de tal aplicação. / The growing complexity of software and the increasing workload to which systems have been submitted are known trends in the computing system field, especially when distributed and web systems are considered. The increasing workload generates demand for systems that can make a better use of computing resources, while the increment of system complexity demands specific actions to prevent design faults. Therefore, software engineers have two main objectives to be concerned with: optimization and dependability. In order to accomplish these objectives, monitoring systems have been proposed to gather data from running systems so that their behavior can be analyzed. The present dissertation intends to contribute in the following domains: identifying relevant metrics for monitoring distributed Java applications; and developing a tool to monitor and profile distributed applications, using the new resources available in JDK 1 .5 as well as some already known techniques like dynamic classloading and bytecode instrumentation. In order to evaluate the proposed tool, three test cases have been developed: one with a well known application running without modification; another for evaluating the tools’ overhead in different scenarios; and a third one to evaluate a distributed application been monitored. We understand that the proposed tool is successful in monitoring distributed applications by the use of distinct APIs and techniques because: Nprof can monitor a distributed application by monitoring different nodes of the application simultaneously; and Nprof allows the online visualization of the collected data. Also, simultaneous collection of data from different nodes of a distributed application can be useful for discovering relations among events that occur during the execution of the application.

Risk management is an essential tool for ensuring the safety and timeliness of maritime operations and transportation. Some of the many risk factors that can compromise the smooth operation of maritime activities include harsh weather and pirate activity. However, identifying and quantifying the extent of these risk factors for a particular vessel is not a trivial process. One challenge is that processing the vast amounts of automatic identification system (AIS) messages generated by the ships requires significant computational resources. Another is that the risk management process partially relies on human expertise, which can be timeconsuming and error-prone. In this thesis, an existing Risk Management Framework (RMF) is augmented to address these issues. A parallel/distributed version of the RMF is developed to e ciently process large volumes of AIS data and assess the risk levels of the corresponding vessels in near-real-time. A genetic fuzzy system is added to the RMF's Risk Assessment module in order to automatically learn the fuzzy rule base governing the risk assessment process, thereby reducing the reliance on human domain experts. A new weather risk feature is proposed, and an existing regional hostility feature is extended to automatically learn about pirate activity by ingesting unstructured news articles and incident reports. Finally, a geovisualization tool is developed to display the position and risk levels of ships at sea. Together, these contributions pave the way towards truly automatic risk management, a crucial component of modern maritime solutions. The outcomes of this thesis will contribute to enhance Larus Technologies' Total::Insight, a risk-aware decision support system successfully deployed in maritime scenarios.

A crescente complexidade dos programas de computador e o crescimento da carga de trabalho a qual eles são submetidos têm sido tendências recorrentes nos sistemas computacionais, em especial para sistemas distribuídos como aplicações web e sistemas corporativos. O aumento da carga de trabalho gera uma demanda por sistemas que façam melhor uso dos recursos computacionais disponíveis, enquanto a maior complexidade gera uma demanda por sistemas que se preocupem em minimizar o número de erros. Portanto, podem-se identificar dois objetivos a serem perseguidos pelos desenvolvedores de sistemas de software: melhorar o desempenho e aumentar a confiabilidade dos sistemas. A fim de alcançar os objetivos expostos, são desenvolvidos sistemas de monitoramento para automatizar a coleta e análise de dados sobre os sistemas computacionais alvo. O presente trabalho visa contribuir nos seguintes aspectos: na identificação dos dados relevantes para o monitoramento de aplicações distribuídas desenvolvidas para a plataforma Java; e na criação de uma ferramenta de monitoramento de aplicações distribuídas, explorando os novos recursos do JDK 1.5, bem como os recursos já disponíveis em Java, como carga dinâmica de classes e transformação de bytecodes A fim de avaliar a ferramenta proposta foram elaborados três estudos de caso: um utiliza uma aplicação existente sem necessidade de sua adaptação; outro avalia a sobrecarga da ferramenta frente a diferentes parâmetros; e o terceiro avalia o monitoramento de um sistema distribuído. Entende-se que a ferramenta atinge o objetivo de monitoramento de aplicações distribuídas, por meio da incorporação de técnicas e APIs distintas, ao permitir: o monitoramento de uma aplicação distribuída por meio do monitoramento de diversos nodos de tal aplicação concomitantemente; e a visualização das informações coletadas de forma online. Adicionalmente, a coleta simultânea de dados de diferentes nodos de uma aplicação distribuída pode ser útil para a descoberta de relações entre eventos que ocorrem durante a execução de tal aplicação. / The growing complexity of software and the increasing workload to which systems have been submitted are known trends in the computing system field, especially when distributed and web systems are considered. The increasing workload generates demand for systems that can make a better use of computing resources, while the increment of system complexity demands specific actions to prevent design faults. Therefore, software engineers have two main objectives to be concerned with: optimization and dependability. In order to accomplish these objectives, monitoring systems have been proposed to gather data from running systems so that their behavior can be analyzed. The present dissertation intends to contribute in the following domains: identifying relevant metrics for monitoring distributed Java applications; and developing a tool to monitor and profile distributed applications, using the new resources available in JDK 1 .5 as well as some already known techniques like dynamic classloading and bytecode instrumentation. In order to evaluate the proposed tool, three test cases have been developed: one with a well known application running without modification; another for evaluating the tools’ overhead in different scenarios; and a third one to evaluate a distributed application been monitored. We understand that the proposed tool is successful in monitoring distributed applications by the use of distinct APIs and techniques because: Nprof can monitor a distributed application by monitoring different nodes of the application simultaneously; and Nprof allows the online visualization of the collected data. Also, simultaneous collection of data from different nodes of a distributed application can be useful for discovering relations among events that occur during the execution of the application.

abstract: Large-scale $\ell_1$-regularized loss minimization problems arise in high-dimensional applications such as compressed sensing and high-dimensional supervised learning, including classification and regression problems. In many applications, it remains challenging to apply the sparse learning model to large-scale problems that have massive data samples with high-dimensional features. One popular and promising strategy is to scaling up the optimization problem in parallel. Parallel solvers run multiple cores on a shared memory system or a distributed environment to speed up the computation, while the practical usage is limited by the huge dimension in the feature space and synchronization problems. In this dissertation, I carry out the research along the direction with particular focuses on scaling up the optimization of sparse learning for supervised and unsupervised learning problems. For the supervised learning, I firstly propose an asynchronous parallel solver to optimize the large-scale sparse learning model in a multithreading environment. Moreover, I propose a distributed framework to conduct the learning process when the dataset is distributed stored among different machines. Then the proposed model is further extended to the studies of risk genetic factors for Alzheimer's Disease (AD) among different research institutions, integrating a group feature selection framework to rank the top risk SNPs for AD. For the unsupervised learning problem, I propose a highly efficient solver, termed Stochastic Coordinate Coding (SCC), scaling up the optimization of dictionary learning and sparse coding problems. The common issue for the medical imaging research is that the longitudinal features of patients among different time points are beneficial to study together. To further improve the dictionary learning model, I propose a multi-task dictionary learning method, learning the different task simultaneously and utilizing shared and individual dictionary to encode both consistent and changing imaging features. / Dissertation/Thesis / Doctoral Dissertation Computer Science 2017

Este trabalho apresenta uma ferramenta denominada FAGAC que se destina à administração e gerência de aglomerados de computadores, através de uma interface Web. A ferramenta tem a característica de ser pouco intrusiva no ambiente, ou seja, consumir poucos recursos computacionais a fim de não causar atrasos na execução dos serviços e processos do sistema. Inclui também funcionalidades que geram informações para o cliente ou administrador do sistema, a respeito do estado de ocupação de memória e de CPU, monitoramento do estado da carga de cada computador, tráfego gerado na rede, espaços em disco, informações de hardware e configurações do sistema. A validação da ferramenta foi feita por meio de experimentos comparativos das cinco principais funcionalidades comuns entre o FAGAC e o Ganglia, mostrando melhores resultados nas cinco funcionalidades, e que FAGAC é menos intrusivo que o Ganglia. / This research presents a tool named FAGAC for cluster management and administration of agglomerated of computers, through a web interface. This tool has the characteristic of being little intrusive in the environment, what means that it should consume a little computational resource in order to not delay the services and processes in execution at the system. The tool has functions to inform the customer or system administrator about the status of memory and CPU occupation, monitorating the load of each computer, the traffic generated in the net, disk space, hardware informations and configurations of the system. It was validated by comparing the results of the experiments from the main similar functions between FAGAC and Ganglia, showing best results for five functions tested, and that FAGAC is less intrusive than Ganglia.

Diversas políticas de escalonamento para aplicações paralelas voltadas a ambientes computacionais distribuídos têm sido propostas. Embora tais políticas apresentem bons resultados, elas são, geralmente, avaliadas em cenários específicos. Quando o cenário muda, com diferentes ambientes distribuídos e condições de carga, essas políticas podem ter seu desempenho deteriorado. Nesse contexto, este trabalho apresenta um estudo comparativo envolvendo dez políticas de escalonamento avaliadas em diferentes cenários. Cada uma das políticas foi submetida a uma combinação de quatro cargas de trabalho de ocupação da UCP e três variações da taxa de comunicação média entre os processos, utilizando a rede. Foram considerados ainda três sistemas distribuídos distintos: dois clusters, com diferentes quantidades de nós, e um grid computacional. Foi utilizada a simulação com ambientes próximos ao real e cargas de trabalho obtidas de modelos realísticos. Os resultados demonstraram que, embora as políticas sejam voltadas a ambientes computacionais paralelos e distribuídos, quando o cenário muda, o desempenho cai e a ordem de classificação entre as políticas se altera. Os resultados permitiram ainda demonstrar a necessidade de se considerar a comunicação entre os processos durante o escalonamento em grids computacionais. / Several scheduling policies for parallel applications directed to the distributed computational environments have been proposed. Although such policies present good results, they, generally, are evaluated in specific scenarios. When scenario change, by using different distributed environments and workload conditions, these policies can have its performance spoiled. In this context, this work presents a comparative study involving ten scheduling policies evaluated on different scenarios. Each policy was submitted to a combination of four CPU occupation workloads and three variations of interprocess average communication rates, using the network. Three different distributed systems had been yet considered: two clusters, with different amounts of nodes, and one grid computing. Simulation was used with environments near to the real and workloads obtained of realistic models. Although the policies are directed to parallel and distributed environments, the results have demonstrated that when scenario change, the performance falls and the ranking between the policies changes too. The results have still allowed to demonstrate the necessity of considering interprocess communication during the scheduling in a grid computing.