Methods and apparatus using commutative error detection values for fault isolation in multiple node computers

• US 7,383,490 B2
• Filed: 04/14/2005
• Issued: 06/03/2008
• Est. Priority Date: 04/14/2005
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Singh, Sarabjeet, Vranas, Pavlos, Chen, Dong, Gara, Alan, Heidelberger, Philip, Coteus, Paul, Takken, Todd, Giampapa, Mark E., Steinmacher-Burow, Burkhard D., Almasi, Gheorghe, Blumrich, Matthias Augustin, Hoenicke, Dirk I.
• Primary Examiner(s): Lamarre; Guy J.
• Application Number:
  US11/106,069
• Publication Number:
  US 20060248370A1
• Time in Patent Office: 1,146 Days
• Field of Search: 714/4, 714/100, 714/800, 714/821, 714/712
• US Class Current: 714/800
• CPC Class Codes: G06F 11/1633 using mutual exchange of the output between the redundant processing components

Abstract

Methods and apparatus perform fault isolation in multiple node computing systems using commutative error detection values for—example, checksums—to identify and to isolate faulty nodes. When information associated with a reproducible portion of a computer program is injected into a network by a node, a commutative error detection value is calculated. At intervals, node fault detection apparatus associated with the multiple node computer system retrieve commutative error detection values associated with the node and stores them in memory. When the computer program is executed again by the multiple node computer system, new commutative error detection values are created and stored in memory. The node fault detection apparatus identifies faulty nodes by comparing commutative error detection values associated with reproducible portions of the application program generated by a particular node from different runs of the application program. Differences in values indicate a possible faulty node.

Claims

1. A signal-bearing computer memory medium tangibly embodying a program of machine-readable instructions executable by a digital processing apparatus to perform node fault detection operations in a computing system using commutative error detection values, where the computing system comprises a plurality of nodes, where each of the nodes comprises at least a node processor, a node memory, a network interface and a commutative error detection apparatus;

the computing system further comprising a network connecting the plurality of nodes through the network interfaces of the nodes, and wherein node fault detection occurs when the computing system executes at least a portion of an application program at least twice, wherein during each execution of the portion of the application program at least one commutative error detection value is generated and saved to the commutative error detection apparatus associated with at least one node of the plurality when data generated during execution of a reproducible segment of the portion of the application program is injected into the network by the at least one node, the node fault detection operations comprising;

retrieving the at least one commutative error detection value generated during a first execution of the portion of the application program from the commutative error detection apparatus of the at least one node;

saving the at least one commutative error detection value associated with the first execution of the portion of the application program to a computer memory medium;

retrieving the at least one commutative error detection value generated during a second execution of the portion of the application program from the commutative error detection apparatus of the at least one node; and

comparing the at least one commutative error detection value from the first execution of the portion of the application program to the at least one commutative error detection value from the second execution of the portion of the application program.

2. The signal-bearing computer memory medium of claim 1 where the node fault detection operations further comprise:

saving the at least one commutative error detection value from the second execution of the portion of the application program to a computer memory medium before comparing the at least one commutative error detection value from the second execution of the portion of the application program to the at least one commutative error detection value from the first execution of the portion of the application program.

3. The signal-bearing computer memory medium of claim 1 wherein comparing the at least one commutative error detection value from the first execution of the portion of the application program to the at least one commutative error detection value from the second execution of the portion of the application program occurs during the second execution of the portion of the application program after the at least one commutative error detection value from the second execution is generated, whereby if there is a difference between the at least one commutative error detection values a node fault condition is indicated.

4. The signal-bearing computer memory medium of claim 3 where the second execution of the application program is halted as soon as the node fault condition is detected.

5. The signal-bearing computer memory medium of claim 1 where the node fault detection operations further comprise:

detecting a fault condition in one of the nodes of the computer system when there is a difference between the at least one commutative error detection value associated with the first execution of the portion of the application program and the at least one commutative error detection value associated with the second execution of the portion of the application program.

6. The signal-bearing computer memory medium of claim 1 where the node fault detection operations further comprise:

determining that the at least one node is operating normally if there is no difference between the at least one commutative error detection value associated with the first execution of the portion of the application program and the at least one commutative error detection value associated with the second execution of the portion of the application program.

