Commitment ordering

1986:; Algorithm 4.1) is an algorithm independent of implementation details that enforces exactly the CO property. It does not block data access (nonblocking) and consists of aborting a certain set of transactions (only if needed) upon committing a transaction. It aborts a (uniquely determined at any given time) minimal set of other undecided (neither committed, nor aborted) transactions that run locally and can cause serializability violation in the future (can later generate cycles of committed transactions in the conflict graph; this is the ABORT set of a committed transaction T; after committing T no transaction in ABORT at commit time can be committed, and all of them are doomed to be aborted). This set consists of all undecided transactions with directed edges in the conflict graph to the committed transaction. The size of this set cannot increase when that transaction is waiting to be committed (in the ready state: processing has ended,) and typically decreases in time as its transactions are being decided. Thus, unless 4998:(multi-core) to reach its needed data, with additional incurred overhead. Thus, as the number of cores increases, the amount and type of data assigned to each core should be balanced according to data usage, so a core is neither overwhelmed to become a bottleneck, nor becoming idle too frequently and underutilized in a busy system. Another consideration is putting in a same core partition all the data that are usually accessed by a same transaction (if possible), to maximize the number of local transactions (and minimize the number of global, distributed transactions). This may be achieved by occasional data re-partition among cores based on load balancing (data access balancing) and patterns of data usage by transactions. Another way to considerably mitigate this downside is by proper physical data replication among some core partitions in a way that read-only global transactions are possibly (depending on usage patterns) completely avoided, and replication changes are synchronized by a dedicated commit mechanism. 5487:)). Like for CO such a set is time dependent, and becomes empty eventually. Practically, almost in all needed implementations a transaction should be committed only when the set is empty (and no set optimization is applicable). The local (to the database) concurrency control mechanism (separate from the ECO algorithm) ensures that local cycles are eliminated (unlike with CO, which implies serializability by itself; however, practically also for CO a local concurrency mechanism is utilized, at least to ensure Recoverability). Local transactions can be always committed concurrently (even if a precedence relation exists, unlike CO). When the overall transactions' local partial order (which is determined by the local conflict graph, now only with possible temporary local cycles, since cycles are eliminated by a local serializability mechanism) allows, also global transactions can be voted on to be committed concurrently (when all their transitively (indirect) preceding (via conflict) 5846:(SerializableSI), a low overhead modification of SI, provides good performance results versus SI, with only small penalty for enforcing serializability. A different method, by combining SI with MVCO (COSI), makes SI serializable as well, with a relatively low overhead, similarly to combining the generic CO algorithm with single-version mechanisms. Furthermore, the resulting combination, COSI, being MVCO compliant, allows COSI compliant database systems to inter-operate and transparently participate in a CO solution for distributed/global serializability (see below). Besides overheads also protocols' behaviors need to be compared quantitatively. On one hand, all serializable SI schedules can be made MVCO by COSI (by possible commit delays when needed) without aborting transactions. On the other hand, SerializableSI is known to unnecessarily abort and restart certain percentages of transactions also in serializable SI schedules. 2447:) that handles local sub-transactions (the distributed transaction's portion in a single location, e.g., network node), even if these data are accessed indirectly by other entities in the distributed system during a transaction (i.e., indirect access requires a direct access through a local sub-transaction). Thus recoverable data in a distributed transactional system are typically partitioned among transactional data managers. In such system, these transactional data managers typically comprise the participants in the system's atomic commitment protocol. If each participant complies with CO (e.g., by using SS2PL, or COCOs, or a combination; see above), then the entire distributed system provides CO (by the theorems above; each participant can be considered a separate transactional object), and thus (distributed) serializability. Furthermore: When CO is utilized together with an atomic commitment protocol also 1866:. The highest probability instance of such a rare event involves two transactions on two simultaneous opposite cycles. Such global cycles (deadlocks) overlap with local cycles that are resolved locally and are typically resolved by local mechanisms without involving atomic commitment. Formally it is also a global cycle, but practically it is local (portions of local cycles generate a global one; to see this, split each global transaction (node) to local sub-transactions (its portions confined each to a single database); a directed edge exists between transactions if an edge exists between any respective local sub-transactions; a cycle is local if all its edges originate from a cycle among sub-transactions of the same database, and global if not; global and local can overlap: the same cycle among transactions can result from several different cycles among sub-transactions, and be both local and global). 2019:, a single local cycle elimination mechanism, for both guaranteeing local serializability and handling locking based local deadlocks. Practically an additional concurrency control mechanism is always utilized, even solely to enforce recoverability. The generic CO algorithm does not affect the local data access scheduling strategy when it runs alongside any other local concurrency control mechanism. It affects only the commit order, and for this reason, it does not need to abort more transactions than those needed to be aborted for serializability violation prevention by any combined local concurrency control mechanism. At most, the net effect of CO may be a delay of commit events (or voting in a distributed environment), to comply with the needed commit order (but not more delay than its special cases, for example, SS2PL, and on average significantly less). 1931:) and resulting aborted transactions' re-executions are time-consuming, regardless of concurrency control used. If databases schedule transactions independently, global cycles are unavoidable (in a complete analogy to cycles/deadlocks generated in local SS2PL; with distribution, any transaction or operation scheduling coordination results in autonomy violation and is typically in substantial performance penalty). However, their likelihood can be made very low in many cases by implementing database and transaction design guidelines that reduce the number of conflicts involving a global transaction. This, primarily by properly handling hot spots (database objects with frequent access,) and avoiding conflicts by using commutativity when possible (e.g., when extensively using counters, as in finances, and especially multi-transaction 2105:). However, the COCO is typically an integral part of the database system. The COCO's functions are to vote to commit on ready global transactions (the processing has ended) according to the local commitment order, to vote to abort on transactions for which the database system has initiated an abort (the database system can initiate abort for any transaction, for many reasons), and to pass the atomic commitment decision to the database system. For local transactions (when can be identified), no voting is needed. For determining the commitment order, the COCO maintains an updated representation of the local conflict graph (or local augmented conflict graph for capturing also locking deadlocks) of the undecided (neither committed nor aborted) transactions as a data structure (e.g., utilizing mechanisms similar to 1797:(across two or more databases) in this graph generate voting-deadlocks. The graph's global cycles provide complete characterization for voting deadlocks and may include any combination of materialized and non-materialized conflicts. Only cycles of (only) materialized conflicts are also cycles of the regular conflict graph and affect serializability. One or more (lock related) non-materialized conflicts on a cycle prevent it from being a cycle in the regular conflict graph and make it a locking related deadlock. All the global cycles (voting-deadlocks) need to be broken (resolved) to both maintain global serializability and resolve global deadlocks involving data access locking. Indeed they are all broken by the atomic commitment protocol due to missing votes upon a voting deadlock. 1499:). Such blocking happens only if the second transaction conflicts with the first transaction (see above). Thus this "wait for vote to commit" graph is identical to the global conflict graph. A cycle in the "wait for vote to commit" graph means a deadlock in voting. Hence there is a deadlock in voting if there is a cycle in the conflict graph. The local serializability mechanisms eliminate local cycles (confined to a single database). Consequently, only global cycles are left, which are then eliminated by the atomic commitment protocol when it aborts deadlocked transactions with missing (blocked) respective votes. 4901:(chip), or in many chips, possibly distributed geographically in many computers. In such an environment, if recoverable (transactional) data are partitioned among threads (cores), and it is implemented in the conventional way for distributed CO, as described in previous sections, then DOCO and Strictness exist automatically. However, downsides exist with this straightforward implementation of such environment, and its practicality as a general-purpose solution is questionable. On the other hand, tremendous performance gain can be achieved in applications that can bypass these downsides in most situations. 2349:

Consequently the protocol aborts some transactions with a missing vote. This breaks the global cycle, the voting-deadlock is resolved, and the related blocked votes are free to be executed. Breaking the global cycle in the global conflict graph ensures that global CO and global serializability are maintained. Thus, in the case of incompatible local (partial) commitment orders, no action is needed since the atomic commitment protocol resolves it automatically by aborting a transaction that is a cause for the incompatibility. Furthermore, global deadlocks due to locking (global cycles in the

1150:

transactions and possibly others in conflict with the deadlocked (and thus blocked) will be free to be voted on. It is worthwhile noting that each database involved with the voting-deadlock continues to vote regularly on transactions that are not in conflict with its deadlocked transaction, typically almost all the outstanding transactions. Thus, in the case of incompatible local (partial) commitment orders, no action is needed since the atomic commitment protocol resolves it automatically by aborting a transaction that is a cause of incompatibility. This means that the above

1113:

atomic commitment protocol are scheduled for each (unaborted) distributed transaction (in what follows, "a vote" means a YES vote). Suppose a precedence relation (conflict) exists between two transactions. In that case, the second will not be voted on before the first is completed (either committed or aborted), to prevent possible commit order violation by the atomic commitment protocol. Such can happen since the commit order by the protocol is not necessarily the same as the voting order. If no precedence relation exists, both can be voted on concurrently. This

1943:

augmented conflict graph (for better performance by earlier release upon transaction-end of computing resources and typically locked data). For example, existing locking based global deadlock detection methods, other than the timeout, can be generalized also to consider local commit and vote direct blocking, besides data access blocking. A possible compromise in such mechanisms is effectively detecting and breaking the most frequent and relatively simple to handle length-2 global cycles, and using timeout for undetected, much less frequent, longer cycles.

5771:

earlier multi-version theories). For different versions conflict chronological order is replaced by version order, and possibly reversed, while keeping the usual definitions for conflicting operations. Results for the regular and augmented conflict graphs remain unchanged, and similarly to CO a distributed MVCO enforcing algorithm exists, now for a mixed environment with both single-version and multi-version resources (now single-version is a special case of multi-version). As for CO, the MVCO algorithm needs only (unmodified)

222: 5195:)) generalizes CO. When local transactions (transactions confined to a single database) can be distinguished from global (distributed) transactions (transactions that span two databases or more), commitment order is applied to global transactions only. Thus, for a local (to a database) schedule to have the ECO property, the chronological (partial) order of commit events of global transactions only (unimportant for local transactions) is consistent with their order on the respective local conflict graph. 775:, including its special cases, and together with its generalizations (see CO variants below), provides a general, high performance, fully distributed solution (no central processing component or central data structure are needed) for guaranteeing global serializability in heterogeneous environments of multidatabase systems and other multiple transactional objects (objects with states accessed and modified only by transactions; e.g., in the framework of 764:

local mechanism that already provides conflict serializability, enforcing CO locally does not cause any other aborts, since enforcing CO locally does not affect the data access scheduling strategy of the mechanism (this scheduling determines the serializability related aborts; such a mechanism typically does not consider the commitment events or their order). The CO solution requires no communication overhead since it uses (unmodified)

397: 1054:, and the schedule will violate serializability when all the transactions on a cycle are committed. In this case, no partial order for commitment events can be found. Thus, cycles in the conflict graph need to be broken by aborting transactions. However, any conflict serializable schedule can be made CO without aborting any transaction by properly delaying commit events to comply with the transactions' precedence partial order. 2114:

protocol's decision on each global transaction. The decisions are delivered from the COCO to the database system through their interface, as well as local transactions' commit notifications, at a proper commit order. The COCO, including its interfaces, can be enhanced, if it implements another variant of CO (see below) or plays a role in the database's concurrency control mechanism beyond voting in atomic commitment.

5096:. Duration of transaction T2 is longer with SS2PL than with SCO. SS2PL delays write operation w2 of T2 until T1 commits, due to a lock on x by T1 following read operation r1. If t time units are needed for transaction T2 after starting write operation w2 in order to reach ready state, than T2 commits t time units after T1 commits. However, SCO does not block w2, and T2 can commit immediately after T1 commits. ( 2319: 2156:. It means that if not complying with CO, then global serializability cannot be guaranteed under this condition (the condition of no local concurrency control information sharing between databases beyond atomic commit protocol messages). Atomic commitment is a minimal requirement for a distributed transaction since it is always needed, which is implied by the transaction definition. 108: 66: 25: 2610:), one on each node, and the database data are partitioned between the two data managers in a way that each has an exclusive control of its own (local to the node) portion of data: Each handles its own data and locks without any knowledge on the other manager's. For each distributed transaction such data managers need to execute the available atomic commitment protocol. 1130:

database systems exists on conflicts, since the needed communication is massive and unacceptably degrades performance) it means that the transaction resides on a global cycle (involving two or more databases) in the global conflict graph. In this case, the atomic commitment protocol will fail to collect all the votes needed to commit that transaction: By the

339: 284: 5090: 1070:

protocol (which can be fully distributed). Atomic commitment protocol is essential to enforce atomicity of each distributed transaction (to decide whether to commit or abort it; this procedure is always carried out for distributed transactions, independently of concurrency control and CO). A common example of an atomic commitment protocol is the

1507:

commit of another transaction (which now cannot get to ready state), with the same effect as a direct blocking of a vote or a local commit. A cycle is generated in the conflict graph only if such blocking by a lock is also represented by an edge. With such added edges representing events of blocking-by-a-lock, the conflict graph is becoming an

5880:

commitment order, i.e., to determine when it is the transaction's turn to be voted on locally in the atomic commitment protocol. Thus, all the CO variants exhibit the same behavior in regard to atomic commitment. This means that they are all interoperable via atomic commitment (using the same software interfaces, typically provided as

1096:(either explicit or implicit) by each participant, which means an obligation of the voting participant to obey the decision of the protocol, either commit or abort. Otherwise, a participant can unilaterally abort the transaction by an explicit NO vote. The protocol commits the transaction only if YES votes have been received from 2412:, which reduces the performance of the system. CO allows to achieve distributed serializability under very general conditions, without a distributed lock manager, exhibiting the benefits already explored above for multidatabase environments; in particular: reliability, high performance, scalability, the possibility of using 643:). They also provide global serializability without local concurrency control information distribution, can be combined with any relevant concurrency control, and allow optimistic (non-blocking) implementations. Both use additional information for relaxing CO constraints and achieving better concurrency and performance. 779:, and within Cloud computing and Grid computing). The CO solution scales up with network size and the number of databases without any negative impact on performance (assuming the statistics of a single distributed transaction, e.g., the average number of databases involved with a single transaction, are unchanged). 5081:(SS2PL) rules. The atomic commitment protocol mechanism is not needed here for consensus on commit, but rather for the end of phase-two synchronization point. Probably for this reason, without considering the atomic commitment voting mechanism, automatic global deadlock resolution has not been noticed before CO. 5175:(OCO) the generic local CO algorithm is utilized without data access blocking, and thus without local deadlocks. OCO without transaction or operation scheduling constraints covers the entire CO class, and is not a special case of the CO class, but rather a useful CO variant and mechanism characterization. 5477:

