1,720,981 research outputs found
Rigorous Design of Distributed Transactions
No full textDatabase replication is traditionally envisaged as a way of increasing fault-tolerance and availability. It is advantageous to replicate the data when transaction workload is predominantly read-only. However, updating replicated data within a transactional framework is a complex affair due to failures and race conditions among conflicting transactions. This thesis investigates various mechanisms for the management of replicas in a large distributed system, formalizing and reasoning about the behavior of such systems using Event-B. We begin by studying current approaches for the management of replicated data and explore the use of broadcast primitives for processing transactions. Subsequently, we outline how a refinement based approach can be used for the development of a reliable replicated database system that ensures atomic commitment of distributed transactions using ordered broadcasts. Event-B is a formal technique that consists of describing rigorously the problem in an abstract model, introducing solutions or design details in refinement steps to obtain more concrete specifications, and verifying that the proposed solutions are correct. This technique requires the discharge of proof obligations for consistency checking and refinement checking. The B tools provide significant automated proof support for generation of the proof obligations and discharging them. The majority of the proof obligations are proved by the automatic prover of the tools. However, some complex proof obligations require interaction with the interactive prover. These proof obligations also help discover new system invariants. The proof obligations and the invariants help us to understand the complexity of the problem and the correctness of the solutions. They also provide a clear insight into the system and enhance our understanding of why a design decision should work. The objective of the research is to demonstrate a technique for the incremental construction of formal models of distributed systems and reasoning about them, to develop the technique for the discovery of gluing invariants due to prover failure to automatically discharge a proof obligation and to develop guidelines for verification of distributed algorithms using the technique of abstraction and refinement
Formal Development of Fault Tolerant Transactions for a replicated Database using Ordered Broadcasts
No full textData replication across several sites improves fault tolerance as available sites can take over the load of failed sites. Data is usually accessed within a transactional framework. However, updating replicated data within a transactional framework is a complex affair due to failures and conflicting transactions. Group communication primitives have been proposed to support transactions in a asynchronous distributed system. In this paper we outline how a refinement based approach with Event B can be used for the development of a reliable replicated database system that ensure atomic commitment of update transactions using group communication primitives
Rigorous Design of Fault-Tolerant Transactions for Replicated Database Systems using Event B
No full textSystem availability is improved by the replication of data objects in a distributed database system. However, during updates, the complexity of keeping replicas identical arises due to failures of sites and race conditions among conflicting transactions. Fault tolerance and reliability are key issues to be addressed in the design and architecture of these systems. Event B is a formal technique which provides a framework for developing mathematical models of distributed systems by rigorous description of the problem, gradually introducing solutions in refinement steps, and verification of solutions by discharge of proof obligations. In this paper, we present a formal development of a distributed system using Event B that ensures atomic commitment of distributed transactions consisting of communicating transaction components at participating sites. This formal approach carries the development of the system from an initial abstract specification of transactional updates on a one copy database to a detailed design containing replicated databases in refinement. Through refinement we verify that the design of the replicated database confirms to the one copy database abstraction
An incremental development of the Mondex system in Event-B
No full textA development of the Mondex system was undertaken using Event-B and its associated proof tools. An incremental approach was used whereby the refinement between the abstract specification of the system and its detailed design was verified through a series of refinements. The consequence of this incremental approach was that we achieved a very high degree of automatic proof. The essential features of our development are outlined. We also present some modelling and proof guidelines that we found helped us gain a deep understanding of the system and achieve the high degree of automatic proo
Formal Specifications and Verification of Message Ordering Properties in a Broadcasting System using Event B
No full textCausal and total order broadcast has been proposed as a mechanism to provide fault tolerance for constructing reliable distributed systems. The use of formal methods to develop a model of a system, specifying critical properties and the verification of them is a way of obtaining better design of dependable services. Event B is a formal technique which provides a framework for developing mathematical models of distributed systems by rigorous description of the problem, gradually introducing solutions in the refinement steps, and verification of solutions by discharge of proof obligations. In this paper, we present a formal development of a system in Event B where processes communicate by broadcast and the messages are delivered following a causal and a total order. We first present separate models of a broadcast system each for a causal order and a total order. Subsequently, we verify that the models of the system preserves the required ordering properties. Further, we develop a model of a system satisfying both causal and a total order on the messages. Later in the refinement, we outline how these ordering properties can correctly be implemented by the vector clocks. In this approach we discover some interesting invariant properties which describes the relationship of abstract causal and total order with the vector clocks and the sequence numbers
Verification of Liveness Properties in Distributed Systems
No full textThis paper presents liveness properties that need to be preserved by Event-B models of distributed systems. Event-B is a formal technique for development of models of distributed systems related via refinement. In this paper we outline how enabledness preservation and non-divergence are related to the liveness properties of the B models of the distributed systems. We address the liveness issues related to our model of distributed transactions and outline the construction of proof obligations that need to be discharged to ensure liveness
Analysis of cooperation semantics for transaction processing with full and partial aborts in active database
No full textMaintaining legal requirements of digital signature through public key cryptographic system
No full textFormal Development of a Total Order Broadcast for Distributed Transactions using Event-B
No full textAbstract. In a replicated database system, copies of the database are kept across several sites for fault-tolerance and availability. Data access in such systems is usually done within a transactional framework. A read-only transaction accesses data locally and an update transaction modifies the database at all sites. Total order broadcast primitives have been proposed to support transactions and allow fault-tolerant cooperation between the sites in a distributed system. In this paper, we identify and analyze the problem of formation of deadlocks among conflicting update transactions due to race conditions and outline how a system of total order broadcast prevents deadlocks and transaction failures. Later we outline how a refinement based approach with Event-B can be used for formal development of the models of total order broadcast. In this approach we begin with the abstract model of a total order broadcast and verify that the required ordering properties are preserved by the system. total order can correctly be implemented by using a notion of sequence number. This technique requires us to discharge proof obligations due to consistency and refinement checking. To discharge the proof obligations we are required to discover invariants that describes the relationship between the abstract total order and the underlying mechanism.
- …
