Editing Two-phase commit protocol (section)

==Implementing the two-phase commit protocol==

===Common architecture===
In many cases the 2PC protocol is distributed in a computer network. It is easily distributed by implementing multiple dedicated 2PC components similar to each other, typically named [[transaction manager]]s (TMs; also referred to as 2PC agents or Transaction Processing Monitors), that carry out the protocol's execution for each transaction (e.g., [[The Open Group]]'s [[X/Open XA]]). The databases involved with a distributed transaction, the participants, both the coordinator and participants, register to close TMs (typically residing on respective same network nodes as the participants) for terminating that transaction using 2PC. Each distributed transaction has an ad hoc set of TMs, the TMs to which the transaction participants register. A leader, the coordinator TM, exists for each transaction to coordinate 2PC for it, typically the TM of the coordinator database. However, the coordinator role can be transferred to another TM for performance or reliability reasons. Rather than exchanging 2PC messages among themselves, the participants exchange the messages with their respective TMs. The relevant TMs communicate among themselves to execute the 2PC protocol schema above, "representing" the respective participants, for terminating that transaction. With this architecture the protocol is fully distributed (does not need any central processing component or data structure), and scales up with number of network nodes (network size) effectively.

This common architecture is also effective for the distribution of other [[Atomic commit|atomic commitment protocol]]s besides 2PC, since all such protocols use the same voting mechanism and outcome propagation to protocol participants.<ref name="bernstein1987" /><ref name="weikum2001" />

===Protocol optimizations===
[[Database]] research has been done on ways to get most of the benefits of the two-phase commit protocol while reducing costs by protocol optimizations<ref name="bernstein1987" /><ref name="weikum2001" /><ref name="Bern2009" /> and protocol operations saving under certain system's behavior assumptions.

====Presumed abort and presumed commit====
Presumed abort or Presumed commit are common such optimizations.<ref name="weikum2001" /><ref name=Bern2009/><ref name="mohan1983">[[C. Mohan]], Bruce Lindsay (1985): [http://portal.acm.org/citation.cfm?id=850772  "Efficient commit protocols for the tree of processes model of distributed transactions"],''ACM SIGOPS Operating Systems Review'',
19(2),pp. 40-52 (April 1985)</ref> An assumption about the outcome of transactions, either commit, or abort, can save both messages and logging operations by the participants during the 2PC protocol's execution. For example, when presumed abort, if during system recovery from failure no logged evidence for commit of some transaction is found by the recovery procedure, then it assumes that the transaction has been aborted, and acts accordingly. This means that it does not matter if aborts are logged at all, and such logging can be saved under this assumption. Typically a penalty of additional operations is paid during recovery from failure, depending on optimization type. Thus the best variant of optimization, if any, is chosen according to failure and transaction outcome statistics.

====Tree two-phase commit protocol====
The [[Tree (data structure)|Tree]] 2PC protocol<ref name="weikum2001" /> (also called Nested 2PC, or Recursive 2PC) is a common variant of 2PC in a [[computer network]], which better utilizes the underlying communication infrastructure. The participants in a distributed transaction are typically invoked in an order which defines a tree structure, the invocation tree, where the participants are the nodes and the edges are the invocations (communication links). The same tree is commonly utilized to complete the transaction by a 2PC protocol, but also another communication tree can be utilized for this, in principle. In a tree 2PC the coordinator is considered the root ("top") of a communication tree (inverted tree), while the participants are the other nodes. The coordinator can be the node that originated the transaction (invoked recursively (transitively) the other participants), but also another node in the same tree can take the coordinator role instead. 2PC messages from the coordinator are propagated "down" the tree, while messages to the coordinator are "collected" by a participant from all the participants below it, before it sends the appropriate message "up" the tree (except an abort message, which is propagated "up" immediately upon receiving it or if the current participant initiates the abort).

The Dynamic two-phase commit (Dynamic two-phase commitment, D2PC) protocol<ref name="weikum2001" /><ref name="raz1995">[[Yoav Raz]] (1995): [[doi:10.1007/3-540-58907-4_14|"The Dynamic Two Phase Commitment (D2PC) protocol "]],''Database Theory — ICDT '95'', ''Lecture Notes in Computer Science'', Volume 893/1995, pp. 162-176, Springer, {{ISBN|978-3-540-58907-5}}</ref> is a variant of Tree 2PC with no predetermined coordinator. It subsumes several optimizations that have been proposed earlier. Agreement messages (Yes votes) start to propagate from all the leaves, each leaf when completing its tasks on behalf of the transaction (becoming ready). An intermediate (non leaf) node sends ready when an agreement message to the last (single) neighboring node from which agreement message has not yet been received. The coordinator is determined dynamically by racing agreement messages over the transaction tree, at the place where they collide. They collide either at a transaction tree node, to be the coordinator, or on a tree edge. In the latter case one of the two edge's nodes is elected as a coordinator (any node). D2PC is time optimal (among all the instances of a specific transaction tree, and any specific Tree 2PC protocol implementation; all instances have the same tree; each instance has a different node as coordinator): By choosing an optimal coordinator D2PC commits both the coordinator and each participant in minimum possible time, allowing the earliest possible release of locked resources in each transaction participant (tree node).