分布式实时事务提交协议

在分布式实时数据库系统中，保证事务原子性的唯一途径是研究和开发出一个实时的原子提交协议．首先详细分析了事务因数据访问冲突而形成的各种依赖关系，在此基础上提出了实时的原子乐观提交协议——2SC协议，该协议减少了事务的等待时间，提高了事务的并发度，且能无缝地和现有的并发控制协议集成在一起，保证事务的可串行化和原子性．通过模拟实验研究表明，采用该协议能够减少超过截止期的事务数目。     

A Commit Strategy for Distributed Real-Time Transaction

Ramamritham gives three common types of constraints for the execution his-tory of concurrent transactions. This paper extends the constraints and gives the fourth type of constraint. Then the weak commit dependency and abort dependency between transactions, be-cause of data access conflicts, axe analyzed. Based on the analysis, an optimistic commit protocol 2LC (two-Level Commit) is proposed, which is specially designed for the distributed real-time do-main. It allows transactions to optimistically access the locked data in a controlled manner, which reduces the data inaccessibility and priority inversion inherent and undesirable in distributed real-time database systems. Furthermore, if the prepared transaction is aborted, the transactions in its weak commit dependency set will execute as normal according to 2LC. Extensive simulation ex-periments have been performed to compare the performance of 2LC with that of the base protocol,the permits reading of modified prepared-data for timeliness (PROMPT) and the deadline-driven conflict resolution (DDCR). The simulation results show that 2LC is effective in reducing the num-ber of missed transaction deadlines. Furthermore, it is easy to be incorporated with the existing concurrency control protocols.     

分布式实时事务提交处理

由于提交处理的复杂性,分布式实时事务很难满足其截止期.提出了一种新的提交协议A2SC(主动的双空间提交),它适合于分布式实时事务提交处理的需要.分析了由于数据冲突访问而形成的各种依赖关系.当处于准备状态的事务和处于提交状态的事务发生数据冲突访问时,A2SC允许处于执行状态的事务在一种控制的方式下乐观地访问锁住的数据.当处于准备状态的事务夭折时,仅仅只有其夭折依赖集中的事务夭折.进一步提出了"没有结果的运行"的观念.当一个事务发现它是没有结果的允许时,它将主动夭折.进行了广泛的模拟实验比较A2SC和其它协议比如基准协议、PROMPT和DDCR的性能.模拟结果表明A2SC在最小化错过截止期的事务数方面较成功,因此A2SC适合于高性能分布式实时事务.     

Coordinator log transaction execution protocol

The coordinator log transaction execution protocol proposed in this paper centralizes logging on a per transaction basis and exploits piggybacking to provide the semantics of a distributed atomic commit at a minimal cost. The protocol eliminates two rounds of messages (one phase) from the presumed commit protocol and dramatically reduces the number of log forces needed for distributed atomic commit. We compare the coordinator log transaction execution protocol to existing protocols, explain when it is desirable, and discuss how it affects the write ahead log protocol and the database crash recovery algorithm. Recommended by: Tamer Ozsu     

Speculative locking protocols to improve performance for distributed database systems

We have proposed speculative locking (SL) protocols to improve the performance of distributed database systems (DDBSs) by trading extra processing resources. In SL, a transaction releases the lock on the data object whenever it produces corresponding after-image during its execution. By accessing both before and after-images, the waiting transaction carries out speculative executions and retains one execution based on the termination (commit or abort) mode of the preceding transactions. By carrying out multiple executions for a transaction, SL increases parallelism without violating serializability criteria. Under the naive version of SL, the number of speculative executions of the transaction explodes with data contention. By exploiting the fact that a submitted transaction is more likely to commit than abort, we propose the SL variants that process transactions efficiently by significantly reducing the number of speculative executions. The simulation results indicate that even with manageable extra resources, these variants significantly improve the performance over two-phase locking in the DDBS environments where transactions spend longer time for processing and transaction-aborts occur frequently.     

A Formal Model of Crash Recovery in a Distributed System

A formal model for atomic commit protocols for a distributed database system is introduced. The model is used to prove existence results about resilient protocols for site failures that do not partition the network and then for partitioned networks. For site failures, a pessimistic recovery technique, called independent recovery, is introduced and the class of failures for which resilient protocols exist is identified. For partitioned networks, two cases are studied: the pessimistic case in which messages are lost, and the optimistic case in which no messages are lost. In all cases, fundamental limitations on the resiliency of protocols are derived.     

A hybrid distributed optimistic concurrency control method for high-performance real-time transaction processing

The conventional lock scheme tends to suffer from a cascade of blockings,while the optimistic concurrency control(OCC) scheme may suffer from wasting resources.To overcome these problems,some researchers have proposed a combination of OCC and lock in transaction processing.Using this method,Thomasian proposed the hybrid method for conventional distributed transaction processing,and Lam proposed the DOCC-DA protocol for distributed realtime databased system based on forward validation.This paper proposes a new protocol,called Hybrid Distributed Optimistic Concurrency COntrol Embedded in two-Phase Commit,which is based on back validation.The new protocol makes use of access invariance and runtime inforbased on back validation.The new protocol makes use of access invariance and runtime infor mation which can guarantee a rerun transaction to meet its deadline and abort the fruitless run transactions as early as possible.A series of simulation experiments have been done to investigate the performance of the new protocol.The results show that its performance is consitently better than that of other protocols.     

