  Software Transactional Memory Systems (STM) are a promising alternative to
lock based systems for concurrency control in shared memory systems. In
multiversion STM systems, each write on a transaction object produces a new
version of that object. The advantage obtained by storing multiple versions is
that one can ensure that read operations do not fail. Opacity is a commonly
used correctness criterion for STM systems. Multi-Version permissive STM system
never aborts a read-only transaction. Although many multi-version STM systems
have been proposed, to the best of our knowledge none of them have been
formally proved to satisfy opacity. In this paper we present a time-stamp based
multiversion STM system that satisfies opacity and mv-permissiveness. We
formally prove the correctness of the proposed STM system. We also present
garbage collection procedure which deletes unwanted versions of the transaction
objects and formally prove it correctness.
