Multiversion post ordering: A new concurrency control method

This paper presents a new concurrency control algorithm called Multiversion Post Ordering (MVPO). MVPO is a conservative multiversion timestamp ordering method. The main drawback of multiversion timestamp ordering protocols is that they reject write steps that arrive "too late", forcing transaction to restart. MVPO remedies this problem by delaying "early reads". These operations are only delayed, however, until the values they are assigned to read have been produced. Thus, MVPO is free of both unnecessary delay and restart. In addition, MVPO uses a data structure, called the write table, which can be accessed directly by individual transaction managers, eliminating the need for a centralized scheduler. This allows a high degree of parallelism among transactions. The MVPO method is compared to two multiversion timestamp protocols, and, its advantages and limitations are discussed.