We present here the results of our investigation of a transactional model of parallel programming on cluster computing systems. This model is specifically targeted for graph applications with the goal of harnessing unstructured parallelism inherently present in many such problems. In this model, tasks for vertex-centric computations are executed optimistically in parallel as serializable transactions. A key-value based globally shared object store is implemented in the main memory of the cluster nodes for storing the graph data. Task computations read and modify data in the distributed global store, without any explicitly programmed message-passing in the application code. Based on this model we developed a framework for parallel programming of graph applications on computing clusters. We present here the programming abstractions provided by this framework and its architecture. Using several graph problems we illustrate the simplicity of the abstractions provided by this model. These problems include graph coloring, k-nearest neighbors, and single-source shortest path computation. We also illustrate how incremental computations can be supported by this programming model. Using these problems we evaluate the transactional programming model and the mechanisms provided by this framework.

We address the problem of building scalable transaction management mechanisms for multi-row transactions on key-value storage systems, which are commonly termed as NoSQL systems. We develop scalable techniques for transaction management utilizing the snapshot isolation (SI) model. Because the SI model can lead to non-serializable transaction executions, we investigate two conflict detection techniques for ensuring serializability. To support scalability, we investigate system architectures and mechanisms in which the transaction management functions are decoupled from the storage system and integrated with the application-level processes. We present two system architectures and demonstrate their scalability under the scale-out model of cloud computing platforms. In the first system architecture all transaction management functions are executed in a fully decentralized manner by the application processes. The second architecture is based on a hybrid approach in which the conflict detection functions are performed by a dedicated service. We perform a comparative evaluation of these architectures using the TPC-C benchmark and demonstrate their scalability.

We present here a transaction management protocol using causal snapshot isolation in partially replicated multi-version databases. We consider here replicated databases consisting of multiple disjoint data partitions. A partition is not required to be replicated at all database sites, and a site may contain replicas for any number of partitions. Transactions can execute at any site and read or write data from any subset of the partitions, and its updates are propagated asynchronously to other sites. The protocol ensures that the snapshot observed by a transaction contains data versions that are causally consistent. The protocol requires propagating updates only to the sites replicating the updated items. In developing this protocol, we address the issues that are unique in supporting transactions with causal consistency together with the snapshot isolation model in partially replicated databases. Through experimental evaluations, we demonstrate the scalability of this model and its performance benefits over full replication models.

We present here a system architecture and its underlying mechanisms for building autonomically scalable and resilient services on cooperatively shared computing platforms. Specifically, our focus is on utilizing computing platforms exhibiting the following characteristics. The resources at a node in such platforms are allocated to competing users on fair-share basis, without any reserved resource capacities for any user. There is no platform-wide resource manager for the placement of users on different nodes. The users independently select nodes for their applications. Moreover, a node can become unavailable at any time due to crashes or shutdowns. Building scalable services in such environments poses unique challenges due to node-level fluctuations in the available resource capacities and node crashes. The service load may surge in a short time due to flash crowds. Autonomic scaling of service capacity is performed by dynamic control of the degree of service replication based on the estimated service capacity and the observed load. We present here models for estimating the service capacity at a node under fluctuating operating conditions. Furthermore, we develop adaptive and agile load distribution mechanisms for distributing load among replicas based on their time-varying service capacities. We present the results of our evaluations of these mechanisms on PlanetLab, which exemplifies the platform level characteristics considered here.Copyright © 2013 John Wiley & Sons, Ltd.

