Transaction management in replicated-architecture multi-level-secure database systems

A replicated-architecture multilevel-secure database system is a centralized database system that uses data replication to provide multilevel security. Multilevel security is an extension of the concept of operating system protection: multilevel-secure computer systems provide multiple protection classes and access modes for data and programs, and restrict access to data and programs based on those classes and modes. The protection classes are ordered, hence the term multilevel. The most critical problem associated with implementing replicated-architecture multilevel-secure database systems is transaction management: correct concurrency control, mutual consistency of replicas, and atomic recovery from failures, all under the constraints of multilevel security.;The seven transaction processing algorithms presented here represent several approaches we have discovered. There are both immediate-write algorithms that update replicas simultaneously and deferred-write algorithms that do not. Some of the algorithms preserve the transaction abstraction across two or more security classes, providing multilevel transaction processing, a new issue that had not been studied in the literature. We find several other interesting results related to transaction management algorithms for the replicated architecture: (1) that, in many cases, database transactions are best modeled as sets of subjects instead of single subjects, (2) that full recovery is always possible and in some cases we can do even better by continuing operation under partial failure, (3) that the available algorithms for transaction management in the replicated architecture have about the same performance, which is also about the same as a conventional database system without multilevel security; thus one of these algorithms may be chosen for reasons other than performance, and (4) that the available algorithms have significant structural differences with no clear winners. Our most important result is that, due to the choices of algorithms now available, we should be able to implement correct and secure transaction management in the replicated architecture under a variety of circumstances.