User:Dingo1729/History of commitment ordering

Commitment ordering (or Commit ordering, CO; Raz 1990a, 1990b), publicly introduced in May 1991, has solved the years old open fundamental Global serializability problem (e.g., Silberschatz et al. 1991, page 120; see second quotation) through a generalization of the de-facto standard for Global serializability, SS2PL, and provided insight into it. Though published in prestigious academic journal (Raz 1994 - IPL) and refereed conferences ((Raz 1992 - VLDB), (Raz 1993a - ACM PODS), (Raz 1993b - IEEE RIDE-IMS)), as well as in three patents (Raz 1991a), the CO solution has been largely misunderstood and misrepresented (e.g., Weikum and Vossen 2001, pages 102, 700, and Breitbart and Silberschatz 1992), and to a great extent ignored in relevant database research texts (e.g., the text-books Liu and Özsu 2009, and Silberschatz et al. 2010), until recently: In Bernstein and Newcomer 2009 it is related to as the fourth major concurrency control method in addition to the earlier known three major methods (see last quotation). On the other hand, in some research articles the CO solution has been utilized without using the name CO, without referencing the CO work, and without explaining properly how and why CO achieves Global serializability (e.g., Haller et al. 2005, Voicu and Schuldt 2009b).

In concurrency control of databases and transaction processing (transaction management), CO is a class of interoperable Serializability techniques, both centralized and distributed. It is also the name of the resulting transaction schedule property. In a CO compliant schedule the chronological order of commitment events of transactions is compatible with the precedence order of the respective transactions. CO provides an effective, general solution to the Global serializability problem, i.e., achieving serializability in a distributed environment of multiple autonomous database systems and other transactional objects, that possibly utilize a different concurrency control mechanism each (e.g., as in Grid computing and Cloud computing). CO also provides an effective solution for Distributed serializability in general. The concept of CO has evolved in three threads of development, seemingly initially independent:

1. Dynamic atomicity (DA) at the MIT (Weihl 1984); its definition was changed to be equivalent to CO in (Fekete et al. 1988; prior to CO).
2. Analogous execution and serialization order (AESO) at the University of Houston (Georgakopoulus and Rusinkiewics 1989).
3. Commitment ordering (CO) at Digital Equipment Corporation (Raz 1990a, 1990b).

Similarity between the initial concepts above and their final merging in equivalent or identical definitions caused researchers in the past to refer to them as "the same" (e.g., Weikum and Vossen 2001, page 720). However essential differences exist between their respective final research results and time-lines:

1. The originally defined DA is close to CO, but is strictly contained in CO (which makes an essential difference in implementability; unlike CO, no general algorithm for DA is known). Only in (Fekete et al. 1988; precedes CO) DA is defined to be equivalent to CO (in a model that supports sub-transactions), but without a full-fledged generic local and distributed algorithms.
2. The definition of the AESO schedule property evolved to the definition of Strong recoverability (STRC) in (Breitbart et al. 1991). The definition of STRC is identical to the CO definition. However, this should not be confused with the CO algorithmic techniques and theoretical results: No such techniques and results have been proposed for STRC, in particular the key result that local CO implies Global serializability with no concurrency control information distribution (preserving local autonomy: no need in external information locally). (Breitbart et al. 1991) appeared in September 1991. An already accepted for publication version of the article, circulated before its publication, does not have a word about Strong recoverability, and does not include the Abstract part which describes it and uses the term "commitment order".
3. Atomic commitment protocol (ACP) and voting deadlocks (or an equivalent mechanism), which are crucial for the CO solution and CO's efficient distribution, are utilized neither for Dynamic atomicity (DA, which has a partial replacement though) nor for Strong recoverability (STRC).

Three patents filed for the CO techniques in 1991-3 were granted in 1996-7 (Raz 1991a). They have been extensively referenced in other patents since.

All three development threads have converged at definitions of schedule properties identical or equivalent to CO, and noticed that Strong strict two-phase locking (SS2PL or Rigorousness) possesses their respective properties. The DA work has provided additional examples of algorithms that generate DA compliant schedules, as well as implying that local DA (the original DA) implies global serializability while using only local concurrency control information. STRC is shown to imply Serializability but no proof is given that local STRC implies Global serializability with only local concurrency control information. General algorithms are given neither for DA nor for STRC. Only the CO articles have provided (patented) general algorithms for CO and methods to turn any concurrency control mechanism into a CO compliant one, for achieving global serializability across autonomous transactional objects (i.e., using only local concurrency control information; e.g., autonomous databases) with possibly different concurrency controls. The CO articles have also provided generalizations of CO that guarantee Global serializability with more concurrency and better performance by using additional local information (ECO in Raz 1993a, and MVCO in Raz 1993b).

A unique and novel element in the CO techniques and patents, besides ordering commit events, is the utilization of the atomic commitment protocol voting mechanism to break global cycles (also referred to as distributed cycles; span two or more transactional objects) in the conflict graph, for guaranteeing global serializability. It is achieved by applying a specific vote ordering strategy: voting in local precedence order. Also locking based global deadlocks are resolved automatically by the same mechanism as a side benefit. This allows effective implementations of distributed CO (and resulting distributed serializability), while allowing any, uninterrupted transaction operations scheduling without any conflict information distribution (e.g., local precedence relations, locks, timestamps, tickets). Furthermore, CO does not use any additional, artificial transaction access operations (e.g., "take timestamp" or "take ticket"), which typically result in additional, artificial conflicts that reduce concurrency.

The CO solution has been utilized extensively since 1997 in numerous works within the subject of Transactional processes (e.g., Schuldt et al. 2002, where CO is referenced). Some of them include descriptions of CO utilization in commercial distributed software products. Recently CO has been utilized as the basis for the concurrency control of Re:GRIDiT (e.g., Voicu et al. 2009a, Voicu and Schuldt 2009b), a proposed approach to transaction management in Grid computing and Cloud computing. The latter two articles and all other related articles by the same authors neither mention the name CO nor reference CO's articles.

CO has been utilized in a work on fault tolerance of transactional systems with replication (Vandiver et al. 2007).

With the proliferation of Multi-core processors CO also has been increasingly utilized in Concurrent programming (Parallel programming) and Transactional memory (and especially in Software transactional memory, STM) for achieving serializability optimistically by "commit order" (e.g., Ramadan et al. 2009, Zhang et al. 2006, von Parun et al. 2007).

Background

Serializability has been identified as the major criterion for the correctness of transactions executing concurrently. Consequently a general, practical variant of it, Conflict serializability, is supported in all general-purpose database systems. However, if several database systems (or any other transactional objects) inter-operate, Global serializability is not maintained in general, even if each database system (transactional object) provides conflict serializability, and overall correctness is not guaranteed. The problem of guaranteeing Global serializability in a heterogeneous distributed system effectively, with reasonable performance, has been researched for many years and characterized as open (Silberschatz et al. 1991, page 120). Commitment ordering (CO; Raz 1990b, 1992, 1994) has provided a general solution to the problem. CO was disclosed publicly by Yoav Raz in May 1991, immediately after its patent filing (see CO patents below). It was disclosed by lectures and publication submission and distribution to tens of database researchers. More details about the CO solution can be found in Global serializability.

A description of CO and some bibliographic notes are given in (Weikum and Vossen 2001). This is the first known text-book on concurrency control that deals with CO. The description of CO in two separate sections titled "Commitment ordering" (Ibid, pages 102, 700) lacks several fundamental aspects of the CO technique (e.g., using voting in atomic commitment protocol and voting deadlocks) and thus is an unsatisfactory and misleading description of the CO technique. Also the bibliographic notes there are inaccurate, since the original DA (in Weihl 1989; referred to in the quotation below) is different from CO:

"Commitment order-preserving conflict serializability, as mentioned in Chapter 3, was proposed, using different terminology, by Weihl 1989, Breitbart et al. 1991, and Breibart and Silberschats 1992, as well as Raz 1992, 1993, 1994."

(Ibid, page 720)

