Exploring Progress Guarantees in Multi-Version Software Transactional Memory Systems

In the current era of multi-core processors, Software Transactional Memory systems (STMs) have garnered significant interest as an elegant alternative for addressing synchronization and concurrency issues with multi-threaded programming to utilize the cores properly. Client programs use STMs by issuing transactions. A transaction of STMs is a piece of code that performs reads and writes to the shared memory. Typical STMs work on read/write methods which maintain single-version corresponding to each transactional-object or t-object called as Single-Version Read-Write STMs (SV-RWSTMs or RWSTMs). It has been shown in the literature that maintaining multiple versions corresponding to each t-object reduces the number of aborts and enhances performance. Several Multi-Version RWSTMs (or MV-RWSTMs) have been proposed in the literature that maintain multiple versions and provide increased concurrency along with better performance than SV-RWSTMs. Some STMs work at higher-level operations and ensure greater concurrency than MVRWSTMs and SV-RWSTMs. They include more semantically rich operations such as push/pop on stack objects, enqueue/dequeue on queue objects and insert/lookup/delete on sets, trees or hash table objects depending upon the underlying data structure used to implement higher-level systems. Such STMs are known as Single-Version Object-based STMs (SV-OSTMs or OSTMs). To achieve the greater concurrency further, researchers have proposed Multi-Version OSTM (or MV-OSTM) which maintains multiple versions corresponding to each t-object in OSTMs. MV-OSTM system reduces the number of aborts and improves performance than SV-OSTMs, MV-RWSTMs, and SV-RWSTMs. All the STMs defined above ensure that transaction either commits or aborts. A transaction aborted due to conflicts (two transactions are said to be in conflict if both of them are accessing same t-object x and at least one of the transaction performs write/update on x) is typically re-issued with the expectation that it will complete successfully in a subsequent incarnation. However, many existing STMs fail to provide starvation freedom, i.e., in these systems, it is possible that concurrency conflicts may prevent an incarnated transaction from committing. To overcome this limitation, we developed an efficient STM system which ensuresstarvationfreedom as a progress condition. An STM system is said to be starvation-free if a thread invoking a transaction Ti gets the opportunity to retry Ti on every abort (due to the presence of a fair underlying scheduler with bounded termination) and Ti is not parasitic, i.e., Ti will try to commit given a chance then Ti will eventually commit. Wait-freedom is another interesting progress condition for STMs in which every transaction commits regardless of the nature of concurrent transactions and the underlying scheduler. But it was shown in the literature that it is not possible to achieve wait-freedom in dynamic STMs in which t-objects of transactions are not known in advance. So in this thesis, we explore the weaker progress condition starvation-freedom for transactional memory systems (SV-RWSTMs, MV-RWSTMs, SV-OSTMs, and MV-OSTMs) vi while assuming that the t-objects of the transactions are not known in advance. Some researchers have explored starvation-freedom in SV-RWSTMs while maintaining single-version corresponding to each t-object. We denote such an algorithm as Starvation-Free Single-Version RWSTM (or SF-SV-RWSTM). Although SF-SV-RWSTM guarantees starvationfreedom, but it can still abort many transactions spuriously which brings down the efficiency and progress of the entire system. To overcome this issue, we systematically developed a novel and efficient starvation free algorithm as Starvation-free Multi-Version RWSTM (SF-MV-RWSTM). It maintains multiple versions corresponding to each t-object which reduces the number of aborts and enhances the performance than SF-SV-RWSTMs. Proposed SF-MV-RWSTM can be used either with the case where the number of versions is unbounded and Garbage Collection (GC) is used to delete unwanted versions as SF-MV-RWSTM-GC or where only the latest K-versions are maintained, as Starvation-Free K-Version RWSTM (or SF-K-RWSTM). Our experimental analysis demonstrates that the proposed SF-K-RWSTM algorithm performs best among its variants (SFMV-RWSTM and SF-MV-RWSTM-GC) along with state-of-the-art STMs under long-running transactions with high contention. SF-K-RWSTM satisfies the popular correctness-criteria local opacity and ensures the progress condition as starvation-freedom. To achieve starvation-freedom along with higher concurrency, we proposed StarvationFreedom in SV-OSTM as SF-SV-OSTM which assigns the priority to the transaction on abort. SF-SV-OSTM satisfies the correctness criteria conflict-opacity while ensuring the progress condition as starvation-freedom. To achieve the greater concurrency further while ensuring the starvation-freedom, we maintained multiple versions corresponding to each t-object in starvation-free OSTMs and proposed a novel and efficient Starvation-Freedom Multi-Version OSTM (or SF-MV-OSTM). The number of versions maintained by SF-MV-OSTM either be unbounded with Garbage Collection (GC) as SF-MV-OSTM-GC or bounded with the latest K-versions as SF-K-OSTM. SF-K-OSTM ensures starvation-freedom, satisfies the correctness criteria as local opacity and shows the performance benefits as compared with state-of-the-art STMs. This thesis explores the progress guarantee starvation-freedom in single and multi-version RWSTMs, single and multi-version OSTMs while satisfying the correctness-criteria as conflictopacity and local opacity. It shows that maintaining multiple versions improves the concurrency than single-version while reducing the number of aborts and increasing the throughput. This motivated us to use efficient multi-version STMs to improve the performance of smart contract executions in blockchain systems. Blockchain platforms such as Ethereum and several others execute complex transactions in blocks through user-defined scripts known as smart contracts. Normally, a block of the chain consists of multiple transactions of smart contracts that are added by a miner. To append a correct block into the blockchain, miners execute these transactions of smart contracts sequentially. Later the validators serially re-execute the smart contract transactions of the block. If the validators agree with the final state of the block as recorded by the miner and reach the consensus, then the block is said to be validated and the respective miner gets an incentive on such a valid block successfully added to the blockchain. Nowadays, multi-core processors are ubiquitous. By employing serial execution of the transactions, the miners and validators fail to utilize the cores properly and as a result, have poor throughput. Adding concurrency to smart contracts execution can result in better utilization of the cores and as a result higher throughput. In this thesis, we develop a framework to execute the smart contract transactions concurrently by miner using efficient Multi-Version Software Transactional Memory systems (MVSTMs). The miner proposes a block which consists of a set of transactions, block graph, the hash of the previous block and final state of each shared t-object. The block graph captures the conflicting relations among the transactions. Later, the validators re-execute the same smart contract transactions concurrently and deterministically with the help of the block graph given by miner to verify the final state. If the validation is successful then the proposed block is appended into the blockchain as a part of the consensus protocol. In the case of the blockchain as a cryptocurrency like Ethereum, Bitcoin, the respective miner also gets a reward for producing the block. If validation is not successful, then validator discards the proposed block. Concurrent execution of smart contract transactions by miner and validator achieve significant performance gain as compared to serial miner and validator. But concurrent execution of smart contracts poses some interesting challenges. So, in this thesis, we show how to overcome these challenges to improve the performance of smart contract execution by executing them concurrently using efficient MVSTM protocols