Search

Healthcare systems are growing very fast, especially emergency departments (EDs) which constitute the major bottleneck of these complex concurrent systems. Emergency departments, where patients arrive without any prior notice, are considered real-time complex dynamic systems. Enhancing these systems requires tailored modeling techniques and a process optimization approach. A new mathematical approach is proposed in order to help multiple emergency units cooperate and share none-consumable resources to achieve the required flow. To achieve the cooperation, the process is modeled by a new subclass of Petri nets. The new Petri net model was proposed in a previous work and is used in this study in order to tackle the problem of modeling and managing these emergency units. The proposed Petri net is named Resource Preservation Net (RPN). Few theorems and lemmas are proposed to support the proposed Petri net model and to prove the correctness of cooperation and resource sharing. In this contribution, a model of cooperative healthcare units is proposed to achieve sound resource sharing and collaboration. The objective function of the proposed model is to improve the key performance indicators: patients length of stay (LoS), resource utilization rates, and patients waiting time. The cooperation among multiple EDs is then proposed through the study of merging two or more units. The cooperative and noncooperative behavior are also studied through theorems of soundness, separability and serializability, and a proof of scalability.

Software Defined Networking (SDN) is a new approach of managing and programming networks enabled by OpenFlow. For load balancing, a migration among OpenFlowDevice (OFDevice) is needed from heavy-loaded controller to least-loaded controller. During migration of OFDevice, the response time, jitter and packet loss for the end user are high. To address this problem, we propose a method in which the response time, jitter and packet loss are minimized during device migration. In this approach for migrating the optimal OFSwitch, we use-liveness, safety, and serializability. The proposed approach focuses on selecting such a OFDevice which causes minimum load on the controller. The experimental results show that our proposed method improves response time, jitter and packet loss.

A method for detecting potential violations of integrity constraints of concurrent transactions running under snapshot isolation (SI) is presented. Although SI provides a high level of isolation, it does not, by itself, ensure that all integrity constraints are satisfied. In particular, while current implementations of SI enforce all internal integrity constraints, in particular key constraints, they fail to enforce constraints implemented via triggers. One remedy is to turn to serializable SI (SSI), in which full serializability is guaranteed. However, SSI comes at the price of either a substantial number of false positives, or else a high cost of constructing the full direct serialization graph. In this work, a compromise approach, called constraint-preserving snapshot isolation (CPSI), is developed, which while not guaranteeing full serializability, does guarantee that all constraints, including those enforced via triggers, are satisfied. In contrast to full SSI, CPSI requires testing concurrent transactions for conflict only pairwise, and thus involves substantially less overhead while providing a foundation for resolving conflicts via negotiation rather than via abort and restart. As is the case with SSI, CPSI can result in false positives. To address this, a hybrid approach is also developed which combines CPSI with a special version of SSI called CSSI, resulting in substantially fewer false positives than would occur using either approach alone.

Flash memory has accelerated the architectural evolution of storage systems with its unique characteristics compared to magnetic disks. The no-overwrite property of flash memory naturally supports transactions, a commonly used mechanism in systems to provide consistency. However, existing embedded transaction designs in flash-based Solid State Drives (SSDs) either limit the transaction concurrency or introduce high overhead in tracking transaction states. This leads to low or unstable SSD performance. In this paper, we propose a transactional SSD (TxSSD) architecture, LightTx, to enable better concurrency and low overhead. First, LightTx improves transaction concurrency arbitrarily by using a page-independent commit protocol. Second, LightTx tracks the recent updates by leveraging the near-log-structured update property of SSDs and periodically retires dead transactions to reduce the transaction state tracking cost. Experiments show that LightTx achieves nearly the lowest overhead in garbage collection, memory consumption and mapping persistence compared to existing embedded transaction designs. LightTx also provides up to 20.6 percent performance improvement due to improved transaction concurrency.

Large scale cloud applications are difficult to program due to the need to access data in a consistent manner. To lift this burden from programmers, Deferred Update Replication (DUR) protocols provide serializable transactions with both high availability and performance in read-dominated workloads. However, the inherently optimistic nature of DUR protocols makes them prone to thrashing in conflict-intensive scenarios: existing DUR schemes, in fact, avoid any synchronization during transaction execution; thus, these schemes end up aborting any update transaction whose reads are no longer up to date by the time it attempts to commit. To tackle this problem, we introduce Bumper, a set of innovative techniques to reduce aborts of transactions in high-contention scenarios. At its core, Bumper relies on two key ideas. First, we spare update transactions from spurious aborts (i.e., unnecessary aborts of serializable transactions), by attempting to serialize the transactions in the past. For this, we use a novel distributed concurrency control scheme that we call Distributed Time-Warping (DTW). And second, we avoid aborts due to contention hot spots (that cannot be tackled by DTW) via a programming abstraction that we call Delayed Actions. These, allow for efficiently serializing, in an abort-free fashion, the execution of conflict-prone data manipulations. By means of an extensive evaluation, on a distributed system of 160 nodes, we show that Bumper can boost performance up to 3 × in conflict-intensive workloads, while imposing negligible (about 2.5%) overheads in uncontended scenarios.

