Back to Main

Concurrency Control in Transactional Systems

Course Number: CS5280


Pre-requisite: Operating Systems or Databases or Instructor Permission

Credits: 3


Nowadays, all computing machines (cell phones, laptops, computation servers) have multi-core chips in them. These multi-core processors can be seen as parallel processors. Now, in order to harness the power of the multi-core hardware, the software applications being developed also have to be parallelized. This is commonly achieved through multi-threading. The multi-threaded application, would normally have to synchronize while accessing shared data. This involves concurrency control among the threads. Many techniques have been developed to address the concurrency control issues in transactional systems (in the context of databases).


Recently, many of researchers and industry practitioners are extending these techniques for software systems as well. Interestingly these techniques have become relevant in the context of smart contract executions in Blockchains. Efficient execution of smart contracts through parallelization in Blockchains is an active research area.


As a part of this course, we will see how the various concurrency control techniques that have been successfully employed traditionally in databases and have resulted in scaling up of databases. A very good example of this is IRCTC database server which can handle around 1000 inquiries per second and 125,000 transactions daily (https://www.business-standard.com/article/companies/irctc-s-payment-gateway-gains-traction-handles-125-000-transactions-daily-121080401273_1.html). Further, we will also see how these techniques can be extended to software systems and blockchains.


Some of the topics I plan to cover as a part of this course are as follows:


Computation Models: Page and Object Models


Correctness for page model: Serializability - review of the basic theory, view serializability, conflict serializability, multiversion serializability.


Concurrency control algorithms for page model: Locking schedulers:Two phase locking & variants, Nonlocking schedulers: Timestamp and optimistic methods, Multiversion Concurrency Control Protocols


Page model crash and recovery: Expanded schedules, correctness criteria for page model, sufficient syntactic conditions for page model, handling aborts, crash recovery notion of correctness, redo winner and history algorithms - checkpoints, log truncation, transaction abort, rollbacks


Correctness notion for object model: Conflict serializability for Flat Object Transactions, Tree Reducibility, Sufficient Conditions for Tree Reducibility


Concurrency Control Algorithms for objects model: Locking for Flat Object Transactions, Layered Locking, Locking on General Transaction Forests, Hybrid Algorithms


Object model crash and recovery: Correctness criteria for the object model, simple redo-history algorithm, enhanced redo-history algorithm, complete redo-history algorithm for two-layered systems and for General Object Model Executions


Concurrency control and recovery in distributed databases: Concurrency Control in Homogeneous Federations, serializability in heterogeneous federations, achieving global serializability through local Guarantees, distributed recovery: two and three-phase commit protocols


Concurrency control paradigms in parallel programming: Linearizablity, sequential consistency, global atomicity etc.


Resurgence of Transactions: Software and hardware transactional memory. Correctness Criteria for Transactional Memory: Opacity, Virtual Worlds Consistency etc.


TEXT

Gerhard Weikum and Gottfried Vossen, Transactional Information Systems: Theory, Algorithms and the Practice of Concurrency Control and Recovery, Morgan-Kaufmann Publishers, San Francisco, CA, 2002.


REFERENCES

(Available for free download at http://research.microsoft.com/en-us/people/philbe/ccontrol.aspx)