The bibliographic notes, as well as other CO related text in the book, ignore the different ways the respective properties' definitions are utilized by the three evolvement threads (works), and the different results of each work (see below summaries of main results of each). Also, some theorems about CO given in the book are significantly weaker than what implied by the CO work, miss its essence, and again misleading.

Such misleading inaccuracies, omissions of fundamentals, and misrepresentation appear also in several other research articles that have mentioned and referenced the CO publications, and it is evident that the CO solution for global serializability has been misunderstood by many database researchers even years after its public introduction in 1991 (see Quotations in Global serializability). Many articles and books published after 1991, that discuss distributed and global concurrency control, have not mentioned CO at all. CO is neither referenced nor mentioned even in the new 6th edition of a database textbooks in 2010, Silberschatz et al. 2010, which deals with distributed concurrency control and global serializability, and resorts to much less effective than CO serializability methods (see benefits of CO in Global serializability), or methods that violate Global serializability (e.g., Two-level serializability, which is argued there to be correct under certain narrow conditions).

On the other hand, CO is referenced in (Bernstein and Newcomer 2009, page 145) as follows:

"Not all concurrency control algorithms use locks... Three other techniques are timestamp ordering, serialization graph testing, and commit ordering. Timestamp ordering assigns each transaction a timestamp and ensures that conflicting operations execute in timestamp order. Serialization graph testing tracks conflicts and ensures that the serialization graph is acyclic. Commit ordering ensures that conflicting operations are consistent with the relative order in which their transactions commit, which can enable interoperability of systems using different concurrency control mechanisms."

"Commit ordering is presented in Raz (1992)." (Ibid, page 360)

Comments:

1. Beyond the common locking based algorithm SS2PL, which is a CO variant itself, also additional variants of CO that use locks exist, (see below). However, generic, or "pure" CO indeed does not use locks (but can be implemented with similar, non-blocking mechanisms to keep conflict information).
2. Since CO mechanisms order the commit events according to conflicts that already have occurred, it is better to describe CO as "Commit ordering ensures that the relative order in which transactions commit is consistent with the order of their respective conflicting operations."

Also on the other hand, it seems that for some researchers CO has become an obvious method and in many cases it has been utilized by them without reference to the CO work. CO has been utilized extensively in research, and most of the times unreferenced (and under different names, e.g., Re:GRIDiT in Voicu and Schuldt 2009b).

In what follows the evolvement of CO is described. Additional section below briefly describes later utilization of CO.

Three threads of development

Commitment ordering (CO) has evolved in three, seemingly initially independent, threads of development:

1. Dynamic atomicity (DA) at the MIT (Weihl 1984); its definition was changed to be equivalent to CO in (Fekete et al. 1988; prior to CO).
2. Analogous execution and serialization order (AESO) at the University of Houston (Georgakopoulus and Rusinkiewics 1989).
3. Commitment ordering (CO) at Digital Equipment Corporation (Raz 1990a, 1990b).

Similarity between the initial concepts above and their final merge in equivalent or identical definitions caused in the past researchers to refer to them as "the same." However essential differences exist between their respective final research results and time-lines:

1. The originally defined DA is close to CO, but is strictly contained in CO (which makes an essential difference in implementability; unlike CO, no general algorithm for DA is known). Only in (Fekete et al. 1988; precedes CO) DA is defined to be equivalent to CO (in a model that supports sub-transactions), but without a full-fledged generic local and distributed algorithms.
2. The definition of the AESO schedule property evolved to the definition of Strong recoverability (STRC) in (Breitbart et al. 1991). The definition of STRC is identical to the CO definition. However, this should not be confused with the CO algorithmic techniques and theoretical results: No such techniques and results have been proposed for STRC, in particular the key result that local CO implies Global serializability with no concurrency control information distribution (preserving local autonomy: no need in external information locally). (Breitbart et al. 1991) appeared in September 1991. An already accepted for publication version of the article, circulated before its publication, does not have a word about Strong recoverability, and does not include the Abstract part which describes it and uses the term "commitment order".
3. Atomic commitment protocol (ACP) and voting deadlocks (or an equivalent mechanism), which are crucial for the CO solution and CO's efficient distribution, are utilized neither for Dynamic atomicity (DA, which has a partial replacement though) nor for Strong recoverability (STRC).

These evolvement threads are described in what follows with respective summaries of main results relevant to CO.

Dynamic atomicity

---

Dynamic atomicity (DA) appears in the Ph.D dissertation (Weihl 1984) and possibly in earlier publications by the same author. The DA work seems to be the first one to deal with modular concurrency control in a multi-object environment, i.e., to guarantee global serializability (referred to as global atomicity; different terminology) by local properties of the objects. It is defined using a variant of input-output automata, a formalism developed at the MIT to deal with systems in the context of abstract data types. DA has been also described and utilized in numerous publications later, both in its original version which is different from CO, e.g., (Weihl 1988, Weihl 1989), and in its enhanced version, equivalent to the CO property, e,g., in (Fekete et al. 1988, Fekete et al. 1990), and in the book (Lynch et al. 1993). The revised DA is defined as schedule property (to be checked for existence) without a generic local algorithm and without a full-fledged distributed algorithm. Optimality result (necessity for achieving global serializability under certain conditions) is given for the original DA, but not for the enhanced DA.

DA is strictly contained in CO

While DA has not been originally defined as the CO property, under certain transaction model translation from the input-output automata model to the model common for dealing with databases concurrency control it appears very close to CO, but strictly contained in CO: With CO, order of commit events of every two transactions with conflicts needs to be compatible with their precedence order; with DA the first commit needs to precede at least one (non-commit, as demonstrated) operation of the second transaction (Weihl 1988, and Weihl 1989, page 264):

"If the sequence of operations executed by one committed transaction conflicts with the operations executed by another committed transaction, then some operations executed by one of the transactions [explicitly not commit; by following examples there commit does not count as operation] must occur after the other transaction has committed."

I.e., DA has an additional restriction over CO (see also footnote about this in the linked last version of (Raz 1990b, page 5) ), and thus it is a proper subset of CO.

The additional operation needed for DA makes a difference in implementability, and no effective general DA algorithm is known (i.e., covering the entire DA set), versus an effective general CO algorithm that exists.

Local DA implies global serializability

With the original definition of DA the proof of achieving global serializability by local DA can be done without involving atomic commitment protocol and voting. In (Weihl 1989) DA is shown to provide global serializability when applied locally in transactional objects. Some protocols are shown to have the DA property but no general mechanisms to enforce DA and thus global serializability are shown. Atomic commitment protocol and related voting are not part of the formal model used. Global (voting) deadlock resolution by an atomic commitment protocol, which is the foundation of the distributed CO algorithm, is not mentioned.

Comment: The commitment event is a synchronization point across all the local sub-transactions of a distributed transaction. Thus, with the DA definition, when two transaction are in conflict, the extra operation in the second transaction (in any of its local sub-transactions), after the commitment of the first, guarantees proper commitment order of the two transactions, which implies global serializability. Thus local DA guarantees global serializability. The same arguments also imply that local SS2PL guarantees global serializability. However, with CO no extra operation is available to enforce proper commitment order, and hence an atomic commitment protocol mechanism and a vote ordering strategy , referred to as $CD^{3}C$ in (Raz 1990b, 1992), are needed to enforce the correct commitment order for distributed transactions (i.e., globally; assuming autonomy, i.e., no entity exists that "knows" the global precedence order to determine the correct global commit order. Maintaining such an entity, either centralized or distribute, is typically expensive).

DA is changed to be equivalent to CO

Only a later definition of DA in (Fekete et al. 1988, Fekete et al. 1990; prior to CO), and in (Lynch et al. 1993, Page 201) is equivalent to the definition of CO, using only commit events order. A mechanism that enforces global DA and serializability when DA exists locally is described: a Generic scheduler (e.g., Lynch et al. 1993, Page 207). However , no generic local algorithm and full-fledged distributed algorithm are given (they are given in the CO publications and its patents): DA is described as a property that is provided by some known locking algorithms. It is proven there that if DA exists locally, then it also exists globally (as also the later CO work has noticed). No mechanism that turns any local concurrency control mechanism into a CO compliant mechanism, as the generic local CO algorithm does, is given for DA.

