Concurrency Control in a Secure Multilevel Database via a Two-Snapshot Algorithm

Abstract

We offer a concurrency conirol algorithm for replicated, secure, multilevel databases. We compare the algorithm with a multiversion approach and with the typical full-replication approach. In the full-replication approach, each security level maintains a container that holds a complete copy of data at lower security levels. In the approach described here, access to data at lower security levels is through shared, read-only snapshots, where a constant number of snapshots at each level – two, as it turns out – is sufficient. We derive necessary properties for snapshots, give a switching algorithm to assign read-downs to snapshots, specify a snapshot creation algorithm, demonstrate that the approach is free of indirect channels and starvation, and prove one-copy serializability on execution histories. In contrast to some comparable algorithms, our algorithm is correct for any security structure that is a partial order.