This dissertation presents algorithms for data structures called distributed hash tables (DHT) or structured overlay networks, which are used to build scalable self-managing distributed systems. The provided algorithms guarantee lookup consistency in the presence of dynamism: they guarantee consistent lookup results in the presence of nodes joining and leaving. Similarly, the algorithms guarantee that routing never fails while nodes join and leave. Previous algorithms for lookup consistency either suffer from starvation, do not work in the presence of failures, or lack proof of correctness. Several group communication algorithms for structured overlay networks are presented. We provide an overlay broadcast algorithm, which unlike previous algorithms avoids redundant messages, reaching all nodes in O(log n) time, while using O(n) messages, where n is the number of nodes in the system. The broadcast algorithm is used to build overlay multicast. We introduce bulk operation, which enables a node to efficiently make multiple lookups or send a message to all nodes in a specified set of identifiers. The algorithm ensures that all specified nodes are reached in O(log n) time, sending maximum O(log n) messages per node, regardless of the input size of the bulk operation. Moreover, the algorithm avoids sending redundant messages. Previous approaches required multiple lookups, which consume more messages and can render the initiator a bottleneck. Our algorithms are used in DHT-based storage systems, where nodes can do thousands of lookups to fetch large files. We use the bulk operation algorithm to construct a pseudo-reliable broadcast algorithm. Bulk operations can also be used to implement efficient range queries. Finally, we describe a novel way to place replicas in a DHT, called symmetric replication, that enables parallel recursive lookups. Parallel lookups are known to reduce latencies. However, costly iterative lookups have previously been used to do parallel lookups. Moreover, joins or leaves only require exchanging O(1) messages, while other schemes require at least log(f) messages for a replication degree of f. The algorithms have been implemented in a middleware called the Distributed k-ary System (DKS), which is briefly described. / QC 20100824

The distribution of real-time GIS (Geographic Information System) data among users is now more important than ever as it becomes increasingly affordable and important for scientific and government agencies to monitor environmental phenomena in real-time. A growing number of sensor networks are being deployed all over the world, but there is a lack of solutions for their effective monitoring. Increasingly, GIS users need access to real-time sensor data from a variety of sources, and the data must be represented in a visually-pleasing way and be easily accessible. In addition, users need to be able to collaborate with each other to share and discuss specific sensor data. The real-time acquisition, analysis, and sharing of sensor data from a large variety of heterogeneous sensor sources is currently difficult due to the lack of a standard architecture to properly represent the dynamic properties of the data and make it readily accessible for collaboration between users. This thesis will present a JEE-based publisher/subscriber architecture that allows real-time sensor data to be displayed collaboratively on the web, requiring users to have nothing more than a web browser and Internet connectivity to gain access to that data. The proposed architecture is evaluated by showing how an AJAX-based and a Flash-based web application are able to represent the real-time sensor data within novel collaborative environments. By using the latest web-based technology and relevant open standards, this thesis shows how map data and GIS data can be made more accessible, more collaborative and generally more useful.

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.

In distributed systems, dependency among different computations of an application leads to a problem of deciding the locations of computations. Spatial requirements of a computation can be expressed in terms of spatial relationships with other computations. This research presents programming abstractions and language constructs which can be used for specifying spatial coordination requirements for distributed computations. A spatial coordination middleware has been implemented for satisfying spatial coordination requirements of systems implemented using the Actor model of concurrent computation. Our approach abstracts spatial requirements of concurrent computations and provides key programming primitives for specifying these requirements. We have also implemented a number of higher level spatial coordination primitives which can be translated into the basic primitives. Spatial requirements can be specified using these primitives and then the runtime system converts them into a constraint satisfaction problem and satisfies them. Our approach reduces the programming complexity and provides a middleware which separates spatial requirements from functional code and enables the application programmer to change spatial requirements at runtime without effecting application's functionality. We have identified some of the high level primitives and provided a mechanism to develop high level primitives on top of the basic primitives. This thesis presents the rationale, design, implementation, and evaluation of spatial coordination. By comparing programs written with and without our spatial coordination primitives, we show how spatial coordination enables a programmer to specify spatial requirements declaratively and simplify the programming task. Experimental results demonstrate the performance of the approach, as the number of constraints increases.

