Version: 18 November, 2011
Earlier versions appeared with the name The 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:
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:
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.
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).
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:
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:
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.
Commitment ordering (CO) has evolved in three, seemingly initially independent, threads of development:
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:
These evolvement threads are described in what follows with respective summaries of main results relevant to CO.
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.
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):
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.
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 CD3C 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).
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):
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:
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:
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 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 dynamic atomicity and CO. 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).
(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 CD3C 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.
and Strong recoverability
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.
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 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 article: Commitment ordering
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.
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.
(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).
(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 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:
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.
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.
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:
CO has been referenced in multiple research articles, patents and patents pending. The following are examples of CO utilization.
(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.
(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 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:
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).
The CO work is not referenced there.
CO is described in (Krakowiak 2007, page 9-15, Distributed transactions) as follows:
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:
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:
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.
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.
(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):
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).
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: