System for distributed computation processing includes dynamic assignment of predicates to define interdependencies

• US 5,329,626 A
• Filed: 10/23/1990
• Issued: 07/12/1994
• Est. Priority Date: 10/23/1990
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Chang, Edward Y., Lu, Edward S., Cheng, Edward C., Lee, Dora L., Lutgardo, Alberto, Klein, Johannes
• Primary Examiner(s): Lee, Thomas C.
• Assistant Examiner(s): ORZECH, JENNIFER
• Application Number:
  US07/601,990
• Time in Patent Office: 1,358 Days
• Field of Search: 395/375, 395/575, 395/600, 395/800, 395/200, 395/650
• US Class Current: 709/248
• CPC Class Codes: G06F 9/466 Transaction processing

Abstract

During the processing of a transaction or other distributed computation, a computation management system creates a number of agents to handle various aspects or portions of the computations to be performed. Each agent progresses through a predefined set of state transitions which define the status of the agent at any point in time. The computation management system defines for each agent a set of dependencies, each dependency corresponding to a state transition which will be blocked until a particular state transition occurs in another specified agent. By defining selected combinations of dependencies for each agent, a variety of different interdependencies and cooperating protocols can be implemented. The distributed processing management system can be used both for managing transaction processing and for synchronizing events in other types of distributed computations.

Claims

1. In a computer system, a method of performing distributed computations, the steps of the method performed by said computer system comprising:

providing a set of cooperating computational agents to perform each distributed computation, each computational agent being programmed to progress through a sequence of state transitions among a predefined set of states;

defining and storing in at least one computer memory a plurality of distinct predicates that can be assigned to ones of said computational agents, each distinct predicate specifying a distinct state transition dependency between state transitions of first and second specified ones of said computational agents;

each said defined predicate specifying a state transition of said first computational agent that is to be blocked until said second computational agent performs a specified action that satisfies said each defined predicate;

wherein a first one of said plurality of defined predicates is a mutual strong commit dependency predicate that requires said specified first and second computational agents to commit a distributed computation'"'"'s results only when said first and second computational agents mutually agree to commit said distributed computation'"'"'s results and otherwise requires said first and second computational agents not to commit said distributed computation'"'"'s results; and

wherein a second one of said plurality of defined predicates is a finish dependency predicate that determines which of said specified first and second computational agents must finish a corresponding portion of said distributed computation before the other of said specified first and second computational agents;

dynamically assigning a set of predicates to the set of computational agents performing each distributed computation so as to define a corresponding set of state transition interdependencies said set of computational agents;

wherein each assigned predicate is selected from said plurality of predicates, and different sets of predicates are assigned to the sets of computational agents for different distributed computations;

storing in at least one computer memory dependency data for each said computational agent specifying (A) a first set of state transitions of said each computational agent that are to be blocked, (B) preconditions for allowing each of said first set of state transitions to proceed, (C) a second set of state transitions of said each computation agent that are preconditions for state transitions by other ones of said computational agents for which each of said second set of state transitions are preconditions;

performing each distributed computation with said set of computational agents provided for that distributed computation, including blocking state transitions by ones of said set computational agents in accordance with said predicates assigned to said set of computational agents, and allowing each said blocked state transition to proceed when said action specified by the corresponding predicate is performed.

2. The method of performing distributed computations of claim 1, said performing step including:

upon each state transition in each one of said computational agents, when said stored dependency data indicates that said state transition is a pre-condition for state transitions by other specified ones of said computational agents, sending messages to said other specified ones of said computational agents notifying that said state transition has taken place;

receiving said messages from other ones of said computational agents; and

when a state transition by one of said computational agents is blocked, waiting to receive messages corresponding to said pre-conditions specified by said stored dependency data for said blocked state transition, and allowing said blocked state transition to proceed when said messages corresponding to said specified pre-conditions are received.

3. The method of performing distributed computations of claim 1, further including:

providing resources to be accessed by said computational agents;

establishing a plurality of distinct resource conflict resolution rules for determining whether to allow any specified two of said computational agents to share access to any of said resources;

each of said plurality of resource conflict resolution rules including (A) distinct dependency criteria requiring predefined state transition dependencies between state transitions of said any specified two computational agents as a precondition for allowing said two computational agents to share access to any of said resources;

at least one of said plurality of resources conflict resolution rules including (B) timing criteria for allowing shared access to any of said resources only after specified state transitions occur; and