Software transactional memory (STM) is one of the techniques used towards achieving non-blocking process synchronization in multi-threaded computing environment. In spite of its high potential, one of the major limitations of transactional memory (TM) is that in order to ensure data consistency as well as progress condition, TM often forces transactions to abort. This paper proposes a new concurrency control mechanism. It starts with the existing TM implementations for obstruction freedom and eventually builds a new STM methodology. The primary objective is to reduce aborting of transactions in some typical scenarios. A programming model is described for a chain of update transactions that share the same data object among themselves. Using the proposed approach, any new update transaction appended in this chain need not wait for the earlier transactions to finish. The proposed STM allows wait-free, non-blocking implementation of a mix of read and multiple update transactions on the same shared data object with higher throughput.

The concept of a digital ecosystem (DE) has been used to explore scenarios in which multiple online services and resources can be accessed by users without there being a single point of control, which can be used to effectively serialise their interactions. We argue in this paper that this weak coupling between services places additional demands on the modelling of compensation and recovery management in long-running transactions over traditional SOC related formalisms. We describe an adaptation of Shields’ vector languages, in that the synchronisation constraint is removed (no shared actions), as a formal semantics for a transaction in terms of the common ordering constraints on the underlying interactions between its participants. The notation afforded by the so-called transaction languages captures the invocations on each participant service (online resource), and at each point during execution, across the whole transaction. Concurrency is modelled explicitly through a notion of independence, which is lifted onto tuples of sequences (one for each participant of the transaction) rather than individual sequences, as in Mazurkiewicz trace languages or events, as in the event structures model. Participating subcomponents execute concurrently and failure of one or more causes the recovery of the whole transaction. Compensations are triggered immediately upon failure and concurrent forward actions are compensated concurrently. We highlight the benefits of our true-concurrent approach in the context of DEs and outline connections of transaction languages to other partial order models. Further, we discuss how our approach supports forward recovery in that recovering the whole transaction is avoided wherever possible.