7. The signal-bearing computer memory medium of claim 1 wherein executing at least a portion of the application program comprises executing the entire application program.

8. The signal-bearing computer memory medium of claim 1 where the commutative error detection values comprise checksums.

9. A signal-bearing computer memory medium tangibly embodying a program of machine-readable instructions executable by a digital processing apparatus to perform node fault detection operations in a computing system using commutative error detection values, where the computing system comprises a plurality of nodes, where each of the nodes comprises at least a node processor, a node memory, a network interface and a commutative error detection apparatus;

the computing system further comprising a network connecting the plurality of nodes through the network interfaces of the nodes, and wherein node fault detection occurs when the computing system executes multiple portions of an application program at least twice, wherein during each execution of the multiple portions of the application program a plurality of commutative error detection values are generated and saved to the respective commutative error detection apparatus associated with the plurality of nodes when data generated during execution of reproducible segments of the multiple portions of the application program is injected into the network by the nodes, the node fault detection operations comprising;

during the first execution and second executions of the multiple portions of the application program, retrieving the commutative error detection values from the commutative error detection apparatus associated with the plurality of nodes;

saving the plurality of commutative error detection values associated with at least the first execution of the multiple portions of the application program to a computer memory medium; and

comparing on a node-by-node basis the plurality of commutative error detection values associated with the first execution of the multiple portions of the application program to the plurality of commutative error detection values associated with the second execution of the multiple portions of the application program, where at least one difference in commutative error detection values between the first and second executions of the application program indicates a node fault condition.

10. The signal-bearing computer memory medium of claim 9 wherein comparing the plurality of commutative error detection values further comprises:

comparing sequences of commutative error detection values generated during the first and second executions of the multiple portions of the application program to determine when a first difference in commutative error detection values occurred between the first and second executions of the multiple portions of the application program; and

tracing the fault to a particular node that generated the first difference in commutative error detection values.

11. The signal-bearing computer memory medium of claim 10 where the operations further comprise:

identifying which portion of the application program caused the first difference in commutative error detection values between the first and second executions of the multiple program portions.

12. The signal-bearing computer memory medium of claim 9 wherein comparing the commutative error detection values from the first execution of the multiple portions of the application program to the commutative error detection values from the second execution of the multiple portions of the application program occurs as the commutative error detection values are generated during the second execution of the multiple portions of the application program, whereby as soon as a first difference between commutative error detection values is detected a node fault condition is indicated.

13. The signal-bearing computer memory medium of claim 12 where the second execution of the multiple portions of the application program is halted as soon the node fault condition is detected.

14. The signal-bearing computer memory medium of claim 12 wherein the node generating the first difference in commutative error detection values between the first and second executions of the multiple portions of the application program is faulty.

15. The signal-bearing computer memory medium of claim 9 where the node fault detection operations further comprise:

saving the commutative error detection values from the second execution of the multiple portions of the application program to a computer memory medium before comparing the commutative error detection values from the second execution of the multiple portions of the application program to the commutative error detection values from the first execution of the multiple portions of the application program.

16. The signal-bearing computer memory medium of claim 9 where commutative error detection values are saved at generation times, where a commutative error detection value saved at generation n by a node is affected only by messages received from other nodes in generations earlier then generation n.

17. The signal-bearing computer memory medium of claim 9 where the application program contains instructions that specify when to save commutative error detection values to the commutative error detection apparatus of the plurality of nodes.

18. The signal-bearing computer memory medium of claim 17 where data injected by the plurality of nodes into the network is contained in data packets.

19. The signal-bearing computer memory medium of claim 18 where the data packets comprise header and data payload portions, and where the header portion contains instructions that a commutative error detection value should be calculated for at least a portion of the data packet.

20. The signal-bearing computer memory medium of claim 19 where the instructions indicate that a commutative error detection value should be calculated for at least a portion of the data packet header.

21. The signal-bearing computer memory medium of claim 19 where the instructions indicate that a commutative error detection value should be calculated for at least a portion of the data packet payload.

22. The signal-bearing computer memory medium of claim 9 where executing multiple portions of the application program comprises executing the entire application program.

23. The signal-bearing computer memory medium of claim 9 where the commutative error detection values comprise checksums.

24. A node fault detection apparatus for use in a computing system, where the computing system comprises a plurality of nodes, where each of the nodes comprises at least a node processor, a node memory, a network interface and a commutative error detection apparatus;

