Towards the design of correct, scalable, and interoperable caching algorithms

Caching is being used pervasively in computer systems to store data closer to where it is used in order to improve performance. Many caching protocols/algorithms have been proposed and developed to cache data retrieved from relational databases (DBs) that store most business data. Different caches support different data access properties, depending on applications and cache sophistication. Because many applications issue transactions they may interfere with each other resulting in corrupted data. Consequently, caching algorithms control access to the cached data by transactions in order to provide applications with a consistent view of data. Because of the many active communicating components in the distributed environment, the design of caching algorithms that provide consistent view of data is difficult and scalable algorithms are yet to be created. Furthermore, the caching algorithms are not compatible with each other and cannot interoperate. This project will address a number of important problems that arise in the design and implementation of such caching algorithms: - A Cache Modelling framework based on the Unified Modelling Language (UML) will be developed - the framework will facilitate the design and implementation of caching algorithms. It will be used to design, develop, implement, and evaluate sophisticated caching algorithms that are scalable and interoperable. The algorithms will include coordinators that communicate with the caching clients to coordinate access to the cached data and thus off-load the DB that tends to be the operations bottleneck. - Methodologies will be developed for (i) proving that caching algorithms are correct and that they indeed provide a consistent view of data and (ii) verifying that the developed code is correct. - Algorithms will be evaluated using simulation techniques and benchmarking to demonstrate that scalable and interoperable caching algorithms are possible.