Non-blocking commit protocol systems and methods

Systems and methods are provided for atomic single-failure non-blocking and double-failure non-blocking commitment protocols. The protocols may be used for a variety of transactions that involve two or more parties including an initiator of the transaction, a coordinator of the transaction, and one or more participants in the transaction. The participants notify the coordinator when they are prepared to commit the transaction. The coordinator then determines when to commit or abort the transaction. If the coordinator disconnects from one or more of the participants, the participants can resolve the transaction independently. Some embodiments also include a distributor that interacts with the coordinator and the participants to resolve the transaction. If one or more parties become disconnected from the coordinator or the distributor, the participants vote to determine whether to receive instructions from the coordinator or the distributor.

BACKGROUND

1. Field of the Invention

This invention relates to systems and methods for maintaining atomicity and reducing blocking in distributed systems.

2. Description of the Related Art

For a transaction to be atomic, a system either executes all of the operations in the transaction to completion or none of the operations. Atomicity allows multiple operations to be linked so that the final outcome of the overall transaction is known. System failures can prevent atomicity. For example, a device or communication failure in a distributed system executing a transaction can cause some of the parties participating in the transaction to execute the transaction to completion while other parties abort the transaction. This puts the parties in different states and can corrupt system information if the parties cannot roll-back to a stable condition consistent with a known state before the transaction was initiated.

In a distributed system, an atomic commit protocol (ACP) resolves transactions between a number of different parties involved in the transaction. The ACP ensures that all parties to the transaction agree on a final outcome by either committing to the transaction or aborting the transaction. Several such protocols are described below.

I. Deterministic Atomic Commit Protocol

A plurality of nodes may participate in a transaction and then send messages to each other to indicate that they are each prepared to commit the transaction. Once a particular participant receives “prepared” messages from all other participating nodes, the participant commits to the transaction and sends a “committed” message to the other participating nodes. If the participant receives an “abort” message from another participating node, the participant also aborts. Thus, the protocol in this example is deterministic in that the outcome of the transaction is causally determined when the participating nodes are prepared to commit. The transaction eventually commits when all participants successfully send “prepared” messages to the other participants. Each participating node uses this rule to decide for itself how to resolve the transaction.

However, failure of a participant can block the transaction until the participant recovers. If, for example, the participant prepares for the transaction but crashes before sending any “prepared” message, and all other participants send “prepared” messages, the transaction is blocked while the functioning participants wait to determine whether or not the failed participant prepared or aborted the transaction. Further, the functioning participants do not know whether or not the failed participant committed to the transaction after receiving their “prepared” messages. Thus, the functioning participants block the transaction until the failed participant recovers. The transaction may block for an indeterminate amount of time, which may be forever in the case of a permanent failure.

Some ACPs are non-deterministic and use a coordinator to manage the ACP and reduce blocking when a participating node fails. For example, in a conventional two-phase commit protocol the participants send “prepared” messages or “abort” messages to the coordinator rather than to each other. In a first phase, the coordinator decides whether to commit or abort the transaction. If the coordinator receives “prepared” messages from all participants, the coordinator decides to commit the transaction. If the coordinator receives an “abort” message from at least one participant, the coordinator decides to abort the transaction. In a second phase, the coordinator logs its decision and sends messages to the participating nodes to notify them of the decision. The participants can then take appropriate action.

Since the coordinator makes a unilateral decision, failure of a single participant will not block the transaction. If a participant fails or loses communication with the coordinator before sending a prepared or “abort” message, the coordinator unilaterally decides to abort after a predetermined amount of time. However, the two-phase commit protocol can still block the transaction under certain circumstances. For example, if the coordinator fails and all participants send “prepared” messages, the participants will block until the coordinator recovers and resolves the protocol.

Conventional three-phase commit protocols attempt to solve the blocking problem of the two-phase commit protocol by adding an extra phase in which a preliminary decision of whether to commit or abort the transaction is communicated to the participating nodes. If the coordinator fails, the participating nodes select one of the participants to be a new coordinator that resumes the protocol. When the failed coordinator recovers, it does so as a participant and no longer acts in the role of the coordinator. However, in many applications it is not practical to implement the conventional three-phase commit protocol. Further, the three-phase commit protocol may block if multiple participants fail or if there is a communication failure.

SUMMARY

The systems and methods described herein provide single-failure non-blocking commitment and double-failure non-blocking commitment protocols.

In one embodiment, a distributed system is provided, where the distributed system is configured to resolve a transaction among a set of parties within the distributed system. The distributed system may include a plurality of participants configured to permit communication among the plurality of participants and to resolve a transaction; a coordinator configured to communicate with the plurality of participants to resolve the transaction; wherein the plurality of participants are configured to determine whether to commit the transaction based on messages from the coordinator, and if not, to determine among the plurality of participants whether to commit the transaction.

In an additional embodiment, a method is provided for resolving a transaction among a set of nodes. The method may include determining whether communication with a coordinator node is available; if communication with the coordinator node is available, receiving messages from the coordinator node indicating whether to commit or abort a transaction; and if communication with the coordinator node is not available, receiving messages from other nodes involved in the transaction indicating whether to commit or abort the transaction.

In an additional embodiment, a distributed system is provided to resolve a transaction among a set of parties within a distributed system. The distributed system may include a set of participant nodes configured to permit communication among the plurality of nodes and to resolve a transaction among a set of parties from the plurality of nodes; an initiator located on a first node configured to communicate with the plurality of participant nodes; a coordinator located on the first node; and wherein the initiator is further configured to receive a start command to start the transaction, add participant nodes to the set of participant nodes after the start of the transaction to form an updated set of participant nodes, and send a message to the coordinator, the message configured to indicate that the initiator is prepared to commit the transaction and to indicate that the participant nodes in the updated set of participant nodes are to be included in the transaction.

In a further embodiment, a method is provided for resolving a transaction among a set of parties within a distributed system. The method may include receiving a command to start an transaction; receiving a first set of participant nodes to be included in the transaction; receiving additional participant nodes to be included in the transaction; adding the additional participant nodes to the first set of participant nodes; receiving a command to commit the transaction; and sending a message to a coordinator node to prepare for the transaction, the message including the updated first set of participant nodes.

DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS

Systems and methods for providing atomic non-blocking commit protocols will now be described. These protocols may be used for a variety of transactions that involve two or more parties, where the parties include at least one initiator and one or more participants. For example, these protocols may be used in distributed file systems as described in U.S. patent application Ser. No. 10/007,003 entitled “Systems and Methods for Providing a Distributed File System Utilizing Metadata to Track Information About Data Stored Throughout the System,” filed Nov. 9, 2001 which claims priority to Application No. 60/309,803 filed Aug. 3, 2001, U.S. patent application Ser. No. 10/281,467 entitled “Systems and Methods for Providing A Distributed File System Incorporating a Virtual Hot Spare,” filed Oct. 25, 2002, and U.S. patent application Ser. No. 10/714,326 entitled “Systems And Methods For Restriping Files In A Distributed File System,” filed Nov. 14, 2003, which claims priority to Application No. 60/426,464, filed Nov. 14, 2002, all of which are hereby incorporated by reference herein in their entirety.

A. The Initiator

The initiator has several responsibilities. In one embodiment, the initiator is responsible for starting transactions, assigning work items to participants for execution on the transactions, and deciding when to request a commit or abort for a transaction. In the examples discussed herein, the initiator sends “prepare” messages to all of the participants when the initiator wants to commit a transaction and “abort” messages when the initiator wants to abort a transaction. In addition, the initiator receives “aborted” messages and “committed” messages from the participants indicating whether the participants have completed the transaction. Typically, the initiator is allowed to abort a transaction, by sending an “abort” message to the participants, at any point up until the initiator has sent “prepare” messages to the participants. Once the initiator has sent all of the “prepare” messages, the transaction is out of the initiator's hands.

In some embodiments, the initiator controls message synchronization. For example, the initiator may mediate the distribution of the “abort” messages to guarantee that the “start” messages have been processed on all participants before they receive an “abort” or “aborted” message. As another example, the initiator may wait to collect responses to the “start” messages from one or more participants before sending the “prepare” messages.

In a distributed file system, for example, the initiator may start a transaction to write or restripe data blocks across a plurality of nodes corresponding to the participants. The initiator then sends requests to the participants to read data blocks, allocate space for data blocks, write data blocks, calculate parity data, store parity data, send messages to another participant, combinations of the forgoing, or the like.

B. The Participants

The participants' responsibilities include executing transactions, receiving messages from the initiator, and sending messages to the initiator indicating whether the transaction was completed by sending “aborted” or “committed” messages. For example, if a particular participant has an error while performing the transaction, becomes disconnected from the initiator, or receives an “abort” message from the initiator, the participant aborts the transaction and sends an “aborted” message to the initiator. If the participant commits the transaction, it sends a “committed” message to the initiator.

In one embodiment, the participants are located on separate nodes from one another. However, in some embodiments, a participant can share a node with another party. Moreover, in some embodiments, the participants have durable logs that they use to store requested transaction procedures and protocol states. As discussed in detail below, if a failure causes a particular participant to restart, the log is consulted to determine the last state of the participant. The information in the log can also be provided to other participants.

In one embodiment, the parties involved in the transaction are interconnected through a bidirectional communication link. The link between two or more parties may be up or down. If the link is down, the messages are dropped. If the link is up, the messages are received in the order they are sent. In one embodiment, the link comprises a “keep-alive” mechanism that quickly detects when nodes or other network components fail. The parties are notified when a link goes up or down. When a link goes down between two parties, for example, both parties are notified before it comes back up. In one embodiment, the link comprises a TCP connection. In one embodiment, the link could also include an SDP connection over Infiniband, a wireless network, a wired network, a serial connection, IP over FibreChannel, proprietary communication links, connection based datagrams or streams, and/or connection based protocols.

Any party, including participants and initiators, is said to fail when it stops executing. The failed party may, however, be able to reboot or otherwise restart. Once the failure is resolved by restarting, the party may resume participation in the transaction. A party can also fail wherein one or more communication links with other parties go down. This failure is over once the communication links are back up.

