Serializability

Summary

In concurrency control of databases, transaction processing (transaction management), and various transactional applications (e.g., transactional memory and software transactional memory), both centralized and distributed, a transaction schedule is serializable if its outcome (e.g., the resulting database state) is equal to the outcome of its transactions executed serially, i.e. without overlapping in time. Transactions are normally executed concurrently (they overlap), since this is the most efficient way. Serializability is the major correctness criterion for concurrent transactions' executions. It is considered the highest level of isolation between transactions, and plays an essential role in concurrency control. As such it is supported in all general purpose database systems. Strong strict two-phase locking (SS2PL) is a popular serializability mechanism utilized in most of the database systems (in various variants) since their early days in the 1970s. Serializability theory pro

Official source

https://en.wikipedia.org/wiki/Serializability

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (22)

Related publications

Related people (6)

Related people

Related units (2)

Related units

Related concepts (23)

Related concepts

Related courses (7)

This course provides a deep understanding of the concepts behind data management systems. It covers fundamental data management topics such as system architecture, data models, query processing and optimization, database design, storage organization, and transaction management.

This course is intended for students who want to understand modern large-scale data analysis systems and database systems. It covers a wide range of topics and technologies, and will prepare students to be able to build such systems as well as read and understand recent research publications.

The course covers fundamental principles for understanding and building systems for managing and analyzing large amounts of data.

Related courses

Related lectures (21)

Related lectures

, ,

We show that it is impossible to design a transactional memory system which ensures parallelism, i.e. transactions do not need to synchronize unless they access the same application objects, while ensuring very little consistency, i.e. a consistency condition, called weak adaptive consistency, introduced here and which is weaker than snapshot isolation, processor consistency, and any other consistency condition stronger than them (such as opacity, serializability, causal serializability, etc.), and very little liveness, i.e. that transactions eventually commit if they run solo.

2014

The PCL Theorem: Transactions cannot be Parallel, Consistent, and Live

Victor Bushkov, Panagiota Fatourou, Rachid Guerraoui

We establish a theorem called the PCL theorem, which states that it is impossible to design a transactional memory algorithm that ensures (1) parallelism, i.e., transactions do not need to synchronize unless they access the same application objects, (2) very little consistency, i.e., a consistency condition, called weak adaptive consistency, introduced here and that is weaker than snapshot isolation, processor consistency, and any other consistency condition stronger than them (such as opacity, serializability, causal serializability, etc.), and (3) very little liveness, i.e., which transactions eventually commit if they run solo.

ASSOC COMPUTING MACHINERY2019

Safety, Liveness and Parallelism in Concurrent Computing

Victor Bushkov

The correctness of a shared object, which can be accessed by several processes concurrently, is specified through two different kinds of properties - safety and liveness. When implementing a shared object it is important to specify its correctness in a such way that it should be feasible under given assumptions. In this work we study the question of implementability of shared objects that satisfy certain safety and liveness properties under certain assumptions. In particular, we study implementability of liveness properties of transactional memory (TM) shared objects with strict serializability, a strong safety property. TM allows a programmer to encapsulate pieces of sequential code within transactions that run concurrently and it ensures that transactions run in some consistent manner by committing or aborting them. First, we give a formal definition of a liveness property in the TM context. Then, we proceed to show that certain classes of liveness properties of TM can not be implemented with strict serializability in a system in which processes are prone to failures. We also show that, in general, we cannot find a weakest non-implementable (resp. strongest implementable) liveness of TM when we require some common safety property like strict serializability. Moreover, we generalize this result to other shared object types and give a characterization of safety properties for which we can find weakest non-implementable (resp. strongest implementable) liveness. In addition to correctness properties we study the limitations of parallelism which affects performance and scalability of implementations. Specifically, we show that we cannot implement a TM which guarantees disjoint-access parallelism, which say that transactions do not need to synchronize unless they access the same application objects, while guaranteeing very weak safety and the weakest non-blocking liveness.

EPFL2015