Alternative correctness criteria for concurrent execution oftransactions in multilevel secure databases

Investigates issues related to transaction concurrency control in multilevel secure databases. This paper demonstrates how the conflicts between the correctness requirements and the secrecy requirements can be reconciled by proposing two different solutions. It first explores the correctness criteria that are weaker than one-copy serializability. 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 require the scheduler to be trusted. It proposes three different, increasingly stricter notions of serializability (level-wise serializability, one-item read serializability and pair-wise serializability) that can serve as substitutes for one-copy serializability. The paper then investigates secure concurrency control protocols that generate one-copy serializable histories and presents a multiversion timestamping protocol that has several very desirable properties: it is secure, produces multiversion histories that are equivalent to serial one-copy histories in which transactions are placed in a timestamp order, eliminates starvation and can be implemented using single-level untrusted schedulers     

Read-down conflict-preserving serializability as a correctness criterion for multilevel-secure optimistic concurrency control: CSR/RD

It is important to note that conflict-preserving serializability and related theory are artifacts of an era of database development where correctness alone was the overriding concern. With the advent of multilevel-secure databases, there is clearly a need to reexamine such theories. Any correctness criterion to govern transaction processing in the multilevel security context has to incorporate both secureness and correctness in a unified manner. This paper makes original contributions in two different but closely related areas to the optimistic concurrency control in multilevel-secure, single-version databases. First, read-down conflict-preserving serializability (CSR/RD) captures multilevel-secure database consistency requirements and secure transaction correctness properties via a single notion. Second, it presents a multilevel-secure optimistic concurrency control (MLS/OCC) scheme that has several desirable properties: If lower-level transactions were somehow allowed to continue with their executions in spite of the conflict with high-level transactions, covert timing-channel freeness would be satisfied. This sort of optimistic approach for conflict insensitiveness and the properties of non-blocking and deadlock freedom make the optimistic concurrency control scheme especially attractive to multilevel-secure transaction processing.     

一种基于时间戳的面向对象数据库的并发控制算法

本文提出了一种基于时间戳的面向对象数据库（ＯＯＤＢ，ｏｂｊｅｃｔ－ｏｒｉｅｎｔｅｄｄａｔａｂａｓｅ）的并发控制算法．设计这一算法时，我们首先按照ＯＯＤＢ的数据模型对传统的时间戳算法进行扩展，然后利用抽象数据类型的语义定义了相容性矩阵，对不同级别的并发性冲突操作进行不同的处理，从而达到在系统开销尽可能小的情况下，尽可能大地增加数据库存取操作的并发度的效果．这一算法的优点是：①利用对象版本的时间信息减少了数据项的读写时间戳所需的额外存储空间；②消除了封锁算法带来的封锁及死销预防或死锁检测所需要的系统开销。本文还用模拟的方法给出了新算法和ＯＲＩＯＮ中使用的封锁算法之间的性能比较     

安全数据库系统中的事务

在多级安全数据库系统中经典的BLP模型的“向上写”违反了数据库的完整性,并产生隐通道和带来多实例问题,事务间的提交和回退依赖也会产生隐通道,在对事务安全性分析的基础上提出了安全事务模型和安全事务正确性标准一安全冲突可串行化(SCSR),最后给出了一个避免隐通道的安全并发控制算法．     

Towards a General Concurrency Control Algorithm for Database Systems

The concurrency control problem in database systems has been examined by many people and several concurrency control algorithms have been proposed. The most popular algorithms are two-phase locking and timestamp ordering. This paper shows that two-phase locking and timestamp ordering are special cases of a more general concurrency control algorithm. This general algorithm is described in detail and is proven to work correctly. We show that two-phase locking and timestamp ordering represent the two end points of a series of concurrency control algorithms. Each of them is a special case of the general algorithm proposed in this paper. Moreover, each of these special cases can be selected in advance, and can even be changed dynamically during execution.     

一种面向混合实时事务调度的并发控制协议

