Serializability

Synonyms

Transactional consistency in a replicated database

Definition

While transactions typically specify their read and write operations on logical data items, a replicated database has to execute them over the physical data copies. When transactions run concurrently in the system, their executions may interfere. The replicated database system has to isolate these transactions. The strongest and most well-known correctness criterion for replicated databases is one-copy-serializability. A concurrent execution of transactions in a replicated database is one-copy-serializable if it is “equivalent” to a serial execution of these transactions over a single logical copy of the database.

Main Text

A transaction is a sequence of read and write operations on the data items of the database. A read operation of transaction T_i on data item x is denoted as r_i(x) and a write operation on x as w_i(x). A transaction T_i either ends with a commit c_i (all operations succeed) or with an abort a_i...