Two-phase commit protocol | EPFL Graph Search

In transaction processing, databases, and computer networking, the two-phase commit protocol (2PC, tupac) is a type of atomic commitment protocol (ACP). It is a distributed algorithm that coordinates all the processes that participate in a distributed atomic transaction on whether to commit or abort (roll back) the transaction. This protocol (a specialised type of consensus protocol) achieves its goal even in many cases of temporary system failure (involving either process, network node, communication, etc. failures), and is thus widely used. However, it is not resilient to all possible failure configurations, and in rare cases, manual intervention is needed to remedy an outcome. To accommodate recovery from failure (automatic in most cases) the protocol's participants use logging of the protocol's states. Log records, which are typically slow to generate but survive failures, are used by the protocol's recovery procedures. Many protocol variants exist that primarily differ in loggi

The Complexity of Reliable and Secure Distributed Transactions

Junxiong Wang

The use of transactions in distributed systems dates back to the 70's. The last decade has also seen the proliferation of transactional systems. In the existing transactional systems, many protocols employ a centralized approach in executing a distributed transaction where one single process coordinates the participants of a transaction. The centralized approach is usually straightforward and efficient in the failure-free setting, yet the coordinator then turns to be a single point of failure, undermining reliability/security in the failure-prone setting, or even be a performance bottleneck in practice. In this dissertation, we explore the complexity of decentralized solutions for reliable and secure distributed transactions, which do not use a distinguished coordinator or use the coordinator as little as possible. We show that for some problems in reliable distributed transactions, there are decentralized solutions that perform as efficiently as the classical centralized one, while for some others, we determine the complexity limitations by proving lower and upper bounds to have a better understanding of the state-of-the-art solutions. We first study the complexity on two aspects of reliable transactions: atomicity and consistency. More specifically, we do a systematic study on the time and message complexity of non-blocking atomic commit of a distributed transaction, and investigate intrinsic limitations of causally consistent transactions. Our study of distributed transaction commit focuses on the complexity of the most frequent executions in practice, i.e., failure-free, and willing to commit. Through our systematic study, we close many open questions like the complexity of synchronous non-blocking atomic commit. We also present an effective protocol which solves what we call indulgent atomic commit that tolerates practical distributed database systems which are synchronous "most of the time", and can perform as efficiently as the two-phase commit protocol widely used in distributed database systems. Our investigation of causal transactions focuses on the limitations of read-only transactions, which are considered the most frequent in practice. We consider "fast" read-only transactions where operations are executed within one round-trip message exchange between a client seeking an object and the server storing it (in which no process can be a coordinator). We show two impossibility results regarding "fast" read-only transactions. By our impossibility results, when read-only transactions are "fast", they have to be "visible", i.e., they induce inherent updates on the servers. We also present a "fast" read-only transaction protocol that is "visible" as an upper bound on the complexity of inherent updates. We then study the complexity of secure transactions in the model of secure multiparty computation: even in the face of malicious parties, no party obtains the computation result unless all other parties obtain the same result. As it is impossible to achieve without any trusted party, we focus on optimism where if all parties are honest, they can obtain the computation result without resorting to a trusted third party, and the complexity of every optimistic execution where all parties are honest. We prove a tight lower bound on the message complexity by relating the number of messages to the length of the permutation sequence in combinatorics, a necessary pattern for messages in every optimistic execution.

EPFL2018

A Petri Net Model for FDDI

Nicoleta Sergent

Fiber Distributed Data Interface (FDDI) is a high speed local area network operating at 100Mbps using a fiber optic ring transmission medium. The purpose of this paper is to build a Petri net model for the FDDI media access control (MAC) protocol. This model is hierarchically integrated into the Petri net model of the two-phase commitment (2PC) algorithm. By simulating the composed Petri net model we evaluate the latency of the 2PC algorithm. The FDDI model is validated by comparing the data obtained from performance measures and the numerical results derived from simulation.

1997

Evaluating Latency of Distributed Algorithms Using Petri Nets

Nicoleta Sergent

Evaluating Latency of Distributed Algorithms Using Petri Nets N. Sergent The time it takes to a distributed algorithm to finish (the distributed algorithm latency) cannot be directly measured in asynchronous systems if the algorithm starts and ends on different processors, since the system has no global time. A simple method to evaluate this latency is to build and simulate a unified model which includes the network and the distributed algorithm sub-models. In this paper we introduce a network model for UDP (User Datagram Protocol) which allows to establish a relationship between the number of messages exchanged in a distributed algorithm and the communication delays. As an application, we consider the two-phase commitment algorithm. Numerical results derived from simulating the model are compared with data obtained from performance measures.

1997

The Complexity of Reliable and Secure Distributed Transactions

Junxiong Wang

EPFL2018