The focus of our work is on studying the resource availability characteristics of large-scale, cooperatively pooled, shared computing platforms. Our focus is on platforms in which resources at a node are allocated to competing users on fair-share basis, without any reserved resource capacities for any user, and there is no platform-wide resource manager for the placement of users on different nodes. The users independently select nodes for their applications. Our study is focused on the PlanetLab system which exemplifies such platforms. The goal of our study is to develop heuristics based on the observed resource availability characteristics for selecting nodes for deploying applications. Our approach uses the notion of eligibility period, which represents a contiguous duration for which a node satisfies a given resource requirement. We study the characteristics of the eligibility periods of Planetlab nodes for various resource capacity requirements. Based on this study we develop heuristics for identifying nodes that are likely to satisfy a given requirement for long durations. We also develop an online model for predicting the idle resource capacity that is likely to be available on a node over a short term. We evaluate and demonstrate the performance benefits of the node selection techniques and the prediction model using the PlanetLab node utilization data traces collected at different intervals over an extended period of several months.

We address the problem of building scalable transaction management mechanisms for multi-row transactions on key-value storage systems. We develop scalable techniques for transaction management utilizing the snapshot isolation (SI)model. Because the SI model can lead to non-serializable transaction executions, we investigate two conflict detection techniques for ensuring serializability under SI. To support scalability, we investigate system models and mechanisms in which the transaction management functions are decoupled from the storage system and integrated with the application-level processes. We present two system models and demonstrate their scalability under the scale-out paradigm of Cloud computing platforms. In the first system model, all transaction management functions are executed in a fully decentralized manner by the application processes. The second model is based on a hybrid approach in which the conflict detection techniques are implemented by a dedicated service. We perform a comparative evaluation of these models using the TPC-C benchmark and demonstrate their scalability.

We propose a Snapshot Isolation based transaction execution and consistency model, referred to as causally coordinated snapshot isolation, for geographically replicated data. The data replication is managed through asynchronous update propagation. Our approach provides snapshot-isolation model over multiple sites and ensures causal ordering of transactions. We present here an efficient protocol for precisely capturing the causal data dependencies of transactions and ensuring the causal ordering based on these dependencies when applying transactions' updates at remote sites. Through experimental evaluations, we demonstrate the benefit of this protocol over an alternative approach for providing causal consistency for georeplicated data. We further extend this model to support session consistency guarantees such as read-your-writes and monotonic reads. Additionally, we provide a notion of group-session where a group of users are involved in a collaborative session. We provide various group-session consistency guarantees for users collaborating in a group. We present the mechanisms for providing these session consistency guarantees and evaluate their performance.

We present here mechanisms and models for building autonomically scalable and resilient services on wide-area shared computing platforms in which resources at a node are allocated to competing users on fair-share basis. There is no platform-wide resource manager for the placement of users on different nodes. Building scalable services in such environments poses unique challenges due to fluctuations in the available resource capacities and node crashes. The service load may surge in a short time due to flash crowds. We present here models for estimating the service capacity under varying operating conditions. Autonomic scaling of service capacity is performed by dynamic control of the degree of service replication based on the estimated service capacity and the observed load. Furthermore adaptive load distribution mechanisms are needed because of the varying service capacities of the individual replicas. We present the results of our evaluations of these mechanisms on Planet Lab.

In this paper we present the design and evaluation of a system for deploying highly available and migratable services in shared infrastructures, such as the PlanetLab, where the available resource capacities at a node can fluctuate significantly. A migratable service can monitor its operating conditions and autonomously relocate itself to another node when the available resource capacities at the current node fall below certain acceptable limits. We utilize the autonomous mobile agent paradigm for building such migratable services. Such agents can monitor their operating conditions and follow various migration policies. We investigate here the mechanisms for service relocation, and client-side protocols to access migratory services. The "blackout periods'', i.e. the time during which the clients are unable to access a migrating service, need to be minimized and kept within some tolerable limits for services required to be highly available. We first present the design of a migratable service implemented using a mobile agent, and evaluate its performance in terms of the blackout periods and the service agent's abilities to autonomously migrate in the network. We replicate service agents to reduce the blackout periods, and develop the coordination protocols for autonomous agent migration in a group of service agents. We also present here our work for monitoring PlanetLab nodes for their available resource capacities in order to assist a migratory service in selecting a target node for relocation.