Chaperones in a distributed system

• US 7,613,774 B1
• Filed: 03/01/2005
• Issued: 11/03/2009
• Est. Priority Date: 03/01/2005
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Caronni, Germano, Scott, Glenn Carter, Rom, Raphael J.
• Primary Examiner(s): STRANGE, AARON N
• Application Number:
  US11/069,804
• Time in Patent Office: 1,708 Days
• Field of Search: 709/205, 709/224, 726/17
• US Class Current: 709/205
• CPC Class Codes: H04L 67/10 in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks
• CPC Class Codes: H04L 67/1065 Discovery involving distributed pre-established resource-based relationships among peers, e.g. based on distributed hash tables [DHT] pre-configuration of logical or physical connections H04L67/1053
• CPC Class Codes: H04L 67/1093 Some peer nodes performing special functions

Abstract

A method for approving a response or a decision of an observed node in a distributed system that includes generating at least one selected from the group consisting of the response and the decision by the observed node, forwarding the at least one selected from the group consisting of the response and the decision to at least one of the plurality of chaperones associated with the observed node based on a chaperone scheme, and approving the least one selected from the group consisting of the response and the decision by the plurality of chaperones using a chaperone voting policy and a chaperone approval policy to obtain at least one selected from the group consisting of a approved response and a approved decision, wherein the distributed system implements an overlay network for message delivery, and wherein the observed node and the plurality of chaperones communicate using the overlay network.

Claims

1. A method for approving a response or a decision of an observed node in a distributed system, comprising:

generating the response to a request from a target node by the observed node;

forwarding the response from the observed node to at least one of a plurality of chaperone nodes associated with the observed node based on a chaperone scheme, wherein the chaperone scheme comprises a per-observed node scheme; and

approving the response by the plurality of chaperone nodes using a chaperone voting policy and a chaperone approval policy to obtain an approved response,

forwarding the approved response to the target node;

wherein the distributed system implements an overlay network for message delivery,

wherein the observed node and the plurality of chaperone nodes communicate using the overlay network, and

wherein the per-observed node scheme comprises selecting the at least one of the plurality of chaperone nodes associated with the observed node using a global unique identifier (GUID) assigned to the observed node.

2. The method of claim 1, wherein the approved response is forwarded to the target node by at least one of the plurality of chaperone nodes.

3. The method of claim 1, wherein the at least one of the plurality of chaperone nodes associated with the observed node are determined by applying a hash function to the GUID a plurality of times to obtain a plurality of GUIDs, wherein each of the plurality of GUIDs is associated with one of the plurality of chaperone nodes.

4. The method of claim 1, wherein functionality necessary to implement at least one selected from the group consisting of the chaperone voting policy, the chaperone approval policy, and the chaperone selection policy is loaded onto all nodes in the distributed system.

5. The method of claim 1, wherein each of the plurality of chaperone nodes comprises at least one selected from the group consisting of knowledge of at least one other of the plurality of chaperone nodes and functionality to locate at least one other of the plurality of chaperone nodes.

6. The method of claim 1, wherein each of the plurality of chaperone nodes comprises authentication material, wherein the authentication material is used to generate the approved response.

7. The method of claim 1, wherein the chaperone approval scheme specifies:

generating an independent response by each of the plurality of chaperone nodes;

agreeing on a value for the independent response using the plurality of independent responses and the chaperone voting policy to obtain an agreed value; and

providing the approved response to the observed node, wherein the approved response comprises the agreed value.

8. The method of claim 7, wherein the independent response is generated by requesting the observed node to provide information necessary to generate the independent response.

9. The method of claim 1, wherein the chaperone approval scheme specifies:

requesting the response from the observed node by each of the plurality of chaperone nodes to obtain a plurality of responses;

agreeing on a value for the response using the plurality of responses and the chaperone voting policy to obtain an agreed value; and

providing the approved response to the observed node, wherein the approved response comprises the agreed value.

10. The method of claim 1, wherein the chaperone approval scheme specifies:

requesting the decision from the observed node by each of the plurality of chaperone nodes to obtain a plurality of decision;