In the following description, reference is made to the accompanying drawings, which form a part hereof, and which show, by way of illustration, specific embodiments or processes in which the invention may be practiced. Where possible, the same reference numbers are used throughout the drawings to refer to the same or like components. In some instances, numerous specific details are set forth in order to provide a thorough understanding of the present disclosure. The present disclosure, however, may be practiced without the specific details or with certain alternative equivalent components and methods to those described herein. In other instances, well-known components and methods have not been described in detail so as not to unnecessarily obscure aspects of the present disclosure.

Improvements to the two-phase commit protocol include converting back to the deterministic approach described above when the coordinator fails or otherwise disconnects from all of the participants. Initially, the participants send “prepared” messages to the coordinator and expect to receive a commit or “abort” message from the coordinator. As participants are disconnected from the coordinator, they send “prepared” messages to the other participants. Once a particular participant is disconnected from the coordinator, it no longer accepts commit or “abort” messages from the coordinator. When the particular participant receives “prepared” messages from all the other participants, it “commits” to the transaction and sends a “committed” message to the other participants. If a participant fails, rather than the coordinator, the coordinator aborts the transaction and notifies all other participants. The participant that failed is notified of the outcome when it recovers from the failure.

When the coordinator is not located on the same node as a participant, this improvement to the two-phase commit protocol is non-blocking (at least for single-failures). However, blocking occurs when the coordinator shares a node with a participant. For example, the shared node may fail before the other participants receive an abort or commit from the coordinator. After losing communication with the coordinator, the other participants block until the shared node recovers from the failure and the participant thereon sends a message to indicate how it resolved the transaction. In many applications, a separate node for the coordinator is not available. Therefore, undesirable blocking may occur.

As discussed above, the modified two-phase commit protocol (“M2PC”) provided a single-failure non-blocking behavior, but required the coordinator to reside on a separate node from all other parties, thereby limiting the ability to implement the modified two-phase commit protocol. Discussed below is a “more-modified” two-phase commit protocol (“MM2PC”) that allows the coordinator to reside on the same node as a participant (for example, a shared participant), such that if that node fails, the non-shared participants can determine the state of the shared participant and deterministically resolve the outcome of the transaction.

The MM2PC protocol is similar to the M2PC protocol in that it utilizes a coordinator c to collect “committed” and “aborted” messages from the participants and to alert the participants as to the transaction's status. The M2PC and MM2PC protocols include, a “first prepared” state in which the participants expect the coordinator to resolve the transaction, for example state Pc as discussed below, and a “second prepared” state for situations in which the coordinator becomes disconnected from one or more of the participants, for example state Pp as discussed below. The participants collect information from the other participants in case the coordinator becomes disconnected from one or more participants. The participants transition to the second prepared state when they have lost their connection to the coordinator. Once in the second prepared state, a participant then determines its status based on status messages from other participants instead of the coordinator. In the MM2PC protocol, however, the coordinator does not send a “commit” message to the shared participant. Instead, the shared participant receives “committed” messages from the other participants. Since the remote participants notify the shared participant of the transaction's outcome, the remote participants can resolve the transaction even if they become disconnected from the coordinator.

The MM2PC protocol may also include “collection” states that allow a participant to verify that the participant has received either “aborted” messages from all of the other participants or “committed” messages from all of the other participants. This verification allows the participant to be sure that the other participants are aware of the status of the transaction before the participant clears its log of status information regarding the transaction.

FIG. 1illustrates an exemplary timing chart according to one embodiment of a commit protocol100for a transaction involving an initiator110(shown as “i”), a first participant112(shown as “p1”), a second participant114(shown as “p2”), a shared participant116(shown as “ps”), and a coordinator118(shown as “c”). The exemplary shared participant116and the coordinator118reside on the same node.

The initiator110is configured to start the transaction by sending “start” messages (not shown) to the coordinator118and the participants p1, p2, ps. In one embodiment, the initiator110collects responses to the “start” messages before requesting the participants p1, p2, and psto commit the transaction. To request commitment to the transaction, the initiator110sends “prepare” messages120(three shown) to the first participant112, the second participant114, and the shared participant116.

The first participant112, the second participant114, and the shared participant116each log their respective “prepare” message120and each determine whether they are prepared to commit the transaction. If the first participant112can commit the transaction, the first participant112sends a “prepared” message122to the coordinator118. If the second participant114can commit the transaction, the second participant114sends a “prepared” message122to the coordinator118. If the shared participant116can commit the transaction, the shared participant116sends a “prepared” message122to the coordinator118. If the coordinator receives a “prepared” message122from the first participant112, the second participant114, and the shared participant116, the coordinator118sends “commit” messages124(two shown) to the first participant112and the second participant114. The coordinator118does not send a “commit” message to the shared participant116.

After receiving the “commit” messages124from the coordinator118, the first participant112and the second participant114each log the “commits” and each send “committed” messages126(six shown) to each other, to the shared participant116, and to the initiator110. For example, the first participant112would send a “committed” message126to the second participant114, the shared participant116, and the initiator110. Upon receiving a “committed” message126from either the first participant112or the second participant114, the shared participant116commits the transaction, logs the received “committed” message126and sends “committed” messages128(three shown) to the initiator110, the first participant112, and the second participant114. The first participant112, the second participant114, and the shared participant116can then clean their respective logs and the commit protocol100ends.

The exemplary timing chart shown inFIG. 1illustrates the commit protocol100when no failures occur. If the coordinator118has not disconnected from the first participant112or the second participant114, the coordinator118determines whether to commit or abort the transaction. The coordinator118commits the transaction when all of the “prepared” messages122are received from each of the participants112,114,116.

As discussed in detail below, if the node with the coordinator118and the shared participant116fails, the first participant112and the second participant114are still able to resolve the transaction. If the coordinator118sent the “commit” messages124before failing, the participants p1, p2112,114commit the transaction since they know that the shared participant116successfully prepared. However, if the coordinator118did not send the “commit” messages124before failing, the participants p1, p2112,114abort the transaction since they do not know whether the shared participant116successfully prepared. When the shared participant116reconnects, the participants p1, P2112,114inform the shared participant116of their decision.

So long as at least one of the first participant112and the second participant114are connected to the coordinator118, the connected participant can still receive a “commit” or “abort” message from the coordinator118. To avoid ending up in different states, the first participant112and the second participant114only decide whether to commit or abort if they have both been disconnected from the coordinator118. Further, once disconnected from the coordinator118, the first participant112or the second participant114no longer accept “commit” or “abort” messages from the coordinator118. Since the participants112,114,116do not look to the coordinator118after a failure, the coordinator118does not log the “prepared” messages122received from the participants112,114,116and does not clean its log at the end of the commit protocol100.

FIGS. 2 and 3illustrate state diagrams according to one embodiment of an MM2PC protocol. Parties in a transaction using the exemplary MM2PC protocol include a coordinator c, a shared participant pson the same node as the coordinator c, one or more remote participants p selected from the set defined by {p1, p2, ps}, and an initiator i.

B. Coordinator States

FIG. 2illustrates a state diagram having an initial state I and a final state F of the coordinator c during execution of the MM2PC protocol. The coordinator c can be in a state “sc” defined by:
scε{(I,S)|S⊂P}∪{F},
wherein P is a set of participants defined by P={p1, p2, . . . , pn, ps}. In addition, the participant pxrepresents any one of the participants in the set P={p1, p2, . . . , pn, ps}. For example, in the MM2PC protocol100shown inFIG. 1, P={p1, p2, ps}. In one embodiment, the variable S is a proper subset of the participants P and represents the participants in P for which the coordinator c has received “prepared” messages. The coordinator c remains in the initial state I until S=P. The coordinator c then transitions to the final state F. As discussed below, the coordinator c can also transition from the initial state I to the final state F if the initiator i or a participant in P aborts the transaction or if any of the participants P disconnect before sending a “prepared” message. In this embodiment, because the shared participant psand the coordinator c are located on the same node, then it may be assumed that the shared participant psand the coordinator c will not become disconnected. Thus, in the exemplary embodiment, the coordinator c would not become disconnected from the shared participant ps, and thus, would only transition from the initial state I to the final state F if the initiator i or a participant in P, not including the shared participant ps, disconnected before sending a “prepared” message.

In the initial state I, the coordinator c receives messages from the initiator i and the participants in P. The coordinator c may receive a “prepared” message from any of the participants px(for example, prepared(px)). If the coordinator c receives a “prepared” message from any of the participants px, the coordinator c adds the participant pxto the set of known prepared participants S (for example, S=S∪{px}).

