I. Stanoi, Divyakant Agrawal, Amr El Abbadi · 1998
In this paper, we explore the use of the simple variants of broadcast protocols for managing replicated databases. In particular, we start with the simplest broadcast primitive, the reliable broadcast protocol, and show how it can be used to ensure correct transaction execution. The protocol is simple, and has several advantages, including prevention of deadlocks. However, it requires a two-phase commitment protocol for ensuring correctness. We then develop a second protocol that uses causal broadcast and avoids the overhead of two-phase commit by exploiting the causal delivery properties of the broadcast primitives to implicitly collect the relevant information used in two-phase commit. Finally, we present a protocol that employs atomic broadcast and completely eliminates the need for acknowledgements during transaction commitment. 1 Introduction Recently there has been increasing interest in the development of broadcast protocols for disseminating information in distributed systems ...
Cited by 1
Sahil Mahajan, Rahul Singhal · 2009
This paper describes Azvasa protocol: a Byzantine fault tolerant distributed commit protocol with proactive recovery for transactions running over untrusted networks. Traditional Three phase agreement protocol among coordinator replicas to tolerate Byzantine faults has been used in distributed commit. We propose two phase agreement protocol to tolerate Byzantine faults which not only reduces total time to reach agreement but also message overhead. Proactive recovery is an essential method for ensuring long term reliability of fault tolerant systems that are under continuous threats from malicious adversaries. The primary benefit of our proactive recovery scheme is faster standby node registration, service migration and reduced overhead in new membership notification to participants.
Cited by 1
Fan Zhi-hua, Jin Xiong, Jie Ma · 2004
Distributed metadata servers are required for cluster file system's scalability. However, how to distribute the file system metadata among multiple metadata servers and how to make the file system reliable in case of server failures are two difficult problem. We present a journal-based failure-recovery mechanism for distributed metadata servers in the dawning cluster file system-DCFS2. The DCFS2 metadata protocol exploits a modified two-phase commit protocol which ensures consistent metadata updates on multiple metadata servers even in case of one server's failure. We focus on the logging policy and concurrent control policy for metadata updates, and the failure recovery policy. The DCFS2 metadata protocol is compared with the two phase commit protocol and some virtues are shown. Some results of performance experiments on our system are also presented.
Cited by 5
Atif, M Muhammad · TU/e Research Portal (Eindhoven University of Technology) · 2009
Abstract—This paper introduces a formal model of the dis-tributed commit protocols in the process algebra mCRL2 and also their general requirements in the modal µ-calculus. We show how to make straightforward models of protocols and by doing so, how it becomes easy to identify problems. We apply this to the well-known Two-Phase Commit Protocol (2PC) and prove it problematic for single site failure. We also apply our method to its “amended ” variant, the Three-Phase Commit Protocol (3PC) and prove it to be erroneous for simultaneous site failures. We present 2PC and 3PC in different communication settings and verify them with respect to their requirements. I.
Cited by 0
Wenbing Zhao, Firat Kart, L. E. Moser et al. · 2009
Web Services can be used to automate business activities that span multiple enterprises over the Internet. Such business activities require a coordination protocol to reach consistent results among the participants in the business activity. In the current state-of-the-art, either classical distributed transactions or extended transactions with compensating transactions are used. However, classical distributed transactions lock data in the databases of different enterprises for unacceptable durations or involve repeated retries, and compensating transactions can lead to inconsistencies in the databases of the different enterprises. In this paper, we describe a novel Reservation Protocol that can be used to coordinate the tasks of a business activity. Instead of resorting to compensating transactions, the Reservation Protocol employs an explicit reservation phase and an explicit confirmation/cancellation phase. We show how our Reservation Protocol maps to the Web Services Coordination specification and describe our implementation of the Reservation Protocol. We compare the performance of the Reservation Protocol with that of the Two Phase Commit Protocol and Optimistic Two Phase Commit Protocol. We also compare the probability of inconsistency of the Reservation Protocol with that of Compensating Transactions. KEY WORDS:
Cited by 0
Wenbing Zhao, Firat Kart, L.E. Moser et al. · International Journal of Web Services Research · 2008
Web services can be used to automate business activities that span multiple enterprises over the Internet. Such business activities require a coordination protocol to reach consistent results among the participants in the business activity. In the current state of the art, either classical distributed transactions or extended transactions with compensating transactions are used. However, classical distributed transactions lock data in the databases of different enterprises for unacceptable durations or involve repeated retries, and compensating transactions can lead to inconsistencies in the databases of the different enterprises. In this article, we describe a novel reservation protocol that can be used to coordinate the tasks of a business activity. Instead of resorting to compensating transactions, the reservation protocol employs an explicit reservation phase and an explicit confirmation and cancellation phase. We show how our reservation protocol maps to the Web services coordination specification, and describe our implementation of the reservation protocol. We compare the performance of the reservation protocol with that of the two-phase commit protocol and optimistic two-phase commit protocol. We also compare the probability of inconsistency for the reservation protocol with that for compensating transactions.
Cited by 7
M. Shahza, Dr. C. Bamford, Prof Taleb-bendiab et al. · 2015
Abstract-Commit protocols are used to ensure transaction atomicity. The two-phase commit (2PC) is a standard commit protocol used in many commercial database systems. Attempts to reduce the cost of commitment have resulted in many variants of 2PC. These are all blocking protocols. But in other protocols when the blocking issue is addressed the result is an increase in the transaction commitment cost. In this paper we propose a design for a non-blocking commit protocol which can survive coordinator failure, yet which does not increase the execution costs in comparison with 2PC, even reducing them in highly reliable environments where failure is not the issue. I.
Cited by 0
B.-C. Jenq, W.H. Kohler, Don Towsley · IEEE Transactions on Software Engineering · 1988
A queuing network model for analyzing the performance of a distributed database testbed system with a transaction workload is developed. The model includes the effects of the concurrency control protocol (two-phase locking with distributed deadlock detection), the transaction recovery protocol (write-ahead logging of before-images), and the commit protocol (centralized two-phase commit) used in the testbed system. The queuing model differs from previous analytical models in three major aspects. First, it is a model for a distributed transaction processing system. Second, it is more general and integrated than previous analytical models. Finally, it reflects a functioning distributed database testbed system and is validated against performance measurements.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
Cited by 24
Tianyang Li, Jin Wu, Songyan Ji et al. · 2025
HotStuff stands out as the first Byzantine Fault Tolerant (BFT) state machine replication protocol to achieve linear communication complexity while maintaining optimistic responsiveness and fairness. However, it is required at least three phases to commit a block, which leads to high latency. Recent studies have focused on developing two-phase variants of HotStuff to reduce its block commitment latency. Nonetheless, two-phase HotStuff suffers from the liveness issue, forcing these protocols to sacrifice one of the three fundamental properties of HotStuff when addressing this problem, thereby facing a trade-off among these properties. In this paper, we introduce a novel protocol, Harmonia, which, to the best of our knowledge, is the first BFT protocol to simultaneously achieve linear communication complexity, optimistic responsiveness, fairness, and the minimum commit latency of two phases. Harmonia overcomes the liveness issue of two-phase HotStuff through its specialized block unlocking mechanism while preserving all the original properties of HotStuff. Experimental results show that Harmonia consistently outperforms HotStuff across various metrics.
Cited by 0
Chris Jensen, Heidi Howard, Antonios Katsarakis et al. · 2024
Distributed transactional datastores are pivotal in supporting the needs of modern applications and services. Datastores rely on distributed transactional protocols to tolerate faults while also aiming for strong consistency and high performance. State-of-the-art transactional protocols, such as FaRM, provide a lock-free execution phase, thus improving performance and simplifying recovery. However, these protocols often come with lengthy and complicated commit phases, requiring multiple round-trips to commit a transaction (or additional replicas). This completely contrasts with the simplicity and efficiency of the traditional two-phase commit (2PC) protocol, which can commit a transaction after a single round-trip, albeit lacking fault tolerance.
Cited by 1Open access
Butler Lampson And, Butler Lampson, David Lomet · 1993
Two phase commit (2PC) is used to coordinate the commitment of transactions in distributed systems. The standard 2PC optimization is the presumed abort variant, which uses fewer messages when transactions are aborted and allows the coordinator to forget about aborted transactions. The presumed commit variant of 2PC uses even fewer messages, but its coordinator must do additional logging. We describe a new form of presumed commit that reduces the number of log writes while preserving the reduction in messages, bringing both these costs below those of presumed abort. The penalty for this is the need to retain a small amount of crash related information forever. 1 Introduction 1.1 Coordinating Distributed Commit Distributed systems rely on the two phase commit (2PC) protocol to coordinate the commitment of transactions [1, 4]. 2PC guarantees the atomicity of distributed transactions, that is, that all cohorts of a transaction either commit or abort the transaction. The cost of 2PC is an...
Cited by 0
Yingyao Rong, Weigang Wu, Zhiguang Chen · 2019
Byzantine Fault-Tolerant (BFT) state machine replication protocol is an important building block for highly available distributed computing. This paper presents COMBFT, a BFT protocol that achieves both efficiency and robustness simultaneously. The major novelty of COMBFT lies in Conflicting-Order-Match (COM), a new request ordering mechanism that uses a new way to select the available sequence number for requests, and detects the possible malicious primary early. COM assigns sequence number based on request interference, and requires both primary and backup nodes to conduct request ordering, which can greatly reduce the impact of malicious primary and clients. When the backup suspects the primary may be malicious, it triggers an efficient commit protocol with two phases (i.e., suspect phase and commit phase) to further confirm whether the primary is malicious, and commit the request. The performance of COMBFT is evaluated via simulations and the results illustrate the outstanding performance of COMBFT in terms of throughput, latency and fault scalability.
Cited by 1
Jiazhen, Lu · UCL Discovery (University College London) · 1990
This thesis studies the methods of evaluating the performance of centralized and distributed database systems by using analytic modeling, simulation and system measurement. Numerous concurrency control and locking mechanisms for distributed database systems have been proposed and implemented in recent years, but relatively little work has been done to evaluate and compare these mechanisms. It is the purpose of this thesis to address these problems. The analytic modeling intends to provide a consistent and novel modeling method to evaluate the performance of locking algorithms and concurrency control protocols in both centralized and distributed databases. In particular, it aims to solve the problems of waiting in database locking, and blocking in concurrency control protocol which have not been solved analytically before. These models, which are based on queueing network and stochastic analysis, are able to achieve a high degree of accuracy in comparison with published simulation results. In addition, detailed simulation models are built to validate the analytic models and to study various concurrency control protocols and distributed locking algorithms; these simulation models are able to incorporate system details at very low levels such as the communication protocols, elementary file server operations, and the lock management mechanisms. In order to further validate the findings through measurements, an actual' distributed database management system is specifically implemented which adopts the two phase commit protocol, majority consensus update algorithm, multicast communication primitives, dynamic server configuration, and failure recovery. Various performance measurements are obtained from the system such as the service time characteristics of communication and file servers, system utilization and throughput, response time, queue length and lock conflict rates. The performance results reveal some interesting phenomena such as systems with coarse granularity outperform those with fine granularity when lock overhead is not negligible, and that the effect of the database granularity is small in comparison with the effect of the number of replicated copies. Results also suggest that centralized two phase commit protocol outperforms other types of two phase commit protocol, such as basic, majority consensus and primary copy two phase commit protocol under some circumstances.
Cited by 0
Dan Duchamp · Columbia Academic Commons (Columbia University) · 1989
The basic two-phase distributed commitment protocol as described in [3, pp. 381-382] can be optimized so that a subordinate update site drops its locks more promptly and makes one fewer log force per transaction. The optimization applies as well to the variations of two-phase commitment (i.e., hierarchical, presumed commit. and presumed abort) described in the same paper.
Cited by 0Open access
Nitesh Kumar, Ashish Kumar, Soumyajit Giri · 2014
Transaction is a set of/unit of sequential operations, which is used for a purpose of Technological, Organizational, programming languages, and operating systems. It examines the performance of the transaction manager with the help of Remote Procedure Calls (RPC) Applications. Remote Procedure Call is a distributed application for constructing the distributed database system. When it communicates between the sender side (client side) and receiver side (server side). It executes the ensure atomicity protocols. Simple optimization of Two Phase Commit Protocol (2PC) reduces non-blocking commit, logging activity, multi-threading design, and improved throughput, reduce multicasting, and reduces the variance of distributed commit protocol. It is totally based on Three Phase Commit Protocol (3PC) in a communication network infrastructure environment such as (LAN, WAN, MAN, etc.), and the performance of the transaction mechanism such as RPC Techniques depends upon the client and server performance. In this paper, we provide a detail examination of the design and performance of the transaction manager of the RPC Applications and we also compile the code and it's create a file, then after that it will execute the code step by step.
Cited by 8
Yousef Al-Houmaily Panos, Panos K. Chrysanthis, Steven P. Levitan · 2007
This paper presents a new read-only optimization called the unsolicited update--vote that when combined with the presumed commit protocol (PrC), eliminates all the logging activities from PrC for read-only transactions and significantly reduces them for partially read-only ones. 1 INTRODUCTION To ensure consistent termination of distributed transactions despite site and communication failures, all the sites participating in a transaction&apos;s execution engage in an atomic commit protocol (ACP). The two-phase commit (2PC) protocol [1] is the simplest and most used ACP. Since 2PC consumes a substantial amount of a transaction&apos;s execution time due to the cost of its coordination messages and forced log writes to stable storage required for recovery, a number of 2PC variants appear in the literature, most notably, presumed abort (PrA) and presumed commit (PrC) [2]. As opposed to PrA, PrC has been designed to reduce the cost associated with committing transactions rather than aborting ones....
Cited by 0
View
Atomic Commit Problem (ACP) is a single-shot agreement problem similar to consensus, meant to model the properties of transaction commit protocols in fault-prone distributed systems. We argue that ACP is too restrictive to capture the complexities of modern transactional data stores, where commit protocols are integrated with concurrency control, and their executions for different transactions are interdependent. As an alternative, we introduce Transaction Certification Service (TCS), a new formal problem that captures safety guarantees of multi-shot transaction commit protocols with integrated concurrency control. TCS is parameterized by a certification function that can be instantiated to support common isolation levels, such as serializability and snapshot isolation. We then derive a provably correct crash-resilient protocol for implementing TCS through successive refinement. Our protocol achieves a better time complexity than mainstream approaches that layer two-phase commit on top of Paxos-style replication.
Cited by 4
Gregory Chockler, Alexey Gotsman · arXiv (Cornell University) · 2018
Atomic Commit Problem (ACP) is a single-shot agreement problem similar to consensus, meant to model the properties of transaction commit protocols in fault-prone distributed systems. We argue that ACP is too restrictive to capture the complexities of modern transactional data stores, where commit protocols are integrated with concurrency control, and their executions for different transactions are interdependent. As an alternative, we introduce Transaction Certification Service (TCS), a new formal problem that captures safety guarantees of multi-shot transaction commit protocols with integrated concurrency control. TCS is parameterized by a certification function that can be instantiated to support common isolation levels, such as serializability and snapshot isolation. We then derive a provably correct crash-resilient protocol for implementing TCS through successive refinement. Our protocol achieves a better time complexity than mainstream approaches that layer two-phase commit on top of Paxos-style replication.
Cited by 0Open access
Maha Abdallah, Rachid Guerraoui, Philippe Pucheral · 2002
Although widely used in distributed transactional systems, the so-called Two-Phase Commit (2PC) protocol introduces a substantial delay in transaction processing, even in the absence of failures. This has led several researchers to look for alternative commit protocols that minimize the time cost associated with coordination messages and forced log writes in 2PC. In particular, variations of a One-Phase Commit (1PC) protocol have recently been proposed. Although efficient, 1PC is however rarely considered in practice because of the strong assumptions it requires from the distributed transactional system. The aim of the paper is to better identify and understand those assumptions. Through a careful look into the intrinsic characteristics of 1PC, we dissect the assumptions underlying it and we present simple techniques that minimize them. We believe that these techniques constitute a first step towards a serious reconsideration of 1PC in the transactional world.
Cited by 44
Tim Kempster, Colin Stirling, Peter Thanisch · 2007
The Centralised Two Phase Commit Protocol (2PC) is the most widely used protocol in commercial distributed systems. Many variants of this protocol exist which try to reduce both the number of messages required to execution. In addition to this the extent to which the operational phase of a transaction and its commit phase overlap varies in practice. We provide a formal framework in which to describe these variations. We define serializability in this framework and show that it holds for many of the optimisations but not for others. 1 Introduction Skip 2 The Model We model a distributed transaction processing environment where transactions arrive at coordinator sites. In our simplified model a transaction consists of a set of actions that are supervised by a transaction coordinator (TC). The TC interacts with one or more resource managers (RMs) by means of message passing in order to perform these actions. Actions performed on resources may change the state of a resource. We are inter...
Cited by 0