An Information-Based Model for Failure-Handling in Distributed Database Systems

We consider the failure atomicity problem of distributed transactions in conjunction with the maximization of database availability. We propose a new information-based model for the distributed transaction-execution, which explicitly expresses the information at each stage during a protocol. In addition to rederiving certain existing results, we prove a fundamental relation among the site failures and the network partitioning. We propose a realistic model for site failures under which we show that the costs of commit and termination protocols can be greatly reduced. Finally, we explore the possible recovery strategies for a failed site and show how they are improved under our site failure model.     

The PROMPT real-time commit protocol

We investigate the performance implications of providing transaction atomicity for firm-deadline real-time applications, operating on distributed data. Using a detailed simulation model, the real-time performance of a representative set of classical transaction commit protocols is evaluated. The experimental results show that data distribution has a significant influence on real-time performance and that the choice of commit protocol clearly affects the magnitude of this influence. We also propose and evaluate a new commit protocol, PROMPT (Permits Reading Of Modified Prepared-data for Timeliness), that is specifically designed for the real-time domain. PROMPT allows transactions to “optimistically” borrow, in a controlled manner, the updated data of transactions currently in their commit phase. This controlled borrowing reduces the data inaccessibility and the priority inversion that is inherent in distributed real-time commit processing. A simulation-based evaluation shows PROMPT to be highly successful, as compared to the classical commit protocols, in minimizing the number of missed transaction deadlines. In fact, its performance is close to the best on-line performance that could be achieved using the optimistic lending approach. Further, it is easy to implement and incorporate in current database system software. Finally, PROMPT is compared against an alternative priority inheritance-based approach to addressing priority inversion during commit processing. The results indicate that priority inheritance does not provide tangible performance benefits     

Reducing the blocking in two-phase commit with backup sites

The blocking phenomena in two-phase commit (2PC) reduces the availability of the system as the blocked transactions keep all the resources until the recovery of the coordinator. The three-phase commit (3PC) protocol involves an extra round of message transmission to resolve the blocking problem. In this paper, we propose a backup commit (BC) protocol to reduce the blocking problem by attaching multiple backup sites to the coordinator site. In BC, after receiving responses from the participants, the coordinator quickly communicates the final decision to the backup sites, before it sends the final decision to the participants. When blocking occurs, the participant sites can terminate the transaction by consulting a backup site of the coordinator. The BC protocol resolves the blocking in most of the coordinator site failures without involving an expensive communication cycle as in 3PC. The simulation experiments indicate that the throughput performance of BC is close to 2PC.     

基于环境一致性的分布式并行数据更新协议

为了保证服务器节点完全对等的分布式并行数据库系统更新结果一致性,提出基于数据环境一致性的分布式并行更新协议DEC-DP2PC(Distributed and Parallel 2PC Based on Data-Environment-Consistency),对经典2PC(two phase commit)在执行条件、表决内容和次数、全局提交和撤销定义等方面进行了针对性改进。性能分析和测试表明,DEC-DP2PC可有效过滤数据副本分布和版本号等数据环境信息不一致情况下事务的执行,减少全局数据环境一致性维护开销和降低系统平均响应时间。     

The Database State Machine Approach

Database replication protocols have historically been built on top of distributed database systems, and have consequently been designed and implemented using distributed transactional mechanisms, such as atomic commitment. We present the Database State Machine approach, a new way to deal with database replication in a cluster of servers. This approach relies on a powerful atomic broadcast primitive to propagate transactions between database servers, and alleviates the need for atomic commitment. Transaction commit is based on a certification test, and abort rate is reduced by the reordering certification test. The approach is evaluated using a detailed simulation model that shows the scalability of the system and the benefits of the reordering certification test.     

Distributed real time database systems: background and literature review

Today’s real-time systems (RTS) are characterized by managing large volumes of dispersed data making real-time distributed data processing a reality. Large business houses need to do distributed processing for many reasons, and they often must do it in order to stay competitive. So, efficient database management algorithms and protocols for accessing and manipulating data are required to satisfy timing constraints of supported applications. Therefore, new research in distributed real-time database systems (DRTDBS) is needed to investigate possible ways of applying database systems technology to real-time systems. This paper first discusses the performance issues that are important to DRTDBS, and then surveys the research that has been done so far on the issues like priority assignment policy, commit protocols and optimizing the use of memory in non-replicated/replicated environment pertaining to distributed real time transaction processing. In fact, this study provides a foundation for addressing performance issues important for the management of very large real time data and pointer to other publications in journals and conference proceedings for further investigation of unanswered research questions.     

A cross-layer atomic commit protocol implementation for transaction processing in mobile ad-hoc networks

