Abortable mutual exclusion is a variant of mutual exclusion, in which processes are allowed to abort in the trying protocol. Scott presented the first local-spin abortable mutual exclusion algorithms. They are based on a queue and perform O(1) remote memory accesses (RMAs) when no processes abort. However, they use unbounded space and a process can perform an unbounded number of RMAs, in the worst case, to enter the critical section. The only other local-spin abortable mutual exclusion algorithm is by Jayanti. It has bounded space and RMA complexity, but a process always performs \Theta(log N) RMAs to enter the critical section, where N is the number of processes. In this thesis, three new, bounded space, abortable mutual exclusion algorithms are presented. We give the first local-spin abortable mutual exclusion algorithm that uses only registers. It has \Theta(log N) RMA complexity, even if no processes abort. We also present the first local-spin abortable mutual exclusion algorithm using more general primitives which has bounded space and in which each process performs O(1) RMAs to enter the critical section when no processes abort. However, this algorithm is local-spin only for a certain type of cache-coherent model. Finally, we present an abortable mutual exclusion algorithm which is local-spin in any cache-coherent model and in which each process performs O(1) RMAs to enter the critical section when no processes abort. We develop a new reference counting method to bound the space used in this algorithm.

Wireless sensor networks (WSN) increasingly permeate modern societies nowadays. But in spite of their plethora of successful applications, WSN are often unable to surmount many operational challenges that unexpectedly arise during their lifetime. Fortunately, robotic agents can now assist a WSN in various ways. This thesis illustrates how mobile robots which are able to carry a limited number of sensors can help the network react to sensor faults, either during or after its deployment in the monitoring region. Two scenarios are envisioned. In the first one, carrier robots surround a point of interest with multiple sensor layers (focused coverage formation). We put forward the first known algorithm of its kind in literature. It is energy-efficient, fault-reactive and aware of the bounded robot cargo capacity. The second one is that of replacing damaged sensing units with spare, functional ones (coverage repair), which gives rise to the formulation of two novel combinatorial optimization problems. Three nature-inspired metaheuristic approaches that run at a centralized location are proposed. They are able to find good-quality solutions in a short time. Two frameworks for the identification of the damaged nodes are considered. The first one leans upon diagnosable systems, i.e. existing distributed detection models in which individual units perform tests upon each other. Two swarm intelligence algorithms are designed to quickly and reliably spot faulty sensors in this context. The second one is an evolving risk management framework for WSNs that is entirely formulated in this thesis.