Web services technology has lately stirred tremendous interest in industry as well as the academia. Web services are self-contained, platform independent functionality which is available over the internet. Web services are defined, discovered & accessed using a standard protocols like WSDL, UDDI & SOAP. With the advent of Service-Oriented Architecture and need for more complex application, it became eminent to have a way in which these independent entities could collaborate in a coherent manner to provide a high level functionality. But the problem of service composition is not an easy one. One reason being the self-contained and loosely coupled interaction style, which happens to be the single most important reason for its popularity. We are proposing a prototype system for distributed coordination of web services. This system is based on the Web Bonds model for coordination. The system, dubbed BondFlow system, allows configuration and execution of workflows configured over web services. Presently BondFlow system allows both centralized as well as distributed coordination of workflows over handhelds, which we claim as an engineering feet and is currently a unique work in this area.

The distribution of real-time GIS (Geographic Information System) data among users is now more important than ever as it becomes increasingly affordable and important for scientific and government agencies to monitor environmental phenomena in real-time. A growing number of sensor networks are being deployed all over the world, but there is a lack of solutions for their effective monitoring. Increasingly, GIS users need access to real-time sensor data from a variety of sources, and the data must be represented in a visually-pleasing way and be easily accessible. In addition, users need to be able to collaborate with each other to share and discuss specific sensor data. The real-time acquisition, analysis, and sharing of sensor data from a large variety of heterogeneous sensor sources is currently difficult due to the lack of a standard architecture to properly represent the dynamic properties of the data and make it readily accessible for collaboration between users. This thesis will present a JEE-based publisher/subscriber architecture that allows real-time sensor data to be displayed collaboratively on the web, requiring users to have nothing more than a web browser and Internet connectivity to gain access to that data. The proposed architecture is evaluated by showing how an AJAX-based and a Flash-based web application are able to represent the real-time sensor data within novel collaborative environments. By using the latest web-based technology and relevant open standards, this thesis shows how map data and GIS data can be made more accessible, more collaborative and generally more useful.

Peer-to-Peer (P2P) computing offers new research challenges in the field of distributed computing. This paradigm can take advantage of a huge number of idle CPU cycles through Internet in order to solve very complex computational problems. All these resources are provided voluntarily by millions of users spread over the world. This means the cost of allocating and maintaining the resources is split and assumed by each owner/peer. For this reason, P2P computing can be seen as a low-cost alternative to expensive super-computers. Obviously, not every kind of parallel application is suitable for a P2P computing environment. Those with high communication requirements between tasks or with high QoS needs should still be performed in a Local Area Networking (LAN) environment. Otherwise, problems with huge computational requirements that can be easily split into millions of independent tasks are suitable for P2P computing, especially as solving these problems with a supercomputer would be extremely expensive. One of the most critical aspects in the design of P2P systems is the development of incentive techniques to enforce cooperation and resource sharing among participants. Incentive policies in P2P distributed computing systems is a new research field that requires specific policies to fight against malicious and selfish behavior by peers. Encouraging peers to collaborate in file-sharing has been widely investigated but, in the P2P computing field, this issue is still at a very early stage of research. Furthermore, the dynamics of peer participation are an inherent property of P2P systems and critical for design and evaluation. This further increases the difficulty of P2P computing. Another critical aspect of P2P computing systems is the development of scheduling techniques to achieve an efficient and scalable management of the computational resources. Unlike file-sharing, based on such immutable resources as files, the mutable ones, such as CPU and Memory are the principal resources involved in P2P computing. Inside the scheduling field, P2P computing can be seen as a particular variant of Grid computing. In a similar way as with the incentive polices, an extensive list of publications can be found that study the scheduling problems for distributed computing, such as Clusters or Grid computing, but few of these focus on P2P computing. For this reason, the scheduling problem in this kind of network is a field that still requires research in depth. In this thesis we propose a Distributed Incentive and Scheduling Integrated Mechanism (DISIM) with a two-level topology and designed to work on largescale distributed computing P2P systems. The low level is formed by associations of peers controlled by super-peers with major responsibilities in managing and gathering information about the state of these groups. Scalability limitations on the first level are avoided by providing the mechanism with an upper level, made up of super-peers interconnected through a logical overlay. Regarding incentives, we propose a mechanism based on credits with a twolevel topology designed to operate on different platforms of shared computing networks. One of the main contributions is a new policy for managing the credits, called Weighted, that increases peer participation significantly. This mechanism reflects P2P user dynamics, penalizes free-riders efficiently and encourages peer participation. Moreover, the use of a popular pricing strategy, called reverse Vickrey Auction, protects the system against malicious peer behavior. Simulation results show that our policy outperforms alternative approaches, maximizing system throughput and limiting free-riding behavior by peers. From the scheduling point of view, the low-level scheduler takes user dynamism into account and is almost optimal since it holds all the status information about the workload and computational power of its constituent peers. Our main contribution at the upper level is to propose three criteria that only use local information for scheduling tasks, providing the overall system with scalability. By setting these criteria, the system can easily, dynamically and rapidly adapt its behavior to very different kinds of parallel jobs in order toachieve an efficient performance. The results obtained proved the efficiency of the overall model and the convergence with the best assignment, achieved with an ideal centralized policy with global information.

