Source: http://www.google.com/patents/US8055711?dq=6076065
Timestamp: 2015-07-05 05:23:43
Document Index: 362138452

Matched Legal Cases: ['Application No. 60', 'Application No. 60', 'Application No. 60', 'Application No. 60', 'Application No. 60', 'Application No. 60', 'Application No. 60', 'application No. 02756944']

Patent US8055711 - Non-blocking commit protocol systems and methods - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inAdvanced Patent SearchPatentsSystems 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...http://www.google.com/patents/US8055711?utm_source=gb-gplus-sharePatent US8055711 - Non-blocking commit protocol systems and methodsAdvanced Patent SearchPublication numberUS8055711 B2Publication typeGrantApplication numberUS 11/262,306Publication dateNov 8, 2011Filing dateOct 28, 2005Priority dateOct 29, 2004Also published asUS8140623, US20060095438, US20070168351Publication number11262306, 262306, US 8055711 B2, US 8055711B2, US-B2-8055711, US8055711 B2, US8055711B2InventorsNeal T. Fachan, Peter J. Godman, Aaron J. PasseyOriginal AssigneeEmc CorporationExport CitationBiBTeX, EndNote, RefManPatent Citations (105), Non-Patent Citations (88), Referenced by (5), Classifications (6), Legal Events (4) External Links: USPTO, USPTO Assignment, EspacenetNon-blocking commit protocol systems and methods
US 8055711 B2Abstract
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.
1. A distributed system configured to resolve an atomic transaction comprising multiple transactions among a set of parties within the distributed system, the distributed system comprising:
a plurality of participants, each of the plurality of participants residing on a node of a computer system and in communication with each of the other of the plurality of participants; and
a coordinator residing on a node of the computer system and in communication with each of the plurality of participants, wherein at least one of the plurality of participants resides on the same node of the computer system as the coordinator;
receive one or more prepared messages from one or more of the plurality of participants, each prepared message indicating whether the sending participant can commit a transaction of the atomic transaction;
decide to either commit or abort the atomic transaction based on the received prepared messages; and
send the decision to either commit or abort the atomic transaction to two or more of the plurality of participants;
receive a prepare message, the prepare message indicating that the participant should commit a transaction of the atomic transaction;
determine whether the participant can commit the transaction;
send a prepared message to the coordinator, the prepared message indicating whether the participant can commit the transaction;
receive decision messages from two or more of the plurality of participants which are different than the coordinator, each decision message indicating that the sending participant has either committed or aborted a transaction of the atomic transaction;
if communication with the coordinator is available, receive the decision to either commit or abort the atomic transaction from the coordinator;
if the decision is received from the coordinator, decide to either commit or abort the transaction based on the received decision;
if communication with the coordinator is not available and the decision was not received from the coordinator, decide to either commit or abort the transaction based on the received decision messages from the two or more of the plurality of participants which are different than the coordinator; and
send the participant's decision to either commit or abort the transaction to each of the other of the plurality of participants with which communication is available.
2. The distributed system of claim 1, wherein the coordinator is further configured to decide to:
commit the atomic transaction if prepared messages have been received from each of the plurality of participants and each received prepared message indicates that the sending participant can commit a transaction of the atomic transaction; and
abort the atomic transaction if at least one prepared message has been received from one of the plurality of participants and the received prepared message indicates that the sending participant cannot commit a transaction of the atomic transaction.
3. The distributed system of claim 1, wherein each of the plurality of participants is further configured to decide to:
commit the transaction if a decision to commit the atomic transaction is received from the coordinator; and
abort the transaction if a decision to abort the atomic transaction is received from the coordinator.
4. The distributed system of claim 2, wherein the coordinator is further configured to abort the transaction if communication between the coordinator and one of the plurality of participants is unavailable.
5. The distributed system of claim 1, wherein each of the plurality of participants is further configured to commit the transaction if all of the received one or more decision messages indicate that the sending participant has committed a transaction of the atomic transaction.
6. The distributed system of claim 1, wherein each of the plurality of participants is further configured to abort the transaction if one of the received one or more decision messages indicate that the sending participant has aborted a transaction of the atomic transaction.
7. The distributed system of claim 1, further comprising a shared participant residing on the same node of the computer system as the coordinator and in communication with each of the plurality of participants, the shared participant configured to:
receive a prepare message from an initiator, the prepare message indicating that the shared participant should commit a transaction of the atomic transaction;
determine whether the shared participant can commit the transaction;
send a prepared message to the coordinator, the prepared message indicating whether the shared participant can commit the transaction;
receive one or more decision messages from one or more of the plurality of participants, each decision message indicating that the sending participant has either committed or aborted a transaction of the atomic transaction; and
decide to either commit or abort the transaction based on the received one or more decision messages.
8. The method of claim 1, wherein each of the plurality of participants is further configured to:
determine that communication with one of the plurality of participants was previously unavailable and has become available; and
send the participant's decision to either commit or abort the transaction to the previously unavailable one of the plurality of participants.
9. The method of claim 8, wherein said determination that communication with one of the plurality of participants was previously unavailable and has become available is based on a message received from said previously unavailable one of the plurality of participants.
10. The method of claim 1, wherein each of the plurality of participants is further configured to:
receive a request message from one or more of the plurality of participants, the request message requesting the participant's decision to either commit or abort the transaction; and
send the participant's decision to either commit or abort the transaction to one or more of the other of the plurality of participant from which a request message was received.
11. A method of resolving an atomic transaction comprising multiple transactions among a plurality of participants, each participant residing on a node of a distributed computer system, the method comprising:
sending, by the one or more computer processors of each of the plurality of participants, a prepared message to a coordinator, the coordinator residing on the same node as at least one of the plurality of participants, the prepared message indicating that the sending participant is prepared to commit a transaction of the atomic transaction;
receiving, by each of a first subset of two or more of the plurality of participants which are different than the coordinator, a decision from the coordinator to either commit or abort the atomic transaction;
determining, by each of a second subset of one or more of the plurality of participants, that communication with the coordinator is not available and that no decision from the coordinator was received;
deciding, by the one or more computer processors of each of the first subset of the plurality of participants, to either commit or abort the transaction;
sending, by the one or more computer processors of two or more of the first subset of the plurality of participants, the decision by the sending participant to either commit or abort the transaction to each of the second subset of the plurality of participants with which communication is available;
receiving, by each of the second subset of the plurality of participants, a decision to either commit or abort the transaction from two or more of the first subset of the plurality of participants; and
deciding, by the one or more computer processors of each of the second subset of the plurality of participants, to either commit or abort the transaction based on the received decisions from the two or more of the first subset of the plurality of participants.
12. The method of claim 11, further comprising receiving, by each of the plurality of participants, a prepare message from an initiator, the prepare message indicating that the receiving participant should prepare for the transaction.
13. The method of claim 11, wherein receiving a decision from the coordinator comprises receiving a commit message from the coordinator node to commit the transaction.
14. The method of claim 11, wherein receiving a decision from the coordinator comprises receiving an abort message from the coordinator node to abort the transaction. Description
The present application claims priority benefit under 35 U.S.C. �119(e) from U.S. Provisional Application No. 60/623,843, filed Oct. 29, 2004 entitled “Non-Blocking Commit Protocol Systems and Methods.” The present application also hereby incorporates by reference herein the foregoing application in its entirety.
The present application relates to U.S. application Ser. No. 11/262,314, titled “Message Batching with Checkpoints Systems and Methods”, filed on Oct. 28, 2005, which claims priority to U.S. Provisional Application No. 60/623,848, filed Oct. 29, 2004 entitled “Message Batching with Checkpoints Systems and Methods,” and U.S. Provisional Application No. 60/628,528, filed Nov. 15, 2004 entitled “Message Batching with Checkpoints Systems and Methods;” and U.S. application Ser. No. 11/262,308, titled “Distributed System with Asynchronous Execution Systems and Methods,” filed on Oct. 28, 2005, which claims priority to U.S. Provisional Application No. 60/623,846, filed Oct. 29, 2004 entitled “Distributed System with Asynchronous Execution Systems and Methods,” and U.S. Provisional Application No. 60/628,527, filed Nov. 15, 2004 entitled “Distributed System with Asynchronous Execution Systems and Methods.” The present application hereby incorporates by reference herein all of the foregoing applications in their entirety.
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.
The systems and methods described herein provide single-failure non-blocking commitment and double-failure non-blocking commitment protocols.
FIG. 1 illustrates an exemplary timing chart of a transaction between an initiator, two participants, a shared participant, and a coordinator using a more-modified two-phase commit protocol.
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.
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.
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 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.
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.
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. 1 illustrates an exemplary timing chart according to one embodiment of a commit protocol 100 for a transaction involving an initiator 110 (shown as “i”), a first participant 112 (shown as “p1”), a second participant 114 (shown as “p2”), a shared participant 116 (shown as “ps”), and a coordinator 118 (shown as “c”). The exemplary shared participant 116 and the coordinator 118 reside on the same node.
The initiator 110 is configured to start the transaction by sending “start” messages (not shown) to the coordinator 118 and the participants p1, p2, ps. In one embodiment, the initiator 110 collects responses to the “start” messages before requesting the participants p1, p2, and ps to commit the transaction. To request commitment to the transaction, the initiator 110 sends “prepare” messages 120 (three shown) to the first participant 112, the second participant 114, and the shared participant 116.
The first participant 112, the second participant 114, and the shared participant 116 each log their respective “prepare” message 120 and each determine whether they are prepared to commit the transaction. If the first participant 112 can commit the transaction, the first participant 112 sends a “prepared” message 122 to the coordinator 118. If the second participant 114 can commit the transaction, the second participant 114 sends a “prepared” message 122 to the coordinator 118. If the shared participant 116 can commit the transaction, the shared participant 116 sends a “prepared” message 122 to the coordinator 118. If the coordinator receives a “prepared” message 122 from the first participant 112, the second participant 114, and the shared participant 116, the coordinator 118 sends “commit” messages 124 (two shown) to the first participant 112 and the second participant 114. The coordinator 118 does not send a “commit” message to the shared participant 116.
After receiving the “commit” messages 124 from the coordinator 118, the first participant 112 and the second participant 114 each log the “commits” and each send “committed” messages 126 (six shown) to each other, to the shared participant 116, and to the initiator 110. For example, the first participant 112 would send a “committed” message 126 to the second participant 114, the shared participant 116, and the initiator 110. Upon receiving a “committed” message 126 from either the first participant 112 or the second participant 114, the shared participant 116 commits the transaction, logs the received “committed” message 126 and sends “committed” messages 128 (three shown) to the initiator 110, the first participant 112, and the second participant 114. The first participant 112, the second participant 114, and the shared participant 116 can then clean their respective logs and the commit protocol 100 ends.
The exemplary timing chart shown in FIG. 1 illustrates the commit protocol 100 when no failures occur. If the coordinator 118 has not disconnected from the first participant 112 or the second participant 114, the coordinator 118 determines whether to commit or abort the transaction. The coordinator 118 commits the transaction when all of the “prepared” messages 122 are received from each of the participants 112, 114, 116.
As discussed in detail below, if the node with the coordinator 118 and the shared participant 116 fails, the first participant 112 and the second participant 114 are still able to resolve the transaction. If the coordinator 118 sent the “commit” messages 124 before failing, the participants p1, p2 112, 114 commit the transaction since they know that the shared participant 116 successfully prepared. However, if the coordinator 118 did not send the “commit” messages 124 before failing, the participants p1, p2 112, 114 abort the transaction since they do not know whether the shared participant 116 successfully prepared. When the shared participant 116 reconnects, the participants p1, P2 112, 114 inform the shared participant 116 of their decision.
So long as at least one of the first participant 112 and the second participant 114 are connected to the coordinator 118, the connected participant can still receive a “commit” or “abort” message from the coordinator 118. To avoid ending up in different states, the first participant 112 and the second participant 114 only decide whether to commit or abort if they have both been disconnected from the coordinator 118. Further, once disconnected from the coordinator 118, the first participant 112 or the second participant 114 no longer accept “commit” or “abort” messages from the coordinator 118. Since the participants 112, 114, 116 do not look to the coordinator 118 after a failure, the coordinator 118 does not log the “prepared” messages 122 received from the participants 112, 114, 116 and does not clean its log at the end of the commit protocol 100.
FIGS. 2 and 3 illustrate 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 ps on 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.
FIG. 2 illustrates 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 px represents any one of the participants in the set P={p1, p2, . . . , pn, ps}. For example, in the MM2PC protocol 100 shown in FIG. 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 ps and the coordinator c are located on the same node, then it may be assumed that the shared participant ps and 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 px to 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 px or the initiator i (for example, aborted (px, i)), or if the coordinator c detects that any of the participants px are 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.
FIG. 3 illustrates a state diagram of any of the participants px during execution of the MM2PC protocol. In the following description of FIG. 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, . . . , pn or the shared participant ps may also be referred to separately. In the MM2PC protocol, the participants in P resolve the transaction if the coordinator c fails. The participant px is 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 ps when the state diagram shown in FIG. 3 corresponds to the participant pn. As another example, if there are three participants, p1, p2, p3 and a shared participant ps, if FIG. 3 corresponds to p1 then p′ may be p2, p3, or ps; if FIG. 3 corresponds to ps then p′ may be p1, p2, or p3.
The state diagram illustrated in FIG. 3 includes 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 px can 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 px has received “prepared” messages. The participant px remains in one of the states of which the variable r is a member until S=P. The participant px then transitions to the final state F. As discussed below, the participant px transitions to the final state F after performing a garbage collection procedure.
The aborted state A and the committed state C are garbage collection states. In these states, the participant px has already committed or aborted the transaction. However, the participant px waits until the other participants in P complete the transaction before clearing its log. If the participant px aborts 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 px has received “aborted” messages. If the participant px commits, 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 px has received “committed” messages.
As mentioned above, the participant px keeps a log that it can use when another participant p′ reconnects or when the participant px restarts after a disconnect or failure. On restart, the participant px no longer accepts messages from the coordinator c. If the last entry in the log was “start,” the participant px did not receive a “prepare” message from the initiator and can abort the transaction. If the last entry in the log was “prepare,” the participant px checks 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 px aborts the transaction. If S≠P\{ps}, the participant px enters 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 px determines whether it has received “aborted” messages from all of the other participants in P (A′=P). If A′≠P, the participant px enters the abort state A. If A′=P, the participant px clears its log and enters the final state F. If the last entry in the log is “commit,” the participant px determines whether it has received “committed” messages from all of the other participants in P (C′=P). If C′≠P, the participant px enters the committed state C. If C′=P, the participant px clears its log and enters the final state F.
function forget( ): clean log set state to F function 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 px does not send the “committed” message to the coordinator c because the coordinator c either told the participant px to 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.
As illustrated in FIG. 3, in the initial state I, the participant px receives a “prepare” message from the initiator i (for example, prepare(i)). If the participant px has an error such that it cannot perform the transaction, the participant px aborts the transaction. The participant px may 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 px receives 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 ps cannot disconnect from the coordinator c since they are on the same node.
If the participant px aborts, 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 px can 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 px may also receive a “prepared” message from another participant (for example, prepared(p′)). As discussed below, if the participant px later 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 px adds the other participant p′ to the subset S (for example, S=S∪{p′}).
In the first prepared state Pc, the participant px expects to receive a “commit” or “abort” message from the coordinator c. As discussed above, in some embodiments, the shared participant ps may ignore commands from the coordinator c. If the participant px receives a “commit” message from the coordinator c (for example, commit(c)), the participant px commits 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 px then enters the committed state C. If the participant px receives an “abort” message from the coordinator c (for example, abort(c)), the participant px aborts 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 px then enters the aborted state A.
While in the first prepared state Pc, the participant px may 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 px adds 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 px aborts 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 px may 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 px adds the other participant p′ to the set of known prepared participants S (for example, S=S∪{p′}). The participant px may also detect a disconnect from the coordinator c (for example, disconnect(c)). As discussed above, the shared participant ps does not disconnect from the coordinator c since it resides on the same node. In determining that the coordinator c is disconnected, the participant px sends a “prepared” message to the other participants in P (for example, prepared(P)) and enters the second prepared state Pp.
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.”
The participant px cannot 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 px does not know whether the shared participant ps successfully prepared. However, if the participant px receives a “committed” message from another participant p′ (for example, committed(p′)), the participant px commits 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 px then 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 px may receive an “aborted” message from another participant p′ (for example, aborted(p′)). In response, the participant px adds 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 px may 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 px adds the other participant p′ to the set of known prepared participants S (for example, S=S∪{p′}). If S=P\{ps}, the participant px aborts the transaction since all of the participants in P except for the shared participant ps have disconnected from the coordinator c but do not know whether the shared participant ps is prepared to commit the transaction.
If another participant p′ connects to the participant px (for example, connect(p′)) while the participant px is in the second prepared state Pp, the participant px sends a “prepared” message to the other participant p′ (for example, prepared(p′)). This informs the other participant p′ of the state of the participant px if, 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 the committed state C, the participant px may receive a “committed” message from another participant p′ (for example, committed(p′)). In response, the participant px adds 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 px clears its log (for example, clean log) and transitions to the final state F.
When the participant px detects the connection or reconnection with another participant p′ (for example, connect(p′)), the participant px notifies the other participant p′ that it is committed to ensure that the earlier “committed” message was not missed. Again, the participant px waits in the committed state C until C′=P. However, if the participant px did 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 px such that it is finished with the transaction, the participant px does 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 px will block as it remains in the completed state C.
To avoid this blocking, the participant px sends 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 px can add the other participant p′ to the variable C′. Likewise, if the participant px receives the committed′(p′) message from another participant p′ while in the committed state C or the final state F, the participant px will respond by sending the committed(p′) message to the other participant p′. In the committed state C, the participant px also adds the other participant p′ to the variable C′.
send committed’ to p′
on committed’ from p′:
As discussed above, the aborted state A is also a garbage collection state wherein the participant px handles information stored in a log during its execution of the MM2PC protocol. In the aborted state A, the participant px may receive an “aborted” message from another participant p′ (for example, aborted(p′)). In response, the participant px adds 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 px clears its log (for example, clean log) and transitions to the final state F.
When the participant px detects the connection or reconnection with another participant p′ (for example, connect(p′)), the participant px notifies the other participant p′ that it has aborted to ensure that the earlier “aborted” message was not missed. Again, the participant px waits in the aborted state A until A′=P. To avoid the blocking problem discussed above in relation to the committed state C, the participant px sends 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 px can add the other participant p′ to the variable A′. Likewise, if the participant px receives the aborted′(p′) message from another participant p′ while in the aborted state A or the final state F, the participant px will respond by sending the aborted(p′) message to the other participant p′. In the aborted state A, the participant px also adds the other participant p′ to the variable A′.
in state (A, A′): on connect to p′: send aborted’ to p′ on aborted from p′: abort_count(A′ ∪ {p′}) on aborted’ from p′: send aborted to p′ abort_count(A′ ∪ {p′}) III. Two-Phase Commit Version 2 Protocol
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. 4 illustrates an exemplary timing chart according to one embodiment of a 2PCV2 commit protocol 400 for a transaction involving an initiator 410 (shown as “i”), a first participant 412 (shown as “p1”), a second participant 414 (shown as “p2”), a shared participant 416 (shown as “ps”) and a coordinator 418 (shown as “c”). As discussed above, the initiator 410 and the coordinator 418 are on the same node. In the example shown in FIG. 4, the shared participant 416 is also on the same node as the initiator 410 and the coordinator 418. The first participant 412 and the second participant 414 are located on remote nodes.
During the transaction, the initiator 410 adds the first participant 412, the second participant 414, and the shared participant 416 to the transaction. As it does so, the initiator 410 sends start messages 419 (three shown) to the first participant 412, the second participant 414, and the shared participant 416. When the initiator 410 is ready to try to commit the transaction, the initiator sends “prepare” messages 420 (four shown) to the coordinator 418, the first participant 412, the second participant 414, and the shared participant 416. In one embodiment, the coordinator 418 is configured to return a response 420 a to the “prepare” message 420. Since the initiator 410 and the coordinator 418 are on the same node, the coordinator 418 receives the “prepare” message 420 before the remote participants 412, 414.
The first participant 412, the second participant 414, and the shared participant 416 respectively log the “prepare” messages 420 and determine whether they are prepared to commit the transaction. If they can commit the transaction, the first participant 412, the second participant 414, and the shared participant 416 each send a “prepared” message 422 (three shown) to the coordinator 418. If the coordinator 418 receives all of the “prepared” messages 422, the coordinator 418 sends “commit” messages 424 (two shown) to the first participant 412 the second participant 414. The coordinator 418 does not send a “commit” message 424 to the shared participant 416.
After receiving the “commit” messages 424 from the coordinator 418, the first participant 412 and the second participant 414 each log their respective “commits” and send “committed” messages 426 to the shared participant 416. Thus, the shared participant 416 learns of the transaction's outcome from the other participants 412, 414. After committing to the transaction, the first participant 412, the second participant 414 and the shared participant 418 send “committed” messages 428 (three shown) to the initiator 410. For garbage collection purposes, the initiator 410 responds by sending “committed” messages 430 to the first participant 412, the second participant 414, and the shared participant 416. After receiving the “committed” message 430 from the initiator 410, the first participant 412, the second participant 414, and the shared participant 416 clear their respective logs and the commit protocol 400 ends.
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.
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.
FIG. 6 is a state diagram illustrating an unknown state U and a prepare state Pj of 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 Pj when 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 ps receives 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.
on disconnect or aborted from p ∈ P:
send aborted to S
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 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.
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 ps is 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.
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 ps of 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 ps are in the second prepared state Pp (for example, S=P\{ps}), the participant p knows that the shared participant ps is 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′).
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.
send committed’ to P \ C′
on committed’ from p′ ∈ P:
set state to (Ci, C′ ∪ {p′}, P)
As discussed above, the transaction may include a shared participant ps. The shared participant ps is 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 ps that the transaction is committed.
FIG. 8 is a state diagram illustrating the states of the shared participant ps according to one embodiment. The shared participant ps operates 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 to FIG. 7. However, since the shared participant ps does not receive a “commit” message from the coordinator c, the shared participant ps does not enter the first prepared state Pc. Rather, when the shared participant ps receives the prepare(i) message from the initiator i, the shared participant ps transitions directly to the second prepared state Pp.
Since the shared participant ps does 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 ps transitions to the first committed state Ci. In the second prepared state Pp, the shared participant ps may 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 ps 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, and transitions to the first committed state Ci.
function abort( ): log abort send aborted to {i, c} set state to U function commit_i(C′, P): log commit send committed to i set state to (Ci, C′, P) function commit_p(C′, P): send committed’ to P \ C′ set state to (Cp, C′, P) in state U: on committed’ from p′: send committed to p′ on prepared from p′: send aborted to p′ on start from i: set state to (I, �) in state (I, S): on local failure: abort( ) on aborted from i: abort( ) on prepared from p′: set state to (I, S ∪ {p′}) on prepare(P) from i: log prepare send prepared to c set state to (Pp, S, P) in state (Pp, S, P): if S = P \ {ps}: abort( ) on connect to p′ ∈ P: send prepared to p′ on aborted from p′ ∈ P: abort( ) on committed from p′ ∈ P: commit_i({p′}, P) on committed’ from p′ ∈ P: commit_i({p′}, P) send committed to p′ on prepared from p′ ∈ P: set state to (Pp, S ∪ {p′}, P) in state (Ci, C′, P): on committed(T) from i: commit_p(C′ ∪ T, P) on committed’ from p′ ∈ P: set state to (Ci ,C′ ∪ {p′}, P) send committed to p′ in state (Cp, C′, P): if C′ = P: log done set state to U on connect to p′ ∈ P: send committed’ to p′ on committed from p′ ∈ P: set state to (Cp, C′ ∪ {p′}, P) on committed’ from p′ ∈ P: set state to (Cp, C′ ∪ {p′}, P) send committed to p′ IV. 2.5-Phase Commit Protocol
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. 9 illustrates an exemplary timing chart according to one embodiment of a 2.5PC protocol 900 for a transaction involving an initiator 910 (shown as “i”), a first participant 912 (shown as “p1”), a second participant 914 (shown as “p2”), a coordinator 916 (shown as “c”), and a distributor 918 (shown as “d”). The coordinator 916 and the distributor 918 are on separate nodes. If the coordinator 916 and the distributor 918 do not share a node with the first participant 912 or the second participant 914, then the commit protocol 900 allows for double-failure non-blocking.
The initiator 910 sends “prepare” messages 920 (two shown) to the first participant 912 and the second participant 914. The first participant 912 and the second participant 914 log their respective “prepare” messages 920 and determine whether they are prepared to commit the transaction. If the first participant 912 can commit the transaction, the first participant 912 sends a “prepared” message 922 to the coordinator 916. If the second participant 914 can commit the transaction, the second participant 914 sends a “prepared” message 922 to the coordinator 916. If the coordinator receives both of the “prepared” messages 922, the coordinator 916 sends a “commit” message 924 to the distributor 918.
If the coordinator 916 and one of the participants 912, 914 were to fail (for example, a double-failure) after the coordinator 916 sends the “commit” message 924, the distributor 918 knows the coordinator's 916 decision and can resolve the transaction. Thus, the protocol 900 is double-failure non-blocking. In response to the “commit” message 924 from the coordinator 916, the distributor 918 sends “commit” messages 926 (three shown) to the first participant 912, the second participant 914, and the coordinator 916.
After receiving the “commit” messages 926 from the distributor 918, the first participant 912 and the second participant 914 respectively log the “commits” and send “committed” messages 928 (six shown) to each other, to the coordinator 916, and to the initiator 910. Upon receiving a “committed” message 928, the first participant 912 and the second participant 914 clear their respective logs and the 2.5PC protocol 900 ends.
If the coordinator 916 fails or disconnects before informing the distributor 918 of its decision, the distributor 918 aborts because it does not know if all the participants 912, 914 prepared successfully. However, the coordinator 916 can also send “abort” or “commit” messages to the participants 912, 914. Therefore, as discussed in detail below, when the coordinator 916 is disconnected from the distributor 918, the participants 912, 914 decide whether to accept “commit” or “abort” messages from the coordinator 916 or the distributor 918. If the participants 912, 914 decide to accept the decision of the distributor 918, the distributor sends an “abort” message to the participants 912, 914.
If the coordinator 916 loses its connection with the distributor 918 before sending the “commit” message 924, the coordinator 916 aborts. Since the distributor also aborts, the coordinator 916 sends “abort” messages to the participants 912, 914 without waiting for the participants to decide whether to accept the decision of the coordinator 916.
If, on the other hand, the coordinator 916 loses its connection to the distributor 918 after sending the “commit” message 924, the coordinator 916 is still committed. However, the coordinator 916 does not know whether the distributor 918 received the “commit” message 924. If the distributor 918 did receive the “commit” message 924, it may have sent the “commit” messages 926 to one or more of the participants 912, 914. If the distributor 918 did not receive the “commit” message 924, the distributor 918 may abort the transaction when the participants 912, 914 decide to accept the distributor's 918 decision. Thus, the coordinator 916 waits for the participants 912, 914 to decide to accept its decision before committing the transaction.
FIG. 10 is 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 Sfor and Sagainst of the participants in P. The variable Sfor includes participants that vote for the coordinator c and the variable Sagainst includes participants that vote for the distributor d.
As illustrated in FIG. 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.
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 Sfor if 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.
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.
set state to (C , �, �)
if |Sfor| > └|P|/2┘:
if |Sagainst| > ┌|P|/2┐:
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.
FIG. 11 is 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 Sfor and adds participants that vote for the coordinator c to the set of participants voting for the coordinator Sagainst.
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.
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 Sfor or 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.
if |Sagainst| < ┌|P|/2┐:
if |Sagainst| ≧ ┌|P|/2┐:
FIGS. 12A-12D are 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.
As illustrated in FIG. 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.
As illustrated in FIG. 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.
As illustrated in FIG. 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.
As illustrated in FIG. 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 in FIG. 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.
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.
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 in FIG. 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.
The participant p ends the transaction in the final state F. As illustrated in FIG. 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′)).
on start: set state to (I, �)
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′.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS5163131Sep 8, 1989Nov 10, 1992Auspex Systems, Inc.Parallel i/o network file server architectureUS5181162Dec 6, 1989Jan 19, 1993Eastman Kodak CompanyDocument management and production systemUS5212784Oct 22, 1990May 18, 1993Delphi Data, A Division Of Sparks Industries, Inc.Automated concurrent data backup systemUS5230047Apr 16, 1990Jul 20, 1993International Business Machines CorporationMethod for balancing of distributed tree file structures in parallel computing systems to enable recovery after a failureUS5251206Apr 12, 1991Oct 5, 1993International Business Machines Corp.Hybrid switching system for a communication nodeUS5258984Jun 13, 1991Nov 2, 1993International Business Machines CorporationMethod and means for distributed sparing in DASD arraysUS5329626 *Oct 23, 1990Jul 12, 1994Digital Equipment CorporationSystem for distributed computation processing includes dynamic assignment of predicates to define interdependenciesUS5359594May 15, 1992Oct 25, 1994International Business Machines CorporationPower-saving full duplex nodal communications systemsUS5403639Sep 2, 1992Apr 4, 1995Storage Technology CorporationFile server having snapshot application data groupsUS5459871Aug 26, 1993Oct 17, 1995International Computers LimitedDetection and resolution of resource deadlocks in a distributed data processing systemUS5481699Mar 23, 1995Jan 2, 1996Digital Equipment CorporationDurable atomic storage update managerUS5548724Mar 21, 1994Aug 20, 1996Hitachi, Ltd.File server system and file access control method of the sameUS5548795Mar 28, 1994Aug 20, 1996Quantum CorporationMethod for determining command execution dependencies within command queue reordering processUS5568629Nov 4, 1993Oct 22, 1996At&T Global Information Solutions CompanyMethod for partitioning disk drives within a physical disk array and selectively assigning disk drive partitions into a logical disk arrayUS5596709Nov 12, 1992Jan 21, 1997International Business Machines CorporationMethod and apparatus for recovering parity protected dataUS5606669May 23, 1995Feb 25, 1997International Business Machines CorporationSystem for managing topology of a network in spanning tree data structure by maintaining link table and parent table in each network nodeUS5612865Jun 1, 1995Mar 18, 1997Ncr CorporationDynamic hashing method for optimal distribution of locks within a clustered systemUS5649200Dec 2, 1996Jul 15, 1997Atria Software, Inc.Dynamic rule-based version control systemUS5657439Nov 3, 1995Aug 12, 1997International Business Machines CorporationDistributed subsystem sparingUS5668943May 24, 1996Sep 16, 1997International Business Machines CorporationVirtual shared disks with application transparent recoveryUS5680621Jun 7, 1995Oct 21, 1997International Business Machines CorporationSystem and method for domained incremental changes storage and retrievalUS5694593Oct 5, 1994Dec 2, 1997Northeastern UniversityDistributed computer database system and methodUS5696895Jun 19, 1995Dec 9, 1997Compaq Computer CorporationFault tolerant multiple network serversUS5734826Sep 17, 1992Mar 31, 1998International Business Machines CorporationVariable cyclic redundancy coding method and apparatus for use in a multistage networkUS5754756Feb 29, 1996May 19, 1998Hitachi, Ltd.Disk array system having adjustable parity group sizes based on storage unit capacitiesUS5761659Feb 29, 1996Jun 2, 1998Sun Microsystems, Inc.Method, product, and structure for flexible range locking of read and write requests using shared and exclusive locks, flags, sub-locks, and countersUS5774643Oct 13, 1995Jun 30, 1998Digital Equipment CorporationEnhanced raid write hole protection and recoveryUS5799305 *Nov 2, 1995Aug 25, 1998Informix Software, Inc.Method of commitment in a distributed database transactionUS5805578Mar 12, 1996Sep 8, 1998International Business Machines CorporationAutomatic reconfiguration of multipoint communication channelsUS5805900Sep 26, 1996Sep 8, 1998International Business Machines CorporationMethod and apparatus for serializing resource access requests in a multisystem complexUS5806065May 6, 1996Sep 8, 1998Microsoft CorporationData system with distributed tree indexes and method for maintaining the indexesUS5822790Feb 7, 1997Oct 13, 1998Sun Microsystems, Inc.Voting data prefetch engineUS5862312Oct 24, 1995Jan 19, 1999Seachange Technology, Inc.Loosely coupled mass storage computer clusterUS5870563Oct 11, 1995Feb 9, 1999International Business Machines CorporationMethod and apparatus for optimizing message transmissionUS5878410Sep 13, 1996Mar 2, 1999Microsoft CorporationFile system sort order indexesUS5878414Jun 6, 1997Mar 2, 1999International Business Machines Corp.Constructing a transaction serialization order based on parallel or distributed database log filesUS5884046Oct 23, 1996Mar 16, 1999Pluris, Inc.Apparatus and method for sharing data and routing messages between a plurality of workstations in a local area networkUS5884098Apr 18, 1996Mar 16, 1999Emc CorporationRAID controller system utilizing front end and back end caching systems including communication path connecting two caching systems and synchronizing allocation of blocks in caching systemsUS5884303Feb 6, 1997Mar 16, 1999International Computers LimitedParallel searching techniqueUS5890147Mar 7, 1997Mar 30, 1999Microsoft CorporationScope testing of documents in a search engine using document to folder mappingUS5917998Jul 26, 1996Jun 29, 1999International Business Machines CorporationMethod and apparatus for establishing and maintaining the status of membership sets used in mirrored read and write input/output without loggingUS5933834Oct 16, 1997Aug 3, 1999International Business Machines IncorporatedSystem and method for re-striping a set of objects onto an exploded array of storage units in a computer systemUS5943690Apr 7, 1997Aug 24, 1999Sony CorporationData storage apparatus and method allocating sets of dataUS5963963Jul 11, 1997Oct 5, 1999International Business Machines CorporationParallel file system and buffer management arbitrationUS5966707Dec 2, 1997Oct 12, 1999International Business Machines CorporationMethod for managing a plurality of data processes residing in heterogeneous data repositoriesUS5996089Dec 16, 1997Nov 30, 1999Seachange International, Inc.Loosely coupled mass storage computer clusterUS6000007May 18, 1998Dec 7, 1999Monolithic System Technology, Inc.Caching in a multi-processor computer systemUS6014669Oct 21, 1997Jan 11, 2000Sun Microsystems, Inc.Highly-available distributed cluster configuration databaseUS6021414Dec 28, 1998Feb 1, 2000Sun Microsystems, Inc.Single transaction technique for a journaling file system of a computer operating systemUS6029168Jan 23, 1998Feb 22, 2000Tricord Systems, Inc.Decentralized file mapping in a striped network file system in a distributed computing environmentUS6038570May 31, 1995Mar 14, 2000Network Appliance, Inc.Method for allocating files in a file system integrated with a RAID disk sub-systemUS6044367Apr 15, 1998Mar 28, 2000Hewlett-Packard CompanyDistributed I/O storeUS6052759Nov 12, 1998Apr 18, 2000Stallmo; David C.Method for organizing storage devices of unequal storage capacity and distributing data using different raid formats depending on size of rectangles containing sets of the storage devicesUS6055543Nov 21, 1997Apr 25, 2000VeranoFile wrapper containing cataloging information for content searching across multiple platformsUS6055564Mar 11, 1998Apr 25, 2000Hewlett Packard CompanyAdmission control where priority indicator is used to discriminate between messagesUS6070172Mar 6, 1997May 30, 2000Oracle CorporationOn-line free space defragmentation of a contiguous-file file systemUS6081833Jul 8, 1996Jun 27, 2000Kabushiki Kaisha ToshibaMemory space management method, data transfer method, and computer device for distributed computer systemUS6081883Dec 5, 1997Jun 27, 2000Auspex Systems, IncorporatedProcessing system with dynamically allocatable buffer memoryUS6108759Sep 17, 1997Aug 22, 2000Powerquest CorporationManipulation of partitions holding advanced file systemsUS6117181Dec 23, 1998Sep 12, 2000Sun Microsystems, Inc.Synchronization mechanism for distributed hardware simulationUS6122754May 22, 1998Sep 19, 2000International Business Machines CorporationMethod and system for data recovery using a distributed and scalable data structureUS6138126Jul 21, 1999Oct 24, 2000Network Appliance, Inc.Method for allocating files in a file system integrated with a raid disk sub-systemUS6154854Jan 8, 1998Nov 28, 2000Emc CorporationLogical partitioning of a redundant array storage systemUS6173374Feb 11, 1998Jan 9, 2001Lsi Logic CorporationSystem and method for peer-to-peer accelerated I/O shipping between host bus adapters in clustered computer networkUS6202085Dec 6, 1996Mar 13, 2001Microsoft CorportionSystem and method for incremental change synchronization between multiple copies of dataUS6209059Sep 25, 1997Mar 27, 2001Emc CorporationMethod and apparatus for the on-line reconfiguration of the logical volumes of a data storage systemUS6219693Nov 4, 1997Apr 17, 2001Adaptec, Inc.File array storage architecture having file system distributed across a data processing platformUS6226377Jun 3, 1998May 1, 2001Avaya Technology Corp.Prioritized transaction server allocationUS6279007Nov 30, 1998Aug 21, 2001Microsoft CorporationArchitecture for managing query friendly hierarchical valuesUS6321345Mar 1, 1999Nov 20, 2001Seachange Systems, Inc.Slow response in redundant arrays of inexpensive disksUS6334168Feb 19, 1999Dec 25, 2001International Business Machines CorporationMethod and system for updating data in a data storage systemUS6353823Mar 8, 1999Mar 5, 2002Intel CorporationMethod and system for using associative metadataUS6384626Apr 18, 2001May 7, 2002Micro-Star Int'l Co., Ltd.Programmable apparatus and method for programming a programmable deviceUS6385626Nov 19, 1998May 7, 2002Emc CorporationMethod and apparatus for identifying changes to a logical object based on changes to the logical object at physical levelUS6393483Jun 30, 1997May 21, 2002Adaptec, Inc.Method and apparatus for network interface card load balancing and port aggregationUS6397311May 22, 1995May 28, 2002Texas Instruments IncorporatedSystem and method for defragmenting a file systemUS6405219Sep 24, 1999Jun 11, 2002F5 Networks, Inc.Method and system for automatically updating the version of a set of files stored on content serversUS6408313Dec 16, 1998Jun 18, 2002Microsoft CorporationDynamic memory allocation based on free memory sizeUS6415259Jul 15, 1999Jul 2, 2002American Management Systems, Inc.Automatic work progress tracking and optimizing engine for a telecommunications customer care and billing systemUS6421781Aug 10, 1998Jul 16, 2002Openwave Systems Inc.Method and apparatus for maintaining security in a push serverUS6434574Dec 17, 1998Aug 13, 2002Apple Computer, Inc.System and method for storing and retrieving filenames and files in computer memory using multiple encodingsUS6449730Apr 5, 2001Sep 10, 2002Seachange Technology, Inc.Loosely coupled mass storage computer clusterUS6453389Jun 25, 1999Sep 17, 2002Hewlett-Packard CompanyOptimizing computer performance by using data compression principles to minimize a loss functionUS6457139Dec 30, 1998Sep 24, 2002Emc CorporationMethod and apparatus for providing a host computer with information relating to the mapping of logical volumes within an intelligent storage systemUS6463442Jun 30, 1998Oct 8, 2002Microsoft CorporationContainer independent data binding systemUS6496842May 28, 1999Dec 17, 2002Survol Interactive TechnologiesNavigating heirarchically organized informationUS6499091Nov 13, 2000Dec 24, 2002Lsi Logic CorporationSystem and method for synchronizing data mirrored by storage subsystemsUS6502172Jan 11, 2002Dec 31, 2002Via Technologies, Inc.Memory accessing and controlling unitUS6502174Mar 3, 1999Dec 31, 2002International Business Machines CorporationMethod and system for managing meta dataUS6523130Mar 11, 1999Feb 18, 2003Microsoft CorporationStorage system having error detection and recoveryUS6526478Feb 2, 2000Feb 25, 2003Lsi Logic CorporationRaid LUN creation using proportional disk mappingUS6546443Dec 15, 1999Apr 8, 2003Microsoft CorporationConcurrency-safe reader-writer lock with time out supportUS6549513Oct 12, 1999Apr 15, 2003AlcatelMethod and apparatus for fast distributed restoration of a communication networkUS6557114Sep 18, 2001Apr 29, 2003Seachange Technology, Inc.Loosely coupled mass storage computer clusterUS6567894Dec 8, 1999May 20, 2003International Business Machines CorporationMethod and apparatus to prefetch sequential pages in a multi-stream environmentUS6567926Nov 7, 2001May 20, 2003Seachange International, Inc.Loosely coupled mass storage computer clusterUS6571244Oct 28, 1999May 27, 2003Microsoft CorporationRun formation in large scale sorting using batched replacement selectionUS6571349Oct 5, 1999May 27, 2003Seachange Technology, Inc.Loosely coupled mass storage computer clusterUS6574745Apr 30, 2002Jun 3, 2003Seachange International, Inc.Loosely coupled mass storage computer clusterUS6594655Jan 4, 2001Jul 15, 2003Ezchip Technologies Ltd.Wildcards in radix- search tree structuresUS6594660Jan 24, 2000Jul 15, 2003Microsoft CorporationShare latch clearingUS6671686 *Nov 2, 2001Dec 30, 2003Guy PardonDecentralized, distributed internet data managementUS20010056492 *Jan 17, 2001Dec 27, 2001Bressoud Thomas C.Method, apparatus and system for maintaining connections between computers using connection-oriented protocolsUS20020083078 *Nov 2, 2001Jun 27, 2002Guy PardonDecentralized, distributed internet data managementUS20040024731 *Aug 5, 2002Feb 5, 2004Microsoft CorporationCoordinating transactional web services* Cited by examinerNon-Patent CitationsReference1 *"Analysis of Transaction Management Performance," by Dan Duchamp (1989).2 *"Porting OMTTs to CORBA," by Raul Silaghi et al. (2003).3Apr. 13, 2009 Response to Jan. 13, 2009 Non-Final Rejection in U.S. Appl. No. 11/449,153, filed Oct. 28, 2005.4Apr. 15, 2011 Office Action in U.S. Appl. No. 11/449,153 dated Apr. 15, 2011.5Apr. 20, 2004 International Search Report PCT/US03/36699.6Arthur S. Rose, Letter to Steven M. Bauer, Aug. 31, 2007.7Arthur S. Rose, Letter to Steven M. Bauer, Aug. 7, 2006.8Arthur S. Rose, Letter to Steven M. Bauer, Feb. 23, 2007.9Arthur S. Rose, Letter to Steven M. Bauer, Jun. 22, 2007.10Arthur S. Rose, Letter to Steven M. Bauer, Nov. 9, 2006.11Aug. 19, 2010 Final Office Action in U.S. Appl. No. 11/449,153, filed Jun. 8, 2006.12Aug. 6, 2004 International Search Report PCT/US03/33704.13Birk, Y., Deterministic load-balancing schemes for disk-based video-on-demand storage servers, Mass Storage Systems 1995; Storage-At the Forefront of Information Infrastructures', Proceedings of the Fourteenth IEEE Symposium on Monterey, CA, Sep. 11-14, 1995, pp. 17-25.14Birk, Y., Deterministic load-balancing schemes for disk-based video-on-demand storage servers, Mass Storage Systems 1995; Storage—At the Forefront of Information Infrastructures', Proceedings of the Fourteenth IEEE Symposium on Monterey, CA, Sep. 11-14, 1995, pp. 17-25.15Bob Duzett, et al., An Overview of the nCube 3 Supercomputer, IEEE, Jul. 1992, pp. 458-464.16Byteandswitch, "Discovery Chooses Isilon," Apr. 23, 2007, 1 (Exhibit C).17Coulouris et al., Distributed Systems Concepts and Design, Addison-Wesley, Second Edition, 1994, pp. 353-371 and 377-405.18Darrell D.E. Long et al., Swift/RAID: A Distributed RAID System, Computing Systems, vol. 7, No. 3 Summer 1994, pp. 333-359.19Dorai et al.:, "Transport Threads: Resource Sharing in SMT Processor for High Single-Thread Performance", proceedings of the 2002 International Conference on Parallel Architectures and Complication Techniques, Sep. 2002, 12 pages.20European Search Report dated May 21, 2007 issued to EP application No. 02756944.1-2201.21Feb. 22, 2008 International Search Report PCT/US07/018326.22Garcia-Molina H et al: "Database System Implementation, passage" Database System Implementation, Jan. 1, 2000, pp. I-V, 423-509.23Gerhard Weikum, et al., Transactional Information Systems: Theory, Algorithms, and the Practice of Concurrency Control and Recovery, Morgan Kaufmann, 2002, pp. 1-450.24Gerhard Weikum, et al., Transactional Information Systems: Theory, Algorithms, and the Practice of Concurrency Control and Recovery, Morgan Kaufmann, 2002, pp. 451-863.25Gibson, Garth A. et al., The Scotch Parallel Storage System, IEEE, 1995, pp. 403-410.26Gray J et al: "Transaction processing: concepts and techniques (excerpt), Passage" Transaction Processing: Concepts and Techniques, Jan. 1, 1993, pp. 373-445.27Haerder T et al: "Principles of Transaction-Oriented Database Recovery" ACM Computing Surveys, ACM, New York, NY, US, vol. 15, No. 4, Dec. 1, 1983, pp. 287-317.28Hisayuki Aoki, Parallel Filesystem MFS, IPSJ SIG Technical Reports, Japan, Information Processing Society of Japan, Aug. 26, 1996, vol. 96, No. 79, pp. 31 to 36 (stamped Citation 1 / English Translation attached) total 23 pages.29 *Increasing the Resilience of Distributed and Replicated Database Systems, Keidar et al. (1998).30IOS Commands, Feb. 6, 2005, Pantz.org, [online], , pp. 1-12 as printed.31IOS Commands, Feb. 6, 2005, Pantz.org, [online], <web.archive.org/web/20050206184604/http://pantz.org/os/ios/ioscommands.shtml>, pp. 1-12 as printed.32IP Forwarding with Cisco Routers Lab Exercises, Jun. 15, 1999 [online], , pp. 1-11 as printed.33IP Forwarding with Cisco Routers Lab Exercises, Jun. 15, 1999 [online], <ws.edu.isoc.org/data1999/1481713642400af6a2de65a/ip—fwd—cisco—config.ppt>, pp. 1-11 as printed.34Isilon Systems, "Isilon IQ Platform Overview", 1-4 (Exhibit A).35Isilon Systems, "Uncompromising Reliability through Clustered Storage", Sep. 2006, 1-10 (Exhibit B).36Jan. 13, 2009 Non-Final Rejection in U.S. Appl. No. 11/449,153, filed Oct. 28, 2005.37Jan. 23, 2009 Examination Report EP 02 75 6944, 5 pages.38Jan. 6, 2010 Office Action in U.S. Appl. No. 11/449,153, filed Jun. 8, 2006.39Jim Gray and Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufmann, 1993, pp. 1-328.40Jim Gray and Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufmann, 1993, pp. 329-664.41Jim Gray and Andreas Reuter, Transaction Processing: Concepts and Techniques, Morgan Kaufmann, 1993, pp. 665-1105.42John Henry Hartman, The Zebra Striped Network File System, 1994, pp. 1-148, University of California at Berkeley.43Jul. 27, 2009 Final Office Action in U.S. Appl. No. 11/449,153, filed Jun. 8, 2006.44Keidar, et al.: Increasing the Resilience of Distributed and Replicated Database Systems (1998) pp. 1-25.45Kenneth P. Birman, Building Secure and Reliable Network Applications, Manning, 1996, pp. 1-327.46Kenneth P. Birman, Building Secure and Reliable Network Applications, Manning, 1996, pp. 328-620.47Kumar Akhil, "An analysis of borrowing policies for escrow transactions in a replicated data environment", Institute of Electrical and Electronics Engineers; Proceedings of the International Conference on Data Engineering, Los Angeles, Feb. 5-9, 1990; Los Alamitos, IEEE, Comp. Soc. Press, US. vol. Conf. 6, Feb. 5, 1990, pp. 446-454, XP010018185 ISBN: 978-0-8186-2025-6 p. 446, left-hand column, line 1-p. 447, last line.48Kumar Akhil, "An analysis of borrowing policies for escrow transactions in a replicated data environment", Institute of Electrical and Electronics Engineers; Proceedings of the International Conference on Data Engineering, Los Angeles, Feb. 5-9, 1990; Los Alamitos, IEEE, Comp. Soc. Press, US. vol. Conf. 6, Feb. 5, 1990, pp. 446-454, XP010018185 ISBN: 978-0-8186-2025-6 p. 446, left-hand column, line 1—p. 447, last line.49Levy E., Ed.-Institute of Electrical and Electronics Engineers: "Incremental restart (database management)" Proc. Int. Conf. Data Eng., Kobe, JP, Apr. 8-12, 1991; IEEE Comp. Soc. Press, U.S., vol. Conf. 7, Apr. 8, 1991, pp. 640-648.50Levy E., Ed.—Institute of Electrical and Electronics Engineers: "Incremental restart (database management)" Proc. Int. Conf. Data Eng., Kobe, JP, Apr. 8-12, 1991; IEEE Comp. Soc. Press, U.S., vol. Conf. 7, Apr. 8, 1991, pp. 640-648.51Lougher P. et al., "Scalable storage servers for digital audio and video," International Conference on Storage and Recording Systems, 1994, Keele, UK, Jan. 1, 1994, pp. 140-143.52May 18, 2009 Int'l Search report PCT/US08/059798, 18 pages.53May 8, 2008 Int'l Search report PCT/US07/018324, 13 pages.54MCSA/MSCE/MCDBA Self Paced Training Kit: MS SQL Server 2000 System Administration, May 14, 2003, Microsoft Press, Second Edition, 12 pages.55Michael Stonebraker et al., Distributed Raid: A new Multiple copy Algorithm, IEEE 1990, pp. 430-437, Berkeley, California.56Nancy A. Lynch, Distributed Algorithms, Morgan Kaufmann, 1996, pp. 1-409.57Nancy A. Lynch, Distributed Algorithms, Morgan Kaufmann, 1996, pp. 410-871.58Nov. 15, 2002 International Search Report PCT/US02/24728.59Oct. 22, 2009 Int'l Preliminary Report on Patentability PCT/US08/059798, 10 pages.60Oct. 27, 2009 Response to Jul. 27, 2009 Final Rejection in U.S. Appl. No. 11/449,153, filed Jun. 8, 2006.61Oct. 8, 2008 European Supplemental Search Report EP 02 75 6944, 6 pages.62Pei Cao et al., The TickerTAIP parallel RAID architecture, 1993, 12 pages, Princeton, NJ.63Pei Cao et al., The TickerTAIP parallel RAID architecture, ACM Transactions on Computer Systems, vol. 12, No. 3, Aug. 1994, 34 pages, Palto Alto, California.64Peterson, Zachary Nathaniel Joseph, "Data Placement for Copy-On-Write Using Virtual Contiguity," Master of Science in Computer Science Thesis, University of California, Santa Cruz, Sep. 2002, 67 pages.65Philip A. Bernstein, Vassos Hadzilacos, and Nathan Goodman, Concurrency Control and Recovery in Database Systems, Addison-Wesley, 1987.66Ramez Elmasri, Fundamentals of Database Systems 3rd ed, Sep. 30, 1999, Addison-Wesley, pp. 155, 169, 171, 172, 173, 178, 181, 182, 381, 771.67Reddy, P. Krishna et al., Reducing the blocking in two phase commit with backup sites Apr. 15, 2003, Elsevier, pp. 39-47.68Sanjay Ghemawat et al., The Google File System, Symposium on Operating Systems Principles, Oct. 19-22, 2003, 15 pages, Bolton Landing, NY.69Sape Mullender, editor, Distributed Systems (2nd Ed.), ACM Press/Addison-Wesley Publishing Co., New York, NY, USA, 1993, pp. 1-327.70Sape Mullender, editor, Distributed Systems (2nd Ed.), ACM Press/Addison-Wesley Publishing Co., New York, NY, USA, 1993, pp. 328-604.71Stallings, William, "Operating Systems," Prentice Hall, Fourth Edition, 2001, pp. 197-253 and 265-293.72Steven M. Bauer, Letter to Arthur S. Rose, Feb. 6, 2007.73Steven M. Bauer, Letter to Arthur S. Rose, Jun. 7, 2007 (including claim chart).74Steven M. Bauer, Letter to Arthur S. Rose, Oct. 31, 2006.75Steven M. Bauer, Letter to Arthur S. Rose, Sep. 25, 2006.76Steven M. Bauer, Letter to Steve Goldman, Jul. 31, 2006 (including the first page of the patents), 8 pages.77Steven M. Bauer, Letter to Steve Goldman, Jul. 31, 2006 (including the first pages of the patents).78Supp EPO Search Report, App. No. EP 03 78 3599; dated Apr. 29, 2008, 2 pages.79Taneja Group Technology Analysts, "The Power of InfiniBand and Clustered Storage", Dec. 2005, 1-8 (Exhibit E).80Tanenbaum, Andrew S., MINIX Operating System, Japan, Apr. 21, 1989, 1st Edition, pp. 328, 505; Also attached is what Applicant believes is the English language version: Tanenbaum, Andrew S., Operating Systems: Design and Implementation, Prentice-Hall, 1987, pp. 279, 347, 348.81Todd A. Gerety, Letter to Arthur S. Rose, Jun. 26, 2007 (including exhibits listed separately).82United States Court of Appeals, Federal Circuit, Seachange International, Inc. Vs. C-Cor, Inc., Jun. 29, 2005, 22 pages.83United States Court of Appeals, Federal Circuit, Seachange International, Inc. Vs. nCUBE, Corp., Oct. 26, 2004, 28 pages.84United States District Court, Delaware, Seachange International, Inc. Vs. nCUBE, Corp., Apr. 7, 2004, 13 pages.85United States District Court, Delaware, Seachange International, Inc. Vs. nCUBE, Corp., Aug. 29, 2000, 12 pages.86Wedde H. F., et al.: "A universal framework for managing metadata in the distributed Dragon Slayer System", Proceedings of the Euromicro Conference. Euromicro. Informatics: Inventing the Future, Proceedings of Euromicro Workshop on Multimedia and Telecommunications, vol. 2, Sep. 5, 2000, pp. 96-101.87Yamashita, Hirofumi, et al., "Development of RAID Filesystem VAFS/HR," The Special Interest Group Notes of IPSJ, Japan, Information Processing Society of Japan, Sep. 16, 1994, vol. 94, No. 80, p. 9-16.88Yoshitake Shinkai, Cluster File System: HAMFS, Fujitsu, Japan, Fujitsu Limited, Jul. 9, 1999, vol. 50, No. 4, pp. 210 to 214 (stamped Citation 2 / English Translation attached) total 16 pages.* Cited by examinerReferenced byCiting PatentFiling datePublication dateApplicantTitleUS8200836 *Sep 29, 2008Jun 12, 2012Microsoft CorporationDurable exactly once message delivery at scaleUS8214847Jun 27, 2008Jul 3, 2012Microsoft CorporationDistributed messaging system with configurable assurancesUS8862642Jun 29, 2012Oct 14, 2014Emc CorporationEndurant cacheUS20090133039 *Sep 29, 2008May 21, 2009Microsoft CorporationDurable exactly once message delivery at scaleUS20140337303 *May 7, 2013Nov 13, 2014Red Hat, IncBandwidth optimized two-phase commit protocol for distributed transactions* Cited by examinerClassifications U.S. Classification709/205, 709/237, 709/230International ClassificationG06F15/16Cooperative ClassificationG06F17/30227European ClassificationG06F17/30CLegal EventsDateCodeEventDescriptionJan 19, 2006ASAssignmentOwner name: ISILON SYSTEMS, INC., WASHINGTONFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:FACHAN, NEAL T.;GODMAN, PETER J.;PASSEY, AARON J.;REEL/FRAME:017472/0666Effective date: 20060103Mar 31, 2011ASAssignmentEffective date: 20101229Free format text: MERGER;ASSIGNOR:ISILON SYSTEMS, INC.;REEL/FRAME:026066/0785Owner name: ISILON SYSTEMS LLC, WASHINGTONApr 4, 2011ASAssignmentOwner name: IVY HOLDING, INC., MASSACHUSETTSEffective date: 20101229Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:ISILON SYSTEMS LLC;REEL/FRAME:026069/0925Apr 6, 2011ASAssignmentFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:IVY HOLDING, INC.;REEL/FRAME:026083/0036Effective date: 20101231Owner name: EMC CORPORATION, MASSACHUSETTSRotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services