Upon receiving “prepared” messages from all of the participants in the set P (for example, S=P), the coordinator c sends a “commit” message to the participants in P except for the shared participant ps(for example, commit(P\{ps}) and changes from the initial state I to the final state F. As noted above, in this embodiment, the coordinator c does not send “commit” messages to the shared participant ps. If the coordinator c receives an “aborted” message from any of the participants pxor the initiator i (for example, aborted (px, i)), or if the coordinator c detects that any of the participants pxare disconnected (for example, disconnect (px)), the coordinator c sends an “abort” message to the participants in P except for the shared participant ps(for example, abort(P\{ps})). As noted above, in this embodiment, the coordinator c does not send “abort” messages to the shared participant ps. The coordinator c then changes from the initial state I to the final state F and no longer participates in the transaction.

The following exemplary pseudocode further describes the coordinator's execution of the MM2PC protocol:

function abort(S):send abort to S \ {ps}set state to Ffunction commit(S):send commit to S \ {ps}set state to Fin state (I, S):on disconnect from p ∉ S:abort(P)on aborted from (px, i):abort(P)on prepared from (px):if S ∪ {px} ≠ P:set state to (I, S ∪ {px})else:commit(P)on start:set state to (I, Ø)

C. Participant States

FIG. 3illustrates a state diagram of any of the participants pxduring execution of the MM2PC protocol. In the following description ofFIG. 3, reference to a “participant px” refers to any of the participants px(for example, p1, p2, . . . , pn, ps) including the shared participant ps. The participants p1, p2, . . . , pnor the shared participant psmay also be referred to separately. In the MM2PC protocol, the participants in P resolve the transaction if the coordinator c fails. The participant pxis configured to communicate with the coordinator c, the initiator i and one or more other participants p′ selected from P. The other participant p′ may be, for example, the shared participant pswhen the state diagram shown inFIG. 3corresponds to the participant pn. As another example, if there are three participants, p1, p2, p3and a shared participant ps, ifFIG. 3corresponds to p1then p′ may be p2, p3, or ps; ifFIG. 3corresponds to psthen p′ may be p1, p2, or p3.

The state diagram illustrated inFIG. 3includes an initial state I, a first prepared state Pc, a second prepared state Pp, an aborted state A, a committed state C, and a final state F. In the first prepared state Pc, the participant p expects to receive an “abort” or “commit” message from the coordinator c. In the second prepared state Pp, the participants in P decide amongst themselves how to resolve the transaction. The participant pxcan be in a state “spx” defined by:
spxε{(r,S)|rε{I,Pc,Pp,A,C}; S⊂P}∪{F}
wherein the variable S is a proper subset of the participants P and represents the participants in P for which the participant pxhas received “prepared” messages. The participant pxremains in one of the states of which the variable r is a member until S=P. The participant pxthen transitions to the final state F. As discussed below, the participant pxtransitions to the final state F after performing a garbage collection procedure.

A detailed discussion of each participant state is set forth below.

1. Garbage Collection and Restart

The participant pxrecords messages sent or received during the MM2PC protocol in a log. The participant pxcan provide the information in the log to another participant p′ that may not have received one or more messages sent, for example, when the other participant p′ was disconnected. The participant pxcan also use the information when the participant pxrestarts after a disconnect or failure to determine the outcome of the transaction.

The aborted state A and the committed state C are garbage collection states. In these states, the participant pxhas already committed or aborted the transaction. However, the participant pxwaits until the other participants in P complete the transaction before clearing its log. If the participant pxaborts the transaction, it includes itself in a set of known aborted participants A′ (for example, A′={px}); A′ represents a subset of the participants in P for which the participant pxhas received “aborted” messages. If the participant pxcommits, it includes itself in a set of known committed participants C′ (for example, C′={px}); C′ represents a subset of the participants in P for which the participant pxhas received “committed” messages.

As mentioned above, the participant pxkeeps a log that it can use when another participant p′ reconnects or when the participant pxrestarts after a disconnect or failure. On restart, the participant pxno longer accepts messages from the coordinator c. If the last entry in the log was “start,” the participant pxdid not receive a “prepare” message from the initiator and can abort the transaction. If the last entry in the log was “prepare,” the participant pxchecks to see if it has received “prepared” messages from all of the participants in P except for the shared participants ps(S=P\{ps}). If S=P\{ps}, the participant pxaborts the transaction. If S≠P\{ps}, the participant pxenters or remains in the second prepared state Pp, which is discussed in detail below.

If the last entry in the log was “abort,” the participant pxdetermines whether it has received “aborted” messages from all of the other participants in P (A′=P). If A′≠P, the participant pxenters the abort state A. If A′=P, the participant pxclears its log and enters the final state F. If the last entry in the log is “commit,” the participant pxdetermines whether it has received “committed” messages from all of the other participants in P (C′=P). If C′≠P, the participant pxenters the committed state C. If C′=P, the participant pxclears its log and enters the final state F.

The following exemplary pseudocode illustrates one embodiment of garbage collection and restart for the participant px:

function forget( ):clean logset state to Ffunction abort_count(A′):if A′ ≠ P:set state to (A, A′)else:forget( )function commit_count(C′):if C′ ≠ P:set state to (C, C′)else:forget( )function abort(A′):log(abort)send aborted to (P ∪ {i, c}}) \ {px}abort_count(A′)function commit(C′):log(commit)send committed to (P ∪ {i}) \ {px}function prepare_p_count(S):if S ≠ P \ {ps}:set state to (Pp, S)else:abort({px})on start:set state to (I, Ø)on restart:if last log was start:abort({px})if last log was prepare:prepare_p_count({px})if last log was abort:abort_count({px})if last log was commit:commit_count({px})
The functions abort_count( ) and commit_count( ) respectively check A′ and C′ against the participants in P. The function forget( ) clears the log at the end of the transaction so it can be used for subsequent transactions. The abort( ) function sends an “aborted” message to the other participants in P, the initiator i, and the coordinator c. The commit( ) function sends a “committed” message to the other participants P and the initiator i. The participant pxdoes not send the “committed” message to the coordinator c because the coordinator c either told the participant pxto commit or the participants in P decided to commit when the coordinator c was no longer involved in the transaction. Further details about the aborted state A and the committed state C are discussed below.

2. The States

a. The Initial State I

As illustrated inFIG. 3, in the initial state I, the participant pxreceives a “prepare” message from the initiator i (for example, prepare(i)). If the participant pxhas an error such that it cannot perform the transaction, the participant pxaborts the transaction. The participant pxmay also abort the transaction if it detects a disconnect from the initiator i or the coordinator c (for example, disconnect(i, c)) or if it receives an “aborted” message from another participant p′ (for example, aborted(p′)). If the participant pxreceives the “aborted” message from another participant p′, it adds itself and the other participant p′ to the set of known aborted participants A′ (for example, A′={px, p′}). Further, the participant p aborts if it receives an “abort” message from the coordinator c (for example, abort(c)). It should also be noted that the shared participant pscannot disconnect from the coordinator c since they are on the same node.

If the participant pxaborts, it sends an “aborted” message to the participants in P, the coordinator c and the initiator i (for example, aborted(P, c, i)), and enters the aborted state A. If, on the other hand, the participant pxcan commit the transaction after receiving the “prepare” message from the initiator i, it sends a “prepared” message to the coordinator c (for example, prepared(c)) and enters the first prepared state Pc.

While in the initial state I, the participant pxmay also receive a “prepared” message from another participant (for example, prepared(p′)). As discussed below, if the participant pxlater enters the second prepared state Pp, it will need to know that the other participant p′ is also in the second prepared state Pp. Thus, upon receiving a “prepared” message from the other participant p′, the participant pxadds the other participant p′ to the subset S (for example, S=S∪{p′}).

The following exemplary pseudocode illustrates one embodiment of the participant pxin the initial state I:

in state (I, S):on disconnect from i or c:abort({px})on abort from c:abort({px})on aborted from p′:abort({px, p′})on prepared from p′:set state to (I, S ∪ {p′})on prepare from i:if error:abort({px})else:log(prepare)send prepared to cset state to (Pc, S)

b. The First Prepared State Pc

In the first prepared state Pc, the participant pxexpects to receive a “commit” or “abort” message from the coordinator c. As discussed above, in some embodiments, the shared participant psmay ignore commands from the coordinator c. If the participant pxreceives a “commit” message from the coordinator c (for example, commit(c)), the participant pxcommits the transaction and sends a “committed” message to the other participants in P, the coordinator c, and the initiator i (for example, committed(P, c, i)). The participant pxthen enters the committed state C. If the participant pxreceives an “abort” message from the coordinator c (for example, abort(c)), the participant pxaborts the transaction and sends an “aborted” message to the other participants in P, the coordinator c, and the initiator i (for example, aborted(P, c, i)). The participant pxthen enters the aborted state A.

While in the first prepared state Pc, the participant pxmay receive a “committed” or “aborted” message from another participant p′ (for example, committed(p′) or aborted(p′)). In response to receiving a “committed” message from another participant p′, the participant pxadds itself and the other participant p′ to the set of known committed participants C′ (for example, C′={px, p′}), sends a “committed” message to the other participants in P, the coordinator c, and the initiator (for example, committed(P, c, i)), and transitions to the committed state C. In response to receiving an “aborted” message from another participant p′, the participant pxaborts the transaction, adds itself and the other participant p′ to the set of known aborted participants A′ (for example, A′={px, p′}), sends an “aborted” message to the other participants in P, the coordinator c, and the initiator i (for example, aborted(P, c, i)), and enters the aborted state A.

The participant pxmay also receive a “prepared” message from another participant p′ while in the first prepared state Pc. Upon receiving the “prepared” message from another participant p′, the participant pxadds the other participant p′ to the set of known prepared participants S (for example, S=S∪{p′}). The participant pxmay also detect a disconnect from the coordinator c (for example, disconnect(c)). As discussed above, the shared participant psdoes not disconnect from the coordinator c since it resides on the same node. In determining that the coordinator c is disconnected, the participant pxsends a “prepared” message to the other participants in P (for example, prepared(P)) and enters the second prepared state Pp.

The following exemplary pseudocode illustrates one embodiment of the participant pxin the first prepared state Pc:

in state (Pc, S):on disconnect from c:send prepared to P \ {p}prepare_p_count(S ∪ {p})on abort from c:abort({p})on aborted from p′:abort({p, p′})on commit from c:commit({p})on committed from p′:commit({p, p′})on prepared from p′:set state to (Pc, S ∪ {p′})
The definitions for the functions abort, commit, and prepare_p_count are discussed above in section I with respect to “The Initial State I.”

c. The Second Prepared State Pp

In the second prepared state Pp, the participants in P decide amongst themselves how to resolve the transaction. As discussed above, the shared participant psdoes not enter the second prepared state Pp because it cannot disconnect from the coordinator c.

The participant pxcannot decide to commit once all of the participants in P (except for the shared participant ps) enter the second shared state Pp because the participant pxdoes not know whether the shared participant pssuccessfully prepared. However, if the participant pxreceives a “committed” message from another participant p′ (for example, committed(p′)), the participant pxcommits since receiving the “committed” message from the other participant p′ indicates that the other participant p′ received a “commit” message from the coordinator c and also committed. The participant pxthen adds itself and the other participant p′ to the set of known committed participants C′, sends a “committed” message to the other participants in P, the coordinator c, and the initiator i (for example, committed(P, c, i)), and transitions to the committed state C.

While in the second prepared state Pp, the participant pxmay receive an “aborted” message from another participant p′ (for example, aborted(p′)). In response, the participant pxadds itself and the other participant p′ to the set of known aborted participants A′, sends an “aborted” message to the other participants in P, the coordinator c, and the initiator i (for example, aborted(P, c, i)), and transitions to the aborted state A.

