Method and system for constructing adaptive and resilient software

• US 6,226,627 B1
• Filed: 04/17/1998
• Issued: 05/01/2001
• Est. Priority Date: 04/17/1998
• Status: Expired due to Term

• Current Assignee: Paradise IP LLC (IP Edge LLC)
• Original Assignee: Fuji Xerox Company Limited (Fujifilm Holdings Corporation), Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Polak, Wolfgang H.
• Primary Examiner(s): Powell, Mark
• Assistant Examiner(s): Khatri, Anil
• Application Number:
  US09/061,890
• Time in Patent Office: 1,110 Days
• Field of Search: 706/14, 706/15, 706/16, 706/19, 706/21, 706/47, 704/9, 704/10, 717/19
• US Class Current: 706/14
• CPC Class Codes: G06F 11/142 Reconfiguring to eliminate the error group management mechanisms in a peer-to-peer network H04L67/1044
• CPC Class Codes: G06F 11/1479 Generic software techniques for error detection or fault masking
• CPC Class Codes: G06F 2201/835 Timestamp
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 5/046 Forward inferencing; Production systems

Abstract

A dependency action system uses redundant sets of dynamically reconfigurable functional components to achieve robustness and fault tolerance, and to achieve self-optimization by learning and planning techniques that use time-stamps and or computation stamps as a key indicator. The dependency action system is based on functional components, or actions, which act on data values that are stored in stamped storage locations. Data is read and written to these storage locations, updating the stamps as appropriate. The execution of an action is controlled by the stamps of its enabling and disabling storage locations. The dependency action system specifies an action as enabled if new data has arrived in the enabling storage locations. Updating the stamp of the disabling storage locations disables the action. If an alternative action succeeds and produces a value, the other alternative actions become disabled. If one action fails to produce a value to a storage location, other alternative actions may still be enabled and can be executed. Thus, the dependency action system supports automatic recovery from failure of an individual action. The dependency action system accumulates statistical information about the behavior of the actions, which includes the probability that a particular disabling storage location will be updated by an action and the average cost of an action. The dependency action system uses this information to plan a sequence of action executions that most likely leads to the cheapest solution of a given task.

Claims

1. A method for executing a software system, the software system comprising:

a set of storage locations, each storage location having a storage value and at least one associated attribute value;

a plurality of actions, each action having at least two of the plurality of storage locations associated with that action; and

a selection rule;

the method comprising;

determining a set of enabled actions based on the associated attribute values for the at least two storage locations associated with each action;

selecting an enabled action from the set of enabled actions based on the selection rule;

executing the selected enabled action; and

updating the storage value and the at least one associated attribute value for at least one of the storage locations associated with the selected enabled action based on a result of the execution of the selected enabled action.

2. The method of claim 1, wherein the plurality of actions can be dynamically redefined substantially at any time during execution of the software system.

3. The method of claim 1, wherein the set of storage locations can be dynamically redefined substantially at any time during execution of the software system.

4. The method of claim 1, wherein the storage locations can be dynamically reassociated with the actions substantially at any time during execution of the software system.

5. The method of claim 1, further comprising generating at least one output value from the plurality of storage locations.

6. The method of claim 5, wherein generating the at least one output value comprises outputting the at least one output value or generating a communication.

7. The method of claim 1, further comprising updating cost and modification probabilities associated with each action.

8. The method of claim 7, where the cost and modification probabilities can be dynamically updated substantially at any time during the operation of the method.

9. The method of claim 8, where modification probabilities associated with an action are the probabilities that execution of the action will modify some of the storage locations associated with the action.

10. The method of claim 8, wherein updating cost and modification probabilities comprises:

determining whether a change in updated cost and modification probabilities associated with an action meets predetermined criteria; and

adjusting the selection rule based on the updated cost and modification probabilities if the change meets the predetermined criteria.

