The History of Commitment Ordering

In databases and transaction processing (transaction management), Commitment ordering (or Commit ordering; CO) is a Serializability technique, 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). This problem has been considered open until the public introduction of the CO solution in May 1991. 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),
  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).

The originally defined DA is close to CO, but is strictly contained in CO. Only in (Lynch et al. 1993) it is defined to be equivalent to CO.

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 (but this should not be confused with the CO algorithmic techniques and theoretical results; no such techniques and results have been proposed for STRC).

All three development threads have converged at definitions of schedule properties 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 observing that local 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 general algorithms for CO and (patented; (Raz 1991a)) 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 information (Raz 1993a,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 (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 (and resulting distributed serializability), while allowing any, uninterrupted transaction operations scheduling, without any conflict information distribution (e.g., local conflicts, 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.

CO has been utilized extensively since 1997 in numerous works within the subject of Transactional processes (e.g., Schuldt et al. 2002). 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)), an approach to Grid computing and Cloud computing with data replication.

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 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), disclosed publicly in May 1991 in lectures and publication submission and distribution to database researchers, has provided a general solution to the problem. More details 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 description of the CO technique. Also the bibliographic notes there are inaccurate, since the original DA (referred to in the quote 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, completely 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). Strangely, some theorems AbOUT CO given in the book are significantly weaker than what implied by the CO work, and miss its essence.

Such 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 years after its public introduction in 1991 (see Quotes 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 new editions of two database textbooks, in 2009 and 2010, that deal with distributed concurrency control and global serializability, and resort to less effective than CO methods (see benefits of CO in Global serializability).

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 does not use locks.
  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."

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),
  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).

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. It uses 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 described and utilized in numerous articles later, e.g., (Weihl 1988,1989), and a book (Lynch et al. 1993).

DA is strictly contained in CO

While DA has not been originally defined as CO, 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) operation of the second transaction (Weihl 1989, page 264), i.e., an additional restriction over CO; see also footnote in the last version of (Raz 1990b, page 5)).

Local DA implies global serializability

With such 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 voting strategy 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 (Lynch et al. 1993, page 201) is equivalent to the definition of CO, using only commit events order (but with no reference to (Raz 1990b,1992)). Since atomic commitment protocol and voting are not mentioned in (Lynch et al. 1993), it seems that a link is missing there (a voting strategy that enforces commit order, referred to as CD3C in (Raz 1990b,1992); see also Enforcing global CO in Commitment ordering, and section on DA optimality below) in proving that local DA implies global serializability, when using the new DA (CO) definition. Without such mechanism (atomic commitment protocol and a voting strategy), a typically expensive global entity that maintains global precedence order and resulting global commit order is needed in a multi-object environment, which violates the assumed object autonomy (object concurrency control information independence and isolation; no global precedence order is known). When compromising autonomy, the major benefit of effective distributed CO, i.e., no concurrency control information distribution, is lost.

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 voting strategy, 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 voting strategy (without the additional constraint), which is CO.

Main DA results

Comment: DA here is the original DA, not CO.

  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. DA is an optimal property (in a formal model without voting in atomic commitment protocol; CO, which strictly contains DA, is the optimal property in a model where voting exists)

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.

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. 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 voting strategy). Neither atomic commitment protocol nor voting 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

Early versions of (Raz 1990b) reference neither DA, nor STRC, but later versions and other CO articles reference both.

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 erronous 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 ABORTCO(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. DA, which was already well published and known in its research domain in the beginning of 1990, is more general than SEP mentioned above (and SS2PL), but less general than CO. DA has no known published general algorithm.

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 voting 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 voting 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 70ies. 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 70ies. 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 80ies (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 theory of conflicts in multiversion concurrency control is introduced to define MVCO properly. An identical theory has been later utilized by others 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).

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 granted in 1996, and using MVCO in 1997. CO was disclosed outside of DEC by lectures and technical reports' distribution to 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.

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 is utilized instead)
  6. 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
  7. Local CO is a necessary condition for guaranteeing Global serializability when using autonomous resource managers (CO is optimal)
  8. SCO locking mechanism which provides shorter average transaction duration than that of SS2PL, and thus better concurrency; can be converted to from an SS2PL one in a straightforward way
  9. 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.)
  10. New theory of conflicts in multiversion concurrency control in order to define MVCO
  11. CO variants inter-operate transparently, guaranteeing Global serializability and automatic global deadlock resolution in a mixed distributed environment with different variants

Later utilization of CO

CO has been quoted in multiple research articles and utilized in numerous patents and patents pending. The following are examples of CO utilization.

Semi-optimistic database scheduler

(Perrizo and Tatarinov 1999) presents a database scheduler, described as "semi-optimistic," which implements Strict CO (SCO). (Raz 1992) is quoted there multiple times, however (Raz 1991b), which introduced SCO, probably has been unknown to the authors. 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 (possibly blocking on commit instead), while blocking on the other types, 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). 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).

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 provides 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.

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. 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.

See also

  • Serializability
  • Commitment ordering
  • Global serializability
  • User comments in Talk:Global serializability#Are the experts experts? which have triggered this article.

References

Dynamic atomicity

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 (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 (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.

Later utilization of CO

Semi-optimistic database scheduler

Transactional processes

Grid computing, Cloud computing, and Re:GRIDiT

ja:コミットメント順序付けの歴史