Serializability Preserving Extensions of Concurrency Control Protocols

Dmitri Chkliaev, Jozef Hooman and Peter van der Stok

Appeared in: Proceedings of the Andrei Ershov International Conference "Perspectives of Systems Informatics", LNCS 1755, Springer-Verlag, Novosibirsk, pages 180-193, 1999.


The verification system PVS is used to obtain mechanized support for the formal specification and verification of concurrency control protocols, concentrating on database applications. A method to verify conflict serializability has been formulated in PVS and proved to be sound and complete with the interactive proof checker of this tool. The method has been used to verify a few basic protocols. Next we present a systematic way to extend these protocols with new actions and control information. We show that is such an extension satisfies a few simple correctness conditions, the new protocol is serializable by construction.

Postscript © Springer-Verlag