ALTERNATIVE CORRECTNESS CRITERIA FOR CONCURRENT EXECUTION OF TRANSACTIONS IN MULTILEVEL SECURE DATABASES

This paper investigates issues related to transaction concurrency cont rol in multilevel secure databases. It demonstrates how the conflicts between the correctness requirements and the secrecy requirements can be reconciled by proposing two different solutions. This paper, first, explores the correctness criteria that are weaker than one-copy seria lizability. Each of these weaker criteria, though not as strict as one -copy serializability, is required to preserve database consistency in some meaningful way, and moreover, its implementation does not requir e the scheduler to be trusted. It proposes three different, increasing ly stricter notions of serializability-level-wise serializability, one -item read serializability and pair-wise serializability-thai can serv e as substitutes for one-copy serializability. This paper, then, inves tigates secure concurrency control protocols that generate one-copy se rializable histories and presents a multiversion timestamping protocol that has several very desirable properties: It is secure, produces mu ltiversion histories that are equivalent to serial one-copy histories in which transactions are placed in a timestamp order, eliminates star vation, and can be implemented using single-level untrusted schedulers .