The participant pxmay also receive a “prepared” message from another participant p′ message while in the second prepared state Pp. Upon receiving the “prepared” message from another participant p′, the participant pxadds the other participant p′ to the set of known prepared participants S (for example, S=S∪{p′}). If S=P\{ps}, the participant pxaborts the transaction since all of the participants in P except for the shared participant pshave disconnected from the coordinator c but do not know whether the shared participant psis prepared to commit the transaction.

If another participant p′ connects to the participant px(for example, connect(p′)) while the participant pxis in the second prepared state Pp, the participant pxsends a “prepared” message to the other participant p′ (for example, prepared(p′)). This informs the other participant p′ of the state of the participant pxif, for example, the other participant p′ did not receive one or more messages while it was disconnected.

The following exemplary pseudocode illustrates one embodiment of the participant p in the second prepared state Pp: in state (Pp, S):

in state (Pp, S):on connect to p′:send prepared to p′on aborted from p′:abort({p, p′})on committed from p′:commit({p, p′})on prepared from p′:prepare_p_count(S ∪ {p′})

d. The Committed State C

As discussed above, the committed state C is a garbage collection state wherein the participant pxhandles information stored in a log during its execution of the MM2PC protocol. The participant pxwaits until the other participants in P complete the transaction before clearing its log so that it can provide the information in the log to another participant p′ that may not have received one or more messages sent, for example, when the other participant p′ was disconnected.

In the committed state C, the participant pxmay receive a “committed” message from another participant p′ (for example, committed(p′)). In response, the participant pxadds the other participant p′ to the set of known committed participants C′ (for example, C′=C′∪{p′}). Once all the participants in P have committed (for example, C′=P), the participant pxclears its log (for example, clean log) and transitions to the final state F.

When the participant pxdetects the connection or reconnection with another participant p′ (for example, connect(p′)), the participant pxnotifies the other participant p′ that it is committed to ensure that the earlier “committed” message was not missed. Again, the participant pxwaits in the committed state C until C′=P. However, if the participant pxdid not receive a “committed” message from the other participant p′ when it was disconnected, and if the other participant p′ did receive the earlier “committed” message from the participant pxsuch that it is finished with the transaction, the participant pxdoes not know whether the other participant p′ committed. To avoid a large number of messages being sent between the participants in P, the participants in P are not required to respond to “committed” messages. Thus, the other participant p′ will not send another “committed” message to the participant px. Therefore, the participant pxwill block as it remains in the completed state C.

To avoid this blocking, the participant pxsends a “committed′” message to the other participant p′ (for example, committed′(p′)) in response to connect(p′). The committed′ message indicates to the receiver of the message that the sender does not know if the receiver has resolved the transaction. If the other participant p′ is in the committed state C or the final state F, it will return the committed(p′) message to the participant px. Thus, in the committed state C, the participant pxcan add the other participant p′ to the variable C′. Likewise, if the participant pxreceives the committed′(p′) message from another participant p′ while in the committed state C or the final state F, the participant pxwill respond by sending the committed(p′) message to the other participant p′. In the committed state C, the participant pxalso adds the other participant p′ to the variable C′.

The following exemplary pseudocode illustrates one embodiment of the participant pxin the committed state C:

e. The Aborted State A

As discussed above, the aborted state A is also a garbage collection state wherein the participant pxhandles information stored in a log during its execution of the MM2PC protocol. In the aborted state A, the participant pxmay receive an “aborted” message from another participant p′ (for example, aborted(p′)). In response, the participant pxadds the other participant p′ to the set of know aborted participants A′ (for example, A′=A′∪{p′}). Once all the participants in P have aborted (for example, A′=P), the participant pxclears its log (for example, clean log) and transitions to the final state F.

When the participant pxdetects the connection or reconnection with another participant p′ (for example, connect(p′)), the participant pxnotifies the other participant p′ that it has aborted to ensure that the earlier “aborted” message was not missed. Again, the participant pxwaits in the aborted state A until A′=P. To avoid the blocking problem discussed above in relation to the committed state C, the participant pxsends an “aborted′” message to the other participant p′ (for example, aborted′(p′)) in response to connect(p′). The aborted′ message indicates to the receiver of the message that the sender does not know if the receiver has resolved the transaction. If the other participant p′ is in the aborted state A or the final state F, it will return the aborted(p′) message to the participant px. Thus, in the aborted state A, the participant pxcan add the other participant p′ to the variable A′. Likewise, if the participant pxreceives the aborted′(p′) message from another participant p′ while in the aborted state A or the final state F, the participant pxwill respond by sending the aborted(p′) message to the other participant p′. In the aborted state A, the participant pxalso adds the other participant p′ to the variable A′.

The following exemplary pseudocode illustrates one embodiment of the participant pxin the aborted state A:

While the MM2PC protocol allows for the coordinator to reside on the same node as a participant, the MM2PC does not address set-up phase transactions and may involve a large number of clean up messages. The two-phase commit version 2 protocol (“2PCV2”) addresses set-up phase transactions, allows for the addition of late participation additions, and reduces clean up messages. The 2PCV2 protocol includes an initiator i, a coordinator c, as well as a set of participants {p1, p2, . . . pn}. The initiator i and the coordinator c reside on the same node such that they never get disconnected from each other. In addition, one of the participants may also reside on the same node as the initiator and the coordinator. The participant, if any, that resides on the same node as the initiator and the coordinator is referred to herein as the shared participant ps. The remote participants notify the shared participant of the transaction's outcome thereby allowing the remote participants to resolve the transaction if they become disconnected from the coordinator. In addition, the initiator receives “committed” messages from the participants rather than from the coordinator.

FIG. 4illustrates an exemplary timing chart according to one embodiment of a 2PCV2 commit protocol400for a transaction involving an initiator410(shown as “i”), a first participant412(shown as “p1”), a second participant414(shown as “p2”), a shared participant416(shown as “ps”) and a coordinator418(shown as “c”). As discussed above, the initiator410and the coordinator418are on the same node. In the example shown inFIG. 4, the shared participant416is also on the same node as the initiator410and the coordinator418. The first participant412and the second participant414are located on remote nodes.

During the transaction, the initiator410adds the first participant412, the second participant414, and the shared participant416to the transaction. As it does so, the initiator410sends start messages419(three shown) to the first participant412, the second participant414, and the shared participant416. When the initiator410is ready to try to commit the transaction, the initiator sends “prepare” messages420(four shown) to the coordinator418, the first participant412, the second participant414, and the shared participant416. In one embodiment, the coordinator418is configured to return a response420ato the “prepare” message420. Since the initiator410and the coordinator418are on the same node, the coordinator418receives the “prepare” message420before the remote participants412,414.

The first participant412, the second participant414, and the shared participant416respectively log the “prepare” messages420and determine whether they are prepared to commit the transaction. If they can commit the transaction, the first participant412, the second participant414, and the shared participant416each send a “prepared” message422(three shown) to the coordinator418. If the coordinator418receives all of the “prepared” messages422, the coordinator418sends “commit” messages424(two shown) to the first participant412the second participant414. The coordinator418does not send a “commit” message424to the shared participant416.

After receiving the “commit” messages424from the coordinator418, the first participant412and the second participant414each log their respective “commits” and send “committed” messages426to the shared participant416. Thus, the shared participant416learns of the transaction's outcome from the other participants412,414. After committing to the transaction, the first participant412, the second participant414and the shared participant418send “committed” messages428(three shown) to the initiator410. For garbage collection purposes, the initiator410responds by sending “committed” messages430to the first participant412, the second participant414, and the shared participant416. After receiving the “committed” message430from the initiator410, the first participant412, the second participant414, and the shared participant416clear their respective logs and the commit protocol400ends.

The exemplary timing chart shown inFIG. 4illustrates the commit protocol400when no failures occur. Since the remote participants412,414notify the shared participant416of the transaction's outcome, the remote participants412,414can resolve the transaction if they both become disconnected from the coordinator418.

FIGS. 5-8illustrate state diagrams according to one embodiment of a 2PCV2 protocol. As stated above, parties in a transaction using the 2PCV2 protocol include an initiator i, a coordinator c on the same node as the initiator i, and one or more remote participant p selected from the set defined by {p1, p2, . . . , pn}. The parties may also include a shared participant pson the same node as the initiator i and the coordinator c.

FIG. 5illustrates a state diagram for the initiator i having an unknown state U, an initial state I, a prepare state Pi, an aborted state A, and a committed state C.

1. Unknown State U

The initiator i begins and ends the transaction in the unknown state U. Upon receiving a start command (for example, start( )) from a user, the initiator transitions to the initial state I.

2. Initial State I

While the initiator i is in the initial state I, the transaction is being performed. In one embodiment, the initiator i is configured to manage the transaction among nodes by sending transaction commands to and receiving responses from the nodes involved in the transaction. For example, in a transaction to stripe a file across a plurality of nodes in a distributed file system, the distributed system determines the nodes in which it will save data blocks. For each node selected to participate in the transaction, the distributed system sends a message to the initiator i to include the node as a participant p in the transaction (for example, add_participant(p)). In response to the add_participant(p) message, the initiator i adds the participant p to the set of participants P (for example, P=P∪{p}) and sends a start command to the participant p (for example, start(p)).

While the initiator i is in the initial state I, the user may send an “abort” command (for example, abort( )) or a “commit” command (for example, commit( )) to the initiator i. If the initiator i receives an “abort” command from the user, the initiator i sends an “aborted” message to the participants in P (for example, aborted(P)) and transitions to the aborted state A. If the initiator i receives a “commit” command (for example, commit( )) before the user adds any participants to the transaction (for example, P=Ø), the initiator i returns true to the user (for example, return(true)) and transitions back to the unknown state U.

If the user has added participants to the transaction (for example, P≠Ø), the initiator i sends a “prepare” message to the coordinator c (for example, prepare(c)) and a “prepare” message to the participants in P (for example, prepare(P)), and transitions to the prepare state Pi. The prepare(c) and prepare(P) messages include a final set of participants in the set of participants P. In some embodiments, the prepare(c) message is configured to be received by the coordinator c before the prepare(P) messages are sent. Thus, in one embodiment the prepare(c) message can be implemented as a function call rather than a message.

3. Prepare State Pi

