Alternative correctness criteria for concurrent execution of transactions in multilevel secure databases

Two different areas related to the concurrency control in multilevel secure, multiversion databases are considered. First, the issue of correctness criteria that are weaker than one-copy serializability are explored. The requirements for a weaker correctness criterion are that it should preserve database consistency in some meaningful way, and moreover, it should be implementable in a way that does not require the scheduler to be trusted. Three different, increasingly stricter notions of serializability that can serve as substitutes for one-copy serializability are proposed. Second, a multiversion timestamping protocol is presented that has several very desirable properties: it is secure, produces multiversion histories that are equivalent to one-serial histories in which transactions are placed in a timestamp order, avoids livelocks, and can be implemented using single-level untrusted schedulers