首先给出了一个两层结构的混合实时数据库系统模型,其中支持采用非定期任务调度算法来改进系统的性能．进一步,针对这种模型下混合事务的数据一致性问题,提出了一种新的并发控制协议——MCC-DATI．该协议采用动态优先级驱动的调度算法,通过限制非定期的软实时事务对硬实时事务的阻塞时间,保证硬实时事务的可调度性;同时,采用非定期任务调度算法以及基于时间戳间隔的动态串行化顺序调整机制来减少软实时事务的截止期错失率．仿真实验表明,相对于先前的混合事务的并发控制协议,该协议在不同的系统负载与截止期约束下都能够改进系统的性能。     

内存数据库并发控制算法的实验研究

并发控制算法是数据库系统保证事务执行正确且高效的重要手段,一直是数据库工业界和学术界研究的核心问题之一.将并发控制算法的基本思想归纳为“先定序后检验”,并基于该思想对现有各类并发控制算法进行了重新描述和分类总结.基于在开源内存型分布式事务测试床3TS上的实际对比实验,系统性地探究了各类算法的优缺点和适用场景,为面向内存数据库的并发控制算法的后续研究提供参考.     

The group paradigm for concurrency control protocols

The authors propose a paradigm for developing, describing, and proving the correctness of concurrency control protocols for replicated databases in the presence of failures or communication restrictions. The approach used is to hierarchically divide the problem of achieving one-copy serializability by introducing the notion of a `group' that is a higher level of abstraction than transactions. Instead of dealing with the overall problem, the paradigm breaks it into two simpler ones: (1) a local policy for each group that ensures a total order of all transactions in that group; and (2) a global policy that ensures a correct serialization of all groups. The paradigm is used to demonstrate the similarities between several concurrency control protocols by comparing the way they achieve correctness     

Experimental Study of Concurrency Control Algorithms in Main-memory Database Systems

The concurrency control algorithm is a key approach for a database system to guarantee the correctness and efficiency of the transaction execution. Thus, substantial effort has been devoted to proposing new concurrency control algorithms in both the database industry and academia. In this paper, we take the lead in summarizing the fundamental ideas of concurrency control algorithms as ``ordering-and-verifying''. We then redescribe and sort out the existing concurrency control algorithms following the ordering-and-verifying paradigm. On the basis of extensive comparative experiments on an open-source main-memory distributed transaction testbed called 3TS, we systematically investigate the advantages and disadvantages of the mainstream concurrency control algorithms and finally summarize the preferable application scenario for each algorithm to provide valuable references for follow-up research on concurrency control algorithms used in main-memory databases.     

Multidimensional Timestamp Protocols for Concurrency Control

We propose multidimensional timestamp protocols for concurrency control in database systems where each transaction is assigned a timestamp vector containing multiple elements. The timestamp vectors for two transactions can be equal if timestamp elements are assigned the same values. The serializability order among the transactions is determined by a topological sort of the corresponding timestamp vectors. The timestamp in our protocols is assigned dynamically and is not just based on the starting/finishing time as in conservative and optimistic timestamp methods. The concurrency control can be enforced based on more precise dependency information derived dynamically from the operations of the transactions. Several classes of logs have been identified based on the degree of concurrency or the number of logs accepted by a concurrency controller. The class recognized by our protocols is within D-serializable (DSR), and is different from all previously known classes such as two phase locking (2PL), strictly serializable (SSR), timestamp ordering (TO), which have been defined in literature. The protocols have been analyzed to study the complexity of recognition of logs. We briefly discuss the implementation of the concurrency control algorithm for the new class, and give a timestamp vector processing mechanism. The extension of the protocols for nested transaction and distributed database models has also been included.     

基于多版本的安全实时并发控制协议

安全实时数据库必须同时满足安全性和实时性,然而这两者有时可能相互冲突.为了解决这种冲突,提出了基于多版本的安全实时并发控制协议.协议为每个数据对象提供两个版本:工作版本和只读版本,根据事务和数据对象的安全级为事务提供不同的数据版本,有效地解决了实时性与安全性之间的冲突,最后给出了协议的正确性证明.     

一种基于时标的网格事务并发控制方法

定义了一个网格事务模型，提出了支持该网格事务模型的、基于时标的并发控制协议，证明了协议的正确性。该协议扩充了事务类型，减小了事务的冲突范围，从而避免了大量不必要的事务重启，提高了事务的并发度。性能实验分析表明，该协议是可行且有效的。     

Globally consistent event ordering in one-directional distributedenvironments

We consider communication structures for event ordering algorithms in distributed environments where information flows only in one direction. Example applications are multilevel security and hierarchically decomposed databases. Although the most general one directional communication structure is a partial order, partial orders do not enjoy the property of being consistently ordered, a formalization of the notion that local ordering decisions are ensured to be globally consistent. Our main result is that the crown free property is necessary and sufficient for a communication structure to be consistently ordered. We discuss the computational complexity of detecting crowns and sketch typical applications     

Partitioned data objects in distributed databases

In many distributed databases locality of reference is crucial to achieve acceptable performance. However, the purpose of data distribution is to spread the data among several remote sites. One way to solve this contradiction is to use partitioned data techniques. Instead of accessing the entire data, a site works on a fraction that is made locally available, thereby increasing the site's autonomy. We present a theory of partitioned data that formalizes the concept and establishes the basis to develop a correctness criterion and a concurrency control protocol for partitioned databases. Set-serializability is proposed as a correctness criterion and we suggest an implementation that integrates partitioned and non-partitioned data. To complete this study, the policies required in a real implementation are also analyzed. Recommended by: Hector Garcia-Molina     

A mechanically verified incremental garbage collector

As an application of a system designed for concurrent program verification, we describe a formalisation and mechanical proof of the correctness of Ben-Ari's incremental garbage collection algorithm. The proof system is based on the Manna-Pnueli model of concurrency and is implemented as an extension of the Boyer-Moore prover. The correctness of the garbage collector is represented by two theorems, stating a) that nothing except garbage is ever collected (safety), and b) that all garbage is eventually collected (liveness). We compare our mechanised treatment with several published proofs of the same results.     

面向安全关键嵌入式系统的时钟同步设计

为了满足安全关键性实时嵌入式系统对实时行为正确性和确定性的要求,本文应用ETSEC网络控制器的硬件时间戳特性, ReWorks嵌入式实时操作系统的实时特性,结合IEEE 1588精密度时钟同步协议,设计并实现了一个面向安全关键性领域的时钟同步系统原型.其同步精度达到100纳秒以内,并通过软件插桩测试和验证了该时钟同步系统的正确性和精度.     

时标排序并发控制算法在移动分布式实时数据库中的应用分析

随着移动计算技术的发展,人们要求能够随时随地实时存取数据库的数据,这就导致了移动分布式实时数据库(MDRTDBS)的实现.移动实时应用的根本特性是其事务具有移动性和实时特性,数据具有定时特性.这对移动分布式实时数据库并发控制协议提出了新的挑战,目前这方面的研究还很少.对实时数据库的时标排序并发控制协议进行了分析,针对移动实时应用的特点对将它们应用到MDRTDBS的优缺点进行了阐述,提出了改进的方法.最后提出了新的适用于MDRTDBS的时标排序协议,并指出了未来的研究方向.     

移动数据库事务管理技术研究

以传统的事务并发算法为基础,分析移动数据库与分布式数据库的共性和差异性,探讨基于时间戳代理的并发控制改进模型。该模型经过从支持全局变量到支持不完整事务的演化过程,能够基本满足移动计算环境下各种应用场景的需求。     

远程音、视频重演中的同步技术

音、视频信息的同步重演足多媒体应用系统实现的关键技术和难点之一，该文探讨了音、视频同步的机制，依据基于参考点的同步思想创建了以音频为时间主导的同步模型，提出了在解码端运用的音、视频同步算法，并给出了同步的判断准则和实际处理的过程。算法已应用于基于MPEG-4编码标准的分布式多媒体监控系统中，实验表明，它能准确、可靠地实现音、视频连续同步重演，并具有较好的通用性。     

A shared-variable concurrency analysis of multi-threaded object-oriented programs

In this paper a proof outline logic is introduced for the partial correctness of multi-threaded object-oriented programs like in Java. The main contribution is a generalization of the Owicki& Gries proof method for shared-variable concurrency to dynamic thread creation. This paper also provides a formal justification of this generalization in terms of soundness and completeness proofs.