Our research aims at contributing to the evolution of modern wireless communications and to the development of software-defined radio (SDR) and cognitive radio, in particular. It promotes a general resource management framework that facilitates the integration of computing and radio resource management. This dissertation discusses the need for computing resource management in software-defined and cognitive radios and introduces an SDR computing resource management framework with cognitive capabilities. The hard real-time computing requirements of software-defined digital signal processing chains (SDR applications), the associated radio propagation and quality of service (QoS) implications, and heterogeneous multiprocessor platforms with limited computing resources (SDR platforms) define the context of these studies. We examine heterogeneous computing techniques, multiprocessor mapping and scheduling in particular, and elaborate a flexible framework for the dynamic allocation and reallocation of computing resources for wireless communications. The framework should facilitate partial reconfigurations of SDR platforms, dynamic switches between radio access technologies (RATs), and service and QoS level adjustments as a function of the environmental conditions. It, therefore, assumes the facilities of the platform and hardware abstraction layer operating environment (P-HAL-OE). We suggest a modular framework, distinguishing between the computing system modeling and the computing resource management. Our modeling proposal is based on two computing resource management techniques, which facilitate managing the strict timing constraints of real-time systems. It is scalable and can account for many different hardware architectures and computing resource types. This work focuses on processing and interprocessor bandwidth resources and processing and data flow requirements. Our computing resource management approach consists of a general-purpose mapping algorithm and a cost function. The independence between the algorithm and the cost function facilitates implementing many different computing resource management policies. We introduce a dynamic programming based algorithm, the tw-mapping, where w controls the decision window. We present a general and parametric cost function, which guides the mapping process under the given resource constraints. An instance of it facilitates finding a mapping that meets all processing and data flow requirements of SDR applications with the available processing and bandwidth resources of SDR platforms. Several SDR reconfiguration scenarios and analyses based on simulations demonstrate the suitability and potentials of our framework for a flexible computing resource management. We extend our SDR computing resource management concepts to the cognitive radio context. The two primary objectives of cognitive radio are highly reliable communications whenever and wherever needed and the efficient use of the radio spectrum. We formulate a third objective as the efficient use of computing resources. We analyze the cognitive capabilities of our framework─the cognitive radio’s interface to SDR platforms─and indicate the potentials of our cognitive computing resource management proposal. The cognitive computing resource management needs to be coordinated with the radio resource management. We, therefore, introduce the joint resource management concept for cognitive radios. We present three cognitive cycles and discuss several interrelations between the radio, computing, and application resources, where application resources refer to the available SDR and user applications. Our approach potentiates flexibility and facilitates radio against computing resource tradeoffs. It promotes cognition at all layers of the wireless system for a cooperative or integrated resource management that may increase the performance and efficiency of wireless communications. / El objetivo de las investigaciones que se están llevando a cabo dentro del grupo de investigación es contribuir a la evolución de las radiocomunicaciones modernas y, en particular, al desarrollo de los conceptos software radio (SDR) y cognitive radio. El planteamiento general es el de extender la flexibilidad global del sistema de comunicaciones planteando la definición y desarrollo de un entorno en el que pudiesen explorarse las relaciones entre la computación y las prestaciones del sistema de comunicaciones móviles facilitando la integración de los recursos de computación con los recursos radio. Dentro de este marco, la presente tesis plantea la discusión de la necesidad de la gestión de los recursos de computación en entornos SDR y cognitive radio y define un entorno de operación que asume las características especificas del concepto SDR a la vez que incorpora capacidades cognitivas en la gestión de los recursos de computación de las plataformas que den soporte a las nuevas generaciones de sistemas móviles. Los estrictos requerimientos de procesado en tiempo real de las cadenas de procesado digital de la señal definidas por software (aplicaciones SDR), las implicaciones asociadas con la propagación radio y el concepto de calidad de servicio (QoS) y plataformas heterogéneas de múltiples procesadores con recursos de computo limitados (plataformas SDR) definen el contexto de estos estudios. Se examinan técnicas de cómputo de propósito general para definir un entorno de operación que fuese capaz de asignar de forma flexible y dinámica los recursos de cómputo necesarios para facilitar las radiocomunicaciones a los niveles de QoS deseados. Ello debería facilitar los cambios dinámicos de una tecnología de acceso radio a otra, permitiendo el ajuste del tipo de servicio o calidad de servicio en función de las preferencias de los usuarios y las condiciones del entorno. Dicho entorno de operación asume las potencialidades del platform and hardware abstraction layer operating environment (P-HAL-OE). La estructura del entorno de operación se define de forma modular y consiste en un modelado genérico y flexible de las plataformas de computación SDR y en una gestión de recursos de computación abierta y capaz de ajustarse a diferentes objetivos y políticas. En el trabajo se exponen dos técnicas de gestión que pretenden asegurar la consecución estricta de los límites temporales típicos de los sistemas en tiempo real. En cuanto al modelado, este es escalable y capaz de capturar un amplio abanico de arquitecturas hardware y recursos de computación. En el presente trabajo nos centramos en los recursos y requerimientos del procesado y transferencia de datos. Se introduce un algoritmo de mapeo genérico e independiente de la función de coste. La independencia entre el algoritmo y la función de coste facilita la implementación de diferentes políticas de gestión de recursos computacionales. El tw-mapping es un algoritmo basado en dynamic programming, donde w controla la ventana de decisión. Se presenta una función de coste genérica y parametrizable que permite guiar el proceso de gestión de los recursos. Una instancia de ella facilita encontrar una solución al proceso de asignación de recursos que cumpla todos los requerimientos de procesado y trasferencia de datos de las aplicaciones SDR con los recursos disponibles de las plataformas SDR. Diferentes escenarios y varios análisis basados en simulaciones demuestran la adecuación del entorno de trabajo definido y desarrollado, así como sus potencialidades para una gestión flexible de los recursos de cómputo. Se extienden los conceptos mencionados previamente para entornos cognitive radio. Los principales objetivos del concepto cognitive radio son la disponibilidad de comunicaciones altamente robustas en cualquier lugar y momento en que sean necesarias y el uso eficiente del espectro. Como tercer objetivo formulamos el uso eficiente de los recursos de cómputo. Analizamos las capacidades cognitivas de nuestro entorno de operación─la interfaz del sistema cognitive radio a las plataformas SDR─y resaltamos las potencialidades de nuestra propuesta de gestión cognitiva de los recursos computacionales. Dicha gestión cognitiva de los recursos computacionales plantea una integración con la gestión de los recursos radio. Para ello introducimos el concepto de gestión de recursos conjunta para entornos cognitive radio. Se presentan tres ciclos cognitivos y se discuten algunas interrelaciones entre los recursos radio, de cómputo y de aplicación, donde los recursos de aplicación se refieren a las aplicaciones SDR y de usuario disponibles. Nuestra propuesta de gestión de recursos conjunta potencia la flexibilidad y facilita los intercambios entre recursos radio y de computación