11. The method of claim 1, wherein determining the set of enabled actions comprises determining, for each action and for each at least one enabling storage location and each at least one disabling storage location for that action, whether all such enabling storage locations are initialized and whether the at least one enabling storage location associated with that action has an attribute value greater than the attribute value of all disabling storage locations associated with that action.

12. The method of claim 11, wherein an action is enabled if all of its enabling storage locations are initialized and none of its disabling storage locations are initialized.

13. The method of claim 1, wherein the attribute value is a time-stamp having a value, and determining a set of enabled actions further comprises identifying an action as enabled according to the relative time-stamp values of designated enabling and disabling storage locations associated with the action.

14. The method of claim 1, wherein the attribute value is a computation-stamp having a value, and determining a set of enabled actions further comprises identifying an action as enabled according to the relative computation-stamp values of designated enabling and disabling storage locations associated with the action.

15. The method of claim 1, wherein the selection rule is a preference relation.

16. The method of claim 1, wherein the selection rule is usable to select one of a plurality of enabled actions.

17. A dependency action system, comprising:

a set of storage locations, each storage location having a storage value and at least one associated attribute value;

a plurality of actions;

wherein, for each action, at least two of the plurality of storage locations are associated with that action;

a selection rule; and

an enabled action selector that selects an enabled action from a set of enabled actions based on the selection rule;

wherein;

an action is enabled based on the at least one associated attribute value for the at least two storage locations associated with that action; and

the selected enabled action executes upon being selected and the storage value and the associated attribute value for at least one of the storage locations associated with the selected enabled action is updated based on a result of the execution of the selected enabled action.

18. The dependency action system of claim 17, wherein the plurality of actions are dynamically updated substantially at any time during operation of the dependency action system.

19. The dependency action system of claim 17, wherein the set of storage locations are dynamically updated substantially at any time during operation of the dependency action system.

20. The dependency action system of claim 17, wherein the storage locations associated with at least one of the actions are dynamically updated substantially at any time during operation of the dependency action system.

21. The dependency action system of claim 17, further comprises an output device that outputs at least one output value from the plurality of storage locations.

22. The dependency action system of claim 17, further comprises means for updating cost and modification probabilities associated with each action.

23. The dependency action system of claim 22, where the means for updating the cost and modification probabilities operates dynamically substantially at any time during operation of the dependency action system.

24. The dependency action system of claim 23, where the modification probabilities associated with an action are the probabilities that execution of the action will modify at least one of the storage locations associated with the action.

25. The dependency action system of claim 23, wherein the means for updating the cost and modification probabilities comprises:

means for determining whether a change in updated cost and modification probabilities associated with an action meets predetermined criteria; and

means for determining a new selection rule based on the updated cost and modification probabilities if the change meets the predetermined criteria.

26. The dependency action system of claim 17, wherein the selection rule is usable to select one of a plurality of enabled actions.

27. A method for constructing a software system, comprising:

defining a plurality of actions;

defining a set of storage locations, each storage location having a storage value and at least one associated attribute value;

associating, for each action, at least two of the plurality of storage locations with that action; and

generating a selection rule.

28. The method of claim 27, wherein the attribute value is a time-stamp representing a time when the storage location was last updated.

29. The method of claim 27, wherein the attribute value is a computation-stamp representing whether the storage location has been updated subsequent to a data value being input to the software system.

30. The method of claim 27, wherein associating, for each action, at least two of the plurality of storage locations with that action comprises:

associating at least one of the at least two storage locations as an enabling storage location for that action; and

associating at least one of the at least two storage locations as a disabling storage location for that action.

31. The method of claim 27, wherein generating the selection rule comprises generating a preference relation.

32. The method of claim 31, wherein generating the preference relation comprises:

generating a directed graph from the plurality of actions and the associated storage locations;

determining, for each pair of the plurality of actions, which one of the pair of actions is preferred over the other of the pair of actions; and

recording the preference in the preference relation.

33. The method of claim 27, wherein generating the selection rule comprises generating a selection rule usable to select one of a number of enabled actions of the plurality of actions.