and a network connecting the plurality of nodes through the network interfaces of the nodes, the node fault detection apparatus comprising;

at least one node fault detection processor for performing node fault detection operations;

a node fault detection computer memory medium for storing commutative error detection values retrieved from the commutative error detection apparatus of the plurality of nodes; and

a network interface connecting the node fault detection apparatus to the network of the computing system,

where the at least one processor of the node fault detection apparatus performs at least the following node fault detection operations when the computing system executes a portion of an application program at least twice, wherein during each execution of the portion of the application program at least one commutative error detection value is generated and saved to a commutative error detection apparatus associated with at least one node of the plurality when data generated during execution of a reproducible segment of the portion of the application program is injected into the network by the at least one node, the node fault detection operations comprising;

retrieving the at least one commutative error detection value created during a first execution of the application program from the commutative error detection apparatus of the at least one node;

saving the at least one commutative error detection value from the first execution of the application program to the node fault detection apparatus computer memory medium;

retrieving the at least one commutative error detection value created during a second execution of the application program from the commutative error detection apparatus of the at least one node; and

comparing the at least commutative error detection value from the first execution of the application program to the at least one commutative error detection value from the second execution of the application program.

25. The node fault detection apparatus of claim 24 where the node fault detection operations further comprise:

saving the at least one commutative error detection value from the second execution of the portion of the application program to a computer memory medium before comparing the at least one commutative error detection value from the second execution of the portion of the application program to the at least one commutative error detection value from the first execution of the portion of the application program.

26. The node fault detection apparatus of claim 24 wherein comparing the at least one commutative error detection value from the first execution of the portion of the application program to the at least one commutative error detection value from the second execution of the portion of the application program occurs as soon as the at least one commutative error detection value from the second execution of the portion of the application program is generated, whereby if there is a difference between the at least one commutative error detection values a node fault condition is indicated and the portion of the application program need not be executed in its entirety the second time.

27. The node fault detection apparatus of claim 24 where the node fault detection operations further comprise:

detecting a fault condition in one of the nodes of the computer system when there is a difference between the at least one commutative error detection value associated with the first execution of the portion of the application program and the at least one commutative error detection value associated with the second execution of the portion of the application program.

28. A computing system using commutative error detection values for node fault detection, the computing system comprising:

a plurality of nodes, where each of the nodes comprises at least a node processor, a node memory, a network interface and a commutative error detection apparatus;

a network connecting the plurality of nodes through the network interfaces of the nodes;

a node fault detection apparatus comprising;

a processor for performing node fault detection operations;

a computer memory medium for storing commutative error detection values; and

a network interface connecting the node fault detection apparatus to the network,

where the node fault detection apparatus processor performs at least the following node fault detection operations during first and second executions of multiple portions of an application program by the computing system, wherein during the first and second executions of the multiple portions of the application program a plurality of commutative error detection values are saved to the commutative error detection apparatus of the plurality of nodes when the nodes inject information generated during execution of reproducible segments of the multiple portions of the application program into the network, the node fault detection operations comprising;

during the first execution and second executions of the multiple portions of the application program, retrieving the commutative error detection values from the commutative error detection apparatus associated with the plurality of nodes;

saving the plurality of commutative error detection values associated with at least the first execution of the multiple portions of the application program to the node fault detection computer memory medium; and

comparing on a node-by-node basis the plurality of commutative error detection values associated with the first execution of the multiple portions of the application program to the plurality of commutative error detection values associated with the second execution of the multiple portions of the application program, where at least one difference in commutative error detection values between the first and second executions of the application program indicates a node fault condition.

29. The computing system of claim 28 wherein comparing the plurality of commutative error detection values further comprises:

comparing sequences of commutative error detection values generated during the first and second executions of the multiple portions of the application program to determine when a first difference in commutative error detection values occurred between the first and second executions of the multiple portions of the application program; and

tracing the fault to a particular node that generated the first difference in commutative error detection values.

30. The computing system of claim 28 wherein comparing the commutative error detection values from the first execution of the multiple portions of the application program to the commutative error detection values from the second execution of the multiple portions of the application program occurs as the commutative error detection values are generated during the second execution of the multiple portions of the application program, whereby as soon as a first difference between commutative error detection values is detected a node fault condition is indicated, and the execution of the multiple portions of the application program for the second time need not continue.

