Department of Computer Science and Engineering
University of South Carolina
Author : John Ravan
Advisor : Dr. Csilla Farkas
Date : November 1, 2021
Time : 1:30pm
Place : Virtual Defense
Join Zoom Meeting
Concurrent database transactions within a web service environment can cause a variety of problems without the proper concurrency control mechanisms in place. A few of these problems involve data integrity issues, deadlock, and efficiency issues. Even with today's industry standard solutions to these problems, they have taken a reactive approach rather than proactively preventing these problems from happening. We deliver a twofold solution that presents a proactive prediction-based approach to ensure consistency while keeping execution time the same or faster than current industry solutions. The first part of this solution involves prototyping and formally proving a prediction-based scheduler.
The prediction-based scheduler leverages a prediction-based metric that promotes transactions with reliable reputations based on the transaction's performance metric. This performance metric is based on the transaction's likelihood to commit and its efficiency within the system. We can then predict the outcome of the transaction based on the metric and apply customized lock behaviors to address consistency issues in current web service environments. We have formally proven that the solution will increase consistency among web service transactions without a performance degradation that is worse than industry standard 2PL. The simulation was developed using a multi-threaded approach to simulate concurrent transactions. Experimentation results show that the solution works comparatively with industry solutions with the added benefit of ensured consistency in some cases and deadlock avoidance in others. This work has been published in IEEE Transactions on Services Computing.
The second part of the solution involves building the prediction-based metric mentioned previously. In the initial solution we assumed the prediction-based categorization coming into the solution in order to prove the feasibility and correctness of a prediction-based scheduler.
Once that was established, we extended the four-category solution to a dynamic reputation score built upon transactional attributes. The attributes used in the reputation score are system abort ranking, user abort ranking, efficiency ranking, and commit ranking. With these four attributes we were able to establish a dynamic dominance structure that allowed for a transaction to promote or demote itself based on its performance within the system. This work has been submitted to ACM Transactions on Information Systems and awaiting review.
Both phases provide a complete solution of prediction-based transaction scheduling that provides dynamic categorization no matter the transactional environment.
Future work of this system would involve extending the prediction-based solution to a multi-level secure database with an added dimension. The dimension provides a security classification in addition to attributes for dynamic reputation that allows for transactions to establish dominance. The goal would be to prevent covert timing channels that occur in multi-level secure database systems due to the differing classifications. Our reputation score would provide a cover story for timing differences of transactions of different security levels to allow for a more robust scheduling algorithm. This would allow for high security transactions to gain priority over low security transactions without exposing a covert timing channel.