In the prepare state Pi, the initiator i waits to receive an “aborted” or “committed” message from any one of the participants in P (for example, aborted(p) or committed(p), respectively). If the initiator i receives an “aborted” message from the participant p, the initiator i removes the participant p from the set of known participants P (for example, P=P\{p}) and transitions to the aborted state A. If the initiator i receives a “committed” message from a participant p, the initiator i removes the participant p from the set of known participants P (P=P\{p}), adds the participant p to the set of committed participants C′ (for example, C′={p}), and transitions to the committed state C. As discussed below, the initiator i tracks which participants in P have committed or aborted by removing the participant p from the set of known participants P when an “aborted” or “committed” message is received.

If the initiator i becomes disconnected from the participant p (for example, disconnect(p)), the initiator i removes the participant p from the set of known participants P (for example, P=P\{p}). As discussed below, the disconnected participant p will resolve the transaction without receiving further information from the initiator i. Thus, the initiator i can ignore the disconnected participant p. However, if the initiator i becomes disconnected from all of the participants (for example, P=Ø), the initiator i transitions to the unknown state U and reboots.

4. The Aborted State A and the Committed State C

In the aborted state A, the initiator i removes participants from the set of participants P when it receives “aborted” messages from the participants or detects that the participants have become disconnected. When P=Ø, the initiator i returns false to the user (for example, return(false)) and transitions to the unknown state U.

In the committed state C, the initiator i removes participants from the set of participants P when it receives “committed” messages from the participants or detects that the participants have become disconnected. When the initiator i receives a “committed” message from a participant p, it also adds the corresponding participant p to the set of known committed participants C′ (for example, C′=C′∪{p}). When P=Ø, the initiator i sends “committed” messages to the participants in the set of known committed participants C′ (for example, committed(C′)), returns true to the user (for example, return(true)), and transitions back to the unknown state U. As discussed below, the “committed” message from the initiator i is used for garbage collection.

The following exemplary pseudocode illustrates one embodiment of the initiator i:

C. Coordinator States

FIG. 6is a state diagram illustrating an unknown state U and a prepare state Pjof the coordinator c. The coordinator c begins and ends the transaction in the unknown state U. In the unknown state U, the coordinator c waits to receive a “prepare” message from the initiator i (for example, prepare(i)). The “prepare” message informs the coordinator c that the initiator i has started the transaction. If the coordinator c is connected to all of the participants in P when it receives the prepare(i) message, the coordinator c resets the set of known prepared participants S (for example, S=Ø) and transitions to the prepare state Pj.

If, on the other hand, the coordinator c is disconnected from one or more of the participants when it receives the prepare(i) message, the coordinator c remains in the unknown state U. Thus, the coordinator c quickly aborts the transaction by not transitioning to the prepare state Pjwhen at least one of the participants p is disconnected. When the other participants in P send “prepared” messages to the coordinator c (for example, prepared(p)), the coordinator c responds with an “aborted” message (for example, aborted(p)).

In the prepare state Pj, the coordinator c tracks the participants that are prepared to commit the transaction. When the coordinator c receives a “prepared” message from a participant p (for example, prepared(p)), the coordinator c adds the participant p to the set of known prepared participants S (for example, S=S∪{p}). Once all of the participants in P have prepared (for example, S=P), the coordinator sends a “commit” message to the participants in P except for the shared participant ps(for example, commit(P\{ps})) and transitions back to the unknown state U. As discussed below, the shared participant psreceives the outcome of the transaction from the other participants. As also discussed below, the participants that receive the commit(P\{ps}) message may end up ignoring it and aborting the transaction instead. Thus, the initiator i receives “committed” messages from the participants in P rather than from the coordinator c.

While in the prepare state Pj, the coordinator c may detect a disconnect from one of the participants in P (for example, disconnect(p)) or the coordinator c may receive an “aborted” message from one of the participants in P (for example, aborted(p)). In response, the coordinator c sends an “aborted” message to the prepared participants in S (for example, aborted(S)) and transitions back to the unknown state U.

The following exemplary pseudocode illustrates one embodiment of the coordinator c:

in state U:on prepared from p:send aborted to pon prepare(P) from i:if connected to all in P:set state to (P, Ø, P)else:leave state as Uin state (Pj, S, P):if S = P:send commit to P \ {ps}set state to Uon disconnect or aborted from p ∈ P:send aborted to Sset state to Uon prepared from p ∈ P:set state to (Pj, S ∪ {p}, P)

D. Remote Participant States

FIG. 7is a state diagram illustrating an unknown state U, an initial state I, a first prepared state Pc, a second prepared state Pp, a first committed state Ci, and a second committed state Cp of the remote participant p.

1. The Unknown State U

The participant p is in the unknown state U before and after the transaction. In the unknown state U, the participant p may receive committed′ message from another participant p′ (for example, committed′(p′)). The “committed′” message from another participant p′ indicates that the other participant p′ has committed to the transaction but is waiting to find out the status of the participant p before cleaning its log. Since the participant p is already in the unknown state with a clean log, it determines that it committed to the transaction and sends a “committed” message to the other participant p′ (for example, committed(p′)).

In the unknown state U, the participant p may receive a “prepared” message from another participant p′ (for example, prepared(p′)). As discussed in detail below, the participant p would not have cleaned its log and transitioned to the unknown state U unless it had received “committed” messages from all of the participants. However, the “prepared” message from the other participant p′ indicates that the other participant p′ has not committed the transaction. Thus, the participant p determines that the transaction was aborted and sends an “aborted” message to the other participant p′ (for example, aborted(p′)).

In one embodiment, the participant p receives a start message from the initiator i (for example, start(i)) to signal the beginning of the transaction. In response, the participant p transitions to the initial state I. In other embodiments, the initiator i does not send a start message to the participant p. Instead, the participant p transitions to the initial state I when it receives any message referencing the transaction. In such embodiments, messages in the transaction are no longer delivered to the participant p once the transaction is aborted to prevent the participant p from starting the aborted transaction.

2. The Initial State I

In the initial state I, the participant p performs the operations associated with the transaction. In one embodiment, the initiator i sends one or more request to the participant p to perform tasks for the transaction. In a distributed file system, for example, the initiator i may send requests to the participant p to read data blocks, allocate space for data blocks, write data blocks, calculate parity data, store parity data, send messages to another participant, combinations of the forgoing, or the like. If the participant p has an error while performing the transaction, becomes disconnected from the initiator i (for example, disconnect(i)), or receives an “aborted” message from the initiator i (for example, aborted(i)), the participant aborts the transaction and sends an “aborted” message to the coordinator c, the initiator i, and the participants in the set of known prepared participants S from which it has received “prepared” messages (for example, aborted(c, i, S)). The participant p then transitions back to the unknown state U.

While in the initial state I, the participant p may receive a “prepared” message from another participant p′ (for example, prepared(p′)). For example, another participant p′ may send the prepared(p′) message to the participants in P if it received a “prepare” message from the initiator i and then disconnected from the coordinator c. In response to receiving the prepared(p′) message, the participant p adds the other participant p′ to the set of known prepared participants S (for example, S=S∪{p′}) for use in the second prepared state Pp.

As discussed above, the initiator i can add participants to P as the transaction is being executed. After the participants in P have performed the operations associated with the transaction, the initiator i sends a “prepare” message (for example, prepare(i)) to the participants in P. The prepare(i) message includes the final set of participants in P. If the participant p has not transitioned back to the unknown state U, the participant p responds to the prepare(i) message by logging the prepare, sending a “prepared” message to the coordinator c (for example, prepared(c)) and transitioning to the first prepared state Pc.

Although not shown, in other embodiments the participant p only transitions to the first prepared state Pc from the initial state I if S=Ø. In such embodiments, if S≠Ø, the participant p may transition directly to the second prepared state Pp.

3. The First Prepared State Pc

In the first prepared state Pc, the participant p awaits the outcome of the transaction. The coordinator c may notify the participant p of the outcome by sending a “commit” or “aborted” message to the participant p (for example, commit(c) or aborted(c)). In response to commit(c), the participant p sends a “committed” message to the initiator i and to the shared participant ps(for example, committed(i, ps)). Thus, as discussed in detail below, the shared participant psis notified of the outcome of the transaction. The participant p then transitions to the first committed state Ci. In response to the “aborted” message from the coordinator, the participant p sends an “aborted” message to the coordinator c, the initiator i, and the participants in S. The participant p then transitions back to the unknown state U.

Rather than receiving notice of the transaction's outcome from the coordinator c, another participant p′ may notify the participant p of the outcome by sending a committed′(p′) message. In response to the committed′(p′) message, the participant p adds the other participant p′ to the set of known committed participants C′ (for example, C′={p′}), sends a “committed” message to the initiator i, the shared participant ps, and the other participant p′ (for example, committed(i, ps, p′)), and transitions to the first committed state Ci.

In the first prepared state Pc, the participant p may receive a prepared(p′) message from another participant p′. In response, the participant p adds the other participant p′ to the set of known prepared participants S (for example, S=S∪{p′}) allowing participant p to track the participants from which it has received a “prepared” message if it transitions to the second prepared state Pp. In the first prepared state Pc, the participant p may detect that it has become disconnected from the coordinator (for example, disconnect (c)). In response, the participant sends a “prepared” message to all participants in P (for example, prepared (P)) and transitions to Pp.

4. The Second Prepared State Pp

In one embodiment, the second prepared state Pp is used when the participant p loses its connection with the coordinator c. As noted above, only the participants can notify the shared participant psof the outcome of the transaction. Participants in the second prepared state Pp are not committed. Thus, once the participant p knows that all the participants in P except for the shared participant psare in the second prepared state Pp (for example, S=P\{ps}), the participant p knows that the shared participant psis not committed. The participant p can then abort the transaction, send an “aborted” message to the coordinator c and the initiator i (for example, aborted(c, i)), and transition back to the unknown state U. Thus, once all of the non-shared participants in P are disconnected from the coordinator c, the non-shared participants resolve the transaction by aborting without further instructions from the initiator i or coordinator c.