The following is a quotation from (Fekete et al. 1988, page 49):

"7.3. Dynamic Atomicity

Now we define the "dynamic atomicity" property for a generic object automaton; roughly speaking, it says that the object satisfies the view condition using the completion order as the sibling order R. This restatement of the view condition as a property of a generic object is very convenient for decomposing correctness proofs for locking algorithms: the Serializability Theorem implies that if all the generic objects in a generic system are dynamic atomic, then the system guarantees serial correctness for all non-orphan transaction names. All that remains is to show that the generic objects that model the locking algorithms of interest are dynamic atomic."

Comments:

1. As with the CO solution, Global DA (and resulting Global serializability) is guaranteed only with the possibility of global deadlocks (a deadlock that spans two objects or more; in this case these are global deadlocks that do not necessarily result from data locking but rather from commit blocking, and thus are unique to DA (CO) and relevant to serializability). Such global deadlocks and their resolution, which are the key to the CO algorithmic solution, are not mentioned in conjunction with DA (and unclear if noticed at all).
2. The distribution of the Generic scheduler component is not shown (but can be done similarly to the distribution of an Atomic commitment protocol (ACP)).

In addition, as it is explicitly stated in (Lynch et al. 1993, page 254), no optimality result (see section below) for the new DA is given:

"Weihl also proves that under appropriate conditions, there is no local property strictly weaker than his notion of dynamic atomicity that also guarantees global atomicity. This proof relies on the fact that the precedes order captures precisely an object's local information about global commit order. It would be interesting to explore similar optimality issues for the local dynamic atomicity property defined here."

In comparison, the CO result of the necessity in CO for guaranteeing Global serializability over autonomous resource managers (the original autonomy definition given in the CO work, with no knowledge to identify local transactions) is such an optimality result. This result from (Raz 1992) and its earliest 1990 version (DEC-TR 841) is unnoticed in (Lynch et al. 1993), and the CO work is not referenced there, but the term "commit order" is used (vs. "completion order" in related earlier publications by the authors).

Also, no generalizations of the DA result similar to the CO generalizations are given:

• Extended CO (ECO) relaxes CO locally, and
• Multi-version CO (MVCO) generalizes CO for multi-version concurrency control to provide one-copy serializability (1SR).

The CO work also provides optimality results for ECO and MVCO (and ultimately for VO; see below).

The late publication (Weihl 1989) about the old dynamic atomicity (without mentioning there the new one) has caused some confusion that has lasted for many years: The CO work in the early 1990s references only the old DA definition in (Weihl 1989) and not the new one (that in Fekete et al. 1988, Fekete et al. 1990, Lynch et al. 1993), while indicating the difference between the old DA and the new. Yoav Raz describes in his CO web-page (see external link below) that he knew about the new definition in (Lynch et al. 1993), but only in May 2011 became aware of earlier appearances of the new definition in (Fekete et al. 1988, Fekete et al. 1990), before CO. (Weikum and Vossen 2001) also references (Weihl 1989) for dynamic atomicity, but incorrectly refers to the old definition there as equivalent to CO (which is not: only the new one is equivalent to CO; see details in the Background section above).

Both the original DA and CO are optimal

(Weihl 1989) also shows DA to be optimal in the sense that no broader property (super-class) provides global serializability when applied locally under the assumption of dynamic transaction operations' scheduling (which is the common way in transactional systems). This is similar to a result in (Raz 1990b) that CO is a necessary condition for guaranteeing global serializability across autonomous resource managers (resource managers that do not share any concurrency control information beyond (unmodified) atomic commitment protocol messages). However since CO strictly contains the original DA there, CO is the optimal property in this sense, and not DA. The apparent contradiction in the optimality result stems from the fact that DA optimality is proven in a formal model without voting in atomic commitment protocol. Without a voting mechanism and a vote ordering strategy, referred to as $CD^{3}C$ in (Raz 1990b, 1992), commit order can be enforced only with an operation in a second transaction after the commit of a first preceding transaction, as in the original definition of DA. This makes the optimum without voting, DA, a smaller class (since an additional constraint, the extra operation, exists) than the optimum in a model where voting exists and commit order can be enforced by a vote ordering strategy (without the additional constraint), which is CO.

Main DA results

1. DA implies Serializability
2. Local DA implies Global serializability, even when utilizing local concurrency control information only
3. Certain concurrency control mechanisms (algorithms) provide the DA property
4. The original DA is an optimal property (in a formal model without voting in atomic commitment protocol; CO, which strictly contains the original DA, is the optimal property under the condition of local autonomy in a model where voting exists; no optimality result is given for the new DA - see above)

Analogous execution and serialization order

and Strong recoverability

---

AESO requires serializability as a prerequisite

Analogous (or Similar) execution and serialization order (AESO) is defined in a technical report (Georgakopoulus and Rusinkiewics 1989), and possibly in more technical reports. The AESO property is equivalent to CO, but in its definition serializability is (unnecessarily) required as a prerequisite. Thus It is clear from the definition, that the fact that AESO without the prerequisite implies serializability, has been overlooked. For this reason the ordering of commit events could not have been thought as a serializability implying mechanism in the context of AESO.

AESO is modified to Strong recoverability (CO)

In (Breitbart et al. 1991) a new term appears, Strong recoverability (STRC), which is identical to AESO but drops the (unnecessary) serializability prerequisite. STRC is identical to CO. It is brought there together with the (now redundant) AESO concept. A draft version of this article, circulated in 1991 and already accepted for publication in the September 1991 issue of TSE ("to appear in IEEE Transactions on Software Engineering, September, 1991" is printed at the top), includes AESO but not STRC. It neither includes the Abstract part which describes STRC and uses the term "commitment order". Thus STRC has been added for the TSE published version (the STRC text has been mainly added on top of the original text with the now redundant AESO). It is shown there that STRC implies serializability, and STRC is utilized there to assist proving that a federated database with local Rigorousness (SS2PL) ensures global serializability. It is not shown there how local STRC in general, other than Rigorousness, implies global serializability. With local Rigorousness (SS2PL) global serializability is achieved automatically (see SS2PL in Commitment ordering), while with other STRC (CO) types a certain condition on voting in atomic commitment protocol should be met (a votine ordering strategy). Neither atomic commitment protocol nor vote ordering strategy are mentioned or dealt with in the STRC articles.

No algorithm for STRC beyond SS2PL is given. Atomic commitment protocol, voting, and global deadlocks, which are fundamental elements in the CO solution, are not mentioned there. It is (mistakenly) claimed there that Strong recoverability (STRC) implies Recoverability, and hence the (misleading) property's name. STRC is the focus of (Breitbart and Silberschats 1992), and also there no proper algorithm and method beyond Rigorousness (SS2PL) is given. In the abstracts of both these STRC papers the following sentence appears:

"The class of transaction scheduling mechanisms in which the transaction serialization order can be determined by controlling their commitment order, is defined."

The idea here is opposite to the CO solution: In all the proposed CO mechanisms the serialization order, which is determined by data-access scheduling (the common way), determines the commit order. (Breitbart et al. 1991) does not reference (Raz 1990b), but (Breitbart and Silberschats 1992) does.

Main STRC results

1. Local Rigorousness (SS2PL) implies Global serializability (long known result when published in (Breitbart et al. 1991), but not widely published earlier, e.g., see explicit description in (Raz 1990a), and references in (Raz 1990b, 1992))
2. Several concurency control mechanisms provide Rigorousness
3. Rigorousness implies STRC (CO)
4. STRC implies Serializability (but neither proof, nor proof outline, nor proof idea, about local STRC (CO) implying Global serializability when utilizing local concurrency control information only, have been introduced)

Commitment ordering

---

Main article: Commitment ordering