This dissertation studies interference in wireless networks. Interference results from multiple simultaneous attempts to communicate, often between unassociated sources and receivers, preventing extensive coordination. Moreover, in practical wireless networks, learning network state is inherently expensive, and nodes often have incomplete and mismatched views of the network. The fundamental communication limits of a network with such views is unknown. To address this, we present a local view model which captures asymmetries in node knowledge. Our local view model does not rely on accurate knowledge of an underlying probability distribution governing network state. Therefore, we can make robust statements about the fundamental limits of communication when the channel is quasi-static or the actual distribution of state is unknown: commonly faced scenarios in modern commercial networks. For each local view, channel state parameters are either perfectly known or completely unknown. While we propose no mechanism for network learning, a local view represents the result of some such mechanism. We apply the local view model to study the two-user Gaussian interference channel: the smallest building block of any interference network. All seven possible local views are studied, and we find that for five of the seven, there exists no policy or protocol that universally outperforms time-division multiplexing (TDM), justifying the orthogonalized approach of many deployed systems. For two of the seven views, TDM-beating performance is possible with use of opportunistic schemes where opportunities are revealed by the local view. We then study how message cooperation --- either at transmitters or receivers --- increases capacity in the local view two-user Gaussian interference channel. The cooperative setup is particularly appropriate for modeling next-generation cellular networks, where costs to share message data among base stations is low relative to costs to learn channel coefficients. For the cooperative setting, we find: (1) opportunistic approaches are still needed to outperform TDM, but (2) opportunities are more abundant and revealed by more local views. For all cases studied, we characterize the capacity region to within some known gap, enabling computation of the generalized degrees of freedom region, a visualization of spatial channel resource usage efficiency.

Monitoring and debugging distributed systems is inherently a difficult problem. Events collected during the execution of distributed systems can enable developers to diagnose and fix faults. Process-time diagrams are normally used to view the relationships between the events and understand the interaction between processes over time. A major difficulty with analyzing these sets of events is that they are usually very large. Therefore, being able to search through the event-data sets can enable users to get to points of interest quickly and find out if patterns in the dataset represent the expected behaviour of the system. A lot of research work has been done to improve the search algorithm for finding event-patterns in large partial-order datasets. In this thesis, we improve on this work by parallelizing the search algorithm. This is useful as many computers these days have more than one core or processor. Therefore, it makes sense to exploit this available computing power as part of an effort to improve the speed of the algorithm. The search problem itself can be modeled as a Constraint Satisfaction Problem (CSP). We develop a simple and efficient way of generating tasks (to be executed by the cores) that guarantees that no two cores will ever repeat the same work-effort during the search. Our approach is generic and can be applied to any CSP consisting of a large domain space. We also implement an efficient dynamic work-stealing strategy that ensures the cores are kept busy throughout the execution of the parallel algorithm. We evaluate the efficiency and scalability of our algorithm through experiments and show that we can achieve efficiencies of up to 80% on a 24-core machine.

In distributed systems, dependency among different computations of an application leads to a problem of deciding the locations of computations. Spatial requirements of a computation can be expressed in terms of spatial relationships with other computations. This research presents programming abstractions and language constructs which can be used for specifying spatial coordination requirements for distributed computations. A spatial coordination middleware has been implemented for satisfying spatial coordination requirements of systems implemented using the Actor model of concurrent computation. Our approach abstracts spatial requirements of concurrent computations and provides key programming primitives for specifying these requirements. We have also implemented a number of higher level spatial coordination primitives which can be translated into the basic primitives. Spatial requirements can be specified using these primitives and then the runtime system converts them into a constraint satisfaction problem and satisfies them. Our approach reduces the programming complexity and provides a middleware which separates spatial requirements from functional code and enables the application programmer to change spatial requirements at runtime without effecting application's functionality. We have identified some of the high level primitives and provided a mechanism to develop high level primitives on top of the basic primitives. This thesis presents the rationale, design, implementation, and evaluation of spatial coordination. By comparing programs written with and without our spatial coordination primitives, we show how spatial coordination enables a programmer to specify spatial requirements declaratively and simplify the programming task. Experimental results demonstrate the performance of the approach, as the number of constraints increases.