31. The computing system of claim 30 wherein the node generating the first difference in commutative error detection values between the first and second executions of the multiple portions of the application program is faulty.

32. The computing system of claim 28 where the node fault detection operations further comprise:

saving the commutative error detection values from the second execution of the multiple portions of the application program to the node fault detection apparatus computer memory medium before comparing the commutative error detection values from the second execution of the multiple portions of the application program to the commutative error detection values from the first execution of the multiple portions of the application program.

33. The computing system of claim 28 where the application program contains instructions that specify when to save commutative error detection values to the commutative error detection apparatus of the plurality of nodes.

34. The computing system of claim 33 where data injected by the at least one node into the network is contained in data packets.

35. The computing system of claim 34 where the data packets comprise header and data payload portions, and where the header portion contains instructions that a commutative error detection value should be calculated for at least a portion of the data packet.

36. The computing system of claim 35 where the instructions indicate that that a commutative error detection value should be calculated for at least a portion of the data packet header.

37. The computing system of claim 35 where the instructions indicate that a commutative error detection value should be calculated for at least a portion of the data packet payload.

38. A node fault detection apparatus for use in a computing system, where the computing system comprises a plurality of nodes, where each of the nodes comprises at least a node processor, a node memory, a network interface and a commutative error detection apparatus;

and a network connecting the plurality of nodes through the network interfaces of the nodes, the node fault detection apparatus comprising;

processor means for performing node fault detection operations;

memory means for storing commutative error detection values retrieved from the commutative error detection apparatus of the plurality of nodes; and

network interface means connecting the node fault detection apparatus to the network of the computing system,

where the processor means of the node fault detection apparatus performs at least the following node fault detection operations when the computing system executes a portion of an application program at least twice, wherein during each execution of the portion of the application program at least one commutative error detection value is generated and saved to a commutative error detection apparatus associated with at least one node of the plurality when data generated during execution of a reproducible segment of the portion of the application program is injected into the network by the at least one node, the node fault detection operations comprising;

retrieving the at least one commutative error detection value created during a first execution of the application program from the commutative error detection apparatus of the at least one node;

saving the at least one commutative error detection value from the first execution of the application program to the memory means;

retrieving the at least one commutative error detection value created during a second execution of the application program from the commutative error detection apparatus of the at least one node; and

comparing the at least commutative error detection value from the first execution of the application program to the at least one commutative error detection value from the second execution of the application program.

39. The node fault detection apparatus of claim 38 where the node fault detection operations further comprise:

detecting a fault condition in one of the nodes of the computer system when there is a difference between the at least one commutative error detection value associated with the first execution of the portion of the application program and the at least one commutative error detection value associated with the second execution of the portion of the application program.

40. A node fault detection method for identifying faulty nodes in a computing system using commutative error detection values, where the computing system comprises a plurality of nodes, where each of the nodes comprises at least a node processor, a node memory, a network interface and a commutative error detection apparatus;

and a network connecting the plurality of nodes through the network interfaces of the nodes, and wherein node fault detection occurs when the computing system executes multiple portions of an application program at least twice, wherein during the first and second executions of the multiple portions of the application program a plurality of commutative error detection values are saved to the commutative error detection apparatus of the plurality of nodes when the nodes inject information generated during execution of reproducible segments of the multiple portions of the application program into the network, the method comprising;

during the first execution and second executions of the multiple portions of the application program, retrieving the commutative error detection values from the commutative error detection apparatus associated with the plurality of nodes;

saving the plurality of commutative error detection values associated with at least the first execution of the multiple portions of the application program to a computer memory medium; and

comparing on a node-by-node basis the plurality of commutative error detection values associated with the first execution of the multiple portions of the application program to the plurality of commutative error detection values associated with the second execution of the multiple portions of the application program, where at least one difference in commutative error detection values between the first and second executions of the application program indicates a node fault condition.

41. The node fault detection method of claim 40 wherein comparing the plurality of commutative error detection values further comprises:

comparing sequences of commutative error detection values generated during the first and second executions of the multiple portions of the application program to determine when a first difference in commutative error detection values occurred between the first and second executions of the multiple portions of the application program; and

tracing the fault to a particular node that generated the first difference in commutative error detection values.