Early versions of (Raz 1990b) reference neither DA, nor STRC, but later versions and other CO articles reference both (Weihl 1989) and (Breitbart et al. 1991).

The discovery of CO

"In the beginning of 1990 S-S2PL was believed to be the most general history property that guarantees global serializability over autonomous RMs. The discovery of Commitment Ordering (CO) resulted from an attempt to generalize S-S2PL, i.e., to find a super-set of S-S2PL that guarantees global serializability while allowing to maintain RM autonomy. An intermediate step was discovering a property that I named Separation (SEP; "separating" conflicting operations by a commit event), which is a special case of CO...

...SEP is less restrictive than S-S2PL, and allows optimistic implementations. However, it is far more restrictive than CO. It was noticed later that the Optimistic 2PL scheduler described in [Bern 87] spans exactly the SEP class. A paper on separation, similar to this one, was written by me in July–August 1990, and included results for SEP, parallel to most main results for CO, described here. The first version of the current CO paper was a rewrite of the separation paper. The separation paper included an erroneous theorem, claiming that SEP was the most general property (a necessary condition for) guaranteeing global serializability over autonomous RMs. The proof was almost identical to the proof of theorem 6.2 here. CO was formulated two days after I noticed a mistake in the proof of that theorem: SEP requires aborting more transactions than the minimum necessary to guarantee global serializability. This minimum is exactly defined by $ABORT_{CO}(T)$, when T is committed. Extended CO (ECO; [Raz 91b] was formulated a few days later. Y. R."

From the Preface in (Raz 1990b)

Comment: The DA work in the framework of abstract data types was unknown at that time to most database people. The new DA article (Fekete et al. 1988) appeared (possibly with some modifications) also in (Fekete et al. 1990). DA has no known published explicit general algorithm, and no mention about integration with other concurrency control mechanisms.

The CO algorithms

A general effective technique is provided for generating CO compliant schedules and guaranteeing both Global serializability (for environments with multiple transactional objects) and Distributed serializability (for distributed transactional systems in general). A fundamental element in the technique is an Atomic commitment protocol (ACP; any such protocol). With a certain vote ordering strategy utilized with the APC, a voting-deadlock occurs (i.e., voting of transactions for the ACP is blocked) whenever a global cycles in a system's augmented conflict graph (the union of the (regular) conflict graph and the (reversed edge regular) wait-for graph) is generated (see more below). The ACP resolves such deadlock by aborting a deadlocked transaction, with a missing vote. This abort breaks the global cycle. Breaking all such cycles guarantees both global serializability and automatic locking-based global deadlock resolution. No local conflict information needs to be distributed.

A generic local CO algorithm orders both local commit events for local transactions (transactions confined to a single transactional object) and voting events for global transactions (transactions that span two or more objects) in order to implement the vote ordering strategy above for guaranteeing both local and global CO, as well as global serializability.

CO automatically resolves global deadlocks

(Raz 1990b) and other CO publications show that in a CO compliant environment a global deadlock is generated during the atomic commitment protocol's (ACP) execution if local precedence orders in two or more objects are not compatible (i.e., no global precedence order can embed together the local orders). This generates a cycle in the augmented conflict graph (the union of the (regular) conflict graph and the (reversed edge regular) wait-for graph) of the multi-object system. That global deadlock is a voting-deadlock, which means that voting of distributed transactions on the cycle is blocked. The ACP resolves such voting-deadlock by aborting some transaction with a missing vote and breaking the cycle. If all the cycle's edges represent materialized conflicts than this cycle is also a cycle in the (regular) conflict graph, and breaking it maintains Serializability. If at least one edge represents a non-materialized conflict, then this is not a cycle in the (regular) conflict graph, which reflects a locking based global deadlock. Also such cycle is broken automatically by the same mechanism, and the deadlock is resolved.

The same result applies also to an entirely SS2PL based distributed environment, where all conflicts are non-materialized (locking-based), since SS2PL is a special case of CO. Many research articles about global deadlocks in SS2PL and resolving them have been published since the 1970s. However, no reference except the CO papers is known (as of today, 2009) to notice such automatic global deadlock resolution by ACP (which is always utilized for distributed transactions).

CO is a necessary condition for global serializability across autonomous databases

(Raz 1990b, 1992) show that enforcing CO locally is a necessary condition for guaranteeing serializability globally across autonomous objects. This means that if any autonomous object in a multi-object environment does not comply with CO, than global serializability can be violated. It also means that CO is optimal in the sense of (Weihl 1989): No schedule property exists that both contains CO (i.e., defining a super-class of the class of CO compliant schedules) and guarantees global serializability across autonomous objects.

CO variants

CO variants are special cases and generalizations of CO. Several interesting variants have been developed and investigated in the years 1990-1992. All CO variant can transparently inter-operate in a mixed distributed environment with different variants, guaranteeing Global serializability and automatic locking-based global deadlock resolution. The following are interesting CO variants:

• SS2PL

Strong strict two-phase locking (SS2PL, a name coined in (Raz 1990b); also the name of the resulting schedule property, which is also called Rigorousness or Rigorous scheduling in (Breibart et al. 1991)) is a common serializability technique since the 1970s. It has been known for many years before 1990 that a multi-database environment, where all databases are SS2PL compliant, guarantees Global serializability. As a matter of fact it has been the only known practical method for global serializability, and has become a de facto standard, well known among practitioners in the 1980s (Raz 1990a, 1990b, 1992). SS2PL has many variants and implementations. It provides both Strictness and CO.

• SCO

Strict commitment ordering (SCO; (Raz 1991b)) is the intersection of Strictness and CO. SCO has a sorter average transaction duration than that of SS2PL, and thus better concurrency. Both have similar locking overhead. An SS2PL compliant database system can be converted to an SCO compliant one in a straightforward way without changing strictness based recovery mechanisms.

• OCO

Optimistic commitment ordering (OCO) spans the entire CO class. The name OCO is used to emphasize the fact that this is the optimistic version of CO, versus other, non-optimistic variants of CO.

• ECO

Extended commitment ordering (ECO; (Raz 1993a)) is a generalization of CO that guarantees global serializability as well. It utilizes information about transaction being local (i.e., confined to a single transactional object) to provide more concurrency. With ECO, local transactions do not need to obey the CO rule; global transaction (i.e., not local) obey a similar, generalized rule. As CO it is not blocking, and can be integrated seamlessly with any relevant concurrency control mechanism.

• MVCO

Multi-version commitment ordering (MVCO; (Raz 1993b)) is a generalization of CO that guarantees global serializability as well. It utilizes multiple versions of data to provide more concurrency. It allows implementations where read-only transactions do not block, or being blocked by updaters (read-write transactions). As CO it is not blocking, and can be integrated seamlessly with any relevant concurrency control mechanism.

A new general theory of conflicts in multiversion concurrency control is introduced in (Raz 1993b) to define MVCO properly. Contrary to what is said in (Weikum and Vossen 2001, page 215) the new theory does not add any constraint, but rather newly defines and generalizes in a natural way the noncommutativity-based conflicts of the single-version common concurrency control theory. This theory has been later utilized by others (occasionally referencing Raz 1993b) to analyze Snapshot isolation (SI) in order to make it serializable. Also MVCO can make SI serializable (CO based snapshot isolation (COSI)) with a relatively low overhead, but this has not yet been tested and compared with the successfully tested SerializableSI (which is not MVCO compliant, and cannot participate in a CO distributed solution for global serializability).

• VO

Vote ordering (VO or Generalized CO (GCO); Raz 2009) is the property that contains CO and all its mentioned variants. It is the most general property that does not need concurrency control information distribution. It consists of local conflict serializability (by any mechanism, in its most general form, i.e., commutativity-based, including multi-versioning) and voting by precedence order (a vote ordering strategy).

CO distributed architecture

A distributed architecture for CO has been designed (Raz 1991c), which is an extension of the common architecture for the Two-phase commit protocol (2PC; and for an Atomic commitment protocol in general). The additional component in the architecture is the Commitment Order Coordinator (COCO), which is typically an integral part of a resource manager (e.g., Database system). The COCO orders the resource manager's local commit and voting events to enforce CO.

CO patents

Commitment ordering has been quite widely known inside the transaction processing and databases communities at Digital Equipment Corporation (DEC) since 1990. It has been under company confidentiality due to patenting processes of CO methods for guaranteeing both (local) Serializability and Global serializability which started in 1990 (Raz 1990a). Patents (Raz 1991a) for methods using CO and ECO were filed in 1991 and granted in 1996, and using MVCO filed in 1993 and granted in 1997. CO was disclosed outside of DEC by lectures and technical reports' distribution to tens of database researches in May 1991, immediately after its first patent filing.

A unique and novel element in the CO technique and its patents, besides ordering commit events, is the utilization of the atomic commitment protocol (ACP) voting mechanism to break global cycles (span two or more transactional objects) in the conflict graph, for guaranteeing global serializability. Also locking based global deadlocks are resolved automatically by the same mechanism. This allows effective implementations of distributed CO, while allowing any, uninterrupted transaction operations scheduling, without any conflict information distribution (e.g., by locks, timestamps, tickets), and without any additional, artificial transaction access operations (e.g., "take timestamp" or "take ticket"), which typically result in additional, artificial conflicts that reduce concurrency.

Enhanced theory of CO

An enhanced theory of CO, briefly summarized in (Raz 2009), has been developed by Yoav Raz later, after the CO publication in the early 1990s. The enhanced theory does not provide new results about CO but rather allows a clearer formal presentation of the CO subject and techniques. This theory is utilized in the Wikipedia articles Commitment ordering and Serializability, as well as in this article above. Several new terms are introduced by the enhanced theory:

• A unified theory of conflicts: The terms Materialized conflict and Non-materialized conflict are used for conflicts with other transactions. A conflict may occur when a transaction requests (invokes) access to a database object already accessed by another transaction (when access operations are not commutative; the common theory uses the term "conflict" only for a materialized one).
• Augmented conflict graph, which is the graph of all conflicts, the union of the (regular) conflict graph and the reversed-edge (regular) wait-for graph.
• Vote ordering strategy for the term $CD^{3}C$ in (Raz 1992), meaning voting on (global) transactions in a chronological order compatible with the local precedence order of respective transactions.
• Voting-deadlock for a deadlock in the atomic commitment protocol (ACP) that blocks and prevents voting (a deadlock situation described in (Raz 1992) and other CO articles without using this name).
• Vote ordering (VO or Generalized CO (GCO)) is the property that contains CO and all its mentioned variants. It is the most general property that does not need concurrency control information distribution. It consists of local conflict serializability (by any mechanism, in its most general form, i.e., commutativity-based, including multi-versioning) and voting by precedence order (a vote ordering strategy).

Main CO results

1. SS2PL implies CO
2. CO implies Serializability
3. Local CO implies Global serializability, even when utilizing local concurrency information only (by using voting deadlocks)
4. Locking based global deadlocks are resolved automatically (using voting deadlocks)
5. General, generic algorithms for CO, both local and global, for guaranteeing Global serializability while maintaining object autonomy (i.e., without local concurrency control information distribution; Atomic commitment protocol (ACP) is utilized instead; patented)
6. Distributed atomic commitment protocol based architecture for CO
7. A method for transforming any local concurrency control mechanism to be CO compliant, without interfering with transaction operations scheduling, for participating in a distributed algorithm for Global serializability (patented)
8. Local CO is a necessary condition for guaranteeing Global serializability when using autonomous resource managers (CO is optimal)
9. SCO locking mechanism provides shorter average transaction duration than that of SS2PL, and thus better concurrency and throughput; Usually SS2PL can be converted to SCO in a straightforward way.
10. Generalizations of CO for better concurrency by using additional information: ECO and MVCO, with main results very similar to CO (e.g., also ECO and MVCO are necessary conditions for global serializability (optimal) across autonomous resource managers within their respective defined levels of information, "knowledge"; both are not blocking, and can be integrated seamlessly with any relevant concurrency control mechanisms; related methods patented)
11. New theory of conflicts in multiversion concurrency control (enhancement of previous multi-version theories) in order to define MVCO
12. CO variants inter-operate transparently, guaranteeing Global serializability and automatic global deadlock resolution in a mixed distributed environment with different variants
13. Enhanced newer theory of CO (Augmented conflict graph based)

Later utilization of CO

CO has been referenced in multiple research articles, patents and patents pending. The following are examples of CO utilization.

An object-oriented extensible transaction management system

(Xiao 1995), a Ph.D. Thesis at the University of Illinois at Urbana-Champaign, is the first known explicit description of CO utilization (based on Raz 1992) in a (research) system to achieve Global serializability across transactional objects.

Semi-optimistic database scheduler

(Perrizo and Tatarinov 1998) presents a database scheduler, described as "semi-optimistic," which implements Strict CO (SCO; Raz 1991b). (Raz 1992) is quoted there multiple times (however (Raz 1991b), which has introduced SCO, is not; this publication appeared only as a DEC technical report). Both SCO and SS2PL provide both CO and Strictnes (which is utilized for effective database recovery from failure). SCO does not block on read-write conflicts (unlike SS2PL; possibly blocking on commit instead), while blocking on the other conflict types (exactly as SS2PL), and hence the term "semi-optimistic." As a result SCO provides better concurrency than SS2PL which blocks on all conflict types (see Strict CO).

Transactional processes

Transactional processes are processes that cooperate within atomic transactions. The solutions given in articles for imposing Global serializability across them are completely based on CO. (Schuldt et al. 1999) also demonstrates the utilization of CO in the product SAP R/3, the former name of the main Enterprise Resource Planning (ERP) software product of SAP AG.

Only (Schuldt et al. 2002) references (Raz 1992), but all the other articles, even later ones, do not reference the CO work, e.g., (Haller et al. 2005). Early articles use the name "Commit-order-serializability" for CO, e.g., (Schuldt et al. 1999). Many articles provide only a description of a CO algorithm without using the CO name, or using another name. E.g., (Haller et al. 2005) uses the name "decentralized serialization graph protocol" (DSGT protocol) for an implementation of CO. The protocol is described there (Ibid, page 29) as follows:

"In contrast, each transaction owns a local serialization graph which comprises the conflicts in which the transaction is involved. Essentially, the graph contains at least all conflicts that cause the transaction to be dependent on other transactions. This partial knowledge is sufficient for transactions to decide whether they are allowed to commit. Note that a transaction can only commit after all transactions on which it depends have committed. ...It is important to note that our system model does not require a component that maintains a global serialization graph."

It is obvious that CO is enforced, by its definition. The quote above fits exactly the description of the CO algorithm in (Raz 1992).

In a distributed environment a voting mechanism is a must in order to reach consensus on whether to commit or abort a distributed transaction (i.e., an atomic commitment protocol mechanism). No such mechanism is explicitly mentioned. With such mechanism voting deadlocks occur and typically resolved by the same mechanism. Such automatic Global deadlock resolution is not noticed, and the utilization of known dedicated methods for deadlock resolution is described there. The related articles on transactional processes which use CO are unaware of the possibility of a voting deadlock in case of transactions' local precedence orders incompatibility, a fundamental misunderstanding of the CO mechanism, and thus their arguments for correctness are incorrect (and they do not rely on already proven CO results).

Tolerating byzantine faults in transaction processing systems using commit barrier scheduling

CO has been utilized in a work on fault tolerance in transactional systems with replication (Vandiver et al. 2007, page 14):

"The first two rules are needed for correctness. The query ordering rule ensures that each individual transaction is executed properly. The commit-ordering rule ensures that secondaries serialize transactions in the same order as the primary."

The CO work is not referenced there.

Middleware Architecture with Patterns and Frameworks

CO is described in (Krakowiak 2007, page 9-15, Distributed transactions) as follows:

"...In addition to commitment proper, an atomic commitment protocol can be used for concurrency control, through a method called commitment ordering [Raz 1992]. Atomic commitment is therefore a central issue for distributed transactions..."

Grid computing, Cloud computing, and Re:GRIDiT

Re:GRIDiT (e.g., (Voicu et al. 2009a), (Voicu and Schuldt 2009b)) is an approach to support transaction management with data replication in the Grid and the Cloud. This approach extends the DSGT protocol approach of (Haller et al. 2005) mentioned above, which utilizes Commitment ordering (CO). The following are quotes from (Voicu and Schuldt 2008) which provide details on Re:GRIDiT:

"Our approach extends and generalizes the approaches presented in [ 5 ]... In this paper we define Re:GRIDiT, a transaction protocol for replicated Grid data, that generalizes the approach proposed in [ 5 ] by extending it to support replication."

(page 4; [ 5 ] is (Haller et al. 2005) which implements the DSGT protocol mentioned above)

"3. The commit phase: A transaction t in the commit phase has sufficient knowledge to deduce from its own local serialization graph that it is safe to commit. This is the case when it does not depend on any active transaction, i.e., when there is no incoming edge to t in the serialization graph of t..."

(page 9)

The second quote describes the CO algorithm in (Raz 1992), and it is obvious that Re:GRIDiT is based on CO.

An explicit characterization of CO appears in (Voicu and Schuldt 2009c), another article on Re:GRIDiT:

"Through our protocol a globally serializable schedule is produced (although no central scheduler exists and thus no schedule is materialized in the system) [ 24 ]. Moreover, the update transactions' serialization order is their commit order."

(page 207; [ 24 ] is (Voicu and Schuldt 2008))

Re:GRIDiT utilizes an optimistic version of CO. It uses internal system local sub-transactions for replication, which makes replication for high availability transparent to a user. Replication is done within the boundaries of each write transaction. Such write transaction turns into a "super-transaction" with replicating local sub-transactions. The approach does not suggest to use an external atomic commitment protocol, but rather uses an integrated solution, which must include some form of atomic commitment protocol to achieve atomicity of distributed transactions (however no such protocol is explicitly mentioned, and neither voting and voting deadlocks which are crucial for the CO solution). No benefit in an integrated atomic commitment seems to exist. Also no concurrency control alternatives for different transactional objects in the Grid/Cloud are suggested, contrary to a general CO solution, which allows any CO compliant transactional object (i.e., using any CO variant optimal for the object) to participate in the Grid/Cloud environment. Automatic Global deadlock resolution, which results from the utilization of CO with any atomic commitment protocol over data partitioned in the Grid/Cloud, is not noticed, and the utilization of known dedicated methods for deadlock resolution is described there. The related articles on Re:GRIDiT which use CO are unaware of the possibility of a voting deadlock in case of transactions' local precedence orders incompatibility, a fundamental misunderstanding of the CO mechanism, and thus their arguments for correctness are incorrect (and they do not rely on already proven CO results).

Performance comparison between Re:GRIDiT and SS2PL/2PC (the de facto standard for global serializability; they use the name Strict 2PL for SS2PL) is done there with resulting advantage of Re:GRIDiT (while running the same transaction loads, i.e., the same transaction mixes of the same respective transactions). This comparison is not quite meaningful since Re:GRIDiT comprises an optimistic version of CO, while SS2PL is the most constraining, blocking variant of CO. It is well known that for some transaction loads optimistic is better, while for other loads 2PL would be better. For a meaningful comparison between Re:GRIDiT and a common parallel CO approach, OCO/2PC (OCO is Optimistic CO; see above) should be used instead, and then it can be seen whether the integrated solution of Re:GRIDiT provides any advantage over a straightforward implementation of OCO/2PC (now correctly, a comparison of mechanism overhead only; transaction data access operation blocking should not happen with any of the two solutions, if Re:GRIDiT properly implements an optimistic version of CO, and OCO/2PC with data replication is implemented effectively).

The Re:GRIDiT articles neither reference CO articles nor mention CO, though most of the Re:GRIDiT authors have referenced CO in their previous articles.

In (Voicu et al. 2010) the Re:FRESHiT mechanism, an enhancement of the replication mechanism of RE:GRIDiT, is discussed. Here replication is separated from concurrency control, and no specific concurrency control mechanism is mentioned.

Concurrent programming and Transactional memory

With the proliferation of Multi-core processors CO also has been increasingly utilized in Concurrent programming, Transactional memory, and especially in Software transactional memory (STM) for achieving serializability optimistically by "commit order" (e.g., Ramadan et al. 2009, Zhang et al. 2006, von Parun et al. 2007). Numerous related articles and patents utilizing "commit order" have already been published.

1. Zhang et al. 2006 is a US patent entitled "Software transaction commit order and conflict management" (which references CO US patent 5701480, Raz 1991a).

Its abstract part is the following:

"Various technologies and techniques are disclosed for applying ordering to transactions in a software transactional memory system. A software transactional memory system is provided with a feature to allow a pre-determined commit order to be specified for a plurality of transactions. The pre-determined commit order is used at runtime to aid in determining an order in which to commit the transactions in the software transactional memory system. A contention management process is invoked when a conflict occurs between a first transaction and a second transaction. The pre-determined commit order is used in the contention management process to aid in determining whether the first transaction or the second transaction should win the conflict and be allowed to proceed."

2. von Parun et al. 2007 explicitly uses the term "Commit ordering" and utilizes it for achieving serializability. E,g, (page 1):

"Moreover, IPOT inherits commit ordering from TLS, hence ordered transactions. The key idea is that ordering enables sequential reasoning for the programmer without precluding concurrency (in the common case) on a runtime platform with speculative execution."

3. Ramadan et al. 2009 uses the term "Commit order" (page 2) with respective formulation that follows (page 3):

"2.3 Dependence management The system tracks all dependences at the level of memory bytes or objects. The dependences are tracked as they arise during transaction execution. R→W and W→W dependences restrict commit order, while W→R restrict commit order and forward data from the active transaction. When data is forwarded, the destination transaction must restart if the source restarts or overwrites the memory location whose value was previously forwarded."

"...For each T, we keep track of earlier (T), the set of transactions that must commit before T can commit. We also keep track of notLater (T), the set of transactions that must commit or abort before T can commit. Intuitively, earlier (T) tracks the write-read dependence while notLater (T) tracks all the remaining types of dependences."

Comments:

1. To enforce optimistic CO some implementation of the Generic local CO algorithm in Raz 1992 needs to be utilized.
2. The patent abstract quoted above in 1 describes a general implementation of the Generic local CO algorithm with a pre-determined commit order (this falls into the category of "CO generic algorithm with real-time constraints").
3. In 3 above the union of the sets earlier (T) and notLater (T) is a special case of the set ABORT(T) in the Generic local CO algorithm.
4. No reference to the CO work is given in the references in 2, 3 above.

Local snapshot isolation with Global serializability

(Raz 1993b) has generalized CO to Multi-version CO (MVCO) by providing a general conflict theory for Multi-version concurrency control (MVCC). This conflict theory has allowed to define MVCO properly for the first time, and has shown that MVCO provides One-copy serializability (1SR) which is the generalization of serializability for multi-version concurrency control. It also has already been utilized to analyze Serializable snapshot isolation (SerializableSI). The following articles provide Global MVCO and thus Global 1SR for distributed systems with replication and local Snapshot isolation (SI):

1. (Bornea et al. 2011): "...When an update transaction commits, it creates a new version of the database, identified by a version number assigned by the certifier forming the global commit order."
2. (Jung et al. 2011): "...Although parallel updates allow different update ordering for remote writesets, appearing a violation of the uniform total order guarantee, a mapping table from a local TID to a global commit order preserves the correctness."

Though the Multi-version conflict theory above has been utilized and referenced by some of these articles' authors in the past in conjunction with SerializableSI (which is not MVCO compliant), the articles do not reference (Raz 1993b).

Comments:

1. (Raz 1993b) provides the only general definition (up to equivalent formulation) of Commit ordering for multi-version concurrency control (MVCC) that implies one copy serializability (1SR). This definition is utilized in the articles above. This definition is used for 1SR also in other articles (besides the above), e.g., in (Cahill et al. 2008), and explicitly outlined in (Fekete 2009).
2. In (Elnikety et al. 2006) the terms "commit order" and "commit ordering" are utilized with a meaning different from that in (Raz 1993b), and mentioned there multiple times. This article, about the Tashkent approach, deals with effectively achieving Generalized snapshot isolation (GSI) across replicated databases. While the theory in (Raz 1993b) defines three types of conflicts, (Elnikety et al. 2006) uses only one type, write-write conflict, and hence cannot achieve global serializability which (Bornea et al. 2011) and (Jung et al. 2011) above achieve. A better term to be used for the Tashkent approach is Partial commit ordering (PCO; vs. CO: ordering of commit events is needed only for transactions with write-write conflicts, and not for the other conflict types which CO requires as well). PCO automatically exists in every GSI (and SI) based database.
3. Unlike (Raz 1993b), other articles mentioned and referenced in this section (those that deal with distribution; all but one) distribute and ship conflict information. (Raz 1993b) avoids this for better scalability at the cost of possibly blocking and delaying voting in the atomic commitment protocol (ACP).

CO continues to be ignored in database texts

The CO techniques were invented in 1990-1 and have provided the only known scalable general Global serializability solution (no need in concurrency control information distribution which handicaps all other CO-noncomplying known methods). It also allows the effective distribution of all known concurrency control methods and achieves Global serializability also in a heterogeneous environment with different concurrency control methods. Though CO ("Commitment ordering" or "Commit ordering") and its patents have already been referenced until 2009 in tens of academic articles and tens of patents (e.g., can be found by Google scholar and Google patents by patent numbers), CO has been ignored in major relevant academic texts that have intended to provide updated coverage of the database concurrency control fundamentals and more. Here are examples since 2009:

• Liu, Ling; Özsu, M. Tamer (Eds.) (2009): Encyclopedia of Database Systems, 1st Edition, 3752 pages, Springer, ISBN 978-0-387-49616-0

An encyclopedia on a subject is usually exhaustive, covering all aspects of the subject. Concurrency control is thoroughly covered. CO, an important concept for database concurrency control which emerged publicly 18 years prior to this book, is missing.

• Avi Silberschatz, Henry F Korth, S. Sudarshan (2010): Database System Concepts, 6th Edition, McGraw-Hill, ISBN 0-07-295886-3

Two-level serializability which does not guarantee Global serializability (but rather comprises a relaxed form of it) and relies on a centralized component (clear major disadvantages) is described in detail and proposed as a distributed concurrency control method. No evidence is given for performance or any other advantage over the unmentioned CO which does not have these disadvantages.

• Özsu, M. Tamer, Valduriez, Patrick (2011): Principles of Distributed Database Systems, Third Edition, Springer, ISBN 978-1-4419-8833-1, Chapter 11: Distributed Concurrency Control, Pages 361-403

This chapter has not been changed much (if at all) since the book's 1999 second edition. The old, traditional concurrency control methods which do not scale in distributed database systems, the subject of the book, are described (but not the unmentioned CO which scales, and thus is the most relevant serializability method for distributed databases).

See also

• Serializability
• Commitment ordering
• Global serializability

References

• Abraham Silberschatz, Michael Stonebraker, and Jeffrey Ullman (1991): "Database Systems: Achievements and Opportunities", Communications of the ACM, Vol. 34, No. 10, pp. 110-120, October 1991, DBLP journals/cacm/SilberschatzSU91, doi:10.1145/125223.125272

• Gerhard Weikum, Gottfried Vossen (2001): Transactional Information Systems, Elsevier, ISBN 1-55860-508-8

• Liu, Ling; Özsu, M. Tamer (Eds.) (2009): Encyclopedia of Database Systems, 1st Edition, 3752 pages, Springer, ISBN 978-0-387-49616-0

• Avi Silberschatz, Henry F Korth, S. Sudarshan (2010): Database System Concepts, 6th Edition, McGraw-Hill, ISBN 0-07-295886-3

• Philip A. Bernstein, Eric Newcomer (2009): Principles of Transaction Processing, 2nd Edition, Morgan Kaufmann (Elsevier), ISBN 978-1-55860-623-4

Dynamic atomicity

• William Edward Weihl (1984): "Specification and Implementation of Atomic Data Types", Ph.D. Thesis, MIT-LCS-TR-314, March 1984, MIT, LCS lab.

• William Edward Weihl (1988): "Commutativity-based concurrency control for abstract data types", Proceedings of the Twenty-First Annual Hawaii International Conference on System Sciences, Software Track, January 1988, Volume 2, pp. 205-214, Kailua-Kona, HI, USA, ISBN 0-8186-0842-0 (also MIT/LCS/TM-367, August 1988, and IEEE Transactions on Computers 37(12) December 1988)

• Alan Fekete, Nancy Lynch, Michael Merritt, William Weihl (1988): Commutativity-based locking for nested transactions (PDF) MIT, LCS lab, Technical report MIT/LCS/TM-370, August 1988.

• William Edward Weihl (1989): "Local atomicity properties: modular concurrency control for abstract data types", ACM Transactions on Programming Languages and Systems (TOPLAS), Volume 11, Issue 2, April 1989, pp. 249 - 282, ISSN:0164-0925

• Alan Fekete, Nancy Lynch, Michael Merritt, William Weihl (1990): "Commutativity-based locking for nested transactions" (PDF), Journal of Computer and System Sciences (JCSS), Volume 41 Issue 1, pp 65-156, August 1990, Academic Press, Inc. doi:10.1016/0022-0000(90)90034-I.

• Nancy Lynch, Michael Merritt, William Weihl, Alan Fekete (1993): Atomic Transactions In Concurrent and Distributed Systems, Morgan Kauffman (Elsevier), August 1993, ISBN 978-1-55860-104-8, ISBN 1-55860-104-X

Analogous execution and serialization order

• Dimitrios Georgakopoulos, Marek Rusinkiewicz (1989): "Transaction Management in Multidatabase Systems", Technical Report #UH-CS-89-20, September 1989, University of Houston, Department of Computer Science.

• Yuri Breitbart, Dimitrios Georgakopoulos, Marek Rusinkiewicz, Abraham Silberschatz (1991): "On Rigorous Transaction Scheduling", IEEE Transactions on Software Engineering (TSE), September 1991, Volume 17, Issue 9, pp. 954-960, ISSN: 0098-5589

• Yuri Breitbart, Abraham Silberschatz (1992): "Strong recoverability in multidatabase systems", Second International Workshop on Research Issues on Data Engineering: Transaction and Query Processing, (RIDE-TQP), pp. 170-175, 2–3 February 1992, Tempe, AZ, USA, ISBN 0-8186-2660-7

Commitment ordering

• Yoav Raz (1990a): On the Significance of Commitment Ordering - Call for patenting, Memorandum, Digital Equipment Corporation, November 1990.

• Yoav Raz (1990b): "The Principle of Commitment Ordering, or Guaranteeing Serializability in a Heterogeneous Environment of Multiple Autonomous Resource Managers Using Atomic Commitment", Technical Report DEC-TR 841, Digital Equipment Corporation, November 1990 (1995 last version of the technical report can be found here).

• Yoav Raz (1991a): US patents 5,504,899 (ECO) 5,504,900 (CO) 5,701,480 (MVCO)

• Yoav Raz (1991b): "Locking Based Strict Commitment Ordering, or How to improve Concurrency in Locking Based Resource Managers", Technical Report DEC-TR 844, Digital Equipment Corporation, December 1991.

• Yoav Raz (1991c): "The Commitment Order Coordinator (COCO) of a Resource Manager, or Architecture for Distributed Commitment Ordering Based Concurrency Control", DEC-TR 843, Digital Equipment Corporation, December 1991.

• Yoav Raz (1992): "The Principle of Commitment Ordering, or Guaranteeing Serializability in a Heterogeneous Environment of Multiple Autonomous Resource Managers Using Atomic Commitment", Proceedings of the Eighteenth International Conference on Very Large Data Bases (VLDB), pp. 292-312, Vancouver, Canada, August 1992, DBLP conf/vldb/Raz92 (an abridged version of (raz 1990b)).

• Yoav Raz (1993a): "Extended Commitment Ordering or Guaranteeing Global Serializability by Applying Commitment Order Selectivity to Global Transactions", Proceedings of the Twelfth ACM Symposium on Principles of Database Systems (PODS), Washington, DC, pp. 83-96, May 1993 (also DEC-TR 842, November 1991).

• Yoav Raz (1993b): "Commitment Ordering Based Distributed Concurrency Control for Bridging Single and Multi Version Resources", Proceedings of the Third IEEE International Workshop on Research Issues on Data Engineering: Interoperability in Multidatabase Systems (RIDE-IMS), Vienna, Austria, pp. 189-198, April 1993 (also DEC-TR 853, July 1992).

• Yoav Raz (1994): "Serializability by Commitment Ordering." Information Processing Letters (IPL), Volume 51, Number 5, pp. 257-264, September 1994 (Received August 1991), DBLP journals/ipl/Raz94, WD Q29036205, doi:10.1016/0020-0190(94)90005-1.

• Yoav Raz (2009): Theory of Commitment Ordering - Summary GoogleSites - Site of Yoav Raz. Retrieved 1 Feb, 2011.

Later utilization of CO

An object-oriented extensible transaction management system

• Lun Xiao (1995): An object-oriented extensible transaction management system, Ph.D. Thesis, University of Illinois at Urbana-Champaign, 1995.

Semi-optimistic database scheduler

• William Perrizo, Igor Tatarinov (1998): "A Semi-Optimistic Database Scheduler Based on Commit Ordering" (PDF), 1998 Int'l Conference on Computer Applications in Industry and Engineering, pp. 75-79, Las Vegas, November 11, 1998.

Transactional processes

• Heiko Schuldt, Hans-Jörg Schek, and Gustavo Alonso (1999): "Transactional Coordination Agents for Composite Systems", In Proceedings of the 3rd International Database Engineering and Applications Symposium (IDEAS’99), IEEE Computer Society Press, Montrteal, Canada, pp. 321–331.

• Heiko Schuldt, Gustavo Alonso, Catriel Beeri, Hans-Jörg Schek (2002): "Atomicity and isolation for transactional processes", ACM Transactions on Database Systems (ACM TODS), 27(1): pp. 63-116, 2002.

• Klaus Haller, Heiko Schuldt, Can Türker (2005): "Decentralized coordination of transactional processes in peer-to-peer environments", Proceedings of the 2005 ACM CIKM, International Conference on Information and Knowledge Management, pp. 28-35, Bremen, Germany, October 31 - November 5, 2005, ISBN 1-59593-140-6

Tolerating byzantine faults in transaction processing systems using commit barrier scheduling

• Ben Vandiver, Hari Balakrishnan, Barbara Liskov, Sam Madden (2007): "Tolerating byzantine faults in transaction processing systems using commit barrier scheduling" (PDF), Proceedings of twenty-first ACM SIGOPS symposium on Operating systems principles (SOSP '07), ACM New York ©2007, ISBN 978-1-59593-591-5, doi:10.1145/1294261.1294268

Middleware Architecture with Patterns and Frameworks

• Sacha Krakowiak (2007): Middleware Architecture with Patterns and Frameworks (2009 PDF), eBook, 427 pages, ScientificCommons, Retrieved May 25, 2011.

Grid computing, Cloud computing, and Re:GRIDiT

• Laura Voicu and Heiko Schuldt (2008): "The Re:GRIDiT Protocol: Correctness of Distributed Concurrency Control in the Data Grid in the Presence of Replication", Technical Report CS-2008-002 Department of Computer Science, DBIS UNI BASEL, 2008/9.

• Laura Cristiana Voicu, Heiko Schuldt, Fuat Akal, Yuri Breitbart, Hans Jörg Schek (2009a): "Re:GRIDiT – Coordinating Distributed Update Transactions on Replicated Data in the Grid", 10th IEEE/ACM International Conference on Grid Computing (Grid 2009), Banff, Canada, 2009/10.

• Laura Cristiana Voicu and Heiko Schuldt (2009b): "How Replicated Data Management in the Cloud can benefit from a Data Grid Protocol — the Re:GRIDiT Approach", Proceedings of the 1st International Workshop on Cloud Data Management (CloudDB 2009), Hong Kong, China, 2009/11.

• Laura Cristiana Voicu and Heiko Schuldt (2009c): "Load-Aware Dynamic Replication Management in a Data Grid", On the Move to Meaningful Internet Systems: OTM 2009 Workshops Proceedings, Vilamoura, Portugal, November 1–6, 2009, pp. 201-218, Lecture Notes in Computer Science Vol. 5872, Springer, ISBN 978-3-642-05289-7.

• Laura Cristiana Voicu, Heiko Schuldt, Yuri Breitbart, Hans Jörg Schek (2010): "Flexible Data Access in a Cloud based on Freshness Requirements", Proceedings of the 3rd International Conference on Cloud Computing (IEEE CLOUD 2010), Miami, Florida, USA, 2010/7.

Concurrent programming and Transactional memory

• Hany E. Ramadan, Indrajit Roy, Maurice Herlihy, Emmett Witchel (2009): "Committing conflicting transactions in an STM" (PDF) Proceedings of the 14th ACM SIGPLAN symposium on Principles and practice of parallel programming (PPoPP '09), ISBN 978-1-60558-397-6

• Lingli Zhang, Vinod K.Grover, Michael M. Magruder, David Detlefs, John Joseph Duffy, Goetz Graefe (2006): Software transaction commit order and conflict management United States Patent 7711678, Granted 05/04/2010.

• Christoph von Praun, Luis Ceze, Calin Cascaval (2007) "Implicit Parallelism with Ordered Transactions" (PDF), Proceedings of the 12th ACM SIGPLAN symposium on Principles and practice of parallel programming (PPoPP '07), ACM New York ©2007, ISBN 978-1-59593-602-8 doi:10.1145/1229428.1229443

Local snapshot isolation with Global serializability

• Mihaela A. Bornea, Orion Hodson, Sameh Elnikety, Alan Fekete (2011): "One-Copy Serializability with Snapshot Isolation under the Hood" (PDF), International Conference on Data Engineering (ICDE 2011), Poster session, Hanover, April 11-16, 2011.

• Hyungsoo Jung, Hyuck Han, Alan Fekete, Uwe Roehm (2011): "Serializable Snapshot Isolation for Replicated Databases in High Update Scenarios" (PDF), To appear in VLDB 2011, Seattle Washington, August 29 - September 3, 2011.

• Michael J. Cahill, Uwe Röhm, Alan D. Fekete (2008) "Serializable isolation for snapshot databases", Proceedings of the 2008 ACM SIGMOD international conference on Management of data, pp. 729–738, ISBN 978-1-60558-102-6 (SIGMOD 2008 best paper award).

• Alan Fekete (2009): "Snapshot Isolation and Serializable Execution", Presentation, Page 4 (slide 14), 2009, The university of Sydney (Australia). Retrieved 20 September 2011.

• Sameh Elnikety, Steven Dropsho, Fernando Pedone (2006): "Tashkent: uniting durability with transaction ordering for high-performance scalable database replication" (PDF), Proceedings of the 1st ACM SIGOPS/EuroSys European Conference on Computer Systems 2006 (EuroSys '06), ISBN 1-59593-322-0, doi: 10.1145/1217935.1217947 (also newsletter: ACM SIGOPS Operating Systems Review - Proceedings of the 2006 EuroSys conference Volume 40 Issue 4, October 2006, ACM, New York, NY, USA, doi: 10.1145/1218063.1217947)

External links

• Yoav Raz's Commitment ordering page