Maintaining consistency within a federation infrastructure

Abstract

The present invention extends to methods, systems, and computer program products for a joining node to join a ring of nodes within a rendezvous federation. Embodiments of the invention include establishing a neighborhood of multiple nodes on the ring of nodes. The joining node indicates its intent to take id-space ownership for a portion of the id-space between the joining node and a selected immediately adjacent node. The joining node initiates a one-way monitoring relationship with the selected immediately adjacent node. The joining node receiving an indication from the selected immediately adjacent node that indicates acceptance of the joining node's intent to take id-space ownership for a portion of the id-space between the joining node and the selected node and indicates establishment of a one-way monitoring relationship between the selected node and the joining node. The joining node agrees to participate in a one-way monitoring relationship with the selected node.

1 . In a federation infrastructure of a ring of nodes configured for bi-directional routing, a method for maintaining ring consistency when a joining node joins the ring of nodes, the method comprising:
 an act of a joining node establishing a neighborhood of a plurality of other nodes on the ring, the neighborhood including at least an immediately adjacent predecessor node and an immediately adjacent successor node;   an act of the joining node indicating to one of the immediately adjacent nodes selected from among the immediately adjacent predecessor node and an immediately adjacent successor node, the intent of the joining node to take id-space ownership for a portion of the id-space between the joining node and the selected immediately adjacent node;   an act of the joining node initiating a one-way monitoring relationship with the selected immediately adjacent node;   an act of the joining node receiving an indication from the selected immediately adjacent node that:
 indicates acceptance of the joining node's intent to take id-space ownership for a portion of the id-space between the joining node and the selected immediately adjacent node; and 
 indicates establishment of a one-way monitoring relationship between the selected immediately adjacent node and the joining node; and 
   an act of the joining node agreeing to participate in a one-way monitoring relationship with the selected immediately adjacent node.   
     
     
         2 . The method of  claim 1 , further comprising:
 an act of the joining node receiving an indication from the other immediately adjacent node that:
 indicates id-space ownership for the portion of id-space between the joining node and the other immediately adjacent node; and 
 indicates establishment of a one-way monitoring relationship between the other immediately adjacent node and the joining node; 
   an act of the joining node indicating to the other immediately adjacent node the intent of the joining node to establish id-space ownership for a portion of the id-space between the joining node and the other immediately adjacent node;   an act of the joining node initiating a one-way monitoring relationship with the other immediately adjacent node; and   an act of the joining node receiving an indication from the other immediately adjacent node indicating establishment of a one-way monitoring relationship between the other immediately adjacent node and the joining node.   
     
     
         3 . The method of  claim 1 , wherein the act of the joining node indicating to one of the immediately adjacent nodes selected from among the immediately adjacent predecessor node and an immediately adjacent successor node, the intent of the joining node to take id-space ownership for a portion of the id-space between the joining node and the selected immediately adjacent node comprises an act of sending a token request to a selected immediately adjacent node from among the immediately adjacent predecessor node and an immediately adjacent successor node, the token request including:
 a node identifier such that only the node with the node identifier is capable of replying; and   a first time-to-live duration value, the first time-to-live duration value indicative of a duration for which the joining node can assume a monitoring relationship with the selected immediately adjacent node is active.   
     
     
         4 . The method of  claim 3 , wherein the act of the joining node receiving an indication from the selected immediately adjacent node that indicates acceptance of the joining node's intent to take id-space ownership for a portion of the id-space between the joining node and the selected immediately adjacent node and indicates establishment of a one-way monitoring relationship between the selected immediately adjacent node and the joining node comprises an act of receiving a first token transfer from the selected immediately adjacent node, the first token transfer including:
 the joining node's ownership range of unoccupied node identifiers in the ring of nodes between the joining node and the selected immediately adjacent node;   a second time-to-live duration value, the second time-to-live duration value indicative of a duration for which the selected immediately adjacent node can assume a monitoring relationship with the joining node is active; and   a first establish grant indicative of the selected immediately adjacent node monitoring the joining node.   
     
     
         5 . The method of  claim 4 , wherein the act of the joining node agreeing to participate in a one-way monitoring relationship with the selected immediately adjacent node comprises an act of sending an acknowledgement message to the selected immediately adjacent node, the acknowledgement message including:
 a first ownership range between the joining node and the selected immediately adjacent node; and   a second establish grant indicative of the joining node monitoring the selected immediately adjacent node.   
     
     
         6 . The method of  claim 2 , wherein the act of the joining node receiving an indication from the other immediately adjacent node that indicates id-space ownership for the portion of id-space between the joining node and the other immediately adjacent node indicates establishment of a one-way monitoring relationship between the other immediately adjacent node and the joining node comprises an act of receiving a second token transfer from the other immediately adjacent node, the second token transfer including:
 the joining node's ownership range of unoccupied node identifiers between the joining node and the other immediately adjacent node; and   a third time-to-live duration value, the third time-to-live duration value indicative of a duration for which the other immediately adjacent node can assume a monitoring relationship with the joining node is active.   
     
     
         7 . The method of  claim 6 , wherein the act of act of the joining node indicating to the other immediately adjacent node the intent of the joining node to establish id-space ownership for a portion of the id-space between the joining node and the other immediately adjacent node comprises an act of sending an establishment request to establish a second ownership range between the joining node and the other immediately adjacent node, the establishment request including:
 a second ownership range between the joining node and the other immediately adjacent node;   a fourth time-to-live duration, the fourth time-to-live duration indicative of a duration for which the joining node can assume a monitoring relationship with the other immediately adjacent node is active; and   a third establish grant indicative of the joining node monitoring the other immediately adjacent node.   
     
     
         8 . The method of  claim 7 , wherein the act of the joining node receiving an indication from the other immediately adjacent node indicating establishment of a one-way monitoring relationship between the other immediately adjacent node and the joining node comprises an act of receiving a fourth establish grant for the establishment request, the fourth establish grant indicative of the other adjacent node monitoring the joining node. 
     
     
         9 . The method of  claim 8 , wherein the token request message includes a marker indicating an updated status of the joining node's expected ownership range. 
     
     
         10 . The method of  claim 1 , further comprising:
 an act of the joining node receiving a negative acknowledge (NAK) message from at least one of the nodes on the ring, the NAK message including an indication of the NAK sender's view of the neighborhood; and   an act of updating the joining node's view of the neighborhood based on the NAK sender's view of the neighborhood.   
     
     
         11 . In a federation infrastructure of a ring of nodes configured for bi-directional routing, the ring of nodes including a first selected immediately adjacent node and a second selected immediately adjacent node, a method for maintaining ring consistency when a joining node joins the ring of nodes between the first and second immediately adjacent nodes, the method comprising:
 an act of a first selected immediately adjacent node receiving an indication from the joining node indicating the intent of the joining node to take id-space ownership for a portion of the id-space between the joining node and the first selected immediately adjacent node;   an act of the first selected immediately adjacent node receiving an indication from the joining node of the joining node's intent to initiate a one-way monitoring relationship with the selected immediately adjacent node;   an act of the first selected immediately adjacent node sending an indication to the joining node that:
 indicates acceptance of the joining node's intent to take id-space ownership for a portion of the id-space between the joining node and the first selected immediately adjacent node; and 
 indicates establishment of a one-way monitoring relationship between the first selected immediately adjacent node and the joining node; and 
   an act of the first selected immediately adjacent node receiving an agreement from joining node agreeing to participate in a one-way monitoring relationship with the selected immediately adjacent node.   
     
     
         12 . The method of  claim 11 , further comprising:
 an act of the first selected immediately adjacent node indicating to a second selected immediately adjacent node the first node's intent to terminate any monitoring relationships with the second selected immediately adjacent node;   an act of the first selected immediately adjacent node receiving an indication from the second selected immediately adjacent node indicating the second node's intent to terminate any monitoring relationships with the first selected immediately adjacent node; and   an act of the first selected immediately adjacent node acknowledging the second node's intent to terminate.   
     
     
         13 . The method of  claim 11 , further comprising:
 an act of receiving an introduction message from the joining node, the introduction message including an expected ownership range of node identifiers indicated as being owned by the joining node; and   an act of sending an acknowledgment message to the joining node, the acknowledgement message including an indication that the range of node identifiers identified by the joining node is consistent with the selected immediately adjacent node's range of node identifiers.   
     
     
         14 . In a federation infrastructure of a ring of nodes configured for bi-directional routing, the ring of nodes including a first selected immediately adjacent node and a second selected immediately adjacent node, a method for maintaining ring consistency when a joining node joins the ring of nodes between the first and second immediately adjacent nodes, the method comprising:
 an act of a first selected immediately adjacent node, selected from among the immediately adjacent predecessor node and an immediately adjacent successor node, indicating to the joining node:
 id-space ownership for the portion of id-space between the joining node and the first selected immediately adjacent node; and 
 establishment of a one-way monitoring relationship between the first selected immediately adjacent node and the joining node; 
   an act of the first selected immediately adjacent node receiving an indication of the joining node's intent to establish id-space ownership for a portion of the id-space between the joining node and the first selected immediately adjacent node;   an act of the first selected immediately adjacent node receiving an indication of the joining node's intent to initiate a one-way monitoring relationship with the first selected immediately adjacent node; and   an act of the first selected immediately adjacent node indicating to the joining node the first selected node's intent to establish a one-way monitoring relationship between the first selected node and the joining node.   
     
     
         15 . The method of  claim 14 , further comprising:
 an act of the first selected immediately adjacent node receiving an indication from a second selected immediately adjacent node indicating the second node's intent to terminate any monitoring relationships with the first selected immediately adjacent node;   an act of the first selected immediately adjacent node indicating to the second selected immediately adjacent node the first node's intent to terminate any monitoring relationships with the second selected immediately adjacent node; and   an act of the first selected immediately adjacent node receiving an acknowledgment acknowledging the first node's intent to terminate.   
     
     
         16 . The method of  claim 15 , further comprising an act of the first selected immediately adjacent node acknowledging the indication from the second selected immediately adjacent node. 
     
     
         16 . In a federation infrastructure of a ring of nodes configured for bi-directional routing, the ring of nodes including a leaving node, a first selected immediately adjacent node, and a second selected immediately adjacent node, the first and second nodes being immediately adjacent to and the leaving node on the ring, a method for maintaining ring consistency when the leaving node leaves the ring of nodes, the method comprising:
 an act of the first selected immediately adjacent node receiving an indication from the leaving node indicating the leaving node's intent to leave the ring of nodes;   an act of the first selected immediately adjacent node sending an indication to the second selected immediately adjacent node that:
 indicates acceptance of the leaving node's intent to leave id-space ownership for a portion of the id-space between the leaving node and the first selected immediately adjacent node; and 
 indicates establishment of a one-way monitoring relationship between the first selected immediately adjacent node and the second selected immediately adjacent node; and 
   an act of the first selected immediately adjacent node receiving an indication from the second selected immediately adjacent node that:
 indicates acceptance of the first node's intent to assume id-space ownership for a portion of the id-space between the leaving node and the first selected immediately adjacent node; and 
 indicates establishment of a one-way monitoring relationship between the second selected immediately adjacent node and the first selected immediately adjacent node. 
   
     
     
         18 . The method of claim  17 , wherein the act of the first selected immediately adjacent node receiving an indication from the leaving node indicating the leaving node's intent to leave the ring of nodes comprises the first selected immediately adjacent node receiving a departure message from the leaving node, the departure message including an ownership range of node identifiers indicated as being owned by the leaving node. 
     
     
         19 . The method of  claim 18 , wherein the act of the first selected immediately adjacent node sending an indication to the second selected immediately adjacent node that indicates acceptance of the leaving node's intent to leave id-space ownership for a portion of the id-space between the leaving node and the first selected immediately adjacent node indicates establishment of a one-way monitoring relationship between the first selected immediately adjacent node and the second selected immediately adjacent node comprises:
 an act of the first selected immediately adjacent node sending a first establishment request the second selected immediately adjacent node to establish an ownership range between the first selected immediately adjacent node and the second selected immediately adjacent node, the first establishment request including a first time-to-live duration, the first time-to-live duration indicative of a duration for which the first selected immediately adjacent node can assume a monitoring relationship with the second selected immediately adjacent node is active; and   an act of the first adjacent node receiving a first establish grant for the first establishment request, the first establish grant indicative of the second adjacent node monitoring the first selected immediately adjacent node.   
     
     
         20 . The method of  claim 19 , wherein the act of an act of the first selected immediately adjacent node receiving an indication from the second selected immediately adjacent node that indicates acceptance of the first node's intent to assume id-space ownership for a portion of the id-space between the leaving node and the first selected immediately adjacent node and indicates establishment of a one-way monitoring relationship between the second selected immediately adjacent node and the first selected immediately adjacent node comprises:
 an act of the first adjacent node receiving a second establishment request from the second adjacent node to establish an ownership range between the first adjacent node and the second adjacent node, the second establishment request including a second time-to-live duration, the second time-to-live duration indicative of a duration for which the second adjacent node can assume a monitoring relationship with the first adjacent node is active; and   an act of the first adjacent node sending a second establish grant for the second establishment request, the second establish grant indicative of the first adjacent node monitoring the second adjacent node.