when a first one of said computational agents has access to any one of said resources and a second one of said computational agents requests access to the same one resource, selecting one of said plurality of resource conflict resolution rules, if any, having dependency criteria satisfied by said first and second computational agents, and allowing said second computational agent to share access to said one resource with said first computational agent in accordance with said selected resource resolution rule.

4. The method of performing distributed computations of claim 1, wherein a third one of said plurality of defined predicates is a strong commit dependency predicate that requires said specified first computational agent to commit results computed by said first computational agent only when said specified second computational agent will commit results computed by said second computational agent.

5. The method of performing distributed computations of claim 1, wherein a fourth one of said plurality of defined predicates is a weal commit dependency predicate that prevents said specified first computational agent from committing results computed by said first computational agent when said second computational agent succeeds in finishing a portion of said distributed computation corresponding to said second computational agent unless said second computational agent will commit results computed by said second computational agent.

6. A computer system for performing distributed computations, comprising:

a set of cooperating computational agents for performing each distributed computation, each computational agent being programmed to progress through a sequence of state transitions among a predefined set of states;

at least one computer memory;

a plurality of distinct predicates, stored in said computer memory, that can be assigned to ones of said computational agents, each distinct predicate specifying a distinct state transition dependency between state transitions of first and second specified ones of said computational agents;

each said distinct predicate specifying a state transition of said first computational agent that is to be blocked until said second computational agent performs a specified action that satisfies said each distinct predicate;

wherein a first one of said plurality of distinct predicates is a mutual strong commit dependency predicate that requires said specified first and second computational agents to commit a distributed computation'"'"'s results only when said first and second computational agents mutually agree to commit said distributed computation'"'"'s results and otherwise requires said first and second computational agents not to commit said distributed computation'"'"'s results; and

wherein a second one of said plurality of distinct predicates is a finish dependency predicate that determines which of said specified first and second computational agents must finish a corresponding portion of said distributed computation before the other of said specified first and second computational agents;

said distributed computation coordinator including means for storing in at least one computer memory dependency data for each said computational agent specifying (A) a first set of state transitions of said each computational agent that are to be blocked, (B) preconditions for allowing each of said first set of state transitions to proceed, (C) a second set of state transitions of said each computational agent that are preconditions for state transitions by other ones of said computational agents for which each of said second set of state transitions are preconditions;

a distributed computation coordinator for dynamically assigning a set of predicates to the set of computational agents performing each distributed computation so as to define a corresponding set of state transition interdependencies between said set of computational agents;

wherein each assigned predicate is selected from said plurality of predicates, and different sets of predicates are assigned to the sets of computational agents for different distributed computations;

means for performing each distributed computation with said set of computational agents for that distributed computation;

said set of computational agents for each distributed computation including means for blocking state transitions by said set of computational agents in accordance with said predicates assigned to said set of computational agents; and

said distributed computation coordinator including means for allowing each said blocked state transition to proceed when said action specified by the corresponding predicate is performed.

7. The computer system of claim 6, said distributed computation coordinator including means for responding to each state transition in each one of said computational agents, when said stored dependency data indicates that said state transition is a pre-condition for state transitions by other specified ones of said computational agents, by sending messages to said other specified ones of said computational agents notifying that said state transition has taken place;

each of said computational agents including means for receiving said messages from other ones of said computational agents, and for waiting to receive messages corresponding to said pre-conditions specified by said stored dependency data when a state transition by said each computational agent is blocked, and for allowing said blocked state transition to proceed when said messages corresponding to said specified pre-conditions are received.

8. The computer system of claim 6, further including:

resources to be accessed by said computational agents;

a plurality of distinct resource conflict resolution rules, stored in said at least one computer memory, for determining whether to allow any specified two of said computational agents to share access to any of said resources;

each of said plurality of resource conflict resolution rules including (A) distinct dependency criteria requiring predefined state transition dependencies between state transitions of said any specified two computational agents as a precondition for allowing said two computational agents to share access to any of said resources;

at least one of said plurality of resource conflict resolution rules including (B) timing criteria for allowing shared access to any of said resources only after specified state transitions occur; and

said distributed computation coordinator including resource conflict resolution means;

said resource conflict resolution means, when a first one of said computational agents has access to any one of said resources and a second one of said computational agents requests access to the same one resource, selecting one of said plurality of resource conflict resolution rules, if any, having dependency criteria satisfied by said first and second computational agents, and allowing said second computational agent to share access to said one resource with said first computational agent in accordance with said selected resource conflict resolution rule.