Over the last several years, there has been tremendous growth in online gaming (i. e. playing games over the internet). The Massively Multiplayer Online Role Playing Game (MMORPG) is one type of online game. An MMORPG is played within a virtual world. Users have an in-game representation, called an avatar, that they control. Typically there are over a thousand avatars in the virtual world at one time. Users use client software to connect to an MMORPG server over the internet. If just one server is used then the number of avatars that can be supported in the virtual world at one time is severely limited. In order to overcome this, a multi-server approach is needed. Unlike traditional load balancing and partitioning schemes, which generally use task partitioning, data partitioning is required in this case. This thesis investigates schemes for partitioning and load balancing MMORPG applications on a network of processors. In particular, three different schemes were developed andexamined. These are: Static Av, Static MS and Dynamic MS. Static Avassigns avatars to each server, one at a time, as they enter thesimulation. Static MS assigns equal sized portions of the map of thevirtual world to each server. An avatar is assigned to the server thatowns the part of the map that the avatar is "standing"on. Dynamic MS divides the map into many more segments than there are servers. The map segments are dynamicallydistributed among the servers based on the results of aload balancing algorithm. The thesis details the algorithms and the performance associated with each of the schemes. In summary, Static Av does not perform well, whereas Static MS and Dynamic MS can be used to parallelize MMORPGapplications. To the best of our knowledge, this is thefirst published work that looks at the issue ofparallelizing and load balancing such applications.

Over the last several years, there has been tremendous growth in online gaming (i. e. playing games over the internet). The Massively Multiplayer Online Role Playing Game (MMORPG) is one type of online game. An MMORPG is played within a virtual world. Users have an in-game representation, called an avatar, that they control. Typically there are over a thousand avatars in the virtual world at one time. Users use client software to connect to an MMORPG server over the internet. If just one server is used then the number of avatars that can be supported in the virtual world at one time is severely limited. In order to overcome this, a multi-server approach is needed. Unlike traditional load balancing and partitioning schemes, which generally use task partitioning, data partitioning is required in this case. This thesis investigates schemes for partitioning and load balancing MMORPG applications on a network of processors. In particular, three different schemes were developed andexamined. These are: Static Av, Static MS and Dynamic MS. Static Avassigns avatars to each server, one at a time, as they enter thesimulation. Static MS assigns equal sized portions of the map of thevirtual world to each server. An avatar is assigned to the server thatowns the part of the map that the avatar is "standing"on. Dynamic MS divides the map into many more segments than there are servers. The map segments are dynamicallydistributed among the servers based on the results of aload balancing algorithm. The thesis details the algorithms and the performance associated with each of the schemes. In summary, Static Av does not perform well, whereas Static MS and Dynamic MS can be used to parallelize MMORPGapplications. To the best of our knowledge, this is thefirst published work that looks at the issue ofparallelizing and load balancing such applications.

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.