In the second prepared state Pp, the participant p may receive a “committed” or “aborted” message from another participant p′ (for example, committed′(p′) or aborted(p′)). In response to receiving the committed′(p′) message, the participant p adds the other participant p′ to the set of known committed participants C′ (for example, C′={p′}) and sends a “committed” message to the initiator i and the other participant p′ (for example, committed(i, p′)). To find out which of the other participants in P have also committed, the participant p sends a committed′ message to the participants in P (for example, committed′(P\{p′})). The participant p then transitions to the second committed state Cp.

Sending a “prepared” message is how the participant p asks for the outcome of the transaction. If the other participant p′ has aborted the transaction, the other participant p′ sends the aborted(p′) message to the participant p in response to a “prepared” message (not shown) from the participant p. In response to receiving the aborted(p′) message, the participant p aborts the transaction, sends an “aborted” message to the coordinator c and the initiator i (for example, aborted(c, i)), and transitions to the unknown state U.

In the second prepared state Pp, the participant p may detect a connection to another participant p′ (for example, connect(p′)). In response, the participant p sends a “prepared” message to the other participant p′ (for example, prepared(p′)). When the participant p and the other participant p′ connect, the other participant p′ also sends a “prepared” message to the participant p. When the participant receives a “prepared” message from another participant p′ other than the shared participant p′ (for example, prepared(p′εP\{ps})), the participant adds the other participant p′ to the set of known prepared participants S (for example, S=S\p′).

5. Garbage Collection and Restart

The participant p records messages sent or received during the commit protocol in a log. The participant p can provide the information in the log to another participant p′ that may not have received one or more messages sent, for example, when the other participant p′ was disconnected. The participant p can also use the information when the participant p restarts after a disconnect or failure to determine the outcome of the transaction.

In one embodiment, when the participant p restarts after a failure, the participant p checks its log for a prepare block, a done block, a commit block, or a combination of the forgoing. If the log does not have a prepare block, the participant p restarts in the unknown state U. The participant p also restarts in the unknown state U if the log has a done block. If the log has a prepare block, but no commit block or done block, the participant restarts in the second prepared state Pp. If the log has a prepare block and a commit block, but no done block, the participant p restarts in the second committed state Cp.

The first committed state Ci and the second committed state Cp are garbage collection states. In these states, the participant p has already committed the transaction. However the participant p waits to clear its log until it is sure that the information stored therein will not be needed. The set of known committed participants C′ includes the participants that the participant p knows have also committed the transaction. When the participant p receives a committed′ from another participant p′ (for example, committed′(p′)), the participant p adds the other participant p′ to the set of known committed participants C′ (for example, C′=C′∪{p′}) and sends a “committed” message to the other participant p′ (for example, committed(p′)).

In the first committed state Ci, the participant p waits to receive a “committed” message from the initiator i that includes a set T of participants that the initiator i knows have committed (for example, committed(i)(T)). In response to receiving the committed(i)(T) message, the participant p adds the participants in T to C′ (for example, C′=C′∪T). If C′∪T is not all of the participants in P, the participant sends a committed′ message to query the participants it does not know have committed (for example, committed′(P\C′)). The participant p also sends the committed′(P\C′) message if it detects a disconnect from the initiator i. The participant p then transitions to the second committed state Cp.