transactions (not unique, contrary to CO) can be optimized, if each transaction is assigned with a weight (that can be determined by transaction's importance and by the computing resources already invested in the running transaction; optimization can be carried out, for example, by a reduction from the

5770:

for multi-version resources. Like CO, MVCO is non-blocking, and can be combined with any relevant multi-version concurrency control mechanism without interfering with it. In the introduced underlying theory for MVCO conflicts are generalized for different versions of a same resource (differently from

5678:

Global ECO (all global cycles in the global conflict graph are eliminated by atomic commitment) together with Local serializability (i.e., each database system maintains serializability locally; all local cycles are eliminated) imply Global serializability (all cycles are eliminated). This means that

5118:

Unlike SS2PL, SCO does not block on a read-write conflict but possibly blocks on commit instead. SCO and SS2PL have identical blocking behavior for the other two conflict types: write-read, and write-write. As a result, SCO has shorter average blocking periods, and more concurrency (e.g., performance

2314:

based concurrency control mechanism, neither affecting any transaction's execution process or scheduling nor aborting it. Also, the database's autonomy is not violated. The only low overhead incurred is detecting conflicts (e.g., with locking, but with no data-access blocking; if not already detected

2233:

However, the definition of autonomy above implies, for example, that transactions are scheduled in a way that local transactions (confined to a single database) cannot be identified as such by an autonomous database system. This is realistic for some transactional objects but too restrictive and less

1915:

Locking-based global-deadlocks can also be generated in a completely SS2PL-based distributed environment (special case of CO based). All the vote blocking (and voting-deadlocks) are caused by data-access locks. Many research articles have dealt for years with resolving such global deadlocks, but none

1049:

The commitment decision events are generated by either a local commitment mechanism or an atomic commitment protocol if different processes need to reach a consensus on whether to commit or abort. The protocol may be distributed or centralized. Transactions may be committed concurrently if the commit

5879:

above). Differences between the various variants exist at the local level only (within the participating database systems). Each local CO instance of any variant has the same role, to determine the position of every global transaction (a transaction that spans two or more databases) within the local

4997:

increasing the number of cores for a given amount of recoverable data (database size) decreases the average amount of (partitioned) data per core. This may make some cores idle, while others very busy, depending on data utilization distribution. Also a local (to a core) transaction may become global

4129:

has the global cycle (all conflicts are materialized), and again it is resolved by the atomic commitment protocol, and distributed serializability is maintained. Unlikely for a distributed database system, but possible in principle (and occurs in a multi-database), A can employ SS2PL while B employs

1990:

constraints exist to complete that transaction, it is preferred to wait with committing that transaction and let this set decrease in size. If another serializability mechanism exists locally (which eliminates cycles in the local conflict graph), or if no cycle involving that transaction exists, the

1134:

above, at least one database will delay its vote for that transaction indefinitely to comply with its own commitment (precedence) order, since it will be waiting to the completion of another, preceding transactions on that global cycle delayed indefinitely by another database with a different order.

1112:

In each database system, a local CO algorithm determines the needed commitment order for that database. By the characterization of CO above, this order depends on the local precedence order of transactions, which results from the local data access scheduling mechanisms. Accordingly, YES votes in the

5733:

on it are involved with the respective voting-deadlock, and eventually each has its vote blocked (either directly, or indirectly by a data-access lock). If a local transaction resides on the cycle, it may be in any unaborted state (running, ready, or committed; unlike CO no local commit blocking is

5064:

above is kept automatically. If a local timeout mechanism is used by a database system to resolve (local) SS2PL deadlocks, then aborting blocked transactions breaks not only potential local cycles in the global conflict graph (real cycles in the augmented conflict graph), but also database system's

3883:

Due to data partition, x cannot be accessed directly from B. However, functionality is not limited, and a transaction running on B still can issue a write or read request of x (not common). This request is communicated to the transaction's local sub-transaction on A (which is generated, if does not

1942:

finding (e.g., by a timeout; sometimes mistakenly, unnecessarily) missing votes and typically unaware of global cycles. These protocols can be especially enhanced for CO (including CO's variants below) to prevent unnecessary aborts and accelerate aborts used for breaking global cycles in the global

736:

in such system is problematic. Even if every local schedule of a single database is still 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 would

5012:

property: it uses only local information), while relaxing CO constraints and utilizing additional (local) information for better concurrency and performance: ECO uses knowledge about transactions being local (i.e., confined to a single database), and MVCO uses availability of data versions values.

5007:

Special case schedule property classes (e.g., SS2PL and SCO below) are strictly contained in the CO class. The generalizing classes (ECO and MVCO) strictly contain the CO class (i.e., include also schedules that are not CO compliant). The generalizing variants also guarantee global serializability

4858:

As noted above, only case 4 describes a cycle in the (regular) conflict graph which affects serializability. Cases 1-3 describe cycles of locking based global deadlocks (at least one lock blocking exists). All cycle types are equally resolved by the atomic commitment protocol. Case 1 is the common

1144:

situation involving the databases on that cycle. As a result, the protocol will eventually abort some deadlocked transaction on this global cycle, since each such transaction is missing at least one participant's vote. Selection of the specific transaction on the cycle to be aborted depends on the

770:

protocol messages only, already needed by each distributed transaction to reach atomicity. An atomic commitment protocol plays a central role in the distributed CO algorithm, which enforces CO globally by breaking global cycles (cycles that span two or more databases) in the global conflict graph.

763:

Enforcing CO is an effective way to enforce conflict serializability globally in a distributed system since enforcing CO locally in each database (or other transactional objects) also enforces it globally. Each database may use any, possibly different, type of concurrency control mechanism. With a

5899:

In summary, any single global transaction can participate simultaneously in databases that may employ each any, possibly different, CO variant (while concurrently running processes in each such database, and running concurrently with local and other global transactions in each such database). The

5153:

SCO is as practical as SS2PL since as SS2PL it provides besides serializability also strictness, which is widely utilized as a basis for efficient recovery of databases from failure. An SS2PL mechanism can be converted to an SCO one for better performance in a straightforward way without changing

2113:

with its database system to receive "conflict," "ready" (the processing has ended; readiness to vote on a global transaction or commit a local one), and "abort" notifications from the database system. It also interfaces with the atomic commitment protocol to vote and receive the atomic commitment

538:

Each not-CO-compliant database system is augmented with a CO component (the commitment order coordinator—COCO) which orders the commitment events for CO compliance, with neither data-access nor any other transaction operation interference. As such, CO provides a low overhead, general solution for

2348:

occurs for the databases on that cycle (however, allowed concurrent voting in each database, typically for almost all the outstanding votes, continue to execute). In this case, the atomic commitment protocol fails to collect all the votes needed for the blocked transactions on that global cycle.

5476:

Before a global transaction is committed, a generic local (to a database) ECO algorithm aborts a minimal set of undecided transactions (neither committed, nor aborted; either local transactions, or global that run locally), that can cause later a cycle in the conflict graph. This set of aborted

5054:

of the set of CO schedules. This property is widely utilized in database systems, and since it implies CO, databases that use it and participate in global transactions generate together a serializable global schedule (when using any atomic commitment protocol, which is needed for atomicity in a

4993:

Local sub-transactions of a global transaction are blocked until commit, which makes the respective cores idle. This reduces core utilization substantially, even if scheduling of the local sub-transactions attempts to execute all of them in time proximity, almost together. It can be overcome by

1506:

Finally, blocking by a lock (which has been excluded so far) needs to be considered: A lock blocks a conflicting operation and prevents a conflict from being materialized. Suppose the lock is released only after the transaction end. In that case, it may block indirectly either a vote or a local

1502:

Secondly, also local commits are dealt with: Note that when enforcing CO, also waiting for a regular local commit of a local transaction can block local commits and votes of other transactions upon conflicts, and the situation for global transactions does not also change without the simplifying

1129:

the respective local partial orders together). With CO, precedence orders are also the commitment orders. When participating databases in the same distributed transaction do not have compatible local precedence orders for that transaction (without "knowing" it; typically no coordination between

1100:

participants (thus, a missing vote is typically considered a NO). Otherwise, the protocol aborts the transaction. The various atomic commit protocols only differ in their abilities to handle different computing environment failure situations and the amounts of work and other computing resources

1069:

enforcement algorithm exists that uses local CO of each participating database, and needs only (unmodified) Atomic commitment protocol messages with no further communication. The distributed algorithm is the combination of local (to each database) CO algorithm processes and an atomic commitment

5059:

above is empty because of the locks, and hence such an algorithm is unnecessary in this case. A transaction can be voted on by a database system immediately after entering a "ready" state, i.e., completing running its task locally. Its locks are released by the database system only after it is

1451:

The Local CO property of a global schedule means that each database is CO compliant. From the necessity discussion, the part above directly follows that the theorem is also true when replacing "Global CO" with "Local CO" when global transactions are present. Together it means that Global CO is

5761:

do not block or being blocked for better performance. Utilizing such resources is a common way nowadays to increase concurrency and performance by generating a new version of a database object each time the object is written, and allowing transactions' read operations of several last relevant

5436:

A distributed algorithm to guarantee global ECO exists. As for CO, the algorithm needs only (unmodified) atomic commitment protocol messages. In order to guarantee global serializability, each database needs to guarantee also the conflict serializability of its own transactions by any (local)

2550:

This theorem also means that when SS2PL (or any other CO variant) is used locally in each transactional data manager, and each data manager has exclusive control of its data, no distributed lock manager (which is often utilized to enforce distributed SS2PL) is needed for distributed SS2PL and

1780:

graphs and also may include locking based global cycles (which cannot exist in the local graphs). For example, if all the databases on a global cycle are SS2PL based, then all the related vote blocking situations are caused by locks (this is the classical and probably the only global deadlock

2268:

This definition is probably the broadest such definition possible in the context of database concurrency control, and it makes CO together with any of its (useful: No concurrency control information distribution) generalizing variants (Vote ordering (VO); see CO variants below) the necessary

1149:

mechanism is common, but it may result in more than one needed abort per cycle; both preventing unnecessary aborts and abort time shortening can be achieved by a dedicated abort mechanism for CO). Such abort will break the global cycle involving that distributed transaction. Both deadlocked

2125:

Suppose databases that participate in distributed transactions (i.e., transactions that span more than a single database) do not use any shared concurrency control information and use unmodified atomic commitment protocol messages (for reaching atomicity). In that case, maintaining (local)

5024:

refers in general to CO, ECO, MVCO, or a combination of each of them with any relevant concurrency control mechanism or property (including Multi-version based ECO, MVECO). No other generalizing variants (which guarantee global serializability with no local concurrency control information

1809:

below: Global transactions' voting order must follow the conflict graph order with vote blocking when order relation (graph path) exists between two global transactions. Local transactions are not voted on, and their (local) commits are not blocked upon conflicts. This results in the same

3529:

rules of SS2PL and cannot be executed. This is a distributed deadlock situation, which is also a voting-deadlock (see below) with a distributed (global) cycle of length 2 (number of edges, conflicts; 2 is the most frequent length). The local sub-transactions are in the following states:

1991:

set will be empty eventually, and no abort of a set member is needed. Otherwise, the set will stabilize with transactions on local cycles, and aborting set members will have to occur to break the cycles. Since in the case of CO conflicts generate blocking on commit, local cycles in the

5937:

In a multi-database environment, where each database system (transactional object) is compliant with some CO variant property (VO compliant), any global transaction can participate simultaneously in databases of possibly different CO variants, and Global serializability is guaranteed

5874:

the respective local partial orders together), or a data-access locking related voting deadlock, both implying a global cycle in the global augmented conflict graph and missing votes, the atomic commitment protocol breaks such cycle by aborting an undecided transaction on it (see

771:

CO, its special cases, and its generalizations are interoperable and achieve global serializability while transparently being utilized together in a single heterogeneous distributed environment comprising objects with possibly different concurrency control mechanisms. As such,

620:) than SS2PL whenever read-write conflicts are present (identical blocking behavior for write-read and write-write conflicts; comparable locking overhead). The advantage of SCO is especially during lock contention. Strictness allows both SS2PL and SCO to use the same effective 2367:

in the context of concurrency control. This means that every global serializability solution for autonomous databases must comply with CO. Otherwise, global serializability may be violated (and thus, is likely to be violated very quickly in a high-performance environment).

2559:

For implementing Distributed Optimistic CO (DOCO), the generic local CO algorithm is utilized in all the atomic commitment protocol participants in the system with no data access blocking and thus with no local deadlocks. The previous theorem has the following corollary:

571:) that guarantees global serializability, if the database systems involved do not share concurrency control information beyond atomic commitment protocol (unmodified) messages and have no knowledge of whether transactions are global or local (the database systems are 5837:

method widely utilized due to good performance and similarity to serializability (1SER) in several aspects. The theory in (Raz 1993b) for MVCO described above is utilized later in (Fekete et al. 2005) and other articles on SI, e.g., (Cahill et al. 2008); see also

2081:, and especially in Software transactional memory 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 CO have already been published. 5904:

generated in the augmented global conflict graph may span databases of different CO variants, and generate (if not broken by any local abort) a voting deadlock that is resolved by atomic commitment exactly the same way as in a single CO variant environment.

5491:

transactions are committed, while transitively preceding local transactions can be at any state. This in analogy to the distributed CO algorithm's stronger concurrent voting condition, where all the transitively preceding transactions need to be committed).

4859:

Distributed SS2PL, utilized since the 1980s. However, no research article, except the CO articles, is known to notice this automatic locking global deadlock resolution as of 2009. Such global deadlocks typically have been dealt with by dedicated mechanisms.

1954:

can be enforced locally (in a single database) by a dedicated CO algorithm, or by any algorithm/protocol that provides any special case of CO. An important such protocol, being utilized extensively in database systems, which generates a CO schedule, is the

5115:(a special case of recoverability) and CO, and provides an upper bound for a schedule's concurrency when both properties exist. It can be implemented using blocking mechanisms (locking) similar to those used for the popular SS2PL with similar overheads. 651:) is a container schedule set (property) and technique for CO and all its variants. Local VO is necessary for guaranteeing global serializability if the atomic commitment protocol (ACP) participants do not share concurrency control information (have the 6058: 6055: 6052: 575:). Thus CO (with its variants) is the only general technique that does not require the typically costly distribution of local concurrency control information (e.g., local precedence relations, locks, timestamps, or tickets). It generalizes the popular 1861:

A rare situation of a voting deadlock (by missing blocked votes) can happen, with no voting for any transaction on the related cycle by any of the database systems involved with these transactions. This can occur when local sub-transactions are

818:) conflict graph (precedence graph, serializability graph), as induced by their conflicting access operations (usually read and write (insert/modify/delete) operations; CO also applies to higher-level operations, where they are conflicting if 1494:

as a directed graph with transactions as nodes and a directed edge from any first transaction to a second transaction if the first transaction blocks the vote to commit of the second transaction (opposite to conventional edge direction in a

591:

to achieve global serializability across (SS2PL based) database systems. As a result, CO compliant database systems (with any different concurrency control types) can transparently join such SS2PL based solutions for global serializability.

786:, Optimistic CO (OCO) has also been increasingly utilized to achieve serializability in software transactional memory, and numerous STM articles and patents utilizing "commit order" have already been published (e.g., Zhang et al. 2006). 5919:), the union of CO and all its above variants, is a useful concept and global serializability technique. To comply with VO, local serializability (in it most general form, commutativity based, and including multi-versioning) and the 1080:), a simpler protocol for atomic commitment may be used (e.g., a simple handshake of distributed transaction's participating processes with some arbitrary but known special participant, the transaction's coordinator, i.e., a type of 1852:

on it are involved with the respective voting-deadlock. Eventually, each has its vote blocked (either directly or indirectly by a data-access lock); if a local transaction resides on the cycle, eventually, it has its (local) commit

5909:(now possibly with mixed materialized and non-materialized conflicts, both serializability and data-access-locking deadlock related, e.g., SCO) are resolved locally (each by its respective variant instance's own local mechanisms). 4907:

The MuSiC straightforward implementation described here (which uses, for example, as usual in distributed CO, voting (and transaction thread) blocking in atomic commitment protocol when needed) is for demonstration only, and has

2194:

messages with any other entity. In addition, it does not use for concurrency control any additional local information beyond conflicts (the last sentence does not appear explicitly but rather implied by further discussion in

4791: 5069:

protocol's abort mechanism is relatively slow. Such independent aborts by several entities typically may result in unnecessary aborts for more than one transaction per global cycle. The situation is different for a local

6065:

Yoav Raz (1991b): "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.

1881:

In a CO compliant multidatabase system, a locking-based global-deadlock, involving at least one data-access lock (non-materialized conflict), and two or more database systems, is a reflection of a global cycle in the

1781:

situation dealt with in the database research literature). This is a global deadlock case where each related database creates a portion of the cycle, but the complete cycle does not reside in any local wait-for graph.

1124:

However, since database systems schedule their transactions independently, it is possible that the transactions' precedence orders in two databases or more are not compatible (no global partial order exists that can

5464:

This condition (ECO with local serializability) is weaker than CO, and allows more concurrency at the cost of a little more complicated local algorithm (however, no practical overhead difference with CO exists).

2392:

A distinguishing characteristic of the CO solution to distributed serializability from other techniques is the fact that it requires no conflict information distributed (e.g., local precedence relations, locks,

655:

property). CO and its variants inter-operate transparently, guaranteeing global serializability and automatic global deadlock resolution together in a mixed, heterogeneous environment with different variants.

5055:

multi-database environment). No database modification or addition is needed in this case to participate in a CO distributed solution: The set of undecided transactions to be aborted before committing in the

4660: 4548: 2577:

Global (voting) deadlocks are resolved automatically (and all are serializability related (with non-blocking conflicts) rather than locking related (with blocking and possibly also non-blocking conflicts)).

1793:: An edge exists from a first transaction, either local or global, to a second, if the second is waiting for the first to end in order to be either voted on (if global) or locally committed (if local). All 4923:

condition for the atomic commitment protocol are met automatically. This results in both distributed CO compliance (and thus distributed serializability) and automatic global (voting) deadlock resolution.

5148:

SCO provides shorter average transaction completion time than SS2PL, if read-write conflicts exist. SCO and SS2PL are identical otherwise (have identical blocking behavior with write-read and write-write

2057:

transaction completion constraints are applied) neither algorithm aborts more transactions than the minimum needed (which is determined by the transactions' operations scheduling, out of the scope of the

1050:

partial order allows (if they do not have conflicting operations). Suppose different conflicting operations induce different partial orders of the same transactions. In that case, the conflict graph has

3732:, (or both, if the timeouts fall very close). This will resolve the global deadlock. The remaining transaction will complete running, be voted on, and committed. An aborted transaction is immediately 1104:

The entire CO solution for global serializability is based on the fact that the atomic commitment protocol eventually aborts this transaction in case of a missing vote for a distributed transaction.

599:

are resolved automatically in a CO based multi-database environment, a vital side-benefit (including the special case of a completely SS2PL based environment; a previously unnoticed fact for SS2PL).

2341:

the respective local partial orders together), a global cycle (spans two databases or more) in the global conflict graph is generated. This, together with CO, results in a cycle of blocked votes. A

535:(modular serializability) across any collection of database systems that possibly use different concurrency control mechanisms (CO also makes each system serializability compliant, if not already). 5126:

which is identical to SCO, clearly show this, with approximately 100% gain for some transaction loads; also for identical transaction loads SCO can reach higher transaction rates than SS2PL before

5074:

based mechanisms: Such cannot identify global cycles, and the atomic commitment protocol will break the global cycle, if the resulting voting deadlock is not resolved earlier in another database.

1490:

First, it is assumed, for simplicity, that every transaction reaches the ready-to-commit state and is voted on by at least one database (this implies that no blocking by locks occurs). Define a

5968:; see above), involving at least one data-access lock (non-materialized conflict) and two database systems; thus, not a cycle in the regular conflict graph and does not affect serializability). 4897:) relatively to conventional transaction execution in multiple threads on a same core. In what described below MuSiC is independent of the way the cores are distributed. They may reside in one 5896:) and transparently can be utilized together in any distributed environment (while each CO variant instance is possibly associated with any relevant local concurrency control mechanism type). 5775:

protocol messages with no additional communication overhead. Locking-based global deadlocks translate to voting deadlocks and are resolved automatically. In analogy to CO the following holds:

4436: 2264:

property if it does not share any other database system any local concurrency information beyond (unmodified) atomic commit protocol messages (however, any local information can be utilized).

5451:

When no concurrency control information beyond atomic commitment messages is shared outside a database (autonomy), and local transactions can be identified, it is also a necessary condition.

4369: 4319: 4269: 4219: 4123: 4074: 4025: 3976: 3236: 3186: 3106: 3056: 1920:

automatically resolves them. Such automatic resolutions are regularly occurring unnoticed in all existing SS2PL based multidatabase systems, often bypassing dedicated resolution mechanisms.

5858:

protocol based distributed algorithms. For CO and all its variants atomic commitment protocol is the instrument to eliminate global cycles (cycles that span two or more databases) in the

5738:

As with CO this means that also global deadlocks due to data-access locking (with at least one lock blocking) are voting deadlocks, and are automatically resolved by atomic commitment.

2857: 2744: 2269:

condition for Global serializability (i.e., the union of CO and its generalizing variants is the necessary set VO, which may also include new unknown useful generalizing variants).

4855:

Some limited operation order changes in the schedules above are possible, constrained by the orders inside the transactions, but such changes do not change the rest of the table.

567:(ACP; of any type) is a fundamental part of the solution, utilized to break global cycles in the conflict (precedence, serializability) graph. CO is the most general property (a 3674:

Since the atomic commitment protocol cannot receive votes for blocked sub-transactions (a voting-deadlock), it will eventually abort some transaction with a missing vote(s) by

3523: 3487: 3394: 3359: 3321: 3286: 2892: 2779: 2325:

An arrow from class A to class B indicates that class A strictly contains B; a lack of a directed path between classes means that the classes are incomparable. A property is

1121:

for guaranteeing Global CO (and the local CO of a database; without it both Global CO and Local CO (a property meaning that each database is CO compliant) may be violated).

4866:

is used (i.e., Case 4 is unchanged when Optimistic CO (OCO; see below) replaces SCO on both A and B): No data-access blocking occurs, and only materialized conflicts exist.

3664: 3628: 3595: 3558: 4881:

Certain experimental distributed memory-resident databases advocate multi single-threaded core (MuSiC) transactional environments. "Single-threaded" refers to transaction

3909:

above). However the database system can utilize any CO variant with exactly the same conflicts and voting-deadlock situation, and same resolution. Conflicts can be either

5548: 5244: 2667:, are running concurrently, and both access data x and y. x is under the exclusive control of the data manager on A (B's manager cannot access x), and y under that on B. 1213: 867: 5050:) means that both read and write locks of a transaction are released only after the transaction has ended (either committed or aborted). The set of SS2PL schedules is a 2234:

realistic for general purpose database systems. If autonomy is augmented with the ability to identify local transactions, then compliance with a more general property,

5981:"The Principle of Commitment Ordering, or Guaranteeing Serializability in a Heterogeneous Environment of Multiple Autonomous Resource Managers Using Atomic Commitment" 302: 1442: 6121: 5668: 5641: 5614: 5587: 5430: 5403: 5368: 5341: 5314: 5287: 3878: 3851: 3824: 3797: 3770: 3730: 3703: 3451: 3424: 3136: 3006: 2953: 2926: 2808: 2695: 2665: 2638: 1754:

Here, unlike the regular conflict graph, which has edges only for materialized conflicts, all materialized, and non-materialized conflicts are represented by edges.

1724: 1694: 1667: 1640: 1613: 1582: 1555: 1385: 1358: 1331: 1302: 1275: 1240: 1043: 1016: 985: 956: 929: 898: 5960:

Furthermore, in such environment data-access-locking related global deadlocks are resolved automatically (each such deadlock is generated by a global cycle in the

1908:

Any blocking (edge) in the cycle that is not by a data-access lock directly blocks either voting or local commit. All voting-deadlocks are resolved (almost all by

5866:(implicitly; no global data structure implementation is needed). In cases of either incompatible local commitment orders in two or more databases (when no global 3929:

states, and vote blocking occurs in the two transactions, one on each node, because of the CO voting rule applied independently on both A and B: due to conflicts

2292:) in a multidatabase environment complies with CO, i.e., arranges its local transactions' commitments and its votes on (global, distributed) transactions to the 2492:

Recoverable data are partitioned among the data managers, i.e., each recoverable datum (data item) is controlled by a single data manager (e.g., as common in a

706:, and the term "strong" implies a special case. This means that a substantial recoverability property does not necessarily have the CO property and vice versa. 5137:), and the average duration of a transaction is shorter (faster completion; see chart). The advantage of SCO is especially significant during lock contention. 2363:

if the databases involved do not share any concurrency control information beyond (unmodified) atomic commitment protocol messages, i.e., if the databases are

1057:

CO enforcement by itself is not sufficient as a concurrency control mechanism since CO lacks the recoverability property, which should be supported as well.

5077:

Local SS2PL together with atomic commitment implying global serializability can also be deduced directly: All transactions, including distributed, obey the

2077:

With the proliferation of Multi-core processors, variants of the Generic local CO algorithm have also been increasingly utilized in Concurrent programming,

1456:

Local CO is guaranteed (which is untrue for Global conflict serializability and Local conflict serializability: Global implies Local, but not the opposite).

728:

or any other more loosely defined multidatabase system, which are typically distributed in a communication network, transactions span multiple and possibly

6071:

Yoav Raz (1991c): "Locking Based Strict Commitment Ordering, or How to improve Concurrency in Locking Based Resource Managers", DEC-TR 844, December 1991.

2453:(i.e., deadlocks that span two or more data managers) caused by data-access locking are resolved automatically. Thus the following corollary is concluded: 2408:(DLM). DLMs, which communicate lock (non-materialized conflict) information in a distributed environment, typically suffer from computer and communication 2551:

serializability. It is relevant to a wide range of distributed transactional applications, which can be easily designed to meet the theorem's conditions.

1938:

Atomic commitment protocols are intended and designed to achieve atomicity without considering database concurrency control. They abort upon detecting or

5448:(Local, which implies global) ECO together with local conflict serializability, is a sufficient condition to guarantee global conflict serializability. 4703: 4836:

are determined by the transactions and their initial scheduling only, independently of the concurrency control utilized. With any variant of CO, any

709:

In 2009 CO has been characterized as a major concurrency control method, together with the previously known (since the 1980s) three major methods:

1503:

assumption above: The final result is the same also with a local commitment for local transactions, without voting in atomic commitment for them.

5017:, do not interfere with any transaction's operation scheduling, and can be seamlessly combined with any relevant concurrency control mechanism. 82: 2397:, tickets), which makes it uniquely effective. It utilizes (unmodified) atomic commitment protocol messages (which are already used) instead. 132:

of the topic and provide significant coverage of it beyond a mere trivial mention. If notability cannot be shown, the article is likely to be

6306: 6231: 6203: 6158: 5468:

When all the transactions are assumed to be global (e.g., if no information is available about transactions being local), ECO reduces to CO.

1076:, which is resilient to many types of system failure. In a reliable environment, or when processes usually fail together (e.g., in the same 6089: 5133:

occurs). More concurrency means that with given computing resources more transactions are completed in time unit (higher transaction rate,

38: 6146: 5842:

and the references there), for analyzing conflicts in SI in order to make it serializable. The method presented in (Cahill et al. 2008),

4994:

detaching execution from commit (with some atomic commitment protocol) for global transactions, at the cost of possible cascading aborts.

2506:

These data managers are the participants in the system's atomic commitment protocol for coordinating distributed transactions' atomicity.

2394: 2416:

when desired, no conflict information related communications over the network (which have incurred overhead and delays), and automatic

1962:

protocol (SS2PL: "release transaction's locks only after the transaction has been either committed or aborted"; see below). SS2PL is a

6093:

Proceedings of the Third IEEE International Workshop on Research Issues on Data Engineering: Interoperability in Multidatabase Systems

6078:"Extended Commitment Ordering or Guaranteeing Global Serializability by Applying Commitment Order Selectivity to Global Transactions." 5671: 5163:

SS2PL is a proper subset of SCO (which is another explanation why SCO is less constraining and provides more concurrency than SS2PL).

4591: 4479: 1848:(also blocking by a data-access lock is represented by an edge). Suppose the cycle does not break by any abort. In that case, all the 1392: 3745:

The data partition (x on A; y on B) is important since without it, for example, x can be accessed directly from B. If a transaction

443: 378: 360: 320: 265: 243: 203: 52: 5790:

database system (or transactional object) in a mixed multidatabase environment of single-version and multi-version databases is a

1215:

be undecided (neither committed nor aborted) transactions in a database system that enforces CO for local transactions, such that

184: 5834: 5754: 2329:, if it can be enforced only by blocking transaction's data access operations until certain events occur in other transactions. ( 2117:

The COCO also guarantees CO locally in a single, isolated database system with no interface with an atomic commitment protocol.

156: 6357: 6347: 544: 349: 5881: 4878:

While the examples above describe real, recommended utilization of CO, this example is hypothetical, for demonstration only.

807: 502: 814:) precedence order of the transactions correspond to the precedence (partial) order of the respective transactions in the ( 163: 5993: 5112: 3246: 612: 506: 498: 129: 5942:

for Global serializability; and Global one-copy-serializability (1SER), for a case when a multi-version database exists).

2353:

with at least one data access blocking) result in voting deadlocks and are resolved automatically by the same mechanism.

6352: 5945:

If only local (to a database system) concurrency control information is utilized by every database system (each has the

5729:(also blocking by a data-access lock is represented by an edge). If the cycle does not break by any abort, then all the 5156: 5129: 2110: 2070: 4130:

SCO. In this case the global cycle is neither in the wait-for graph nor in the serializability graph, but still in the

2533:(deadlocks involving two or more data managers with at least one non-materialized conflict) are resolved automatically. 4386: 2493: 2344: 1146: 1139: 616:

and CO, provides better performance (shorter average transaction completion time and resulting in better transaction

170: 4325: 4275: 4225: 4175: 4079: 4030: 3981: 3932: 3192: 3142: 3062: 3012: 1467:

comprises enforcing (local) CO in each participating database system by ordering commits of local transactions (see

5121: 3880:(or signal a materialized conflict for a non-blocking CO variant; see below). Thus serializability can be violated. 540: 125: 2427:

rely on some atomic commitment protocol to coordinate atomicity (whether to commit or abort) among processes in a

1092:

a distributed (global) transaction that spans these participants. An essential stage in each such protocol is the

513:. In a CO compliant schedule, the chronological order of commitment events of transactions is compatible with the 5154:

recovery methods. A description of an SCO implementation can be found in (Perrizo and Tatarinov 1998). See also

4882: 2376: 2015:

above, applied to the local augmented conflict graph rather than the regular local conflict graph, comprises the

1863: 1072: 725: 583: 409: 141: 2191: 564: 152: 6337: 5900:

atomic commitment protocol is indifferent to CO, and does not distinguish between the various CO variants. Any

3921:(below) is used by the distributed database system instead of SS2PL, then the two conflicts in the example are 2405: 1769:

defines time order between conflicting operations, which is opposite to the time order defined by an edge in a

1765:

can also be defined as the graph of non-materialized conflicts. By the common conventions, edge direction in a

418: 236: 230: 44: 2546:, i.e., do not share concurrency control information beyond unmodified messages of atomic commitment protocol. 5854:

With CO and its variants (e.g., SS2PL, SCO, OCO, ECO, and MVCO above) global serializability is achieved via

4935:; page 307), when the CO vote ordering strategy is applied, also Global Strictness is guaranteed. Note that 776: 6219: 6090:"Commitment Ordering Based Distributed Concurrency Control for Bridging Single and Multi Version Resources." 6021: 4953:

In MuSiC environments, if recoverable (transactional) data are partitioned among cores (threads), then both

2813: 2700: 2428: 2106: 524: 6274: 6173:

Lingli Zhang, Vinod K.Grover, Michael M. Magruder, David Detlefs, John Joseph Duffy, Goetz Graefe (2006):

5885: 757: 733: 548: 532: 478: 247: 6273:. 1998 Int'l Conference on Computer Applications in Industry and Engineering. Las Vegas. pp. 75–79. 2542:

for (distributed) serializability in a system meeting conditions 1, 2 above, when the data managers are

2409: 2090: 806:

mechanisms (each transaction can complete its task without having its data-access blocked, which allows

738: 721:, and as an enabler for the interoperability of systems using different concurrency control mechanisms. 5772: 5066: 2294: 766: 3492: 3456: 3363: 3328: 3290: 3255: 2861: 2748: 5479: 4939:

locally is the only mode that allows strictness and "optimistic" (no data access blocking) together.

2469: 2449: 2417: 2152: 2143: 2078: 1051: 783: 729: 494: 490: 486: 118: 5674:

for guaranteeing Global ECO (the condition guarantees Global ECO, which may be violated without it).

6279: 6248: 5371: 4890: 3675: 3642: 3606: 3573: 3536: 2315:

for other purposes) and ordering votes and local transactions' commits according to the conflicts.

2131: 1987: 1939: 568: 470: 4889:

execution of transactions. The purpose is possible orders of magnitude gain in performance (e.g.,

2302:

induced by the local conflict graph (serializability graph) for the respective transactions, then

1395:

for guaranteeing Global CO (the condition guarantees Global CO, which may be violated without it).

353:

that states a Knowledge editor's personal feelings or presents an original argument about a topic.

6342: 5839: 5829: 5513: 5209: 4898: 2401: 1732: 1178: 1077: 832: 177: 137: 6224:

Proceedings of the 12th ACM SIGPLAN symposium on Principles and practice of parallel programming

6196:

Proceedings of the 14th ACM SIGPLAN symposium on Principles and practice of parallel programming

5670:

is voted on to be committed, in every such database system in a multidatabase environment, is a

2049:

guarantees both (local) CO and (local) locking based deadlock resolution. And (when not using a

6191: 6140: 6302: 6227: 6199: 6154: 5078: 5034: 3526: 2599: 1967: 1958: 749: 588: 577: 133: 6322: 2337:

In case of incompatible partial orders of two or more databases (no global partial order can

2222:

for guaranteeing Global serializability (without CO, Global serializability may be violated).

1414: 6009: 5889: 5259: 3826:

and directly writes x, then, without a distributed lock manager the read-lock for x held by

2098: 2033:

When running alone or alongside any concurrency control mechanism in a database system, then

1776:

Note that such a global graph contains (has embedded) all the (reversed edge) regular local

1530:

with added edges: In addition to the original edges a directed edge exists from transaction

1084:

protocol). An atomic commitment protocol reaches consensus among participants on whether to

5646: 5619: 5592: 5565: 5408: 5381: 5346: 5319: 5292: 5265: 3856: 3829: 3802: 3775: 3748: 3708: 3681: 3429: 3402: 3114: 2984: 2931: 2904: 2786: 2673: 2643: 2616: 2375:

with network size and the number of databases without performance penalty when it utilizes

1702: 1672: 1645: 1618: 1591: 1560: 1533: 1363: 1336: 1309: 1280: 1253: 1218: 1021: 994: 963: 934: 907: 876: 6150: 6038: 5957:

for guaranteeing Global serializability (and Global 1SER; otherwise they may be violated).

5767: 5679:

if each database system in a multidatabase environment provides local serializability (by

2435:(i.e., data under transactions' control, e.g., database data; not to be confused with the 2311: 2121:

CO is a necessary condition for global serializability across autonomous database systems.

2012: 1996: 1892: 1527: 702: 552: 519: 514: 482: 465: 5812:: Now a CO compliant single-version database system is automatically also MVCO compliant. 1117:

ensures that also the atomic commitment protocol maintains commitment order, and it is a

4134:(the union of the two). The various combinations are summarized in the following table: 741:. The problem of achieving global serializability effectively had been characterized as 396: 6244: 6136: 2496:; even copies of the same datum under different data managers are physically distinct, 1496: 1453: 819: 815: 556: 2310:

are guaranteed. A database's CO compliance can be achieved effectively with any local

2109:

for capturing conflicts, but with no data-access blocking). The COCO component has an

1995:(see above) indicate local commit-deadlocks, and deadlock resolution techniques as in 6331: 6013: 5867: 5051: 2299: 1963: 811: 6253:"H-Store: A High-Performance, Distributed Main Memory Transaction Processing System" 6095:(RIDE-IMS), Vienna, Austria, pp. 189-198, April 1993. (also DEC-TR 853, July 1992) 5953:), then compliance of each with some (any) CO variant property (VO compliance) is a 2093:

point of view, a CO component that implements the generic CO algorithm locally, the

1757:

Note that all the new edges are all the (reversed to the conventional) edges of the

5709:

Let a multidatabase environment comprise database systems that enforce, each, both

2281:(CO) solution (technique) for global serializability can be summarized as follows: 2011:

with at least one non-materialized conflict reflects a locking-based deadlock. The

1886:, which results in a voting-deadlock. Such a cycle is not a cycle in the (regular) 1810:

voting-deadlock situations and resulting global cycle elimination process for ECO.

810:; however, commitment could be blocked). In a CO schedule, the commitment events' ( 742: 5008:

without distributing local concurrency control information (each database has the

2318: 6299:

Proceedings of the 2008 ACM SIGMOD international conference on Management of data

2512:

Each such data manager is CO compliant (or some CO variant compliant; see below).

2171:

as complying with this requirement without using any additional local knowledge:

6294: 6252: 6215: 6187: 6174: 6117: 4980:

automatically exist globally with unbounded scalability in number of cores used.

4786:{\displaystyle R_{\text{1A}}(x)R_{\text{2B}}(y)W_{\text{1B}}(y)W_{\text{2A}}(x)} 3906: 2372: 2101:

between a (single) database system and an atomic commitment protocol component (

528: 6077: 5988:

Proceedings of the Eighteenth International Conference on Very Large Data Bases

6083:(PODS), Washington, DC, pp. 83-96, May 1993. (also DEC-TR 842, November 1991) 5850:

CO and its variants are transparently interoperable for global serializability

5134: 2218:

database system (or transactional object) in a multidatabase environment is a

737:

lead to unacceptable performance, primarily due to computer and communication

617: 560: 5816:

MVCO can be further generalized to employ the generalization of ECO (MVECO).

5687:

in the theorem above (a generalization of CO's vote ordering strategy), then

2190:, if it does not share any concurrency control information beyond unmodified 1890:(which reflects only materialized conflicts, so such a cycle does not affect 6243:

Robert Kallman, Hideaki Kimura, Jonathan Natkins, Andrew Pavlo, Alex Rasin,

5893: 5871: 3601:

and blocked (a non-materialized conflict situation; no vote on it can occur)

2338: 2134:

for guaranteeing global serializability (a proof technique can be found in (

1696:

from being materialized and have an edge in the regular conflict graph), and

1126: 802:(CO) is a special case of conflict serializability. CO can be enforced with 746: 700:(since 1991). The latter is a misleading name since CO is incomparable with 4969:(allowing effective recovery; 1 and 2 implying Strict CO—see SCO below) and 539:

global serializability (and distributed serializability), instrumental for

6081:

Proceedings of the Twelfth ACM Symposium on Principles of Database Systems

5089: 5980: 5060:

decided by the atomic commitment protocol, and thus the condition in the

474: 3884:

exist already) which issues this request to the local data manager on A.

1828:

Let a multidatabase environment comprise CO compliant (which eliminates

6186:

Hany E. Ramadan, Indrajit Roy, Maurice Herlihy, Emmett Witchel (2009):

5926:

Combining results for CO and its variants, the following is concluded:

5554:

in a database system that ensures serializability locally, such that a

3897:, and the global voting-deadlock is reflected as a cycle in the global 1167: 822:, as well as to conflicts between operations upon multi-version data). 6000:

Raz, Yoav (September 1994), "Serializability by Commitment Ordering",

5717:(which eliminates local cycles in the global conflict graph). Then, a 2085:

Implementation considerations: The Commitment Order Coordinator (COCO)

5119:

simulations of a single database for the most significant variant of

4988:

However, two major downsides, which need special handling, may exist:

4894: 1391:), in each such database system in a multidatabase environment, is a 4844:. Different CO variants may differ on whether a certain conflict is 2089:

A database system in a multidatabase environment is assumed. From a

517:

order of the respective transactions. CO is a broad special case of

4862:

Case 4 above is also an example for a typical voting-deadlock when

2602:

resides on two remote nodes, A and B. The database system has two

1924:

Voting-deadlocks are the key to the operation of distributed CO.

124:

Please help to demonstrate the notability of the topic by citing

4655:{\displaystyle R_{\text{1A}}(x)R_{\text{2B}}(y)W_{\text{2A}}(x)} 4543:{\displaystyle R_{\text{1A}}(x)R_{\text{2B}}(y)W_{\text{1B}}(y)} 4931:

follows automatically in a serial schedule. By Theorem 5.2 in (

1479:

The exact characterization of voting-deadlocks by global cycles

79:

it is impossible to copy edit the article in its current state.

2522:

The entire distributed system guarantees (distributed CO and)

2146:. This is a mathematical fact derived from the definitions of 1916:(except the CO articles) is known (as of 2009) to notice that 390: 332: 277: 215: 101: 59: 18: 6271:

A Semi-Optimistic Database Scheduler Based on Commit Ordering

1927:

Global cycle elimination (here voting-deadlock resolution by

1870:

Also, the following locking based special case is concluded:

6127:

MIT, LCS lab, Technical report MIT/LCS/TM-370, August 1988.

4871:

Hypothetical Multi Single-Threaded Core (MuSiC) environment

3907:

Exact characterization of voting-deadlocks by global cycles

790:

The commitment ordering solution for global serializability

350:

personal reflection, personal essay, or argumentative essay

5804:

Locking-based global deadlocks are resolved automatically.

2439:

property of a schedule) are directly accessed by a single

485:(non-blocking) implementations. With the proliferation of 6175:

Software transaction commit order and conflict management

4919:. Thus both local Optimistic CO (OCO; see below) and the 2400:

A common way to achieve distributed serializability in a

1487:

can be explained in detail by the following observation:

6259:, pages 1496 - 1499, Auckland, New-Zealand, August 2008. 5794:

for guaranteeing Global one-copy-serializability (1SER).

2063:

Example: Concurrent programming and Transactional memory

1912:; see comment above), including this locking-based type. 6269:

Perrizo, William; Tatarinov, Igor (November 11, 1998).

5504:

The Global ECO Enforcing Vote ordering strategy Theorem

4912:

to the implementation in H-Store or any other project.

3853:

on A is not visible on B and cannot block the write of

2538:

Furthermore: The data managers being CO compliant is a

1726:

ends (commits or aborts; true for any locking-based CO)

414: 356: 298: 6214:

Christoph von Praun, Luis Ceze, Calin Cascaval (2007)

5649: 5622: 5595: 5568: 5516: 5411: 5384: 5349: 5322: 5295: 5268: 5212: 4863: 4706: 4594: 4482: 4389: 4328: 4278: 4228: 4178: 4082: 4033: 3984: 3935: 3859: 3832: 3805: 3778: 3751: 3711: 3684: 3645: 3609: 3576: 3539: 3495: 3459: 3432: 3405: 3366: 3331: 3293: 3258: 3195: 3145: 3117: 3065: 3015: 2987: 2934: 2907: 2864: 2816: 2789: 2751: 2703: 2676: 2646: 2619: 2238:(ECO, see below), makes ECO the necessary condition. 2130:

or one of its generalizing variants (see below) is a

1705: 1675: 1648: 1621: 1594: 1563: 1536: 1417: 1366: 1339: 1312: 1283: 1256: 1221: 1181: 1024: 997: 966: 937: 910: 879: 835: 6293:

Michael J. Cahill, Uwe Röhm, Alan D. Fekete (2008):

5780:

The MVCO and Global one-copy-serializability Theorem

6123:

Commutativity-based locking for nested transactions

5378:(ECO) property, if for every two such transactions 3670:

and blocked (a non-materialized conflict; no vote).

2781:

when using notation common for concurrency control.

2203:Using this definition, the following is concluded: 1166:The Vote ordering strategy for Global CO Enforcing 293:

may be too technical for most readers to understand

5662: 5635: 5608: 5581: 5542: 5424: 5397: 5362: 5335: 5308: 5281: 5238: 4785: 4654: 4542: 4430: 4363: 4313: 4263: 4213: 4117: 4068: 4019: 3970: 3872: 3845: 3818: 3791: 3764: 3724: 3697: 3658: 3622: 3589: 3552: 3517: 3481: 3445: 3418: 3388: 3353: 3315: 3280: 3230: 3180: 3130: 3100: 3050: 3000: 2947: 2920: 2886: 2851: 2802: 2773: 2738: 2689: 2659: 2632: 2298:protocol according to the local (to the database) 1803:This observation also explains the correctness of 1718: 1688: 1661: 1634: 1607: 1576: 1549: 1436: 1379: 1352: 1325: 1296: 1269: 1234: 1207: 1037: 1010: 991:(CO) property, if for every two such transactions 979: 950: 923: 892: 861: 509:(history) property, defined in 1988 with the name 75:needs attention from an expert in computer science 6177:United States Patent 7711678, Granted 05/04/2010. 5876: 5065:potential global cycles as a side effect, if the 2377:common distributed atomic commitment architecture 745:until the public disclosure of CO in 1991 by its 684:) schedule property has been referred to also as 6216:"Implicit Parallelism with Ordered Transactions" 5753:)) is a generalization of CO for databases with 5025:distribution) are known, but may be discovered. 4431:{\displaystyle R_{\text{1A}}(x)R_{\text{2B}}(y)} 3917:, depending on CO variant used. For example, if 2458:The CO Based Distributed Serializability Theorem 2071:Concurrent programming and Transactional memory. 2042:guarantees (local) CO (a CO compliant schedule). 1483:The above global cycle elimination process by a 1475:in the theorem above (for global transactions). 581:(SS2PL) property, which in conjunction with the 6295:"Serializable isolation for snapshot databases" 6188:"Committing conflicting transactions in an STM" 5923:(voting by local precedence order) are needed. 5713:(using the condition in the theorem above) and 5691:is guaranteed (no local CO is needed anymore). 2097:(COCO), can be designed straightforwardly as a 1145:atomic commitment protocol's abort policies (a 5797:MVCO compliance of every database system is a 5003:CO variants: special cases and generalizations 4364:{\displaystyle T_{\text{2B}}=R_{\text{2B}}(y)} 4314:{\displaystyle T_{\text{2A}}=W_{\text{2A}}(x)} 4264:{\displaystyle T_{\text{1B}}=W_{\text{1B}}(y)} 4214:{\displaystyle T_{\text{1A}}=R_{\text{1A}}(x)} 4118:{\displaystyle T_{\text{2B}}=R_{\text{2B}}(y)} 4069:{\displaystyle T_{\text{1B}}=W_{\text{1B}}(y)} 4020:{\displaystyle T_{\text{1A}}=R_{\text{1A}}(x)} 3971:{\displaystyle T_{\text{2A}}=W_{\text{2A}}(x)} 3231:{\displaystyle T_{\text{2B}}=R_{\text{2B}}(y)} 3181:{\displaystyle T_{\text{2A}}=W_{\text{2A}}(x)} 3101:{\displaystyle T_{\text{1B}}=W_{\text{1B}}(y)} 3051:{\displaystyle T_{\text{1A}}=R_{\text{1A}}(x)} 2225:CO compliance with every database system is a 1836:(using the condition in the theorem above). A 6301:, pp. 729-738, Vancouver, Canada, June 2008, 5766:(1SER or 1SR) which is the generalization of 5550:be undecided (neither committed nor aborted) 4963:; i.e., DOCO and Distributed serializability) 4840:(i.e., spans two databases or more) causes a 3249:at a certain point in time is the following: 2138:), and a different proof method for this in ( 627:Two major generalizing variants of CO exist, 8: 6112: 6110: 5725:(spans two or more databases) exists in the 4921:Global CO enforcement vote ordering strategy 2598:A distributed database system that utilizes 2565:The Distributed optimistic CO (DOCO) Theorem 1875:The CO Locking-based Global-Deadlock Theorem 1844:(spans two or more databases) exists in the 1615:is blocked by a data-access lock applied by 551:, possibly highly distributed (e.g., within 489:, CO has also been increasingly utilized in 6169: 6167: 5820:Example: CO based snapshot isolation (COSI) 5643:ended (either committed or aborted) before 4915:In a MuSiC environment local schedules are 2504:Participants in atomic commitment protocol: 1360:ended (either committed or aborted) before 53:Learn how and when to remove these messages 16:Concurrency control technique for databases 6153:, Morgan Kaufmann (Elsevier), June 2009, 6040:On the Significance of Commitment Ordering 5442:The ECO and Global Serializability Theorem 4125:ends, which is a voting-deadlock. Now the 2484:. The data managers meet three conditions: 2359:is a necessary condition for guaranteeing 2249:captures the intended notion of autonomy: 1460:Global CO implies Global serializability. 1411:that enforces global CO is referred to as 6278: 6247:, Evan Jones, Yang Zhang, Samuel Madden, 6120:, Michael Merritt, William Weihl (1988): 5888:for atomic commitment, primarily for the 5654: 5648: 5627: 5621: 5600: 5594: 5573: 5567: 5534: 5521: 5515: 5416: 5410: 5389: 5383: 5354: 5348: 5327: 5321: 5300: 5294: 5273: 5267: 5230: 5217: 5211: 4768: 4749: 4730: 4711: 4705: 4637: 4618: 4599: 4593: 4525: 4506: 4487: 4481: 4413: 4394: 4388: 4346: 4333: 4327: 4296: 4283: 4277: 4246: 4233: 4227: 4196: 4183: 4177: 4100: 4087: 4081: 4051: 4038: 4032: 4002: 3989: 3983: 3953: 3940: 3934: 3893:In the scenario above both conflicts are 3864: 3858: 3837: 3831: 3810: 3804: 3783: 3777: 3756: 3750: 3716: 3710: 3689: 3683: 3650: 3644: 3614: 3608: 3581: 3575: 3544: 3538: 3500: 3494: 3464: 3458: 3437: 3431: 3410: 3404: 3371: 3365: 3336: 3330: 3298: 3292: 3263: 3257: 3213: 3200: 3194: 3163: 3150: 3144: 3122: 3116: 3083: 3070: 3064: 3033: 3020: 3014: 2992: 2986: 2955:on each of the nodes) are the following: 2939: 2933: 2912: 2906: 2869: 2863: 2834: 2821: 2815: 2794: 2788: 2756: 2750: 2721: 2708: 2702: 2681: 2675: 2651: 2645: 2624: 2618: 2208:The CO and Global serializability Theorem 1710: 1704: 1680: 1674: 1653: 1647: 1626: 1620: 1599: 1593: 1568: 1562: 1541: 1535: 1468: 1425: 1416: 1371: 1365: 1344: 1338: 1317: 1311: 1288: 1282: 1261: 1255: 1226: 1220: 1199: 1186: 1180: 1029: 1023: 1002: 996: 971: 965: 942: 936: 915: 909: 884: 878: 853: 840: 834: 444:Learn how and when to remove this message 379:Learn how and when to remove this message 321:Learn how and when to remove this message 305:, without removing the technical details. 266:Learn how and when to remove this message 204:Learn how and when to remove this message 5931:The CO Variants Interoperability Theorem 5762:versions (of each object). MVCO implies 5698:situation can be summarized as follows: 5558:of unaborted transactions exists in the 5254:of unaborted transactions exists in the 5250:transactions in a schedule, such that a 5200:Definition: extended commitment ordering 5088: 5013:Like CO, both generalizing variants are 4136: 2959: 2317: 2229:for guaranteeing Global serializability. 1817:situation can be summarized as follows: 229:This article includes a list of general 6106: 5029:Strong strict two phase locking (SS2PL) 1642:(the blocking prevents the conflict of 505:. CO is also the name of the resulting 6023:Theory of Commitment Ordering: Summary 5840:Making snapshot isolation serializable 2852:{\displaystyle T_{2}=R_{\text{2B}}(y)} 2810:reads y on B and writes x on A, i.e., 2739:{\displaystyle T_{1}=R_{\text{1A}}(x)} 2697:reads x on A and writes y on B, i.e., 2027:The Generic Local CO Algorithm Theorem 1805: 1791:local-commit and voting wait-for graph 873:transactions in a schedule, such that 547:) of multi-database systems and other 481:, and related applications. It allows 85:may be able to help recruit an expert. 5990:, Vancouver, Canada, pp. 292–312 5142:The SCO Vs. SS2PL Performance Theorem 2584:Thus, no deadlock handling is needed. 1832:) database systems that enforce each 1731:The graph can also be defined as the 527:, high-performance, distributed, and 303:make it understandable to non-experts 7: 6142:Principles of Transaction Processing 5374:, indirectly). The schedule has the 3925:, all local sub-transactions are in 3918: 2022:The following theorem is concluded: 1516:Definition: augmented conflict graph 6323:Yoav Raz's Commitment ordering page 5562:(that of the database itself) from 5499:can be summarized similarly to CO: 2047:Generic enhanced local CO algorithm 2017:generic enhanced local CO algorithm 1699:This blocking will not stop before 826:Definition: commitment ordering 6251:, John Hugg, Daniel Abadi (2008): 5672:necessary and sufficient condition 5157:Semi-optimistic database scheduler 5094:Read-write conflict: SCO Vs. SS2PL 5056: 3772:is running on B concurrently with 2383:Distributed serializability and CO 1935:, which are typically hot spots). 1739:with the (reversed edge, regular) 1393:necessary and sufficient condition 235:it lacks sufficient corresponding 14: 6226:(PPoPP '07), ACM New York ©2007, 5747:Multi-version Commitment Ordering 5694:Similarly to CO as well, the ECO 4832:Conflicts and thus cycles in the 2443:component (also referred to as a 2425:distributed transactional systems 1387:is voted on to be committed (the 501:(STM) to achieve serializability 34:This article has multiple issues. 5835:multiversion concurrency control 4864:Distributed optimistic CO (DOCO) 3518:{\displaystyle W_{\text{2A}}(x)} 3482:{\displaystyle W_{\text{1B}}(y)} 3389:{\displaystyle R_{\text{1A}}(x)} 3354:{\displaystyle R_{\text{2B}}(y)} 3316:{\displaystyle R_{\text{2B}}(y)} 3281:{\displaystyle R_{\text{1A}}(x)} 2887:{\displaystyle W_{\text{2A}}(x)} 2774:{\displaystyle W_{\text{1B}}(y)} 2555:Distributed optimistic CO (DOCO) 2466:distributed transactional system 2254:Definition: generalized autonomy 1101:needed in different situations. 395: 337: 282: 220: 106: 64: 23: 6046:, Digital Equipment Corporation 5844:Serializable snapshot isolation 5727:Global augmented conflict graph 5703:The ECO Voting-Deadlock Theorem 5495:The condition for guaranteeing 5437:concurrency control mechanism. 5184:General characterization of ECO 5040:Strong Strict Two Phase Locking 2480:) that manage all the system's 1884:Global augmented conflict graph 1846:Global augmented conflict graph 1789:is, in fact, a (reversed edge) 1492:"wait for vote to commit" graph 578:strong strict two-phase locking 545:distributed concurrency control 42:or discuss these issues on the 6002:Information Processing Letters 5949:property, a generalization of 5827:(COSI) is the intersection of 5715:local conflict serializability 5173:Optimistic commitment ordering 4780: 4774: 4761: 4755: 4742: 4736: 4723: 4717: 4649: 4643: 4630: 4624: 4611: 4605: 4537: 4531: 4518: 4512: 4499: 4493: 4425: 4419: 4406: 4400: 4358: 4352: 4308: 4302: 4258: 4252: 4208: 4202: 4112: 4106: 4063: 4057: 4014: 4008: 3965: 3959: 3512: 3506: 3476: 3470: 3383: 3377: 3348: 3342: 3310: 3304: 3275: 3269: 3225: 3219: 3175: 3169: 3095: 3089: 3045: 3039: 2881: 2875: 2846: 2840: 2768: 2762: 2733: 2727: 2613:Two distributed transactions, 2414:optimistic concurrency control 1822:The CO Voting-Deadlock Theorem 808:optimistic concurrency control 795:General characterization of CO 463:) is a class of interoperable 1: 6309:(SIGMOD 2008 best paper award 6051:Yoav Raz (1991a): US patents 5994:Digital Equipment Corporation 5915:(VO or Generalized CO (GCO); 5801:for guaranteeing Global 1SER. 5750: 5484: 5457: 5192: 5108: 5097: 5042:(SS2PL; also referred to as 3659:{\displaystyle T_{\text{2A}}} 3623:{\displaystyle T_{\text{2B}}} 3590:{\displaystyle T_{\text{1B}}} 3553:{\displaystyle T_{\text{1A}}} 2574:No local deadlocks occur, and 2323:Schedule classes containment: 2139: 2102: 753: 647:(VO or Generalized CO (GCO); 640: 632: 607: 499:software transactional memory 6257:Proceedings of the 2008 VLDB 6014:10.1016/0020-0190(94)90005-1 5916: 5877:The distributed CO algorithm 5683:mechanism) and enforces the 5376:Extended commitment ordering 5189:Extended Commitment Ordering 4942:The following is concluded: 4932: 3453:holds read-locks on y. Thus 2901:on A and B (the portions of 2330: 2242: 2236:Extended commitment ordering 2196: 2178:(concurrency control based) 2160: 2135: 2095:Commitment Order Coordinator 1983: 1974:A generic local CO algorithm 1445: 1161:The following is concluded: 1158:for guaranteeing Global CO. 1061:The distributed CO algorithm 694:commit order serializability 681: 677: 673: 669: 648: 119:general notability guideline 83:WikiProject Computer science 6234:doi 10.1145/1229428.1229443 6037:Raz, Yoav (November 1990), 5825:CO based snapshot isolation 5543:{\displaystyle T_{1},T_{2}} 5239:{\displaystyle T_{1},T_{2}} 5062:Global CO enforcing theorem 4138:Voting-deadlock situations 3426:holds a read-lock on x and 2604:transactional data managers 2571:If DOCO is utilized, then: 2494:Shared nothing architecture 2474:transactional data managers 1785:In the presence of CO, the 1208:{\displaystyle T_{1},T_{2}} 862:{\displaystyle T_{1},T_{2}} 719:Serialization graph testing 595:In addition, locking based 408:to comply with Knowledge's 77:. The specific problem is: 6374: 5456:See a necessity proof in ( 5122:locks with ordered sharing 5111:)) is the intersection of 5105:Strict Commitment Ordering 5057:local generic CO algorithm 5032: 3564:(execution has ended) and 2441:transactional data manager 2260:A database system has the 2192:atomic commitment protocol 2180:autonomous database system 2040:Generic local CO algorithm 1980:generic local CO algorithm 1584:if two conditions are met: 1067:Global commitment ordering 782:With the proliferation of 604:strict commitment ordering 565:atomic commitment protocol 541:global concurrency control 126:reliable secondary sources 115:The topic of this article 5979:Raz, Yoav (August 1992), 5786:MVCO compliance of every 1471:below) and enforcing the 1073:two-phase commit protocol 726:federated database system 584:two-phase commit protocol 117:may not meet Knowledge's 6139:, Eric Newcomer (2009): 5962:augmented conflict graph 5862:(and thus also regular) 5833:(SI) with MVCO. SI is a 5764:One-copy-serializability 5721:occurs if and only if a 4927:Furthermore, also local 4834:augmented conflict graph 4132:augmented conflict graph 2406:distributed lock manager 2351:augmented conflict graph 2312:conflict serializability 2009:augmented conflict graph 2007:). A local cycle in the 1999:can be used (e.g., like 1840:occurs if and only if a 1787:augmented conflict graph 1524:augmented conflict graph 1509:augmented conflict graph 987:). The schedule has the 520:conflict serializability 421:may contain suggestions. 406:may need to be rewritten 6020:Raz, Yoav (June 2009), 5755:multi-version resources 5742:Multi-version CO (MVCO) 4076:is not voted on before 3978:is not voted on before 3901:(but not in the global 2961:Local sub-transactions 2429:distributed transaction 2214:CO compliance of every 1993:augments conflict graph 1966:of the intersection of 1437:{\displaystyle CD^{3}C} 777:transactional processes 610:), the intersection of 250:more precise citations. 6358:Distributed algorithms 6348:Transaction processing 5759:read-only transactions 5757:. With such resources 5689:Global serializability 5685:vote ordering strategy 5664: 5637: 5610: 5583: 5544: 5426: 5399: 5364: 5337: 5310: 5283: 5240: 5101: 4787: 4656: 4544: 4432: 4365: 4315: 4265: 4215: 4119: 4070: 4021: 3972: 3874: 3847: 3820: 3793: 3766: 3726: 3699: 3660: 3624: 3591: 3568:(in atomic commitment) 3554: 3519: 3483: 3447: 3420: 3390: 3355: 3317: 3282: 3245:The database system's 3232: 3182: 3132: 3102: 3052: 3002: 2949: 2922: 2899:local sub-transactions 2888: 2853: 2804: 2775: 2740: 2691: 2661: 2634: 2361:Global serializability 2334: 2308:Global serializability 1720: 1690: 1663: 1636: 1609: 1578: 1551: 1473:vote ordering strategy 1438: 1409:vote ordering strategy 1389:vote ordering strategy 1381: 1354: 1327: 1298: 1271: 1236: 1209: 1152:vote ordering strategy 1132:vote ordering strategy 1115:vote ordering strategy 1039: 1012: 981: 952: 925: 894: 863: 758:Global serializability 734:global serializability 533:global serializability 491:concurrent programming 479:transaction processing 359:by rewriting it in an 5665: 5663:{\displaystyle T_{2}} 5638: 5636:{\displaystyle T_{1}} 5611: 5609:{\displaystyle T_{2}} 5584: 5582:{\displaystyle T_{1}} 5545: 5427: 5425:{\displaystyle T_{2}} 5400: 5398:{\displaystyle T_{1}} 5365: 5363:{\displaystyle T_{2}} 5338: 5336:{\displaystyle T_{1}} 5311: 5309:{\displaystyle T_{2}} 5284: 5282:{\displaystyle T_{1}} 5241: 5092: 4788: 4657: 4545: 4433: 4366: 4316: 4266: 4216: 4120: 4071: 4022: 3973: 3875: 3873:{\displaystyle T_{3}} 3848: 3846:{\displaystyle T_{1}} 3821: 3819:{\displaystyle T_{2}} 3794: 3792:{\displaystyle T_{1}} 3767: 3765:{\displaystyle T_{3}} 3727: 3725:{\displaystyle T_{2}} 3700: 3698:{\displaystyle T_{1}} 3661: 3625: 3592: 3555: 3520: 3484: 3448: 3446:{\displaystyle T_{2}} 3421: 3419:{\displaystyle T_{1}} 3391: 3356: 3318: 3283: 3233: 3183: 3133: 3131:{\displaystyle T_{2}} 3103: 3053: 3003: 3001:{\displaystyle T_{1}} 2950: 2948:{\displaystyle T_{2}} 2923: 2921:{\displaystyle T_{1}} 2889: 2854: 2805: 2803:{\displaystyle T_{2}} 2776: 2741: 2692: 2690:{\displaystyle T_{1}} 2662: 2660:{\displaystyle T_{2}} 2635: 2633:{\displaystyle T_{1}} 2531:distributed deadlocks 2450:distributed deadlocks 2321: 2186:A database system is 2091:software architecture 1933:accumulation counters 1888:Global conflict graph 1721: 1719:{\displaystyle T_{1}} 1691: 1689:{\displaystyle T_{1}} 1664: 1662:{\displaystyle T_{2}} 1637: 1635:{\displaystyle T_{1}} 1610: 1608:{\displaystyle T_{2}} 1579: 1577:{\displaystyle T_{2}} 1552: 1550:{\displaystyle T_{1}} 1439: 1382: 1380:{\displaystyle T_{2}} 1355: 1353:{\displaystyle T_{1}} 1328: 1326:{\displaystyle T_{2}} 1299: 1297:{\displaystyle T_{1}} 1272: 1270:{\displaystyle T_{1}} 1237: 1235:{\displaystyle T_{2}} 1210: 1040: 1038:{\displaystyle T_{2}} 1013: 1011:{\displaystyle T_{1}} 982: 980:{\displaystyle T_{2}} 953: 951:{\displaystyle T_{1}} 926: 924:{\displaystyle T_{1}} 895: 893:{\displaystyle T_{2}} 864: 784:Multi-core processors 730:Distributed databases 698:strong recoverability 549:transactional objects 523:and effective means ( 487:multi-core processors 153:"Commitment ordering" 5947:generalized autonomy 5940:sufficient condition 5799:sufficient condition 5647: 5620: 5593: 5566: 5560:local conflict graph 5514: 5480:Max flow in networks 5409: 5382: 5347: 5320: 5293: 5266: 5210: 5010:generalized autonomy 4704: 4592: 4480: 4387: 4326: 4276: 4226: 4176: 4080: 4031: 3982: 3933: 3857: 3830: 3803: 3776: 3749: 3709: 3682: 3643: 3607: 3574: 3537: 3493: 3457: 3430: 3403: 3364: 3329: 3291: 3256: 3193: 3143: 3115: 3063: 3013: 2985: 2932: 2905: 2862: 2814: 2787: 2749: 2701: 2674: 2644: 2617: 2470:distributed database 2418:distributed deadlock 2402:(distributed) system 2290:transactional object 2262:Generalized autonomy 2247:Generalized autonomy 2227:sufficient condition 2144:sufficient condition 2079:Transactional memory 1947:Enforcing CO locally 1703: 1673: 1646: 1619: 1592: 1561: 1534: 1469:Enforcing CO locally 1415: 1364: 1337: 1310: 1281: 1254: 1219: 1179: 1156:sufficient condition 1065:A fully distributed 1022: 995: 964: 935: 908: 877: 833: 653:generalized autonomy 507:transaction schedule 495:transactional memory 6353:Concurrency control 6249:Michael Stonebraker 6137:Philip A. Bernstein 5955:necessary condition 5921:vote order strategy 5792:necessary condition 5731:global transactions 5552:global transactions 5167:Optimistic CO (OCO) 5048:Rigorous scheduling 4974:deadlock resolution 4139: 3525:are blocked by the 2962: 2540:necessary condition 2327:inherently blocking 2279:Commitment ordering 2220:necessary condition 2132:necessary condition 2128:commitment ordering 1952:Commitment ordering 1850:global transactions 1465:Global CO algorithm 1119:necessary condition 1108:Enforcing global CO 989:Commitment ordering 800:Commitment ordering 773:Commitment ordering 715:Time-stamp ordering 666:Commitment ordering 569:necessary condition 471:concurrency control 457:Commitment ordering 6149:2010-08-07 at the 6088:Yoav Raz (1993b): 6076:Yoav Raz (1993a): 5992:(also DEC-TR 841, 5830:Snapshot isolation 5660: 5633: 5606: 5579: 5540: 5422: 5395: 5360: 5333: 5306: 5279: 5236: 5102: 4899:integrated circuit 4783: 4652: 4540: 4428: 4361: 4311: 4261: 4211: 4137: 4115: 4066: 4017: 3968: 3870: 3843: 3816: 3789: 3762: 3722: 3695: 3656: 3620: 3587: 3550: 3527:lock compatibility 3515: 3479: 3443: 3416: 3386: 3351: 3313: 3278: 3228: 3178: 3128: 3098: 3048: 2998: 2960: 2945: 2918: 2884: 2849: 2800: 2771: 2736: 2687: 2657: 2630: 2529:Data-access-based 2431:. Also, typically 2335: 1716: 1686: 1659: 1632: 1605: 1574: 1547: 1434: 1377: 1350: 1323: 1294: 1267: 1232: 1205: 1078:integrated circuit 1035: 1008: 977: 948: 921: 890: 859: 559:, and networks of 361:encyclopedic style 348:is written like a 121: 6307:978-1-60558-102-6 6232:978-1-59593-602-8 6204:978-1-60558-397-6 6159:978-1-55860-623-4 5856:atomic commitment 5773:atomic commitment 5472:The ECO algorithm 5246:be two committed 5179:Extended CO (ECO) 5171:For implementing 5067:atomic commitment 5035:Two-phase locking 4947:The MuSiC Theorem 4822: 4821: 4771: 4752: 4733: 4714: 4640: 4621: 4602: 4528: 4509: 4490: 4416: 4397: 4349: 4336: 4299: 4286: 4249: 4236: 4199: 4186: 4156:Possible schedule 4103: 4090: 4054: 4041: 4005: 3992: 3956: 3943: 3736:and re-executed. 3653: 3617: 3584: 3547: 3503: 3467: 3374: 3339: 3301: 3266: 3241: 3240: 3216: 3203: 3166: 3153: 3086: 3073: 3036: 3023: 2872: 2837: 2759: 2724: 2608:resource managers 2594:Distributed SS2PL 2478:resource managers 2472:system) comprise 2295:atomic commitment 2165:database autonomy 2142:)); it is also a 1959:two phase locking 1929:atomic commitment 1918:atomic commitment 1910:Atomic commitment 1806:Extended CO (ECO) 1735:of the (regular) 767:atomic commitment 686:Dynamic atomicity 622:database recovery 589:de facto standard 511:dynamic atomicity 454: 453: 446: 436: 435: 410:quality standards 389: 388: 381: 331: 330: 323: 276: 275: 268: 214: 213: 206: 188: 116: 100: 99: 57: 6365: 6310: 6291: 6285: 6284: 6282: 6266: 6260: 6241: 6235: 6212: 6206: 6184: 6178: 6171: 6162: 6161:(pages 145, 360) 6134: 6128: 6114: 6096: 6084: 6072: 6067: 6061: 6059:5,701,480 (MVCO) 6047: 6045: 6033: 6032: 6030: 6016: 5996:, November 1990) 5991: 5985: 5892:protocol, e.g., 5890:two phase commit 5860:global augmented 5669: 5667: 5666: 5661: 5659: 5658: 5642: 5640: 5639: 5634: 5632: 5631: 5615: 5613: 5612: 5607: 5605: 5604: 5588: 5586: 5585: 5580: 5578: 5577: 5549: 5547: 5546: 5541: 5539: 5538: 5526: 5525: 5431: 5429: 5428: 5423: 5421: 5420: 5404: 5402: 5401: 5396: 5394: 5393: 5369: 5367: 5366: 5361: 5359: 5358: 5342: 5340: 5339: 5334: 5332: 5331: 5315: 5313: 5312: 5307: 5305: 5304: 5288: 5286: 5285: 5280: 5278: 5277: 5260:precedence graph 5245: 5243: 5242: 5237: 5235: 5234: 5222: 5221: 4850:non-materialized 4792: 4790: 4789: 4784: 4773: 4772: 4769: 4754: 4753: 4750: 4735: 4734: 4731: 4716: 4715: 4712: 4661: 4659: 4658: 4653: 4642: 4641: 4638: 4623: 4622: 4619: 4604: 4603: 4600: 4549: 4547: 4546: 4541: 4530: 4529: 4526: 4511: 4510: 4507: 4492: 4491: 4488: 4437: 4435: 4434: 4429: 4418: 4417: 4414: 4399: 4398: 4395: 4370: 4368: 4367: 4362: 4351: 4350: 4347: 4338: 4337: 4334: 4320: 4318: 4317: 4312: 4301: 4300: 4297: 4288: 4287: 4284: 4270: 4268: 4267: 4262: 4251: 4250: 4247: 4238: 4237: 4234: 4220: 4218: 4217: 4212: 4201: 4200: 4197: 4188: 4187: 4184: 4140: 4124: 4122: 4121: 4116: 4105: 4104: 4101: 4092: 4091: 4088: 4075: 4073: 4072: 4067: 4056: 4055: 4052: 4043: 4042: 4039: 4026: 4024: 4023: 4018: 4007: 4006: 4003: 3994: 3993: 3990: 3977: 3975: 3974: 3969: 3958: 3957: 3954: 3945: 3944: 3941: 3915:non-materialized 3895:non-materialized 3879: 3877: 3876: 3871: 3869: 3868: 3852: 3850: 3849: 3844: 3842: 3841: 3825: 3823: 3822: 3817: 3815: 3814: 3798: 3796: 3795: 3790: 3788: 3787: 3771: 3769: 3768: 3763: 3761: 3760: 3731: 3729: 3728: 3723: 3721: 3720: 3704: 3702: 3701: 3696: 3694: 3693: 3665: 3663: 3662: 3657: 3655: 3654: 3651: 3629: 3627: 3626: 3621: 3619: 3618: 3615: 3596: 3594: 3593: 3588: 3586: 3585: 3582: 3559: 3557: 3556: 3551: 3549: 3548: 3545: 3524: 3522: 3521: 3516: 3505: 3504: 3501: 3488: 3486: 3485: 3480: 3469: 3468: 3465: 3452: 3450: 3449: 3444: 3442: 3441: 3425: 3423: 3422: 3417: 3415: 3414: 3395: 3393: 3392: 3387: 3376: 3375: 3372: 3360: 3358: 3357: 3352: 3341: 3340: 3337: 3322: 3320: 3319: 3314: 3303: 3302: 3299: 3287: 3285: 3284: 3279: 3268: 3267: 3264: 3237: 3235: 3234: 3229: 3218: 3217: 3214: 3205: 3204: 3201: 3187: 3185: 3184: 3179: 3168: 3167: 3164: 3155: 3154: 3151: 3137: 3135: 3134: 3129: 3127: 3126: 3107: 3105: 3104: 3099: 3088: 3087: 3084: 3075: 3074: 3071: 3057: 3055: 3054: 3049: 3038: 3037: 3034: 3025: 3024: 3021: 3007: 3005: 3004: 2999: 2997: 2996: 2963: 2954: 2952: 2951: 2946: 2944: 2943: 2927: 2925: 2924: 2919: 2917: 2916: 2893: 2891: 2890: 2885: 2874: 2873: 2870: 2858: 2856: 2855: 2850: 2839: 2838: 2835: 2826: 2825: 2809: 2807: 2806: 2801: 2799: 2798: 2780: 2778: 2777: 2772: 2761: 2760: 2757: 2745: 2743: 2742: 2737: 2726: 2725: 2722: 2713: 2712: 2696: 2694: 2693: 2688: 2686: 2685: 2666: 2664: 2663: 2658: 2656: 2655: 2639: 2637: 2636: 2631: 2629: 2628: 2482:recoverable data 2445:resource manager 2433:recoverable data 2371:The CO solution 2245:) the notion of 1970:and strictness. 1725: 1723: 1722: 1717: 1715: 1714: 1695: 1693: 1692: 1687: 1685: 1684: 1668: 1666: 1665: 1660: 1658: 1657: 1641: 1639: 1638: 1633: 1631: 1630: 1614: 1612: 1611: 1606: 1604: 1603: 1583: 1581: 1580: 1575: 1573: 1572: 1556: 1554: 1553: 1548: 1546: 1545: 1443: 1441: 1440: 1435: 1430: 1429: 1386: 1384: 1383: 1378: 1376: 1375: 1359: 1357: 1356: 1351: 1349: 1348: 1333:). Then, having 1332: 1330: 1329: 1324: 1322: 1321: 1303: 1301: 1300: 1295: 1293: 1292: 1276: 1274: 1273: 1268: 1266: 1265: 1241: 1239: 1238: 1233: 1231: 1230: 1214: 1212: 1211: 1206: 1204: 1203: 1191: 1190: 1082:one-phase commit 1044: 1042: 1041: 1036: 1034: 1033: 1017: 1015: 1014: 1009: 1007: 1006: 986: 984: 983: 978: 976: 975: 957: 955: 954: 949: 947: 946: 930: 928: 927: 922: 920: 919: 899: 897: 896: 891: 889: 888: 868: 866: 865: 860: 858: 857: 845: 844: 637:multi-version CO 597:global deadlocks 449: 442: 431: 428: 422: 399: 391: 384: 377: 373: 370: 364: 341: 340: 333: 326: 319: 315: 312: 306: 286: 285: 278: 271: 264: 260: 257: 251: 246:this article by 237:inline citations 224: 223: 216: 209: 202: 198: 195: 189: 187: 146: 110: 109: 102: 95: 92: 86: 68: 67: 60: 49: 27: 26: 19: 6373: 6372: 6368: 6367: 6366: 6364: 6363: 6362: 6338:Data management 6328: 6327: 6319: 6314: 6313: 6292: 6288: 6268: 6267: 6263: 6242: 6238: 6213: 6209: 6185: 6181: 6172: 6165: 6151:Wayback Machine 6135: 6131: 6115: 6108: 6103: 6087: 6075: 6070: 6064: 6053:5,504,899 (ECO) 6050: 6043: 6036: 6028: 6026: 6019: 5999: 5983: 5978: 5975: 5966:voting deadlock 5884:, some already 5852: 5822: 5768:serializability 5744: 5719:voting-deadlock 5696:voting-deadlock 5650: 5645: 5644: 5623: 5618: 5617: 5616:. Then, having 5596: 5591: 5590: 5569: 5564: 5563: 5530: 5517: 5512: 5511: 5474: 5412: 5407: 5406: 5405:commits before 5385: 5380: 5379: 5350: 5345: 5344: 5323: 5318: 5317: 5296: 5291: 5290: 5269: 5264: 5263: 5226: 5213: 5208: 5207: 5186: 5181: 5169: 5087: 5085:Strict CO (SCO) 5037: 5031: 5005: 4961:Serializability 4873: 4842:voting deadlock 4817: 4812: 4807: 4802: 4764: 4745: 4726: 4707: 4702: 4701: 4686: 4681: 4676: 4671: 4633: 4614: 4595: 4590: 4589: 4574: 4569: 4564: 4559: 4521: 4502: 4483: 4478: 4477: 4462: 4457: 4452: 4447: 4409: 4390: 4385: 4384: 4342: 4329: 4324: 4323: 4292: 4279: 4274: 4273: 4242: 4229: 4224: 4223: 4192: 4179: 4174: 4173: 4169: 4167: 4162: 4160: 4152: 4147: 4096: 4083: 4078: 4077: 4047: 4034: 4029: 4028: 3998: 3985: 3980: 3979: 3949: 3936: 3931: 3930: 3891: 3860: 3855: 3854: 3833: 3828: 3827: 3806: 3801: 3800: 3779: 3774: 3773: 3752: 3747: 3746: 3742: 3712: 3707: 3706: 3685: 3680: 3679: 3646: 3641: 3640: 3610: 3605: 3604: 3577: 3572: 3571: 3540: 3535: 3534: 3496: 3491: 3490: 3460: 3455: 3454: 3433: 3428: 3427: 3406: 3401: 3400: 3367: 3362: 3361: 3332: 3327: 3326: 3294: 3289: 3288: 3259: 3254: 3253: 3209: 3196: 3191: 3190: 3159: 3146: 3141: 3140: 3118: 3113: 3112: 3079: 3066: 3061: 3060: 3029: 3016: 3011: 3010: 2988: 2983: 2982: 2971: 2968: 2935: 2930: 2929: 2908: 2903: 2902: 2897:The respective 2865: 2860: 2859: 2830: 2817: 2812: 2811: 2790: 2785: 2784: 2752: 2747: 2746: 2717: 2704: 2699: 2698: 2677: 2672: 2671: 2647: 2642: 2641: 2620: 2615: 2614: 2596: 2591: 2557: 2524:serializability 2490:Data partition: 2390: 2385: 2275: 2148:serializability 2123: 2087: 2065: 2013:local algorithm 1976: 1949: 1893:serializability 1838:voting-deadlock 1815:voting-deadlock 1706: 1701: 1700: 1676: 1671: 1670: 1649: 1644: 1643: 1622: 1617: 1616: 1595: 1590: 1589: 1564: 1559: 1558: 1557:to transaction 1537: 1532: 1531: 1485:voting deadlock 1481: 1421: 1413: 1412: 1367: 1362: 1361: 1340: 1335: 1334: 1313: 1308: 1307: 1284: 1279: 1278: 1257: 1252: 1251: 1222: 1217: 1216: 1195: 1182: 1177: 1176: 1110: 1063: 1025: 1020: 1019: 1018:commits before 998: 993: 992: 967: 962: 961: 938: 933: 932: 911: 906: 905: 880: 875: 874: 849: 836: 831: 830: 797: 792: 690:commit ordering 662: 553:cloud computing 466:serializability 450: 439: 438: 437: 432: 426: 423: 413: 400: 385: 374: 368: 365: 357:help improve it 354: 342: 338: 327: 316: 310: 307: 299:help improve it 296: 287: 283: 272: 261: 255: 252: 242:Please help to 241: 225: 221: 210: 199: 193: 190: 147: 145: 123: 111: 107: 96: 90: 87: 81: 69: 65: 28: 24: 17: 12: 11: 5: 6371: 6369: 6361: 6360: 6355: 6350: 6345: 6340: 6330: 6329: 6326: 6325: 6318: 6317:External links 6315: 6312: 6311: 6286: 6280:10.1.1.53.7318 6261: 6245:Stanley Zdonik 6236: 6207: 6179: 6163: 6129: 6105: 6104: 6102: 6099: 6098: 6097: 6085: 6073: 6068: 6062: 6056:5,504,900 (CO) 6048: 6034: 6017: 6008:(5): 257–264, 5997: 5974: 5971: 5970: 5969: 5958: 5943: 5934: 5933: 5864:conflict graph 5851: 5848: 5821: 5818: 5814: 5813: 5806: 5805: 5802: 5795: 5783: 5782: 5743: 5740: 5736: 5735: 5706: 5705: 5676: 5675: 5657: 5653: 5630: 5626: 5603: 5599: 5576: 5572: 5537: 5533: 5529: 5524: 5520: 5507: 5506: 5473: 5470: 5462: 5461: 5453: 5452: 5449: 5445: 5444: 5434: 5433: 5419: 5415: 5392: 5388: 5357: 5353: 5330: 5326: 5303: 5299: 5276: 5272: 5256:conflict graph 5233: 5229: 5225: 5220: 5216: 5203: 5202: 5185: 5182: 5180: 5177: 5168: 5165: 5151: 5150: 5145: 5144: 5086: 5083: 5072:wait-for graph 5033:Main article: 5030: 5027: 5004: 5001: 5000: 4999: 4995: 4990: 4989: 4982: 4981: 4978: 4977: 4976: 4970: 4964: 4950: 4949: 4872: 4869: 4868: 4867: 4860: 4856: 4853: 4829: 4828: 4820: 4819: 4814: 4809: 4804: 4799: 4796: 4793: 4782: 4779: 4776: 4767: 4763: 4760: 4757: 4748: 4744: 4741: 4738: 4729: 4725: 4722: 4719: 4710: 4699: 4696: 4693: 4689: 4688: 4683: 4678: 4673: 4668: 4665: 4662: 4651: 4648: 4645: 4636: 4632: 4629: 4626: 4617: 4613: 4610: 4607: 4598: 4587: 4584: 4581: 4577: 4576: 4571: 4566: 4561: 4556: 4553: 4550: 4539: 4536: 4533: 4524: 4520: 4517: 4514: 4505: 4501: 4498: 4495: 4486: 4475: 4472: 4469: 4465: 4464: 4459: 4454: 4449: 4444: 4441: 4438: 4427: 4424: 4421: 4412: 4408: 4405: 4402: 4393: 4382: 4379: 4376: 4372: 4371: 4360: 4357: 4354: 4345: 4341: 4332: 4321: 4310: 4307: 4304: 4295: 4291: 4282: 4271: 4260: 4257: 4254: 4245: 4241: 4232: 4221: 4210: 4207: 4204: 4195: 4191: 4182: 4171: 4164: 4157: 4154: 4149: 4144: 4127:conflict graph 4114: 4111: 4108: 4099: 4095: 4086: 4065: 4062: 4059: 4050: 4046: 4037: 4016: 4013: 4010: 4001: 3997: 3988: 3967: 3964: 3961: 3952: 3948: 3939: 3903:conflict graph 3899:wait-for graph 3890: 3887: 3886: 3885: 3881: 3867: 3863: 3840: 3836: 3813: 3809: 3786: 3782: 3759: 3755: 3741: 3738: 3719: 3715: 3692: 3688: 3672: 3671: 3649: 3638: 3613: 3602: 3580: 3569: 3543: 3514: 3511: 3508: 3499: 3478: 3475: 3472: 3463: 3440: 3436: 3413: 3409: 3398: 3397: 3385: 3382: 3379: 3370: 3350: 3347: 3344: 3335: 3323: 3312: 3309: 3306: 3297: 3277: 3274: 3271: 3262: 3243: 3242: 3239: 3238: 3227: 3224: 3221: 3212: 3208: 3199: 3188: 3177: 3174: 3171: 3162: 3158: 3149: 3138: 3125: 3121: 3109: 3108: 3097: 3094: 3091: 3082: 3078: 3069: 3058: 3047: 3044: 3041: 3032: 3028: 3019: 3008: 2995: 2991: 2979: 2978: 2975: 2972: 2969: 2966: 2942: 2938: 2915: 2911: 2895: 2894: 2883: 2880: 2877: 2868: 2848: 2845: 2842: 2833: 2829: 2824: 2820: 2797: 2793: 2782: 2770: 2767: 2764: 2755: 2735: 2732: 2729: 2720: 2716: 2711: 2707: 2684: 2680: 2654: 2650: 2627: 2623: 2595: 2592: 2590: 2587: 2586: 2585: 2581: 2580: 2579: 2578: 2575: 2568: 2567: 2556: 2553: 2548: 2547: 2535: 2534: 2527: 2519: 2518: 2514: 2513: 2510:CO compliance: 2507: 2501: 2486: 2485: 2461: 2460: 2437:recoverability 2389: 2388:Distributed CO 2386: 2384: 2381: 2288:(or any other 2274: 2271: 2266: 2265: 2257: 2256: 2231: 2230: 2223: 2211: 2210: 2201: 2200: 2183: 2182: 2122: 2119: 2086: 2083: 2075: 2074: 2064: 2061: 2060: 2059: 2043: 2035: 2034: 2030: 2029: 2005:wait-for graph 1975: 1972: 1957:strong strict 1948: 1945: 1922: 1921: 1913: 1905: 1904: 1898: 1897: 1878: 1877: 1868: 1867: 1864:multi-threaded 1855: 1854: 1825: 1824: 1783: 1782: 1774: 1771:wait-for graph 1767:conflict graph 1763:wait-for graph 1759:wait-for graph 1755: 1751: 1750: 1744: 1743: 1741:wait-for graph 1737:conflict graph 1728: 1727: 1713: 1709: 1697: 1683: 1679: 1656: 1652: 1629: 1625: 1602: 1598: 1586: 1585: 1571: 1567: 1544: 1540: 1528:conflict graph 1519: 1518: 1497:wait-for graph 1480: 1477: 1458: 1457: 1454:if and only if 1449: 1433: 1428: 1424: 1420: 1404: 1403: 1397: 1396: 1374: 1370: 1347: 1343: 1320: 1316: 1291: 1287: 1264: 1260: 1229: 1225: 1202: 1198: 1194: 1189: 1185: 1172: 1171: 1109: 1106: 1062: 1059: 1047: 1046: 1032: 1028: 1005: 1001: 974: 970: 945: 941: 918: 914: 887: 883: 856: 852: 848: 843: 839: 827: 820:noncommutative 796: 793: 791: 788: 703:recoverability 688:(since 1988), 661: 658: 587:(2PC), is the 557:grid computing 503:optimistically 469:techniques in 452: 451: 434: 433: 403: 401: 394: 387: 386: 345: 343: 336: 329: 328: 290: 288: 281: 274: 273: 228: 226: 219: 212: 211: 114: 112: 105: 98: 97: 72: 70: 63: 58: 32: 31: 29: 22: 15: 13: 10: 9: 6: 4: 3: 2: 6370: 6359: 6356: 6354: 6351: 6349: 6346: 6344: 6341: 6339: 6336: 6335: 6333: 6324: 6321: 6320: 6316: 6308: 6304: 6300: 6296: 6290: 6287: 6281: 6276: 6272: 6265: 6262: 6258: 6254: 6250: 6246: 6240: 6237: 6233: 6229: 6225: 6221: 6217: 6211: 6208: 6205: 6201: 6198:(PPoPP '09), 6197: 6193: 6189: 6183: 6180: 6176: 6170: 6168: 6164: 6160: 6156: 6152: 6148: 6145: 6144:, 2nd Edition 6143: 6138: 6133: 6130: 6126: 6124: 6119: 6116:Alan Fekete, 6113: 6111: 6107: 6100: 6094: 6091: 6086: 6082: 6079: 6074: 6069: 6063: 6060: 6057: 6054: 6049: 6042: 6041: 6035: 6025: 6024: 6018: 6015: 6011: 6007: 6003: 5998: 5995: 5989: 5982: 5977: 5976: 5972: 5967: 5963: 5959: 5956: 5952: 5948: 5944: 5941: 5936: 5935: 5932: 5929: 5928: 5927: 5924: 5922: 5918: 5914: 5913:Vote ordering 5910: 5908: 5903: 5897: 5895: 5891: 5887: 5883: 5878: 5873: 5869: 5868:partial order 5865: 5861: 5857: 5849: 5847: 5845: 5841: 5836: 5832: 5831: 5826: 5819: 5817: 5811: 5808: 5807: 5803: 5800: 5796: 5793: 5789: 5785: 5784: 5781: 5778: 5777: 5776: 5774: 5769: 5765: 5760: 5756: 5752: 5748: 5741: 5739: 5732: 5728: 5724: 5720: 5716: 5712: 5708: 5707: 5704: 5701: 5700: 5699: 5697: 5692: 5690: 5686: 5682: 5673: 5655: 5651: 5628: 5624: 5601: 5597: 5574: 5570: 5561: 5557: 5556:directed path 5553: 5535: 5531: 5527: 5522: 5518: 5509: 5508: 5505: 5502: 5501: 5500: 5498: 5493: 5490: 5486: 5482: 5481: 5471: 5469: 5466: 5459: 5455: 5454: 5450: 5447: 5446: 5443: 5440: 5439: 5438: 5417: 5413: 5390: 5386: 5377: 5373: 5355: 5351: 5328: 5324: 5301: 5297: 5274: 5270: 5261: 5257: 5253: 5252:directed path 5249: 5231: 5227: 5223: 5218: 5214: 5205: 5204: 5201: 5198: 5197: 5196: 5194: 5190: 5183: 5178: 5176: 5174: 5166: 5164: 5161: 5159: 5158: 5147: 5146: 5143: 5140: 5139: 5138: 5136: 5132: 5131: 5125: 5123: 5116: 5114: 5110: 5106: 5099: 5095: 5091: 5084: 5082: 5080: 5075: 5073: 5068: 5063: 5058: 5053: 5052:proper subset 5049: 5045: 5041: 5036: 5028: 5026: 5023: 5018: 5016: 5011: 5002: 4996: 4992: 4991: 4987: 4984: 4983: 4979: 4975: 4971: 4968: 4965: 4962: 4959:(and implied 4958: 4955: 4954: 4952: 4951: 4948: 4945: 4944: 4943: 4940: 4938: 4934: 4930: 4925: 4922: 4918: 4913: 4911: 4910:no connection 4906: 4902: 4900: 4896: 4892: 4888: 4885:only, and to 4884: 4879: 4877: 4870: 4865: 4861: 4857: 4854: 4851: 4847: 4843: 4839: 4835: 4831: 4830: 4827: 4824: 4823: 4815: 4810: 4805: 4800: 4797: 4794: 4777: 4765: 4758: 4746: 4739: 4727: 4720: 4708: 4700: 4697: 4694: 4691: 4690: 4684: 4679: 4674: 4669: 4666: 4663: 4646: 4634: 4627: 4615: 4608: 4596: 4588: 4585: 4582: 4579: 4578: 4572: 4567: 4562: 4557: 4554: 4551: 4534: 4522: 4515: 4503: 4496: 4484: 4476: 4473: 4470: 4467: 4466: 4460: 4455: 4450: 4445: 4442: 4439: 4422: 4410: 4403: 4391: 4383: 4380: 4377: 4374: 4373: 4355: 4343: 4339: 4330: 4322: 4305: 4293: 4289: 4280: 4272: 4255: 4243: 4239: 4230: 4222: 4205: 4193: 4189: 4180: 4172: 4165: 4158: 4155: 4150: 4145: 4142: 4141: 4135: 4133: 4128: 4109: 4097: 4093: 4084: 4060: 4048: 4044: 4035: 4011: 3999: 3995: 3986: 3962: 3950: 3946: 3937: 3928: 3924: 3920: 3916: 3912: 3908: 3904: 3900: 3896: 3888: 3882: 3865: 3861: 3838: 3834: 3811: 3807: 3784: 3780: 3757: 3753: 3744: 3743: 3739: 3737: 3735: 3717: 3713: 3690: 3686: 3677: 3669: 3647: 3639: 3637: 3633: 3611: 3603: 3600: 3578: 3570: 3567: 3563: 3541: 3533: 3532: 3531: 3528: 3509: 3497: 3473: 3461: 3438: 3434: 3411: 3407: 3380: 3368: 3345: 3333: 3324: 3307: 3295: 3272: 3260: 3252: 3251: 3250: 3248: 3222: 3210: 3206: 3197: 3189: 3172: 3160: 3156: 3147: 3139: 3123: 3119: 3111: 3110: 3092: 3080: 3076: 3067: 3059: 3042: 3030: 3026: 3017: 3009: 2993: 2989: 2981: 2980: 2976: 2973: 2965: 2964: 2958: 2957: 2956: 2940: 2936: 2913: 2909: 2900: 2878: 2866: 2843: 2831: 2827: 2822: 2818: 2795: 2791: 2783: 2765: 2753: 2730: 2718: 2714: 2709: 2705: 2682: 2678: 2670: 2669: 2668: 2652: 2648: 2625: 2621: 2611: 2609: 2605: 2601: 2593: 2588: 2583: 2582: 2576: 2573: 2572: 2570: 2569: 2566: 2563: 2562: 2561: 2554: 2552: 2545: 2541: 2537: 2536: 2532: 2528: 2525: 2521: 2520: 2516: 2515: 2511: 2508: 2505: 2502: 2499: 2495: 2491: 2488: 2487: 2483: 2479: 2476:(also called 2475: 2471: 2467: 2463: 2462: 2459: 2456: 2455: 2454: 2452: 2451: 2446: 2442: 2438: 2434: 2430: 2426: 2421: 2419: 2415: 2411: 2407: 2403: 2398: 2396: 2387: 2382: 2380: 2378: 2374: 2369: 2366: 2362: 2358: 2354: 2352: 2347: 2346: 2340: 2332: 2328: 2324: 2320: 2316: 2313: 2309: 2305: 2301: 2300:partial order 2297: 2296: 2291: 2287: 2282: 2280: 2272: 2270: 2263: 2259: 2258: 2255: 2252: 2251: 2250: 2248: 2244: 2239: 2237: 2228: 2224: 2221: 2217: 2213: 2212: 2209: 2206: 2205: 2204: 2198: 2193: 2189: 2185: 2184: 2181: 2177: 2174: 2173: 2172: 2170: 2166: 2162: 2157: 2155: 2154: 2149: 2145: 2141: 2137: 2133: 2129: 2120: 2118: 2115: 2112: 2108: 2104: 2100: 2096: 2092: 2084: 2082: 2080: 2073: 2072: 2067: 2066: 2062: 2056: 2052: 2048: 2044: 2041: 2037: 2036: 2032: 2031: 2028: 2025: 2024: 2023: 2020: 2018: 2014: 2010: 2006: 2002: 1998: 1994: 1989: 1985: 1981: 1973: 1971: 1969: 1965: 1964:proper subset 1961: 1960: 1953: 1946: 1944: 1941: 1940:heuristically 1936: 1934: 1930: 1925: 1919: 1914: 1911: 1907: 1906: 1903: 1900: 1899: 1895: 1894: 1889: 1885: 1880: 1879: 1876: 1873: 1872: 1871: 1865: 1860: 1857: 1856: 1851: 1847: 1843: 1839: 1835: 1831: 1827: 1826: 1823: 1820: 1819: 1818: 1816: 1811: 1808: 1807: 1802: 1798: 1796: 1795:global cycles 1792: 1788: 1779: 1775: 1772: 1768: 1764: 1760: 1756: 1753: 1752: 1749: 1746: 1745: 1742: 1738: 1734: 1730: 1729: 1711: 1707: 1698: 1681: 1677: 1654: 1650: 1627: 1623: 1600: 1596: 1588: 1587: 1569: 1565: 1542: 1538: 1529: 1525: 1521: 1520: 1517: 1514: 1513: 1512: 1510: 1504: 1500: 1498: 1493: 1488: 1486: 1478: 1476: 1474: 1470: 1466: 1461: 1455: 1450: 1447: 1431: 1426: 1422: 1418: 1410: 1406: 1405: 1402: 1399: 1398: 1394: 1390: 1372: 1368: 1345: 1341: 1318: 1314: 1306: 1289: 1285: 1262: 1258: 1249: 1245: 1227: 1223: 1200: 1196: 1192: 1187: 1183: 1174: 1173: 1170: 1169: 1164: 1163: 1162: 1159: 1157: 1153: 1148: 1143: 1142: 1141: 1135:This means a 1133: 1128: 1122: 1120: 1116: 1107: 1105: 1102: 1099: 1095: 1091: 1087: 1083: 1079: 1075: 1074: 1068: 1060: 1058: 1055: 1053: 1030: 1026: 1003: 999: 990: 972: 968: 960: 943: 939: 916: 912: 903: 902:in a conflict 885: 881: 872: 854: 850: 846: 841: 837: 828: 825: 824: 823: 821: 817: 813: 809: 805: 801: 794: 789: 787: 785: 780: 778: 774: 769: 768: 761: 759: 755: 751: 748: 744: 740: 735: 731: 727: 722: 720: 716: 712: 707: 705: 704: 699: 695: 691: 687: 683: 679: 675: 671: 667: 659: 657: 654: 650: 646: 645:Vote ordering 642: 638: 634: 630: 625: 623: 619: 615: 614: 609: 605: 602:Furthermore, 600: 598: 593: 590: 586: 585: 580: 579: 574: 570: 566: 562: 558: 554: 550: 546: 542: 536: 534: 531:) to achieve 530: 526: 522: 521: 516: 512: 508: 504: 500: 496: 492: 488: 484: 480: 476: 472: 468: 467: 462: 458: 448: 445: 430: 420: 416: 411: 407: 404:This article 402: 398: 393: 392: 383: 380: 372: 369:November 2011 362: 358: 352: 351: 346:This article 344: 335: 334: 325: 322: 314: 311:November 2011 304: 300: 294: 291:This article 289: 280: 279: 270: 267: 259: 256:November 2011 249: 245: 239: 238: 232: 227: 218: 217: 208: 205: 197: 194:December 2011 186: 183: 179: 176: 172: 169: 165: 162: 158: 155: – 154: 150: 149:Find sources: 143: 139: 135: 131: 127: 120: 113: 104: 103: 94: 84: 80: 76: 73:This article 71: 62: 61: 56: 54: 47: 46: 41: 40: 35: 30: 21: 20: 6298: 6289: 6270: 6264: 6256: 6239: 6223: 6210: 6195: 6182: 6141: 6132: 6122: 6092: 6080: 6039: 6029:November 11, 6027:, retrieved 6022: 6005: 6001: 5987: 5965: 5961: 5954: 5950: 5946: 5939: 5930: 5925: 5920: 5912: 5911: 5907:local cycles 5906: 5902:global cycle 5901: 5898: 5886:standardized 5863: 5859: 5855: 5853: 5843: 5828: 5824: 5823: 5815: 5809: 5798: 5791: 5787: 5779: 5763: 5758: 5746: 5745: 5737: 5730: 5726: 5723:global cycle 5722: 5718: 5714: 5710: 5702: 5695: 5693: 5688: 5684: 5680: 5677: 5559: 5555: 5551: 5503: 5496: 5494: 5488: 5478: 5475: 5467: 5463: 5441: 5435: 5375: 5372:transitively 5255: 5251: 5247: 5199: 5188: 5187: 5172: 5170: 5162: 5155: 5152: 5141: 5127: 5120: 5117: 5104: 5103: 5093: 5076: 5071: 5061: 5047: 5044:Rigorousness 5043: 5039: 5038: 5021: 5019: 5015:non-blocking 5014: 5009: 5006: 4985: 4973: 4966: 4960: 4956: 4946: 4941: 4936: 4928: 4926: 4920: 4916: 4914: 4909: 4904: 4903: 4886: 4880: 4875: 4874: 4849: 4846:materialized 4845: 4841: 4838:global cycle 4837: 4833: 4825: 4813:Vote blocked 4808:Vote blocked 4682:Vote blocked 4565:Vote blocked 4168:materialized 4159:Materialized 4131: 4126: 3926: 3923:materialized 3922: 3914: 3911:materialized 3910: 3902: 3898: 3894: 3892: 3733: 3673: 3667: 3635: 3631: 3598: 3565: 3561: 3399: 3396:is possible) 3244: 2970:Transaction 2898: 2896: 2612: 2607: 2603: 2597: 2564: 2558: 2549: 2543: 2539: 2530: 2523: 2509: 2503: 2497: 2489: 2481: 2477: 2473: 2465: 2457: 2448: 2444: 2440: 2436: 2432: 2424: 2422: 2420:resolution. 2413: 2399: 2391: 2370: 2364: 2360: 2356: 2355: 2350: 2342: 2336: 2326: 2322: 2307: 2303: 2293: 2289: 2285: 2283: 2278: 2276: 2267: 2261: 2253: 2246: 2240: 2235: 2232: 2226: 2219: 2215: 2207: 2202: 2187: 2179: 2175: 2169:independence 2168: 2164: 2158: 2151: 2147: 2127: 2124: 2116: 2094: 2088: 2076: 2069: 2058:algorithms). 2054: 2050: 2046: 2039: 2026: 2021: 2016: 2008: 2004: 2000: 1992: 1979: 1977: 1956: 1951: 1950: 1937: 1932: 1928: 1926: 1923: 1917: 1909: 1901: 1891: 1887: 1883: 1874: 1869: 1858: 1849: 1845: 1842:global cycle 1841: 1837: 1833: 1830:local cycles 1829: 1821: 1814: 1812: 1804: 1800: 1799: 1794: 1790: 1786: 1784: 1777: 1770: 1766: 1762: 1758: 1747: 1740: 1736: 1523: 1515: 1508: 1505: 1501: 1491: 1489: 1484: 1482: 1472: 1464: 1462: 1459: 1408: 1400: 1388: 1304: 1247: 1243: 1165: 1160: 1155: 1151: 1137: 1136: 1131: 1123: 1118: 1114: 1111: 1103: 1097: 1093: 1089: 1085: 1081: 1071: 1066: 1064: 1056: 1048: 988: 958: 901: 870: 804:non-blocking 803: 799: 798: 781: 772: 765: 762: 732:. Enforcing 723: 718: 714: 710: 708: 701: 697: 693: 689: 685: 665: 663: 652: 644: 636: 628: 626: 624:mechanisms. 621: 611: 603: 601: 596: 594: 582: 576: 572: 537: 518: 510: 464: 460: 456: 455: 440: 424: 415:You can help 405: 375: 366: 347: 317: 308: 292: 262: 253: 234: 200: 191: 181: 174: 167: 160: 148: 91:October 2012 88: 78: 74: 50: 43: 37: 36:Please help 33: 6118:Nancy Lynch 5370:, possibly 5149:conflicts). 2176:Definition: 2153:transaction 1452:guaranteed 1248:in conflict 756:; see also 629:extended CO 561:smartphones 248:introducing 130:independent 6332:Categories 5973:References 5788:autonomous 5711:Global ECO 5497:Global ECO 5135:throughput 5113:strictness 5022:CO variant 4967:Strictness 4929:Strictness 4027:ends, and 3889:Variations 2544:autonomous 2498:replicated 2395:timestamps 2365:autonomous 2216:autonomous 2188:Autonomous 2163:) defines 1154:is also a 618:throughput 613:Strictness 573:autonomous 515:precedence 483:optimistic 427:April 2020 231:references 164:newspapers 138:redirected 39:improve it 6343:Databases 6275:CiteSeerX 6101:Footnotes 5964:(i.e., a 5894:X/Open XA 5751:Raz 1993b 5485:Raz 1993a 5483:problem ( 5458:Raz 1993a 5343:precedes 5193:Raz 1993a 5130:thrashing 5109:Raz 1991c 5098:Raz 1991c 5020:The term 4972:(voting) 4826:Comments: 4677:(Blocked) 4570:(Blocked) 4458:(Blocked) 4453:(Blocked) 4170:conflicts 4161:conflicts 3734:restarted 3678:, either 2468:(e.g., a 2373:scales up 2304:Global CO 2241:Only in ( 2140:Raz 1993a 2111:interface 2103:Raz 1991b 2068:See also 2055:real-time 2053:, and no 1988:real-time 1902:Comments: 1834:Global CO 1748:Comments: 1401:Comments: 871:committed 754:Raz 1991a 641:Raz 1993b 633:Raz 1993a 608:Raz 1991c 475:databases 419:talk page 128:that are 45:talk page 6147:Archived 5951:autonomy 5917:Raz 2009 5882:services 5749:(MVCO; ( 5734:needed). 5432:commits. 4986:Comment: 4933:Raz 1992 4905:Comment: 4876:Comment: 4163:on cycle 3740:Comments 3247:schedule 2589:Examples 2404:is by a 2357:Local CO 2345:deadlock 2331:Raz 1992 2286:database 2284:If each 2243:Raz 2009 2197:Raz 1992 2161:Raz 1992 2136:Raz 1992 2099:mediator 1984:Raz 1992 1859:Comment: 1853:blocked. 1801:Comment: 1778:wait-for 1446:Raz 1992 1305:precedes 1140:deadlock 1094:YES vote 1045:commits. 959:precedes 816:directed 750:Yoav Raz 747:inventor 670:Raz 1990 660:Overview 649:Raz 2009 529:scalable 525:reliable 5810:Comment 5262:) from 5191:(ECO; ( 5107:(SCO; ( 4891:H-Store 4883:threads 4675:Running 4568:Running 4456:Running 4451:Running 3676:timeout 3668:running 3599:running 2410:latency 2343:voting- 2273:Summary 2107:locking 2051:timeout 2001:timeout 1168:Theorem 1147:timeout 1138:voting- 869:be two 812:partial 739:latency 711:Locking 696:, and 639:(MVCO; 355:Please 297:Please 244:improve 178:scholar 142:deleted 6305: 6277: 6230: 6202: 6157: 5489:global 5248:global 4937:serial 4917:serial 4895:VoltDB 4887:serial 4818:Voted 4687:Voted 4575:Voted 4463:Voted 3905:; see 3325:(also 2464:Let a 2150:and a 1761:. The 1244:global 1086:commit 1052:cycles 717:, and 635:) and 631:(ECO; 606:(SCO; 563:). An 497:, and 417:. The 233:, but 180: 173: 166: 159: 151: 134:merged 6125:(PDF) 6044:(PDF) 5984:(PDF) 5872:embed 5128:lock 4816:Ready 4811:Ready 4806:Ready 4803:Voted 4801:Ready 4685:Ready 4680:Ready 4672:Voted 4670:Ready 4586:SS2PL 4573:Ready 4563:Ready 4560:Voted 4558:Ready 4471:SS2PL 4461:Ready 4448:Voted 4446:Ready 4381:SS2PL 4378:SS2PL 3927:ready 3705:, or 3636:voted 3632:ready 3566:voted 3562:ready 2600:SS2PL 2526:, and 2339:embed 1997:SS2PL 1733:union 1669:with 1526:is a 1250:with 1127:embed 1090:abort 904:with 724:In a 668:(CO; 543:(and 185:JSTOR 171:books 140:, or 6303:ISBN 6228:ISBN 6200:ISBN 6155:ISBN 6031:2011 5870:can 5510:Let 5206:Let 4893:and 4166:Non- 4151:Node 4146:Node 4143:Case 3799:and 3634:and 3489:and 2967:Node 2928:and 2640:and 2517:Then 2423:All 2306:and 2277:The 2167:and 2045:The 2038:The 2003:and 1813:The 1463:The 1444:in ( 1407:The 1246:and 1175:Let 829:Let 743:open 682:2009 678:1994 674:1992 664:The 157:news 6222:), 6220:PDF 6192:PDF 6010:doi 5681:any 5589:to 5289:to 5079:2PL 5046:or 4957:OCO 4848:or 4698:SCO 4695:SCO 4583:SCO 4474:SCO 3919:SCO 3913:or 3666:is 3630:is 3597:is 3560:is 1968:2PL 1522:An 1242:is 1098:all 1088:or 900:is 760:). 473:of 301:to 6334:: 6297:, 6255:, 6194:) 6166:^ 6109:^ 6006:51 6004:, 5986:, 5460:). 5160:. 4770:2A 4751:1B 4732:2B 4713:1A 4692:4 4639:2A 4620:2B 4601:1A 4580:3 4527:1B 4508:2B 4489:1A 4468:2 4415:2B 4396:1A 4375:1 4348:2B 4335:2B 4298:2A 4285:2A 4248:1B 4235:1B 4198:1A 4185:1A 4102:2B 4089:2B 4053:1B 4040:1B 4004:1A 3991:1A 3955:2A 3942:2A 3652:2A 3616:2B 3583:1B 3546:1A 3502:2A 3466:1B 3373:1A 3338:2B 3300:2B 3265:1A 3215:2B 3202:2B 3165:2A 3152:2A 3085:1B 3072:1B 3035:1A 3022:1A 2977:B 2871:2A 2836:2B 2758:1B 2723:1A 2500:). 2379:. 2199:). 1978:A 1896:). 1511:. 1448:). 713:, 692:, 680:, 676:, 672:, 555:, 493:, 477:, 461:CO 136:, 48:. 6283:. 6218:( 6190:( 6012:: 5938:( 5656:2 5652:T 5629:1 5625:T 5602:2 5598:T 5575:1 5571:T 5536:2 5532:T 5528:, 5523:1 5519:T 5418:2 5414:T 5391:1 5387:T 5356:2 5352:T 5329:1 5325:T 5316:( 5302:2 5298:T 5275:1 5271:T 5258:( 5232:2 5228:T 5224:, 5219:1 5215:T 5124:, 5100:) 4852:. 4798:0 4795:2 4781:) 4778:x 4775:( 4766:W 4762:) 4759:y 4756:( 4747:W 4743:) 4740:y 4737:( 4728:R 4724:) 4721:x 4718:( 4709:R 4667:1 4664:1 4650:) 4647:x 4644:( 4635:W 4631:) 4628:y 4625:( 4616:R 4612:) 4609:x 4606:( 4597:R 4555:1 4552:1 4538:) 4535:y 4532:( 4523:W 4519:) 4516:y 4513:( 4504:R 4500:) 4497:x 4494:( 4485:R 4443:2 4440:0 4426:) 4423:y 4420:( 4411:R 4407:) 4404:x 4401:( 4392:R 4359:) 4356:y 4353:( 4344:R 4340:= 4331:T 4309:) 4306:x 4303:( 4294:W 4290:= 4281:T 4259:) 4256:y 4253:( 4244:W 4240:= 4231:T 4209:) 4206:x 4203:( 4194:R 4190:= 4181:T 4153:B 4148:A 4113:) 4110:y 4107:( 4098:R 4094:= 4085:T 4064:) 4061:y 4058:( 4049:W 4045:= 4036:T 4015:) 4012:x 4009:( 4000:R 3996:= 3987:T 3966:) 3963:x 3960:( 3951:W 3947:= 3938:T 3866:3 3862:T 3839:1 3835:T 3812:2 3808:T 3785:1 3781:T 3758:3 3754:T 3718:2 3714:T 3691:1 3687:T 3648:T 3612:T 3579:T 3542:T 3513:) 3510:x 3507:( 3498:W 3477:) 3474:y 3471:( 3462:W 3439:2 3435:T 3412:1 3408:T 3384:) 3381:x 3378:( 3369:R 3349:) 3346:y 3343:( 3334:R 3311:) 3308:y 3305:( 3296:R 3276:) 3273:x 3270:( 3261:R 3226:) 3223:y 3220:( 3211:R 3207:= 3198:T 3176:) 3173:x 3170:( 3161:W 3157:= 3148:T 3124:2 3120:T 3096:) 3093:y 3090:( 3081:W 3077:= 3068:T 3046:) 3043:x 3040:( 3031:R 3027:= 3018:T 2994:1 2990:T 2974:A 2941:2 2937:T 2914:1 2910:T 2882:) 2879:x 2876:( 2867:W 2847:) 2844:y 2841:( 2832:R 2828:= 2823:2 2819:T 2796:2 2792:T 2769:) 2766:y 2763:( 2754:W 2734:) 2731:x 2728:( 2719:R 2715:= 2710:1 2706:T 2683:1 2679:T 2653:2 2649:T 2626:1 2622:T 2606:( 2333:) 2159:( 1982:( 1773:. 1712:1 1708:T 1682:1 1678:T 1655:2 1651:T 1628:1 1624:T 1601:2 1597:T 1570:2 1566:T 1543:1 1539:T 1432:C 1427:3 1423:D 1419:C 1373:2 1369:T 1346:1 1342:T 1319:2 1315:T 1290:1 1286:T 1277:( 1263:1 1259:T 1228:2 1224:T 1201:2 1197:T 1193:, 1188:1 1184:T 1031:2 1027:T 1004:1 1000:T 973:2 969:T 944:1 940:T 931:( 917:1 913:T 886:2 882:T 855:2 851:T 847:, 842:1 838:T 752:( 459:( 447:) 441:( 429:) 425:( 412:. 382:) 376:( 371:) 367:( 363:. 324:) 318:( 313:) 309:( 295:. 269:) 263:( 258:) 254:( 240:. 207:) 201:( 196:) 192:( 182:· 175:· 168:· 161:· 144:. 122:. 93:) 89:( 55:) 51:(

Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.

Index