The frequent patterns hidden in a graph can reveal crucial information about the network the graph represents. Existing techniques to mine the frequent subgraphs in a graph database generally rely on the premise that the data can be fit into main memory of the device that the computation takes place. Even though there are some algorithms that are designed using highly optimized methods to some extent, many lack the solution to the problem of scalability. In this thesis work, our aim is to find and enumerate the subgraphs that are at least as frequent as the designated threshold in a given graph. Here, we propose a new distributed algorithm for frequent subgraph mining problem that can scale horizontally as the computing cluster size increases. The method described here, uses a partitioning method and Map/Reduce programming model to distribute the computation of frequent subgraphs. In the core of this algorithm, we make use of an existing graph partitioning method to split the given data in the distributed file system and to merge and join the computed subgraphs without losing information. The frequent subgraph computation in each split is done using another known method which can enumerate the frequent patterns. Although current algorithms can efficiently find frequent patterns, they are not parallel or distributed algorithms in that even when they partition the data, they are designed to work on a single machine. Furthermore, these algorithms are computationally expensive but not fault tolerant and are not designed to work on a distributed file system. Using the Map/Reduce paradigm, we distribute the computation of frequent patterns to every machine in a cluster. Our algorithm, first bi-partitions the data via successive Map/Reduce jobs, then invokes another Map/Reduce job to compute the subgraphs in partitions using CloseGraph, recovers the whole set by invoking a series of Map/Reduce jobs to merge-join the previously found patterns. The implementation uses an open source Map/Reduce environment, Hadoop. In our experiments, our method can scale up to large graphs, as the graph data size gets bigger, this method performs better than the existing algorithms.

Adhoc networks do not depend on any fixed infrastructure. The most outstanding features of adhoc networks are non-centralized structure and dynamic topology change due to high mobility. Since mentioned dynamics of mobile adhoc networks complicate reaching the resources in the network, service discovery is significantly an important part of constructing stand-alone and self-configurable mobile adhoc networks. The heterogeneity of the devices and limited resources such as battery are also load up more difficulty to service discovery. Due to the volatile nature of the adhoc networks, service discovery algorithms proposed for mobile and adhoc networks suffer from some problems. Scalability becomes a problem when the service discovery is based on flooding messages over the network. Furthermore, the high traffic which occurs due to the message exchange between network nodes makes the communication almost impossible. Partitioning a network into sub-networks is an efficient way of handling scalability problem. In this thesis, a mobility based service discovery algorithm for clustered MANET is presented. The algorithm has two main parts. First one is for partitioning the MANET into sub-networks, named &ldquo / clustering&rdquo / . Second part is composed of an efficient discovery of services on overall network. Clustering algorithm used in this study is enhanced version of DMAC (Distributed Mobility Adaptive Clustering, which is one of the golden algorithms of the wireless network clustering area). To be fast and flexible in service discovery layer, a simple and fastresponding algorithm is implemented. Integration of two algorithms enables devices to be mobile in the network

Protein-protein interaction networks provide important information about what the biological function of proteins whose roles are unknown might be in a cell. These interaction networks were analyzed by a variety of approaches by running them on a single computer and the roles of the proteins identified were used to predict the function of the proteins unidentified. The functional flow is an approach that takes the network connectivity, distance effect, topology of the network with local and global views into account. With these advantages, that the functional flow produces more accurate results on the prediction of protein functions was presented by the previos conducted researches. However, the application implemented for this approach could not be practically applied on the large and complex network produced for the complex species because of memory limitation. The purpose of this thesis is to provide a new application be implemented on the high computing performance where the application can be scaled on the large data sets. Therefore, Hadoop, one of the open source map/reduce environments, was installed on 18 hosts each of which has eight cores. Method / the first map/reduce job distributes the protein interaction network as a format which allows parallel distributed computing to all the worker nodes, the other map/reduce job generates flows for each known protein function and the role of the proteins unidentified are predicted by accumulating all of these generated flows. It has been observed in the experiments we performed that the application requiring high performance computing can be decomposed into worker nodes efficiently and the application can provide better performance as the resources increase.

We develop two algorithms for important problems in mobile ad hoc networks (MANETs). A MANET is a collection of mobile processors (“nodes”) which communicate via message passing over wireless links. Each node can communicate directly with other nodes within a specified transmission radius; other communication is accomplished via message relay. Communication links may go up and down in a MANET (as nodes move toward or away from each other); thus, the MANET can consist of multiple connected components, and connected components can split and merge over time. We first present a deterministic leader election algorithm for asynchronous MANETs along with a correctness proof for it. Our work involves substantial modifications of an existing algorithm and its proof, and we adapt the existing algorithm to the asynchronous environment. Our algorithm’s running time and message complexity compare favorably with existing algorithms for leader election in MANETs. Second, many algorithms for MANETs require or can benefit from knowledge about the size of the network in terms of the number of processors. As such, we present an algorithm to approximately determine the size of a MANET. While the algorithm’s approximations of network size are only rough ones, the algorithm has the important qualities of requiring little communication overhead and being tolerant of link failures.