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.

A concurrency control algorithm for replicated, secure, multilevel databases is presented. Multiversion and replicated databases can avoid starvation problems without introducing indirect channels by maintaining stable copies of old low-level data values for use by high-level transactions. The algorithm presented improves on two comparable techniques, a direct multiversion approach of T. F. Keefe and W. T. Tsai and the full replication scheme of S. Jajodia and B. Kogan (both in Proc. 1990 IEEE Symp. on Res. In Security & Privacy, May 1990). In the latter, each security level has a container that holds a copy of all lower-level data. It is shown that only a constant number of old copies (two, as it turns out) must be maintained. The correctness of the algorithm is argued, and it is demonstrated that the algorithm is free of indirect channels and starvation.>