In the second committed state Cp, the participant p may receive a “committed” message from another participant p′ (for example, committed(p′)). In response, the participant p adds the other participant p′ to the set of known committed participants C′ (for example, C′=C′∪{p′}). The participant p may also detect a connection to another participant p′ that is not included in the set of known committed participants C′ (for example, connect(p′εP\C′). In response, the participant p queries whether the other participant p′ has committed by sending it a committed′ message (for example, committed′(p′)). When C′=P, the participant p can clean its log and transition to the unknown state U.

The following exemplary pseudocode illustrates one embodiment of the participant p:

E. The Shared Participant

As discussed above, the transaction may include a shared participant ps. The shared participant psis on the same node as the coordinator c and the initiator i. The coordinator c does not send a “commit” message to the shared participant ps. Instead, the other participants in P inform the shared participant psthat the transaction is committed.

FIG. 8is a state diagram illustrating the states of the shared participant psaccording to one embodiment. The shared participant psoperates similar to a remote participant p and can be in the unknown state U, the initial state I, the second prepared state Pp, the first committed state Ci, and the second committed state Cp as discussed above in relation toFIG. 7. However, since the shared participant psdoes not receive a “commit” message from the coordinator c, the shared participant psdoes not enter the first prepared state Pc. Rather, when the shared participant psreceives the prepare(i) message from the initiator i, the shared participant pstransitions directly to the second prepared state Pp.

Since the shared participant psdoes not enter the first prepared state Pc, the shared participant transitions to the first committed state Ci directly from the second prepared state Pp. Thus, upon receiving the committed′(p′) message while in the second prepared state Pp, the shared participant pstransitions to the first committed state Ci. In the second prepared state Pp, the shared participant psmay learn of the outcome of the transaction by receiving a “committed” message from another participant p′ (for example, committed(p′)). In response, the shared participant psadds the other participant p′ to the set of known committed participants C′ (for example, C′={p′}), sends a “committed” message to the initiator i, and transitions to the first committed state Ci.

Like the remote participant p, upon detecting connect(p′), the shared participant psasks the other participant p′ the outcome of the transaction by sending a prepared(p′) message. As discussed above, if the other participant p′ has not resolved the transaction, it will ignore the prepared(p′) message from the shared participant ps. If the other participant p′ has aborted the transaction, it will send aborted(p′) to the shared participant ps.

An artisan will recognize from the disclosure herein that there are other differences between the shared participant psand the remote participant p discussed above. For example, since the shared participant psis on the same node as the coordinator c and the initiator i, the shared participant pswill not detect disconnect(i). Thus, the shared participant psdoes not respond to disconnect(i) in, for example, the unknown state U or the first committed state Ci.

In one embodiment, the shared participant psrestarts as discussed above in relation to the remote participant p.

The following exemplary pseudocode illustrates one embodiment of the shared participant ps:

While the MM2PC and the 2PCV2 protocols provide single-failure non-blocking commitment protocols, it may be useful to provide for double-failure tolerance. The 2.5 Phase Commit (“2.5PC”) protocol provides a double-failure non-blocking atomic commitment protocol. The 2.5PC protocol includes an initiator i, a coordinator c, a distributor d, as well as a set of participants P={P1, P2, . . . pn}. In the 2.5PC protocol, each party is located on a different node from the other parties. It is recognized, however, that the 2.5PC protocol may be implemented such that two parties share a node (for example, the coordinator c shares a machine with one participant p2), but such implementations would only provide single-failure tolerance.

FIG. 9illustrates an exemplary timing chart according to one embodiment of a 2.5PC protocol900for a transaction involving an initiator910(shown as “i”), a first participant912(shown as “p1”), a second participant914(shown as “p2”), a coordinator916(shown as “c”), and a distributor918(shown as “d”). The coordinator916and the distributor918are on separate nodes. If the coordinator916and the distributor918do not share a node with the first participant912or the second participant914, then the commit protocol900allows for double-failure non-blocking.

The initiator910sends “prepare” messages920(two shown) to the first participant912and the second participant914. The first participant912and the second participant914log their respective “prepare” messages920and determine whether they are prepared to commit the transaction. If the first participant912can commit the transaction, the first participant912sends a “prepared” message922to the coordinator916. If the second participant914can commit the transaction, the second participant914sends a “prepared” message922to the coordinator916. If the coordinator receives both of the “prepared” messages922, the coordinator916sends a “commit” message924to the distributor918.

If the coordinator916and one of the participants912,914were to fail (for example, a double-failure) after the coordinator916sends the “commit” message924, the distributor918knows the coordinator's916decision and can resolve the transaction. Thus, the protocol900is double-failure non-blocking. In response to the “commit” message924from the coordinator916, the distributor918sends “commit” messages926(three shown) to the first participant912, the second participant914, and the coordinator916.

After receiving the “commit” messages926from the distributor918, the first participant912and the second participant914respectively log the “commits” and send “committed” messages928(six shown) to each other, to the coordinator916, and to the initiator910. Upon receiving a “committed” message928, the first participant912and the second participant914clear their respective logs and the 2.5PC protocol900ends.

The exemplary timing chart shown inFIG. 9illustrates the 2.5PC protocol900when no failures occur. However, if one or more of the participants912,914fails or disconnects, the coordinator916aborts the transaction and informs the distributor918. The distributor918then informs the remaining participants912,914.

If the coordinator916fails or disconnects before informing the distributor918of its decision, the distributor918aborts because it does not know if all the participants912,914prepared successfully. However, the coordinator916can also send “abort” or “commit” messages to the participants912,914. Therefore, as discussed in detail below, when the coordinator916is disconnected from the distributor918, the participants912,914decide whether to accept “commit” or “abort” messages from the coordinator916or the distributor918. If the participants912,914decide to accept the decision of the distributor918, the distributor sends an “abort” message to the participants912,914.

If the coordinator916loses its connection with the distributor918before sending the “commit” message924, the coordinator916aborts. Since the distributor also aborts, the coordinator916sends “abort” messages to the participants912,914without waiting for the participants to decide whether to accept the decision of the coordinator916.

If, on the other hand, the coordinator916loses its connection to the distributor918after sending the “commit” message924, the coordinator916is still committed. However, the coordinator916does not know whether the distributor918received the “commit” message924. If the distributor918did receive the “commit” message924, it may have sent the “commit” messages926to one or more of the participants912,914. If the distributor918did not receive the “commit” message924, the distributor918may abort the transaction when the participants912,914decide to accept the distributor's918decision. Thus, the coordinator916waits for the participants912,914to decide to accept its decision before committing the transaction.

The participants912,914vote to determine whether to accept the decision (for example, commit or abort) of the coordinator916or the distributor918. For example, if the coordinator916receives a majority of the votes, it will send its decision to the participants912,914. If, on the other hand, the distributor918receives the majority of votes, it will send its decision to the participants912,914. The participants912,914will vote for the coordinator916if they loose their respective connections to the distributor918. The participants912,914will vote for the distributor918if they lose their respective connections with the coordinator916. Otherwise, the participants912,914will vote for the first party (for example, either the coordinator916or the distributor918) to ask for its vote. In one embodiment, only the distributor918asks for votes to avoid a split vote.

If one or more of the participants912,914are disconnected from the coordinator916, the distributor918, or both, neither the coordinator916nor the distributor918may receive the majority of the votes. Thus, the participants912,914send their respective votes to both the coordinator916and the distributor918. When either the coordinator916or the distributor918realizes that it cannot receive the majority of votes, it bows out of the election and notifies the participants912,914.

If both the participants912,914lose their connections with both the coordinator916and the distributor918, the participants912,914deterministically resolve the transaction among themselves as discussed above.

FIGS. 10-12Dillustrate state diagrams according to one embodiment of a 2.5PC protocol. Parties in a transaction using the 2.5PC protocol include a coordinator c, a distributor d, one or more participant p selected from the set defined by {p1, p2, . . . , pn}, and an initiator i.

B. Coordinator States

FIG. 10is a state diagram illustrating an initial state I, a commit state C and a final state F of the coordinator c during execution of the commit protocol. The coordinator c can be in a state “sc” defined by:
Scε{(I,S)|S⊂P}
∪{(C,Sfor,Sagainst)|Sfor,Sagainst⊂P; Sfor∩Sagainst=Ø}
∪{F}
wherein P is a set of participants defined by P={p1, p2, . . . , pn}. The variable S is a proper subset of the participants in P for which the coordinator c has received “prepared” messages. In the commit state C, the coordinator c keeps two mutually exclusive proper subsets Sforand Sagainstof the participants in P. The variable Sforincludes participants that vote for the coordinator c and the variable Sagainstincludes participants that vote for the distributor d.

1. The Initial State I

As illustrated inFIG. 10, the coordinator c starts in the initial state I. In the initial state I, the coordinator c may receive a “prepared” message from one of the participants p (for example, prepared(p)). In response, the coordinator c adds the participant p to the set of known prepared participants S (for example, S=S∪{p}). Once S=P, the coordinator c sends a “commit” message to the distributor d (for example, commit(d)) and transitions to the commit state C.

While in the initial state I, the coordinator c may detect a disconnect from one of the participants p (for example, disconnect(p)), or may receive an “abort” message from the initiator i (for example, abort(i)), an “aborted” message from the participant p (for example, aborted(p)), or a pledged message from one of the participants p (for example, pledged(p)). In response, the coordinator c aborts the transaction and sends an “abort” message to the participants in P and the distributor d (for example, abort(P, d)). The coordinator c then transitions to the final state F.

The “pledged” message from one of the participants p may be a vote from the participant p for the coordinator c or the distributor d. Either way, the coordinator c knows that the “pledged” message is in response to a “pledge” message (discussed below) from the distributor d in the event of a failure. Thus, the coordinator c aborts.

2. The Commit State C

In the commit state C, the coordinator c expects the transaction to be committed but waits in the commit state C in case the distributor d fails and the participants in P need the coordinator c to resolve the transaction. While in the commit state C, the coordinator c may receive the “pledged” message from one of the participants p. As discussed above, the coordinator c adds the participant p to the set of participants voting for the coordinator Sforif the participant p pledges its vote to the coordinator c (for example, pledged(p)(c)). Once |Sfor|>└|P|/2┘, the coordinator c commits the transaction and sends a “commit” message to the participants in P and the distributor d (for example, commit(P, d)). The coordinator c then transitions to the final state F.

If the participant p pledges its vote to the distributor d (for example, pledged(p)(d)), the coordinator c adds the participant p to set of participants voting for the distributor Sagainst. The coordinator c may also detect that it has disconnected from one of the participants (for example, disconnect(p)). If the participant p is not in Sforor Sagainst, in one embodiment, the coordinator c adds the participant p to Sagainst. If |Sagainst|≧┌|P|/2┐, the coordinator c revokes its participation in the election and notifies the participants in P (for example, revoke(P)). The coordinator c then transitions to the final state F.

In the commit state C, the coordinator c may receive the “aborted” message or a “committed” message from one of the participants p (for example, aborted(p) or committed(p)). In response to the “aborted” message, the coordinator c aborts the transaction, sends the “abort” message to all of the participants in P and the distributor d (for example, abort(P, d)) and transitions to the final state F. In response to the “committed” message, the coordinator c commits the transaction, sends a “commit” message to the participants in P and the distributor d (for example, commit(P, d)), and transitions to the final state F.

The following exemplary pseudocode illustrates one embodiment of the coordinator c:

It is recognized that not all error cases are shown in the above pseudocode. In the embodiments discussed above, non-handled messages are ignored. For example, the above pseudocode does not address a failure of the connection between the coordinator c and the distributor d. If the connection goes down, the distributor d starts seeking pledges and the coordinator c starts receiving “pledged” messages or “aborted” messages from one of the participants p (for example, pledged(p) or aborted(p)). Further, the above pseudocode does not have a restart procedure for the coordinator c. If the coordinator c fails, the participants ignore it. When the coordinator c restarts, it has no knowledge of the transaction, but the participants do not care; and if the coordinator then aborts, the coordinator c does not inform the distributor d when it aborts. The distributor d is instead notified of the abort from the participants.

C. Distributor States

FIG. 11is a state diagram illustrating an initial state I, an abort state A, and a final state F of the distributor d during execution of the commit protocol. The distributor d can be in a state “sd” defined by:
sdε{(r,Sfor,Sagainst)|rε{I,A}; Sfor,Sagainst⊂P; Sfor∩Sagainst=Ø}∪{F}
wherein the distributor d adds participants that vote for the distributor d to the set of participants voting for the distributor Sforand adds participants that vote for the coordinator c to the set of participants voting for the coordinator Sagainst.

1. The Initial State I

The distributor d starts in the initial state I where it can detect a disconnect from a participant p (for example, disconnect(p)) or receive pledged messages from the participant p for the coordinator c or the distributor d (for example, pledged(p)(c) or pledged(p)(d)). In response, the distributor d adds the participant p to the corresponding set Sforor Sagainst, as described above.

If the distributor d detects a disconnect from the coordinator c (for example, disconnect(c)) while in the initial state I, the distributor d checks to see if the number of votes for the coordinator are less than the majority and then requests votes from the participants in P that have not yet voted by sending them a “pledge” message (for example, pledge(P\(Sfor∪Sagainst))). The distributor d then transitions to the abort state A where it tries to abort the transaction.

If the distributor d receives an “abort” message from the initiator i or the coordinator c (for example, abort(i, c)) or an “aborted” message from one of the participants p (for example, aborted(p)), the distributor d aborts the transaction. The distributor d then sends an “abort” message to the participants in P (for example, abort(P)) and transitions to the final state F. If, on the other hand, the distributor d receives a “commit” message from the coordinator c (for example, commit(c)) or a “committed” message from one of the participants p (for example, committed(p)), the distributor d commits the transaction. The distributor d then sends a “commit” message to the participants in P (for example, commit(P)) and transitions to the final state F.

2. The Abort State A

In the abort state A, the distributor d tries to get enough votes to abort the transaction. Upon detecting a disconnection from one of the participants p that has not voted for the distributor (for example, disconnect(pεP\Sfor)), the distributor d adds the participant p to the set of participants voting for the coordinator Sagainst. The distributor d may also receive pledged messages from the participant p for the coordinator c or the distributor d (for example, (pledged (p)(c) or pledged (p)(d))). In response, the distributor d adds the participant p to the corresponding sets Sforor Sagainst, as described above. Once |Sagainst|≧┌|P|/2┘, the distributor d revokes its participation in the election and notifies the participants in P (for example, revoke(P)). The distributor d then transitions to the final state F. Once |Sfor|>└|P|/2┘, the distributor d aborts the transaction and sends an “abort” message to the participants (for example, abort(P)). The distributor d then transitions to the final state F.

If the distributor d receives the “aborted” message from one of the participants p (for example, aborted(p)) while in the abort state A, the distributor d aborts the transaction, sends the “abort” message to all of the participants (for example, abort(P)) and transitions to the final state F. If the distributor d receives the “committed” message from one of the participants p (for example, committed(p)) while in the abort state A, the distributor d commits the transaction, sends the “commit” message to all of the participants (for example, commit(P)) and transitions to the final state F. Like the coordinator c, the distributor d does not have a restart procedure. If the distributor d fails, the participants in P will ignore it and continue with the commit protocol.

The following exemplary pseudocode illustrates one embodiment of the distributor d:

D. Participant States

FIGS. 12A-12Dare state diagrams illustrating an initial state I, a first prepared state Pcd, a second prepared state Pc, a third prepared state Pd, a fourth prepared state Pp, an aborted state A, a committed state C and a final state F for a participant p during execution of the commit protocol. The participant p can be in a state “sp” defined by:
spε{(r,S)|rε{I,Pcd,Pc,Pd,Pp}; S⊂P}∪{(A,A′)|A′⊂P}∪{(C,C′)|C′⊂P}∪{F}
wherein P is a set of participants defined by P={p1, p2, . . . , pn}. The variable S is a proper subset of the participants in P for which the participant p has received “prepared” messages. As discussed below, participants in S are in the fourth prepared state Pp.

In the first prepared state Pcd, the participant p has not pledged its vote to the coordinator c or the distributor d, but is prepared and listening to the coordinator or the distributor. In the second prepared state Pc, the participant p has pledged its vote to the coordinator c and is prepared and listening to the coordinator. In the third prepared state Pd, the participant p has pledged its vote to the distributor d and is prepared and listening to the distributor. The participant p transitions to the fourth prepared state Pp from the second prepared state Pc or the third prepared state Pd when it decides to resolve the transaction deterministically without further input from the coordinator c or the distributor d, showing that it is prepared and listening to the other participants.

1. The Initial State I

As illustrated inFIG. 12B, the participant p begins the transaction in the initial state I where it waits for a “prepare” message from the initiator i (for example, prepare(i)). Upon receiving the “prepare” message from the initiator (for example, prepare(i)), the participant p sends a “prepared” message to the coordinator c (for example, prepared(c)) and transitions to the first prepared state Pcd to await an “abort” or “commit” message. If the participant p receives a “prepared” message from another participant p′ (for example, prepared(p′)), the participant p adds the other participant p′ to the set of known prepared participants S (for example, S=S∪{p′}).

In the initial state I, the participant p may receive an “abort” message from the initiator i, the coordinator c, or the distributor d (for example, abort(i, c, d)). The participant p may also receive an “aborted” message from another participant p′ (for example, aborted(p′)) or a “pledge” message from the distributor d (for example, pledge(d)). The “pledge” message from the distributor indicates that the distributor d has lost its connection with the coordinator c. In response to receiving the “abort” message from the initiator, the coordinator, or the distributor (for example, abort(i, c, d)), the “aborted” message from one of the other participants p′ (for example, aborted(p′)), or the “pledged” message from the distributor d (for example, pledge(d)), the participant aborts the transaction and transitions to the aborted state A. Upon aborting the transaction, the participant p sends an “aborted” message to the participants in P, the initiator i, the coordinator c, and the distributor d (for example, aborted(P, i, c, d)).

In the initial state I, the participant p may have an error wherein it cannot commit the transaction (for example, error), or it may detect a disconnect from the initiator i, the coordinator c, or the distributor d (for example, disconnect(i, c, d)). In response, the participant p aborts the transaction, sends the “aborted” message to all of the participants in P, the initiator i, the coordinator c, and the distributor (for example, aborted(P, i, c, d)) and transitions to the aborted state A.

2. The First Prepared State Pcd

As illustrated inFIG. 12D, in the first prepared state Pcd, the participant p has not pledged its vote to the coordinator c or the distributor d. If the participant p detects a disconnect from the coordinator c (for example, disconnect(c)) or receives a “revoke” message from the coordinator c (for example, revoke(c)), the participant p then pledges its vote to the distributor d and sends a “pledged” message for the distributor d to the distributor (for example, pledged (d)(d)) and transitions to the third prepared state Pd. If the participant p receives a “pledge” message from the distributor d (for example, pledge(d)), then the participant p pledges its vote to the distributor d and sends a “pledged” message for the distributor d to the coordinator c and the distributor d (for example, pledged(c, d)(d)) and transitions to the third prepared state Pd.

If, while in the first prepared state Pcd, the participant p detects a disconnect from the distributor d (for example, disconnect(d)) or receives a “revoke” message from the distributor d (for example, revoke(d)), the participant p pledges its vote to the coordinator C. The participant p then sends a “pledged” message for the coordinator c (for example, pledged(c)(c)) to the coordinator c, and transitions to the second prepared state Pc.

In the first prepared state Pcd, the participant may receive a “commit” message from the coordinator c or the distributor d (for example, commit(c, d)) or a “committed” message from another participant p′ (for example, committed(p′)). In response, the participant p commits the transaction and sends a “committed” message to the participants in P, the initiator i, the coordinator c, and the distributor d (for example, committed(P, i, c, d)). The participant p then transitions to the committed state C.

In the first prepared state Pcd, the participant p may also receive an “abort” message from the coordinator c or the distributor d (for example, abort(c, d)), or the “aborted” message from another participant p′ (for example, aborted(p′)). In response, the participant p aborts the transaction, sends the “aborted” message to the participants in P, the initiator i, the coordinator c, and the distributor d, (for example, aborted(P, i, c, d)), and transitions to the aborted state A.

3. The Second Prepared State Pc and the Third Prepared State Pd

As illustrated inFIG. 12D, in the second prepared state Pc, the participant p has pledged its vote to the coordinator c. In the third prepared state Pd, the participant p has pledged its vote to the distributor d. In the second prepared state Pc or the third prepared state Pd, the participant p may receive the “commit” message from the coordinator c or the distributor d (for example, commit(c, d)) or the “committed” message from another participant p′ (for example, committed(p′)). In response, the participant p commits the transaction, sends the “committed” message to the participants in P, the initiator i, the coordinator c, and the distributor d (for example, committed(P, i, c, d)) and transitions to the committed state C.

In the second prepared state Pc or the third prepared state Pd, the participant p may also receive the “abort” message from the coordinator c or the distributor d (for example, abort(c, d)) or the “aborted” message from another participant p′ (for example, aborted(p′)). In response, the participant p aborts the transaction, sends the “aborted message” to the participants in P, the initiator i, the coordinator c, and the distributor d (for example, aborted(P, i, c, d)) and transitions to the aborted state A.

In the second prepared state Pc, the participant p may detect a disconnect from the coordinator c (for example, disconnect(c)) or receive the “revoke” message from the coordinator c (for example, revoke(c)). In response, the participant p sends a “prepared” message to the participants in P (for example, prepared(P)) and transitions to the fourth prepared state Pp.

In the third prepared state Pd, the participant p may detect a disconnect from the distributor (for example, disconnect(d)) or receive the “revoke” message from the distributor (for example, revoke(d)). In response, the participant p sends the “prepared” message to the participants in P (for example, prepared(P)) and transitions to the fourth prepared state Pp.

4. The Fourth Prepared State Pp

As illustrated inFIG. 12D, the participant p transitions to the fourth prepared state Pp from the second prepared state Pc or the third prepared state Pd when it decides to resolve the transaction deterministically without further input from the coordinator c or the distributor d. As illustrated inFIG. 12C, in the fourth prepared state Pp, the participant p waits for all of the other participants in P to enter the fourth prepared state Pp (for example, S=P) before committing the transaction. After committing, the participant p sends the “committed” message to the participants in P, the initiator i, the coordinator c, and the distributor d (for example, committed(P, i, c, d)) and transitions to the committed state C.

When the participant p receives the “prepared” message from another participant p′ (for example, prepared(p′)), the participant p adds the other participant p′ to the set of known participants S. When the participant p detects a connect from another participant p′ (for example, connect(p′)), it sends the “prepared” message to the other participant p′ (for example, prepared(p′)) in case the other participant p′ did not receive the “prepared” message when it was disconnected.

In the fourth prepared state Pp, the participant p may receive the “aborted” message from another participant p′ (for example, aborted(p′)). In response, the participant p adds the other participant p′ to a set of known aborted participants A′ (for example, A′=A′∪{p′} or A′={p′}) and sends the “aborted” message to the participants in P, the initiator i, the coordinator c, and the distributor d (for example, aborted(P, i, c, d)). The participant p then transitions to the aborted state A.

The participant p may also receive the “committed” message from another participant p′ (for example, committed(p′)) while in the fourth prepared state Pp. In response, the participant p commits the transaction and adds the other participant p′ to a set of known committed participants C′ (for example, C′=C′∪{p′} or C′={p′}). The participant p then sends the “committed” message to the participants in P, the initiator i, the coordinator c, and the distributor d (for example, committed(P, i, c, d)) and transitions to the committed state C.

5. The Committed State C

The committed state C and the aborted state A are garbage collection states wherein the participant p handles information stored in a log during its execution of the commit protocol. As illustrated inFIG. 12C, the participant p waits until the other participants in P complete the transaction before clearing its log so that it can provide the information in the log to another participant p′ that may not have received one or more messages sent, for example, when the other participant p′ was disconnected.

In the committed state C, the participant p may receive the “committed” message from another participant p′ (for example, committed(p′)). In response, the participant p adds the other participant p′ to the set of known committed participants C′ (for example, C′=C′∪{p′}). Once all the participants in C′ have committed (for example, C′=P), the participant p cleans its log and transitions to the final state F.

When the participant p detects a connection to another participant p′ (for example, connect(p′)), the participant p sends a “committed′” message to the other participant p′ (for example, committed′(p′)). Again, the participant p waits in the committed state C until C′=P.

6. The Aborted State A

As discussed above, the aborted state A is also a garbage collection state wherein the participant p handles information stored in a log during its execution of the commit protocol. As illustrated inFIG. 12C, in the aborted state A, the participant p may receive the “aborted” message from another participant p′ (for example, aborted(p′)). In response, the participant p adds the other participant p′ to the set of known aborted participants A′ (for example, A′=A′∪{p′}. Once all the participants in A′ have aborted (for example, A′=P), the participant p cleans its log and transitions to the final state F.

When the participant p detects a connect to another participant p′ (for example, connect(p′)), the participant p sends an “aborted′” message to the other participant p′ (for example, aborted′(p′)). Again, the participant p waits in the aborted state A until A′=P.

7. The Final State F

The participant p ends the transaction in the final state F. As illustrated inFIG. 12C, in the final state F, the participant p may receive the “aborted′” message from another participant p′ (for example, aborted′(p′)). In response, the participant sends the “aborted” message to the other participant p′ (for example, aborted(p′)). The participant p may also receive the “committed′” message from another participant p′ (for example, committed′(p′)). In response, the participant p sends the “committed” message to the other participant p′ (for example, committed(p′)).

The following exemplary pseudocode illustrates one embodiment of the participant p:

The 2.5PC protocol is double-failure non-blocking if there are at least three participants and the coordinator c and the distributor d are on different nodes than each other and all participants. For example, if both the coordinator c and the distributor d fail after all the participants in P prepare, the participants will all go to the fourth prepared state Pp and resolve the transaction themselves. If, rather than crashing, the coordinator c and distributor d lose some of their network connections, including the connection between themselves, they may both realize that they can not get enough pledges to resolve the transaction and will send revoke messages to the participants in P. This will result in all the participants in P moving to the fourth prepared state Pp and resolving the transaction.

As another example, if the coordinator c and the participant p both fail, the distributor d will start gathering pledges. If there are at least three participants in P, there will be at least two non-failed participants p′. Thus, the distributor d will be able to get a majority of the votes. The distributor d will then abort the transaction. If the coordinator c and the failed participant p have not crashed, but just on the other side of a network split for example, the coordinator c will fail to gather enough pledges to commit the transaction and will transition to its final state F. The participant p will receive the result when it reconnects to one of the other participants p′.

As another example, a failure of both the distributor d and the participant p will cause all the other participants in P to disconnect from the distributor d. This will result in a majority of pledges to the coordinator c. The coordinator c will then commit the transaction. If the distributor d and the participant p are on the other side of a network split for example, they may or may not commit the transaction. If the distributor d received the original “commit” message from the coordinator c before the link went down, it will commit. However, if the distributor d did not receive the commit, the distributor d will start getting pledges. Once it discovers that it can only get one pledge, it will revoke and transition to its final state F. The participant p will resolve the transaction when it reconnects to another participant p′.