We present a general theory of serializability, unifying a wide range of transactional algorithms, including some that are yet to come. To this end, we provide a compact semantics in which concurrent transactions PUSH their effects into the shared view (or UNPUSH to recall effects) and PULL the effects of potentially uncommitted concurrent transactions into their local view (or UNPULL to detangle). Each operation comes with simple criteria given in terms of commutativity (Lipton's left-movers and right-movers). The benefit of this model is that most of the elaborate reasoning (coinduction, simulation, subtle invariants, etc.) necessary for proving the serializability of a transactional algorithm is already proved within the semantic model. Thus, proving serializability (or opacity) amounts simply to mapping the algorithm on to our rules, and showing that it satisfies the rules' criteria.

XML concurrency control protocol (CCP) is used to guard the consistence and isolation of transactions in Native XML databases. Experiments show that locking overhead of existing approaches based on locking may be huge, especially in the applications with few or without conflicts. Optimistic concurrency control (OCC) is an alternative to locking. This paper presents a new optimistic approach for concurrency control over XML documents named FOCCX (Forward oriented Optimistic Concurrency Control over XML) facing XPath-based API. FOCCX increases the degree of transaction concurrency. This is achieved by aborting the current transaction when a potential UPDATE-UPDATE conflict taking place as early as possible, and reduces comparison times by checking a small write set against read set of a limited number of concurrent transactions. Experimental results show that our protocol has superior performance to approaches based on Backward Oriented mechanism (BOCC).

Recently, with the emergence of mobile technology and mobile banking, debit and credit transactions have been the most common transactions that are widely spreading, using such technologies. In this research, we specify the concurrent debit and credit transactions in temporal logics such as CTL (Computational Tree Logic) and LTL (Linear-Time Temporal Logic). These specifications describe the infinite histories that may be produced by the iterations of such concurrent transactions infinitely many times. We represent the infinite histories as a model of temporal logics formulae. Then, model checkers, such as NuSMV or SPIN, can carry out exhaustive checks of the correctness of the concurrent debit and credit transactions. Moreover, in this paper, we presume that the serializability condition is too strict. Therefore, a relaxed condition has been suggested to keep the database consistent. Moreover, the relaxed condition is easier to encode into temporal logics formulae.

In a shared database system when several transactions are executed simultaneously, the consistency of database should be maintained. The techniques to ensure this consistency are concurrency control techniques. All concurrency-control schemes are based on the serializability property. The serializability properties requires that the data is accessed in a mutually exclusive manner; that means, while one transaction is accessing a data item no other transaction can modify that data item. In this paper we had discussed various concurrency techniques, their advantages and disadvantages and making comparison of optimistic, pessimistic and multiversion techniques. We have simulated the current environment and have analysis the performance of each of these methods.

Transactional memory systems providing snapshot isolation enable concurrent access to shared data without incurring aborts on read-write conflicts. Reducing aborts is extremely relevant as it leads to higher concurrency, greater performance, and better predictability. Unfortunately, snapshot isolation does not provide serializability as it allows certain anomalies that can lead to subtle consistency violations. While some mechanisms have been proposed to verify the correctness of a program utilizing snapshot isolation transactions, it remains difficult to repair incorrect applications. To reduce the programmer’s burden in this case, we present a technique based on dynamic code and graph dependency analysis that automatically corrects existing snapshot isolation anomalies in transactional memory programs. Our evaluation shows that corrected applications retain the performance benefits characteristic of snapshot isolation over conventional transactional memory systems.

We address the problem of building scalable transaction management mechanisms for multi-row transactions on key-value storage systems, which are commonly termed as NoSQL systems. We develop scalable techniques for transaction management utilizing the snapshot isolation (SI) model. Because the SI model can lead to non-serializable transaction executions, we investigate two conflict detection techniques for ensuring serializability. To support scalability, we investigate system architectures and mechanisms in which the transaction management functions are decoupled from the storage system and integrated with the application-level processes. We present two system architectures and demonstrate their scalability under the scale-out model of cloud computing platforms. In the first system architecture all transaction management functions are executed in a fully decentralized manner by the application processes. The second architecture is based on a hybrid approach in which the conflict detection functions are performed by a dedicated service. We perform a comparative evaluation of these architectures using the TPC-C benchmark and demonstrate their scalability.

Optimistic scheduling policy based on the concept of Very Important Transaction.Progressively pessimistic scheduling policy with low runtime overheads.Adaptive scheduler that combines two scheduling policies in a synergistic way.Thorough evaluation of 4 schedulers with the STAMP and the STMBench7 benchmark. Transaction schedulers reduce the number of transaction reexecutions in applications using Software Transactional Memory (STM) by preventing conflicting transactions to run in parallel. Unfortunately, current scheduling solutions are too conservative, rely on coarse measures to serialize transactions, and are specially inadequate for workloads with long transactions.In this paper we introduce an optimistic and adaptive transaction scheduler that takes advantage of the information already collected by the STM runtime to increase parallelism between transactions and, thus, improve transactions' throughput. Our new ProVIT scheduler implements a low-overhead scheduling policy for short transactions that reduces concurrency as contention increases and a fine-grained scheduling policy for long transactions based on the novel concept of Very Important Transaction.Experimental results conducted with the STMBench7 benchmark and the STAMP benchmark suite showed that the ProVIT scheduler has comparable performance to other current scheduling solutions for short transactions, but is up to 65% faster for long-running transactions.

Concurrency control is the problem that database management system (DBMS) meets with difficulties, especially distributed DBMS. There are two main methods of concurrency control such as locking-based and timestamp-based. Each method gets involved in its own disadvantages, but locking-based approach is often realized in most distributed DBMS because its feasibility and strictness lessen danger in distributed environment. Otherwise, timestamp ordering algorithm is merely implemented in central DBMS due to the issue of local counter synchronization among sites in distributed environment. The common solution is broadcasting the message about the change of local counter (at one site) over distributed network so that all remaining sites “know” to update their own counters. However, this solution raises some disadvantages of low performance. So, an advanced approach is proposed to overcome such disadvantages by giving out another measure so-called active number that is responsible for harmonizing local counters among distributed sites. Moreover, another method is proposed to apply minimum spanning tree into reduce cost of broadcasting messages over distributed network.

Distributed storage systems aim to provide strong consistency and isolation guarantees on an architecture that is partitioned across multiple shards for scalability and replicated for fault tolerance. Traditionally, achieving all of these goals has required an expensive combination of atomic commitment and replication protocols -- introducing extensive coordination overhead. Our system, Eris, takes a different approach. It moves a core piece of concurrency control functionality, which we term multi-sequencing, into the datacenter network itself. This network primitive takes on the responsibility for consistently ordering transactions, and a new lightweight transaction protocol ensures atomicity. The end result is that Eris avoids both replication and transaction coordination overhead: we show that it can process a large class of distributed transactions in a single round-trip from the client to the storage system without any explicit coordination between shards or replicas in the normal case. It provides atomicity, consistency, and fault tolerance with less than 10% overhead -- achieving throughput 3.6-35x higher and latency 72-80% lower than a conventional design on standard benchmarks.

Real-time spatial applications have become more and more important. These applications are innovating in the way we live. As a result, there is a huge amount of real-time spatial data generated everyday, accessed simultaneously by two types of transactions, Update transactions and User transactions (continuous requests). In real-time spatial Big Data, the performance can be increased by allowing concurrent execution of transactions. This activity is called concurrency control. The concurrency control algorithm must be used to ensure serializability of transaction scheduling and to maintain data consistency.Several works have been done in this area, but without holding into account the existence of a huge volume of data. In this paper, we apply the technique of imprecise computation for real-time spatial nested transactions. We consider that imprecise transaction consist that a User transaction is decomposed logically into a one mandatory sub-transaction and one or more optional sub-transactions and an Update transaction consists only of a single mandatory sub-transaction. We propose an improvement of an existing Two-Shadow Speculative Concurrency Control (SCC-2S) with priority with the use of the imprecise real-time spatial transaction. Our main objectives are: to guarantee the data freshness, to enhance the deadline miss ratio even in the presence of conflicts and unpredictable workloads and finally to satisfy the requirements of users by the improving of the quality of service (QoS).

There is a trend in recent database research to pursue coordination avoidance and weaker transaction isolation under a long-standing assumption: concurrent serializable transactions under read-write or write-write conflicts require costly synchronization, and thus may incur a steep price in terms of performance. In particular, distributed transactions, which access multiple data items atomically, are considered inherently costly. They require concurrency control for transaction isolation since both read-write and write-write conflicts are possible, and they rely on distributed commitment protocols to ensure atomicity in the presence of failures. This paper presents serializable read-only and write-only distributed transactions as a counterexample to show that concurrent transactions can be processed in parallel with low-overhead despite conflicts. Inspired by the slotted ALOHA network protocol, we propose a simpler and leaner protocol for serializable read-only write-only transactions, which uses only one round trip to commit a transaction in the absence of failures irrespective of contention. Our design is centered around an epoch-based concurrency control (ECC) mechanism that minimizes synchronization conflicts and uses a small number of additional messages whose cost is amortized across many transactions. We integrate this protocol into ALOHA-KV, a scalable distributed key-value store for read-only write-only transactions, and demonstrate that the system can process close to 15 million read/write operations per second per server when each transaction batches together thousands of such operations.

As transaction processing services begin to be used in new application domains, low transaction latency becomes an important consideration. Motivated by such use cases we developed Fragola, a highly scalable low-latency and high-throughput transaction processing engine for Apache HBase. Similarly to other modern transaction managers, Fragola provides a variant of generalized snapshot isolation (SI), which scales better than traditional serializability implementations.

Online transaction processing systems use two-phase locking (2PL) to guarantee serializability. However, traditional 2PL does not perform well under high contention, because a transaction will be blocked when it fails to acquire lock. This paper proposes a scalable work stealing algorithm for 2PL to leverage intra-transaction parallelism. The key idea is to parallelize the lock holder's work among lock waiters. Compared to traditional 2PL, our approach can achieve up to 2.8X throughput improvement for TPC-C new-order transactions under high contention.

This paper introduces the first state-based formalization of isolation guarantees. Our approach is premised on a simple observation: applications view storage systems as black-boxes that transition through a series of states, a subset of which are observed by applications. Defining isolation guarantees in terms of these states frees definitions from implementation-specific assumptions. It makes immediately clear what anomalies, if any, applications can expect to observe, thus bridging the gap that exists today between how isolation guarantees are defined and how they are perceived. The clarity that results from definitions based on client-observable states brings forth several benefits. First, it allows us to easily compare the guarantees of distinct, but semantically close, isolation guarantees. We find that several well-known guarantees, previously thought to be distinct, are in fact equivalent, and that many previously incomparable flavors of snapshot isolation can be organized in a clean hierarchy. Second, freeing definitions from implementation-specific artefacts can suggest more efficient implementations of the same isolation guarantee. We show how a client-centric implementation of parallel snapshot isolation can be more resilient to slowdown cascades, a common phenomenon in large-scale datacenters.

In the last years, remarkable improvements have been made in the ability of distributed database systems performance. A distributed database is composed of some sites which are connected to each other through network connections. In this system, if good harmonization isn't made between different transactions, it may result in database incoherence. Nowadays, because of the complexity of many sites and their connection methods, it is difficult to extend different models in distributed database serially. The principle goal of concurrency control in distributed database is to ensure not interfering in accessibility of common database by different sites. Different concurrency control algorithms have been suggested to use in distributed database systems. In this paper, some available methods have been introduced and compared for concurrency control in distributed database.

Shared-memory languages and systems generally provide weak or undefined semantics for executions with data races. Prior work has proposed memory consistency models that ensure well-defined, easy-to-understand semantics based on region serializability (RS), but the resulting system may throw a consistency exception in the presence of a data race. Consistency exceptions can occur unexpectedly even in well-tested programs, hurting availability and thus limiting the practicality of RS-based memory models. To our knowledge, this paper is the first to consider the problem of availability for memory consistency models that throw consistency exceptions. We first extend existing approaches that enforce RSx , a memory model based on serializability of synchronization-free regions (SFRs), to avoid region conflicts and thus consistency exceptions. These new approaches demonstrate both the potential for and limitations of avoiding consistency exceptions under RSx. To improve availability further, we introduce (1) a new memory model called RIx based on isolation of SFRs and (2) a new approach called Avalon that provides RIx. We demonstrate two variants of Avalon that offer different performance-availability tradeoffs for RIx. An evaluation on real Java programs shows that this work's novel approaches are able to reduce consistency exceptions, thereby improving the applicability of strong memory consistency models. Furthermore, the approaches provide compelling points in the performance-availability tradeoff space for memory consistency enforcement. RIx and Avalon thus represent a promising direction for tackling the challenge of availability under strong consistency models that throw consistency exceptions.

The optimistic variants of Multi-Version Concurrency Control (MVCC) avoid blocking concurrent transactions at the cost of having a validation phase. Upon failure in the validation phase, the transaction is usually aborted and restarted from scratch. The "abort and restart" approach becomes a performance bottleneck for use cases with high contention objects or long running transactions. In addition, restarting from scratch creates a negative feedback loop in the system, because the system incurs additional overhead that may create even more conflicts. In this paper, we propose a novel approach for conflict resolution in MVCC for in-memory databases. This low overhead approach summarizes the transaction programs in the form of a dependency graph. The dependency graph also contains the constructs used in the validation phase of the MVCC algorithm. Then, when encountering conflicts among transactions, our mechanism quickly detects the conflict locations in the program and partially re-executes the conflicting transactions. This approach maximizes the reuse of the computations done in the initial execution round, and increases the transaction processing throughput.

Multi-core in-memory databases promise high-speed online transaction processing. However, the performance of individual designs suffers when the workload characteristics miss their small sweet spot of a desired contention level, read-write ratio, record size, processing rate, and so forth. Cicada is a single-node multi-core in-memory transactional database with serializability. To provide high performance under diverse workloads, Cicada reduces overhead and contention at several levels of the system by leveraging optimistic and multi-version concurrency control schemes and multiple loosely synchronized clocks while mitigating their drawbacks. On the TPC-C and YCSB benchmarks, Cicada outperforms Silo, TicToc, FOEDUS, MOCC, two-phase locking, Hekaton, and ERMIA in most scenarios, achieving up to 3X higher throughput than the next fastest design. It handles up to 2.07 M TPC-C transactions per second and 56.5 M YCSB transactions per second, and scans up to 356 M records per second on a single 28-core machine.

In this paper, we propose one comprehensive distributed database transaction method for InfiniBand transaction integrity in the distributed heterogeneous environment caused by data and application expansion. The method first integrates the functions of the standard online transaction engine and then uses the optimistic concurrency control technique to deal with the online memory allocation problem. On the one hand, it reduces the delay time of the online transaction and on the other hand, allocates the computing cost of the transaction to the server and the client. In the existing enterprise network environment using YCSB as a benchmark test shows that the different keys under the method of response speed are the fastest. The result shows that this kind of hybrid processing scheme can make full use of the advantages of remote direct memory access and fast network, which can further improve the consistency and reliability of the distributed database system.

We will focused the concept of serializability in order to ensure the correct processing of transactions. However, both serializability and relevant properties within transaction-based applications might be affected. Ensure transaction serialization in corrupt systems is one of the demands that can handle properly interrelated transactions, which prevents blocking situations that involve the inability to commit either transaction or related sub-transactions. In addition some transactions has been marked as malicious and they compromise the serialization of running system. In such context, this paper proposes an approach for the processing of transactions in a cloud of databases environment able to secure serializability in running transactions whether the system is compromised or not. We propose also an intrusion tolerant scheme to ensure the continuity of the running transactions. A case study and a simulation result are shown to illustrate the capabilities of the suggested system.

Traditional distributed transaction protocol typically included two-phase locking (2PL) or optimistic concurrency control (OCC). However, both of them have the problems when more concurrency conflicts existed in the conditions for large amount requirements of data and processing. In this paper, we propose one merged concurrency control method in the distributed single transaction to support for conflicts more efficiently. TPC-C experiments and results implied that our merged distributed transaction has better ability to handle concurrency conflicts, especially in the case of many conflicts. It can read, write and recall operations with fully utilizing temporal redundancy and data network and be suitable for large-scale data and computationally intensive projects.

Defining a protocol for commit consensus problem in distributed database transactions is not an easy task because we have to think about a fault tolerant system. In this paper, I present a fault tolerant and simple mechanism designed for solving commit consensus problem, based on replicated validation of messages sent between transaction participants.

Developing and reasoning about systems using eventually consistent data stores is a difficult challenge due to the presence of unexpected behaviors that do not occur under sequential consistency. A fundamental problem in this setting is to identify a correctness criterion that precisely captures intended application behaviors yet is generic enough to be applicable to a wide range of applications. In this paper, we present such a criterion. More precisely, we generalize conflict serializability to the setting of eventual consistency. Our generalization is based on a novel dependency model that incorporates two powerful algebraic properties: commutativity and absorption. These properties enable precise reasoning about programs that employ high-level replicated data types, common in modern systems. To apply our criterion in practice, we also developed a dynamic analysis algorithm and a tool that checks whether a given program execution is serializable. We performed a thorough experimental evaluation on two real-world use cases: debugging cloud-backed mobile applications and implementing clients of a popular eventually consistent key-value store. Our experimental results indicate that our criterion reveals harmful synchronization problems in applications, is more effective at finding them than prior approaches, and can be used for the development of practical, eventually consistent applications.

The requirements for OLTP database systems are becoming ever more demanding. Domains such as finance and computer games increasingly mandate that developers be able to encode complex application logic and control transaction latencies in in-memory databases. At the same time, infrastructure engineers in these domains need to experiment with and deploy OLTP database architectures that ensure application scalability and maximize resource utilization in modern machines. In this paper, we propose a relational actor programming model for in-memory databases as a novel, holistic approach towards fulfilling these challenging requirements. Conceptually, relational actors, or reactors for short, are application-defined, isolated logical actors that encapsulate relations and process function calls asynchronously. Reactors ease reasoning about correctness by guaranteeing serializability of application-level function calls. In contrast to classic transactional models, however, reactors allow developers to take advantage of intra-transaction parallelism and state encapsulation in their applications to reduce latency and improve locality. Moreover, reactors enable a new degree of flexibility in database deployment. We present ReactDB, a system design exposing reactors that allows for flexible virtualization of database architecture between the extremes of shared-nothing and shared-everything without changes to application code. Our experiments illustrate latency control, low overhead, and asynchronicity trade-offs with ReactDB in OLTP benchmarks., Comment: Extended version of SIGMOD 2018 paper with an expanded appendix consisting of additional experiments, figures and code examples

Serializability is a well-understood correctness criterion that simplifies reasoning about the behavior of concurrent transactions by ensuring they are isolated from each other while they execute. However, enforcing serializable isolation comes at a steep cost in performance and hence database systems in practice support, and often encourage, developers to implement transactions using weaker alternatives. Unfortunately, the semantics of weak isolation is poorly understood, and usually explained only informally in terms of low-level implementation artifacts. Consequently, verifying high-level correctness properties in such environments remains a challenging problem. To address this issue, we present a novel program logic that enables compositional reasoning about the behavior of concurrently executing weakly-isolated transactions. Recognizing that the proof burden necessary to use this logic may dissuade application developers, we also describe an inference procedure based on this foundation that ascertains the weakest isolation level that still guarantees the safety of high-level consistency invariants associated with such transactions. The key to effective inference is the observation that weakly-isolated transactions can be viewed as functional (monadic) computations over an abstract database state, allowing us to treat their operations as state transformers over the database. This interpretation enables automated verification using off-the-shelf SMT solvers. Case studies and experiments of real-world applications (written in an embedded DSL in OCaml) demonstrate the utility of our approach., Comment: 46 pages, 12 figures

Software Transactional Memory (STM) algorithms provide programmers with a high-level synchronization technique for concurrent access to shared state. STMs typically guarantee some sort of serializability: the concurrent execution of transactions appears to occur in a sequential order. With Guerraoui and Kapalka’s 2008 paper, serializability of software transactions has been phrased as opacity. While opacity has been accepted as the standard correctness criterion for STMs, later verification approaches nevertheless adopt different formulations – claiming them to be opacity.

P-Store is a well-known partially replicated transactional data store that combines wide-area replication, data partition, some fault tolerance, serializability, and limited use of atomic multicast. In addition, a number of recent data store designs can be seen as extensions of P-Store. This paper describes the formalization and formal analysis of P-Store using the rewriting logic framework Maude. As part of this work, this paper specifies group communication commitment and defines an abstract Maude model of atomic multicast, both of which are key building blocks in many data store designs. Maude model checking analysis uncovered a non-trivial error in P-Store; this paper also formalizes a correction of P-Store whose analysis did not uncover any flaw.

We have proposed that shared objects shall be specified by a sequential specification, which describes the functional aspect of their operations and a consistency criterion that describes how concurrency is taken into account by the object. Obviously, the specification in the presence of concurrency is not a new problem. Four scientific communities, have been addressing this problem and have contributed their own solutions.

We describe a novel use of abstract interpretation in which the abstract domain informs a runtime system to correct synchronization failures. To this end, we first introduce a novel synchronization paradigm, dubbed corrective synchronization, that is a generalization of existing approaches to ensuring serializability. Specifically, the correctness of multi-threaded execution need not be enforced by previous methods that either reduce parallelism (pessimistic) or roll back illegal thread interleavings (optimistic); instead inadmissible states can be altered into admissible ones. In this way, the effects of inadmissible interleavings can be compensated for by modifying the program state as a transaction completes, while accounting for the behavior of concurrent transactions. We have proved that corrective synchronization is serializable and give conditions under which progress is ensured. Next, we describe an abstract interpretation that is able to compute these valid serializable post-states w.r.t. a transaction’s entry state by computing an under-approximation of the serializable intermediate (or final) states as the fixpoint solution over an inter-procedural control-flow graph. These abstract states inform a runtime system that is able to perform state correction dynamically. We have instantiated this setup to clients of a Java-like Concurrent Map data structure to ensure safe composition of map operations. Finally, we report early encouraging results that the approach competes with or out-performs previous pessimistic or optimistic approaches.

For the lack of adaptability about the existing concurrency control algorithms, adaptive decision concurrency control algorithm is proposed. ADCC algorithm divides concurrency control process into two phases in: execution authorizing phase and strategy selecting phase. In execution authorizing phase, algorithm compares statistics and effectiveness of transactions to determine the execution order of conflict transactions. In strategy selecting phase, according to transactions’ read/write status and current conflict rate, algorithm selects optimistic/pessimistic conflict resolution strategy adaptively. Such selection mechanism makes ADCC algorithm have high efficiency no matter database system is busy or idle. Simulation experiment proves that ADCC algorithm this paper proposed is superior to classical strict two phases locking algorithm and hybrid concurrency control. So ADCC algorithm performs well in the period of concurrency control.

This article describes a transactional memory execution model intended to exploit maximum parallelism from sequential and multithreaded programs. A program code section is partitioned into chunks that will be mapped onto threads and executed transactionally. These transactions run concurrently and out of order, trying to exploit maximum parallelism but managed by a specific fully distributed commit control to meet data dependencies. To accomplish correct parallel execution, a partial precedence order relation is derived from the program code section and/or defined by the programmer. When a conflict between chunks is eagerly detected, the precedence order relation is used to determine the best policy to solve the conflict that preserves the precedence order while maximizing concurrency. The model defines a new transactional state called executed but not committed . This state allows exploiting concurrency on two levels: intrathread and interthread. Intrathread concurrency is improved by having pending uncommitted transactions while executing a new one in the same thread. The new state improves interthread concurrency because it permits out-of-order transaction commits regarding the precedence order. Our model has been implemented in a lightweight software transactional memory system, TinySTM, and has been evaluated on a set of benchmarks obtaining an important performance improvement over the baseline TM system.

In multi-version databases, updates and deletions of records by transactions require appending a new record to tables rather than performing in-place updates. This mechanism incurs non-negligible performance overhead in the presence of multiple indexes on a table, where changes need to be propagated to all indexes. Additionally, an uncommitted record update will block other active transactions from using the index to fetch the most recently committed values for the updated record. In general, in order to support snapshot isolation and/or multi-version concurrency, either each active transaction is forced to search a database temporary area (e.g., roll-back segments) to fetch old values of desired records, or each transaction is forced to scan the entire table to find the older versions of the record in a multi-version database (in the absence of specialized temporal indexes). In this work, we describe a novel kV-Indirection structure to enable efficient (parallelizable) optimistic and pessimistic multi-version concurrency control by utilizing the old versions of records (at most two versions of each record) to provide direct access to the recent changes of records without the need of temporal indexes. As a result, our technique results in higher degree of concurrency by reducing the clashes between readers and writers of data and avoiding extended lock delays. We have a working prototype of our concurrency model and kV-Indirection structure in a commercial database and conducted an extensive evaluation to demonstrate the benefits of our multi-version concurrency control, and we obtained orders of magnitude speed up over the single-version concurrency control.

Generally, existing cloud data management systems (CDMSs) support partition tolerance in mandatory and sacrifice consistency according to the CAP theory. Partition tolerance means that the database can be split over multiple servers to guarantee consistency or availability, even though the network is partitioned. This property is mandatory in CDMSs which consist of multiple servers. On the contrary, consistency of database is not strongly required in applications of CDMSs such as online shopping, search engine and so on. However, recently emerging applications such as online gaming, collaborative editing, and social networking require strong consistency, which requires that there be only one copy of each data item, and that only serializable access be permitted. Several approaches have been proposed to support consistency in CDMSs. These can be classified into three groups. In the first group of approaches, transactions are processed over multiple records in only one node. In the second group, limited wider transaction support is given to allow transactions to run in multiple nodes with some constraints. In the third group, transaction services are unbundled from the kernel of database management systems. In this paper, we propose a transaction processing method for CDMSs in which snapshot isolation (SI) techniques are applied to the unbundling transaction approach to increase its transaction throughput. The partition locking used by the unbundling transaction approach is static, and therefore, the number of partitions does not change, even when the number of records or the access frequency increases. This feature of the approach may increase the number of failed transactions when a SI technique is applied to the approach. We propose a dynamic partitioning lock method to solve these problems. Our proposed method monitors the number of transactions that access each partition and the number of records in each partition. Then, it splits any partition that is accessed more times than a particular threshold and maintains the split information using a KD-tree. The results of simulations conducted using our proposed dynamic partitioning lock methods show that less transaction aborts occur with our proposed method than with conventional methods.

Majority of the research in database management system focuses primarily on centralized database systems. However, with the demand for higher performance and higher availability, database systems have moved from centralized to distributed architectures. Concurrency control is an integral part of database systems. In this paper we have proposed a new method of concurrency control on the basis of higher priority locking protocol. Assigning higher priority to the transactions requesting for read lock not only reduces the total execution of transactions but also reduces the waiting time for the transactions waiting in the queue. Keywords-Locking, Timestamp, higher priority, global node.

Modern database systems employ Snapshot Isolation to implement concurrency control and isolationbecause it promises superior query performance compared to lock-based alternatives. Furthermore, Snapshot Isolation never blocks readers, which is an important property for modern information systems, which have mixed workloads of heavy OLAP queries and short update transactions. This paper revisits the problem of implementing Snapshot Isolation in a distributed database system and makes three important contributions. First, a complete definition of Distributed Snapshot Isolation is given, thereby extending existing definitions from the literature. Based on this definition, a set of criteria is proposed to efficiently implement Snapshot Isolation in a distributed system. Second, the design space of alternative methods to implement Distributed Snapshot Isolation is presented based on this set of criteria. Third, a new approach to implement Distributed Snapshot Isolation is devised; we refer to this approach as Incremental. The results of comprehensive performance experiments with the TPC-C benchmark show that the Incremental approach significantly outperforms any other known method from the literature. Furthermore, the Incremental approach requires no a priori knowledge of which nodes of a distributed system are involved in executing a transaction. Also, the Incremental approach can execute transactions that involve data from a single node only with the same efficiency as a centralized database system. This way, the Incremental approach takes advantage of sharding or other ways to improve data locality. The cost for synchronizing transactions in a distributed system is only paid by transactions that actually involve data from several nodes. All these properties make the Incremental approach more practical than related methods proposed in the literature.

As more data management software is designed for deployment in public and private clouds, or on a cluster of commodity servers, new distributed storage systems increasingly achieve high data access throughput via partitioning and replication. In order to achieve high scalability, however, today's systems generally reduce transactional support, disallowing single transactions from spanning multiple partitions. This article describes Calvin, a practical transaction scheduling and data replication layer that uses a deterministic ordering guarantee to significantly reduce the normally prohibitive contention costs associated with distributed transactions. This allows near-linear scalability on a cluster of commodity machines, without eliminating traditional transactional guarantees, introducing a single point of failure, or requiring application developers to reason about data partitioning. By replicating transaction inputs instead of transactional actions, Calvin is able to support multiple consistency levels—including Paxos-based strong consistency across geographically distant replicas—at no cost to transactional throughput. Furthermore, Calvin introduces a set of tools that will allow application developers to gain the full performance benefit of Calvin's server-side transaction scheduling mechanisms without introducing the additional code complexity and inconvenience normally associated with using DBMS stored procedures in place of ad hoc client-side transactions.

The past decade has witnessed an increasing adoption of cloud database technology, which provides better scalability, availability, and fault-tolerance via transparent partitioning and replication, and automatic load balancing and fail-over. However, only a small number of cloud databases provide strong consistency guarantees for distributed transactions, despite decades of research on distributed transaction processing, due to practical challenges that arise in the cloud setting, where failures are the norm, and human administration is minimal. For example, dealing with locks left by transactions initiated by failed machines, and determining a multi-programming level that avoids thrashing without under-utilizing available resources, are some of the challenges that arise when using lock-based transaction processing mechanisms in the cloud context. Even in the case of optimistic concurrency control, most proposals in the literature deal with distributed validation but still require the database to acquire locks during two-phase commit when installing updates of a single transaction on multiple machines. Very little theoretical work has been done to entirely eliminate the need for locking in distributed transactions, including locks acquired during two-phase commit. In this paper, we re-design optimistic concurrency control to eliminate any need for locking even for atomic commitment, while handling the practical issues in earlier theoretical work related to this problem. We conduct an extensive experimental study to evaluate our approach against lock-based methods under various setups and workloads, and demonstrate that our approach provides many practical advantages in the cloud context.

Serving requests with low latency while data are replicated and maintained consistently across large geographical areas, e.g. in multiple data centers (DCs), is challenging. We propose Catenae, a transaction framework that provides serializable transaction support for data replicated in multiple DCs. Catenae leverages periodic replicated epoch messages to reduce synchronization delay among DCs, which results in the reduction of commit latency of transactions. It employs and extends a transaction chain concurrency control algorithm to speculatively execute transactions in DCs with maximized execution concurrency and determinism of transaction ordering. As a result, Catenae is able to commit a transaction with half a RTT to a single RTT across DCs in most of the cases. Evaluations with TPC-C benchmark have shown that Catenae significantly outperforms Paxos Commit over 2-Phase Lock and Optimistic Concurrency Control. Catenae doubles the throughput and halves the commit latency comparing to the both approaches.

Nondeterminism is a useful and prevalent concept in the design and implementation of software systems. An important property of nondeterminism is its latent parallelism: A nondeterministic action can evaluate to multiple behaviors. If at least one of these behaviors does not conflict with concurrent tasks, then there is an admissible execution of the action in parallel with these tasks. Unfortunately, existing implementations of the atomic paradigm - optimistic as well as pessimistic - are unable to fully exhaust the parallelism potential of nondeterministic actions, lacking the means to guide concurrent tasks toward nondeterministic choices that minimize interference. This paper investigates the problem of utilizing parallelism due to nondeterminism. We observe that nondeterminism occurs in many real-world codes. We motivate the need for devising coordination mechanisms that can utilize available nondeterminism. We have developed a system featuring such mechanisms, which leverages nondeterminism in a wide class of query operations, allowing a task to look into the future of concurrent tasks that mutate the shared state during query evaluation and reduce conflict accordingly. We evaluate our system on a suite of 12 algorithmic benchmarks of wide applicability, as well as an industrial application. The results are encouraging.