Transaction processing leads to new challenges in mobile ad-hoc networks, which, in comparison to fixed-wired networks, suffer from problems like node disconnection, message loss, and frequently appearing network partitioning. As the atomic commit protocol is that part of transaction processing in which failures can lead to the most serious data blocking, we have developed a robust and failure-tolerant distributed cross-layer atomic commit protocol called CLCP that uses multiple coordinators. In order to reduce the number of both, failures and messages, our protocol makes use of acknowledgement messages for piggybacking information. We have evaluated our protocol in mobile ad-hoc networks by using several mobility models (i.e. Random Waypoint, Manhattan, and Attraction Point), and compared CLCP with other atomic commit protocols, i.e. 2PC and Paxos Commit, each implemented in 3 versions, i.e. without sending message acknowledgements, with a Relay Routing technique, and with Nearest Forward Progress Routing. Special to our simulation environment is the use of the quasi-unit-disc model, which assumes a non-binary message reception probability that captures real-world behavior much better than the classical unit-disc-model, often used in theory. Using the quasi-unit-disc model, our evaluation shows the following results. CLCP and “2PC without acknowledgement messages” have a significantly lower energy consumption than the other protocols, and CLCP is able to commit significantly more distributed transactions than all the other atomic commit protocols for each of the mobility models.     

An extended transaction to maintain consistency and recovery in multidatabase systems

A complete practical solution to transaction management preserving multidatabase consistency in the presence of multidatabase updates and failures is presented. The approach developed does not require support for the two-phase commit (2PC) protocol in the participating local database management systems (LDBMSs). Furthermore, it does not violate local autonomy; the source code of the LDBMSs is not modified in any way and the multidatabase system (MDBS) does not access or modify any control information of the LDBMS. The principles of the 2PC protocol in the process of global transaction commitment are adopted. The presented method does not rely on any specific concurrency control mechanism for LDBMSs. Consideration is given to global transaction failures due to subtransaction aborts by the LDBMSs and local site crashes. The recovery process is based on undo operations. While a global transaction is in progress, the tables accessed by subtransactions of this transaction at each local site are locked using specially initiated table locks. These locks are stored and maintained in the local database itself as control tables. The approach taken is easy to implement, and its limitations are discussed.     

分布式短事务系统中提交协议的研究

分布式短事务系统具有事务简短、请求频繁的特点。现有的分布式提交协议多面向复杂的长事务应用场景,难以满足短事务处理的需求。针对分布式短事务系统的特点,提出一种新型的分布式事务提交方法。该方法在事务参与者之间建立互用日志,并通过询问协议进行交互,获得事务进展情况,从而减少了强制写日志次数和通信次数,优化了故障处理过程。与其他分布式提交协议和系统比较,本协议可以有效地提高事务效率,并具有更高的日志可用性。     

Commit protocols for externalized-commit heterogeneous database systems

In designing a heterogeneous database systems, one of the main technical challenges is developing techniques for ensuring global commit. That is, guaranteeing that a transaction spanning multiple individual database management systems (DBMSs) either commits at all the participating DBMSs or at none of them. Previous work in this area typically assumes that the participating DBMSs do not provide a mechanism for interacting with their commit facilities. While this is true in many cases, in practice there are systems which support a programmatic interface to their commit protocols. We refer to database systems offering such facilities asexternalized commit DBMSs.The focus of this paper is on commit protocols for these systems. We propose two new commit protocols for externalized commit DBMSs. The first may be used to obtain global commit in heterogeneous database systems composed of DBMSs with different 2-phase commit protocols (e.g., centralized and linear). The second protocol is more general, and ensures global commit even if the participating DBMSs employ 3-phase commit protocols. The more general protocol also preserves database autonomy, since it does not block a DBMS upon failure of another system. We describe both protocols in detail and prove their correctness. Recommended by: M. RusinkiewiczThis work was partially supported by an IBM Research Initiation Grant.     

基于模型检测的不可靠环境下电子商务协议分析

随着网络的大规模应用,电子商务协议的运行环境越来越不可靠。本文用模型检测的方法分析了不可靠环境下电子商务协议的安全性质。结果表明：安全的电子商务协议在不 可靠环境下运行时有可能不再保持安全性质。当安全性质违背时,借助由自动验证工具UPPAAL生成的消息序列查找原因并对协议进行修改。经验证,修改后的协议在不可靠的环
境下保持安全性质。     

多数据库事务处理模型中局部代理的设计与实现

在多数据库事务处理模型中，局部代理提供了全局事务管理层与局部数据库系统的接口，它使多数据库系统能够对分布在不同站点的局部数据库进行透明访问。文中提出了基于两阶段代理（２ＰＣＡ）的局部代理模型，它集成了支持两阶段提交或单阶段提并的数据库系统、以及并不支持事务提交协议的文件系统。文中还介绍了采用专用接口和ＯＤＢＣ两种实现局部代理的方法。文中着重介绍了使用ＯＤＢＣ方法的具体实现，并对两种方法实现的局部代