determining whether the decision is within an allowed operating parameter using information about the allowed operating parameter of the observed node and the chaperone voting policy; and

providing an approved decision to the observed node, if the plurality of chaperone nodes determine that the decision is within the allowed operating parameters.

11. The method of claim 1, wherein the chaperone voting policy specifies a minimum number of the plurality of chaperone nodes that must agree on a value of the response prior to approving the response.

12. The method of claim 1, wherein the overlay network uses at least one distributed hash table.

13. A distributed system, comprising:

an observed node generate a response to a request from a target node; and

a plurality of chaperone nodes, wherein each of the plurality of chaperone nodes is configured to;

provide a signed response to the observed node in response to a request from the observed node, and

approve the response provided by the observed node,

wherein the approved response is forwarded to the target node;

wherein the distributed system implements an overlay network for message delivery,

wherein the observed node and the plurality of chaperone nodes communicate using the overlay network,

wherein the plurality of chaperone nodes are selected using a per-observed node scheme, and

wherein the per-observed node scheme comprises selecting the at least one of the plurality of chaperone nodes associated with the observed node using a global unique identifier (GUID) assigned to the observed node.

14. The distributed system of claim 13, wherein the response and the decision are approved by the plurality of chaperone nodes using a chaperone voting policy and a chaperone approval policy.

15. The distributed system of claim 14, wherein the chaperone voting policy specifies a minimum number of the plurality of chaperone nodes that must agree on a value of the response prior to approving the response.

16. The distributed system of claim 14, wherein the chaperone approval policy specifies:

generating an independent response by each of the plurality of chaperone nodes;

agreeing on a value for the independent response using the plurality of independent responses and the chaperone voting policy to obtain an agreed value; and

providing the approved response to the observed node, wherein the approved response comprises the agreed value, wherein the independent response is generated by requesting the observed node to provide information necessary to generate the independent response.

17. The distributed system of claim 14, wherein the chaperone approval scheme specifies:

requesting the response from the observed node by each of the plurality of chaperone nodes to obtain a plurality of responses;

agreeing on a value for the response using the plurality of responses and the chaperone voting policy to obtain an agreed value; and

providing the approved response to the observed node, wherein the approved response comprises the agreed value.

18. The distributed system of claim 14, wherein the chaperone approval scheme specifies:

requesting the decision from the observed node by each of the plurality of chaperone nodes to obtain a plurality of decision;

determining whether the decision is within an allowed operating parameter using information about the allowed operating parameter of the observed node and the chaperone voting policy; and

providing an approved decision to the observed node, if the chaperones determine that the decision is within the allowed operating parameters.

19. The distributed system of claim 13, wherein the at least one of the plurality of nodes associated with the observed node are determined by applying a hashing function to the GUID a plurality of time to obtain a plurality of GUIDs, wherein each of the plurality of GUIDs is associated with one of the plurality of chaperone nodes.

20. The distributed system of claim 13, wherein each of the plurality of chaperone nodes comprises at least one selected from the group consisting of knowledge of at least one other of the plurality of chaperone nodes and functionality to locate at least one other of the plurality of chaperone nodes.

21. The distributed system of claim 13, wherein each of the plurality of chaperone nodes comprises authentication material, and wherein the authentication material is used in generating the approved response.

22. A computer readable medium comprising software instructions for approving a response or a decision of an observed node in a distributed system, comprising software instructions to:

generate the response to a request from a target node by the observed node;

forward the response from the observed node to at least one of a plurality of chaperone nodes associated with the observed node based on a chaperone scheme, wherein the chaperone scheme comprises a per-observed node scheme; and

approve the response by the plurality of chaperone nodes using a chaperone voting policy and a chaperone approval policy to obtain an approved response,

wherein the distributed system implements an overlay network for message delivery,

wherein the observed node and the plurality of chaperone nodes communicate using the overlay network, and

wherein the per-observed node scheme comprises selecting the at least one of the plurality of chaperone nodes associated with the observed node using a global unique identifier (GUID) assigned to the observed node.