Global Serializability

In concurrency control of databases, transaction processing (transaction management), and other transactional distributed applications, Global serializability (or Modular serializability) is a property of a global schedule of transactions. A global schedule is the unified schedule of all the individual database (and other transactional object) schedules in a multidatabase environment (e.g., federated database). Complying with global serializability means that the global schedule is serializable, has the serializability property, while each component database (module) has a serializable schedule as well. In other words, a collection of serializable components provides overall system serializability, which is usually incorrect. A need in correctness across databases in multidatabase systems makes global serializability a major goal for global concurrency control (or modular concurrency control). With the proliferation of the Internet, Cloud computing, Grid computing, and small, portable, powerful computing devices (e.g., smartphones), as well as increase in systems management sophistication, the need for atomic distributed transactions and thus effective global serializability techniques, to ensure correctness in and among distributed transactional applications, seems to increase.

In a federated database system or any other more loosely defined multidatabase system, which are typically distributed in a communication network, transactions span multiple (and possibly distributed) databases. Enforcing global serializability in such system, where different databases may use different types of concurrency control, is problematic. Even if every local schedule of a single database is serializable, the global schedule of a whole system is not necessarily serializable. The massive communication exchanges of conflict information needed between databases to reach conflict serializability globally would lead to unacceptable performance, primarily due to computer and communication latency. Achieving global serializability effectively over different types of concurrency control has been open for several years. Commitment ordering (or Commit ordering; CO), a serializability technique publicly introduced in 1991 by Yoav Raz from Digital Equipment Corporation (DEC), provides an effective general solution for global (conflict) serializability across any collection of database systems and other transactional objects, with possibly different concurrency control mechanisms. CO does not need the distribution of conflict information, but rather utilizes the already needed (unmodified) atomic commitment protocol messages without any further communication between databases. It also allows optimistic (non-blocking) implementations. CO generalizes Strong strict two phase locking (SS2PL), which in conjunction with the Two-phase commit (2PC) protocol is the de facto standard for achieving global serializability across (SS2PL based) database systems. As a result CO compliant database systems (with any, different concurrency control types) can transparently join existing SS2PL based solutions for global serializability. The same applies also to all other multiple (transactional) object systems that use atomic transactions and need global serializability for correctness (see examples above; nowadays such need is not smaller than with database systems, the origin of atomic transactions).

The most significant aspects of CO that make it a uniquely effective general solution for global serializability are the following:

1. Seamless, low overhead integration with any concurrency control mechanism, with neither changing any transaction's operation scheduling or blocking it, nor adding any new operation.
2. Heterogeneity: Global serializability is achieved across multiple transactional objects (e.g., database management systems) with different (any) concurrency control mechanisms, without interfering with the mechanisms' operations.
3. Modularity: Transactional objects can be added and removed transparently.
4. Autonomy of transactional objects: No need of conflict or equivalent information distribution (e.g., local precedence relations, locks, timestamps, or tickets; no object needs other object's information).
5. Scalability: With "normal" global transactions, computer network size and number of transactional objects can increase unboundedly with no impact on performance, and
6. Automatic global deadlock resolution.

All these aspects, except the first two, are also possessed by the popular SS2PL, which is a (constrained, blocking) special case of CO and inherits many of CO's qualities.