Browsing by Author "Padhye, Vinit"
Now showing 1 - 5 of 5
- Results Per Page
- Sort Options
Item Beehive: A Framework for Graph Data Analytics on Cloud Computing Platforms(2013-07-24) Tripathi, Anand; Padhye, Vinit; Sunkara, Tara SasankWe describe here our current work on the development of a programming framework called Beehive for graph data analysis on cloud computing environments. This framework is based on the speculative computing approach using transactional task executions for harnessing amorphous parallelism in graph data analysis problems. We describe here the architecture and the programming abstractions provided by this framework. We present here the results of programming several graph problems using this framework.Item Scalable Transaction Management with Serializable Snapshot Isolation on HBase(2012-02-16) Padhye, Vinit; Tripathi, AnandKey-value based data storage systems such as HBase and Bigtable provide high scalability and availability compared to traditional relational databases. However, unlike relational databases, the existing key-value stores provide only limited transactional functionality, such as single-row transactions. In this paper, we address the problem of building scalable transaction management mechanisms for multi-row ACID transactions on data storage systems such as HBase. To support scalability and availability, the transaction management functions are decoupled from the data storage system. Furthermore, our design does not depend on any central transaction management layer, instead these functions and the related recovery actions are performed in a decentralized and cooperative manner by the application level processes executing the transactions. Our protocol uses snapshot-isolation model as it provides more concurrency. Since the basic snapshot isolation model does not guarantee serializability, our protocol uses a technique based on identifying dependency cycles amongst transactions to avoid serialization anomalies. The protocol for supporting serializability is also performed in a decentralized manner. We demonstrate the scalability and robustness of our approach as well as the correctness of the protocol in ensuring serializable executions of transactions on HBase. We also present and evaluate an alternative approach based on a hybrid model where certain functions, such as conflict detection, are performed by a dedicated service.Item Scalable Transactions in Partially Replicated Data Systems with Causal Snapshot Isolation(2015-07-14) Tripathi, Anand; Rajappan, Gowtham; Padhye, VinitWe present here a transaction management protocol, which enhances the Partitioned Causal Snapshot Isolation (PCSI) pro- tocol, to support scalable transactions with non-local partition writes in a partially replicated multi-version database. The PCSI protocol is scalable for update transactions that involve local read and writes. However, it faces scalability limitations with non-local partition writes, when partitions are updated from any of the sites. In PCSI, to support non-local partition writes, a ghost replica of that partition is created at the transaction execution site. It is used primarily for assigning update sequence numbers to the local transactions and does not store any data. We present here an alternate approach for supporting non-local partition writes. The update sequence number for a non-local partition update is obtained from one of the remote sites that stores a replica of that partition. This approach raises several problems in regard to stalling of transactions at the remote replica’s site. We develop here a protocol based on the notion of sequence number escrow to address these problems. Through experimental evaluations, we show that this approach for supporting non-local partition updates scales almost linearly.Item Transaction Management using Causal Snapshot Isolation in Partially Replicated Databases(2013-07-24) Padhye, Vinit; Tripathi, AnandWe present here a transaction management protocol using 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. The updates in this model are performed using asynchronous update propagation. The protocol ensures that the snapshot observed by a transaction contains data versions that are causally consistent. 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. Such a model is attractive in geo-scale systems because of its support for partial replication, use of causal consistency model which does not require a global sequencer, and asynchronous propagation of updates.Item A Transactional Model for Parallel Programming of Graph Applications on Computing Clusters(IEEE, 2017) Tripathi, Anand; Padhye, Vinit; Sunkara, Tara Sasank; Tucker, Jeremy; Thirunavukarasu, BhagavathiDhass; Pandey, Varun; Sharma, Rahul R.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.