9. The computer system of claim 6, wherein a third one of said plurality of distinct predicates is a strong commit dependency predicate that requires said specified first computational agent to commit results computed by said first computational agent only when said specified second computational agent will commit results computed by said second computational agent.

10. The computer system of claim 9, wherein a fourth one of said plurality of distinct predicates is a weak commit dependency predicate that prevents said specified first computational agent from committing results computed by said first computational agent when said second computational agent succeeds in finishing a portion of said distributed computation corresponding to said second computational agent unless said second computational agent will commit results computed by said second computational agent.

11. In a computer system, a method of performing distributed computations, the steps of the method performed by said computer system comprising:

providing a set of cooperating computational agents to perform each distributed computation, each computational agent being programed to progress through a sequence of state transitions among a predefined set of states;

defining and storing in at least one computer memory a plurality of distinct predicates that can be assigned to ones of said computational agents, each distinct predicate specifying a distinct state transition dependency between state transitions of first and second specified ones of said computational agents;

each said defined predicate specifying a state transition of said first computational agent that is to be blocked until said second computational agent performs a specified action that satisfies said each defined predicate;

dynamically assigning a set of predicates to the set of computational agents performing each distributed computation so as to define a corresponding set of state transition interdependencies between said set of computational agents;

wherein each assigned predicate is selected from said plurality of predicates, and different sets of predicates are assigned to the sets of computational agents for different distributed computations;

performing each distributed computation with said set of computational agents provided for that distributed computation, including blocking state transitions by ones of said set computational agents in accordance with said predicates assigned to said set of computational agents, and allowing each said blocked state transition to proceed when said action specified by the corresponding predicate is performed;

providing resources to be accessed by said computational agents;

establishing a plurality of distinct resource conflict resolution rules for determining whether to allow any specified two of said computational agents to share access to any of said resources;

each of said plurality of resource conflict resolution rules including (A) distinct dependency criteria requiring predefined state transition dependencies between state transitions of said any specified two computational agents as a precondition for allowing said two computational agents to share access to any of said resources;

at least one of said plurality of resource conflict resolution rules including (B) timing criteria for allowing shared access to any of said resources only after specified state transitions occur; and

when a first one of said computational agents has access to any one of said resources and a second one of said computational agents requests access to the same one resource, selecting one of said plurality of resource conflict resolution rules, if any, having dependency criteria satisfied by said first and second computational agents, and allowing said second computational agent to share access to said one resource with said first computational agent in accordance with said selected resource conflict resolution rule.

12. A computer system for performing distributed computations, comprising:

a set of cooperating computational agents for performing each distributed computation, each computational agent being programmed to progress through a sequence of state transitions among a predetermined set of states;

at least one computer memory;

a plurality of distinct predicates, stored in said computer memory, that can be assigned to ones of said computational agents, each distinct predicate specifying a distinct state transition dependency between state transitions of first and second specified ones of said computational agents;

each said distinct predicate specifying a state transition of said first computational agent that is to be blocked until said second computational agent performs a specified action that satisfies said each distinct predicate;

a distributed computation coordinator dynamically assigning a set of predicates to the set of computational agents performing each distributed computation so as to define a corresponding set of state transition interdependencies between said set of computational agents;

wherein each assigned predicate is elected from said plurality of predicates, and different sets of predicates are assigned to the sets of computational agents for different distributed computations;

means for performing each distributed computation with said set of computational agents for that distributed computation;

said set of computational agents for each distributed computation including means for blocking state transitions by said set of computational agents in accordance with said predicates assigned to said set of computational agents; and

said distributed computation coordinator including means for allowing each said blocked state transition to proceed when said action specified by the corresponding predicate is performed;

resources to be accessed by said computational agents;

a plurality of distinct resource conflict resolution rules, stored in said at least one computer memory, for determining whether to allow any specified two of said computational agents to share access to any of said resources;

each of said plurality of resource conflict resolution rules including (A) distinct dependency criteria requiring predefined state transition dependencies between state transitions of said any specified two computational agents as a precondition for allowing said two computational agents to share access to any of said resources;

at least one of said plurality of resource conflict resolution rules including (B) timing criteria for allowing shared access to any of said resources only after specified state transitions occur; and

said distributed computation coordinator including resource conflict resolution means;

said resource conflict resolution means, when a first one of said computational agents has access to any one of said resources and a second one of said computational agents requests access to the same one resource, selecting one of said plurality of resource conflict resolution rules, if any, having dependency criteria satisfied by said first and second computational agents, and allowing said second computational agent to share access to said one resource with said first computational agent in accordance with said selected resource conflict resolution rule.