Transparent consistent semi-active and passive replication of multithreaded application programs

• US 7,228,452 B2
• Filed: 03/25/2003
• Issued: 06/05/2007
• Est. Priority Date: 03/25/2002
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: Availigent, Inc.
• Inventors: Melliar-Smith, Peter M., Moser, Louise E.
• Primary Examiner(s): Baderman; Scott
• Assistant Examiner(s): LOHN, JOSHUA A
• Application Number:
  US10/400,137
• Publication Number:
  US 20040078618A1
• Time in Patent Office: 1,533 Days
• Field of Search: 714/12
• US Class Current: 714/4.1
• CPC Class Codes: G06F 11/1482 by means of middleware or OS functionality
• CPC Class Codes: G06F 11/1492 by run-time replication performed by the application software
• CPC Class Codes: G06F 11/20 using active fault-masking, e.g. by switching out faulty elements or by switching in spare elements
• CPC Class Codes: G06F 2201/82 Solving problems relating to consistency
• CPC Class Codes: G06F 2209/542 Intercept
• CPC Class Codes: G06F 2209/546 Xcast
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms
• CPC Class Codes: G06F 9/542 Event management; Broadcasting; Multicasting; Notifications

Abstract

A system and method for replicating a multithreaded application program using a semi-active or passive replication strategy, wherein the application program executes under the control of an operating system having a thread library. The method comprises piggybacking mutex ordering information at the Primary replica onto regular multicast messages specifying the order in which threads in the Primary replica have been granted their claims to mutexes; and receiving the multicast messages at a Backup replica containing the mutex ordering information which determines the order in which threads in the Backup replica are granted mutexes. Thread library interpositioning is preferably utilized to intercept calls to functions in the operating system'"'"'s thread library, so that the system and method of the invention may be implemented transparently. The invention enforces strong replica consistency without the need to count instructions, add significant messaging overhead, or modify application code.

Claims

1. A method for replicating a multithreaded application program using a semi-active or passive replication strategy, wherein said application program executes under the control of an operating system having a thread library, the method comprising:

at a Primary replica, piggybacking mutex ordering information onto regular multicast messages specifying the order in which threads in the Primary replica have been granted their claims to mutexes; and

at a Backup replica, receiving said messages containing said mutex ordering information which determines the order in which threads in said Backup replica are granted mutexes;

wherein said messages are multicast according to a protocol that delivers messages reliably and in the same order from the Primary replica to said Backup replicas.

3. A method as recited in claim 1 or 2, further comprising:

employing thread library interpositioning to intercept calls to functions in the operating system'"'"'s thread library.

2. A method for replicating a multithreaded application program using a semi-active or passive replication strategy, wherein said application program executes under the control of an operating system having a thread library, the method comprising:

at a Primary replica, piggybacking mutex ordering information onto regular multicast messages specifying the order in which threads in the Primary replica have been granted their claims to mutexes; and

at a Backup replica, receiving said messages containing said mutex ordering information which determines the order in which threads in said Backup replica are granted mutexes;

wherein strong replica consistency is maintained without

counting the number of instructions between non-deterministic events,

additional messages for claiming, granting and releasing each mutex, and

risk that a result might be communicated to a client but the Backup replicas might lack ordering information necessary for reproducing said result.

4. A method comprising:

for replicating a multithreaded application program using the semi-active or passive replication strategy, wherein said application program executes under the control of an operating system having a thread library, the method comprising;

employing thread library interpositioning to intercept calls to functions in the operating system'"'"'s thread library to render said application program virtually deterministic;

at a Primary replica, piggybacking mutex ordering information onto regular multicast messages specifying the order in which threads in the Primary replica have been granted their claims to mutexes; and

at a Backup replica, receiving said messages that determine the order in which threads in said Backup replica are granted mutexes.

5. A method for replicating a multithreaded application program using the leader-follower strategy of semi-active or passive replication, wherein said application program executes under the control of an operating system having a thread library, the method comprising:

at a Primary replica, piggybacking mutex ordering information onto regular multicast messages specifying the order in which threads in the Primary replica have been granted mutexes;

at a Backup replica, receiving said messages that determine the order in which threads in said Backup replica are to claim mutexes; and

employing thread library interpositioning to intercept calls to functions in the operating system'"'"'s thread library for performing said piggybacking and for controlling said order in which threads in said Backup replica are granted their claims to mutexes.

6. A method as recited in claim 5, wherein if the Primary replica does not have a regular message to multicast, it multicasts a control message containing said mutex ordering information.

7. A method as recited in claim 5, wherein a thread in said Backup replica is not allowed to claim a given mutex, for a given claim, until said Backup replica receives a multicast message that contains said mutex ordering information for said claim from said Primary replica.

8. A method for replicating a multithreaded application program using a semi-active or passive replication strategy, wherein said application program executes under the control of an operating system having a thread library, the method comprising:

providing a consistent multithreading library that is interposed ahead of said operating system'"'"'s thread library so that calls to functions of the operating system'"'"'s thread library can be intercepted to render said application program virtually deterministic;

said virtual determinism enables strong replica consistency to be maintained;

said consistent multithreading library contains wrapper functions for intercepting calls to functions in said operating system'"'"'s thread library;

said application program invokes said wrapper functions of said consistent multithreading library instead of the corresponding functions of said operating system'"'"'s thread library; and

wherein in response to a Primary replica invoking a function of said consistent multithreading library to claim a mutual exclusion construct (mutex), said function invokes the corresponding function of the operating system'"'"'s thread library to claim said mutex and piggybacks mutex ordering information onto regular messages multicast to Backup replicas.

9. A method as recited in claim 8, wherein the invocation of a claim function to claim a mutex by a thread in said Primary replica comprises invoking a claim function of said consistent multithreading library and subsequently piggybacking ordering information onto the next message multicast.

10. A method as recited in claim 8, wherein said consistent multithreading library mechanisms allow concurrency of threads that do not simultaneously acquire a same mutex.

11. A method as recited in claim 8

wherein if the application program runs on an operating system that provides Dynamically Linked Libraries (DLL), the DLL mechanisms are used to interpose the consistent multithreading library ahead of said operating system'"'"'s thread library;

and

wherein said interpositioning causes the application program to invoke said functions of said consistent multithreading library, instead of the corresponding functions of said operating system'"'"'s thread library.

12. A method as recited in claim 11, further comprising inserting a command into the makefile for said application program directing the linker to interpose said consistent multithreading library ahead of said operating system'"'"'s thread library.

13. A method for replicating a multithreaded application program using a semi-active or Passive replication strategy, wherein said application program executes under the control of an operating system having a thread library, the method comprising:

providing a consistent multithreading library that is interposed ahead of said operating system'"'"'s thread library so that calls to functions of the operating system'"'"'s thread library can be intercepted to render said application program virtually deterministic; and

communicating mutex ordering information as messages from said primary replica to said Backup replica specifying the order in which threads in said Primary replica have been granted mutexes to establish the order in which threads in said Backup replica are to claim mutexes;

wherein said message are communicated using a reliable source-ordered multicast group communication protocol;

wherein said multicast protocol delivers messages reliably and in the same source-order to the Backup replicas;

wherein said mutexes are granted in the same source-order to the threads at said Backup replicas; and

wherein said communicating mutex ordering information comprises piggybacking mutex ordering information onto regular multicast messages.

14. A method as recited in claim 13, wherein if the Primary replica does not have a regular message to multicast, it multicasts a control message containing said mutex ordering information.

15. A method as recited in claim 13, wherein said communicating said mutex ordering information comprises multicasting two messages, one message multicast by a first Primary replica to the replicas of other processes, objects or components and another message multicast by a second Primary replica of said other processes, objects or components to first said Primary replica and its Backup replicas.

16. A method of achieving strong replica consistency for a replicated multithreaded application programs using the semi-active or passive replication strategy, comprising:

sanitizing multithreaded application programs by masking multithreading as a source of non-determinism to render said replicated multithreaded application program virtually deterministic

wherein said sanitizing comprises;

piggybacking mutex ordering information onto regular multicast messages from a Primary replica that specifies the order in which threads in the Primary replica have been granted mutexes; and

delivering said messages to a Backup replica that determine the order in which threads in said Backup replica are granted the mutexes that they claim.

17. A method as recited in claim 16, wherein said delivering of messages comprises delivering of two multicast messages, one message multicast by a first Primary replica to the replicas of other processes, objects or components and one message multicast by a second Primary replica of said other processes, objects or components to first said Primary replica and its Backup replicas.

18. A method as recited in claim 16, wherein said delivering using a reliable source-ordered multicast group communication protocol to deliver messages from the Primary replica to the Backup replica.

19. A method as recited in claim 16, further comprising employing thread library interpositioning to intercept calls to functions of the operating system'"'"'s thread library for performing said piggybacking and for controlling said order in which threads in said Backup replica are granted the mutexes that they claim.

20. A method as recited in claim 19, wherein a thread T in said Backup replica is not allowed to claim a given mutex M, for a given Nth time that thread T has claimed any mutex, until it receives said message from said Primary replica that contains the ordering information (T, M, N).

21. A method of achieving strong replica consistency for a replicated multithreaded application programs using the semi-active or passive replication strategy, comprising:

sanitizing multithreaded application programs by masking multithreading as a source of non-determinism to render said replicated multithreaded application program virtually deterministic;

wherein if said Primary replica does not have a regular message to multicast, it multicasts a control message containing said mutex ordering information.

22. A method for replicating a multithreaded application program using a semi-active or passive replication strategy, wherein said application program executes under the control of an operating system, said method comprising:

using a multicast group communication protocol to render the multithreaded application program virtually deterministic;

said virtual determinism enables strong replica consistency to be maintained;

intercepting calls to the functions of the operating system'"'"'s thread library; and

multicasting ordering information from said Primary replica to said Backup replicas, regarding the order in which threads in the Backup replicas are to be granted their claims to mutexes;

wherein said multicasting of ordering information comprises piggybacking said ordering information onto regular messages that are multicast from said Primary replica to said Backup replicas.

23. A method as recited in claim 22, further comprising:

using a mutex to protect shared resources accessed by threads in said application program;

wherein said threads are granted access to said shared resources in the same order at the replicas of said application program.

24. A method as recited in claim 22, wherein said ordering information describes the order in which threads in said Primary replica are granted their claims to mutexes and which is delivered reliably and in the same order to said Backup replicas.

25. A method as recited in claim 22, wherein said means of multicasting and piggybacking said ordering information uses two multicast messages, one message multicast by first said Primary replica to the replicas of other processes, objects or components and one message multicast by second Primary replica of said other processes, objects or components to first said Primary replica and its Backup replicas.

26. A method as recited in claim 22, wherein if said Primary replica does not have a regular message to multicast, it multicasts a control message containing said ordering information.

27. A method as recited in claim 22, further comprising:

maintaining strong replica consistency and application transparency by interpositioning a consistent multithreading library ahead of the operating system'"'"'s thread library and intercepting calls to functions in said operating system'"'"'s thread library.

28. A method as recited in claim 27,

wherein functions of said operating system'"'"'s thread library are wrapped by functions of said consistent multithreading library;

wherein the application program invokes the wrapper functions of said consistent multithreading library, instead of the corresponding functions of said operating system'"'"'s thread library, thereby maintaining strong replica consistency and application transparency.

29. A method as recited in claim 28, wherein said wrapping is performed by dynamically linking said consistent multithreading library to said application program.

30. A software mechanism, embodied on a computer readable medium, program using a semi-active or passive replication strategy, wherein said application program executes under the control of an operating system having a thread library, the mechanism comprising:

control program code;

said control program code at a Primary replica, being configured to piggyback mutex ordering information onto regular multicast messages for specifying the order in which threads in the Backup replicas are granted their claims to mutexes;

said control program code configured to deliver said control messages using a multicast group communication protocol that delivers the messages in an order that determines the order in which the threads in different replicas are granted their claims to mutexes.

31. A software mechanism as recited in claim 30, further comprising a consistent multithreading library containing said control program code that is interpositioned for intercepting calls to functions of the operating system'"'"'s thread library.

32. A software mechanism, embodied on a computer readable medium, replicating a multithreaded application program using a semi-active or passive replication strategy, wherein said application program executes under the control of an operating system having a thread library, the mechanism comprising:

a consistent multithreading library that is interposed ahead of the operating system'"'"'s thread library so that calls to functions of said operating system'"'"'s thread library can be intercepted to render said application program virtually deterministic;

said virtual determinism enables strong replica consistency to be maintained;

said consistent multithreading library contains wrapper functions for intercepting calls to functions of said operating system'"'"'s thread library;

said application program invokes said wrapper functions of said consistent multithreading library instead of the corresponding functions of said operating system'"'"'s thread library;

wherein when a Primary replica invokes a function of the consistent multithreading library to claim a mutex, said consistent multithreading library function invokes the corresponding function of said operating system'"'"'s thread library and subsequently piggybacks ordering information onto the next message that it multicasts.

33. A software mechanism as recited in claim 32, wherein said multicasting said ordering information uses two multicast messages, one message multicast by first said Primary replica to the replicas of other processes, objects or components and one message multicast by second Primary replica of said other processes, objects or components to first said Primary replica and its Backup replicas.

34. A software mechanism as recited in claim 32, wherein if said Primary replica does not have a regular message to multicast, it multicasts a control message containing said ordering information.

35. A software mechanism as recited in claim 34, wherein said message is multicast using a reliable source-ordered multicast group communication protocol.

36. A software mechanism as recited in claim 35:

wherein said source-ordered multicast protocol delivers messages reliably and in the same source order from the Primary replica to the Backup replicas; and

wherein the mutexes are granted in the same order to the threads in the Backup replicas as in the Primary replica, as dictated by the ordering information piggybacked within said messages.

37. A software mechanism as recited in claim 32:

wherein if the application program runs on an operating system that provides Dynamically Linked Libraries (DLL), the dynamic linking mechanisms are used to interpose the consistent multithreading library ahead of the operating system'"'"'s thread library; and

wherein said interpositioning causes the application program to invoke the functions of the consistent multithreading library, rather than the corresponding functions of the operating system'"'"'s thread library.

38. A software mechanism as recited in claim 32, further comprising dynamically linking said consistent multithreading library to said application program and interposing said consistent multithreading library ahead of said operating system'"'"'s thread library to maintain transparency to the application program and the operating system.

39. A software mechanism, embodied on a computer readable medium, achieving strong replica consistency using a semi-active or passive replication strategy for replicating multithreaded application programs, comprising:

control program code configured to sanitize multithreaded application programs by masking multithreading as a source of non-determinism;

library interpositioning of said control program code to intercept calls to functions of the operating system'"'"'s thread library for sanitizing said multithreaded application programs;

wherein when a Primary replica invokes a wrapper function of said consistent multithreading library to claim a mutex, said consistent multithreading library function invokes the corresponding function of said operating system'"'"'s thread library and then piggybacks ordering information onto the next message that it multicasts to the Backup replicas.

40. A software mechanism as recited in claim 39, wherein said control program code comprises a consistent multithreading library containing wrapper functions for said functions of said operating system'"'"'s thread library that claim and release mutexes.

41. A software mechanism as recited in claim 39, wherein said multicasting uses two multicast messages, one message multicast by first said Primary replica to the replicas of other processes, objects or components and one message multicast by second Primary replica of said other processes, objects or components to first said Primary replica and its Backup replicas.

42. A software mechanism as recited in claim 39, wherein if said Primary replica does not have a regular message to multicast, it multicasts a control message containing said ordering information.

43. A software mechanism, embodied on a computer readable medium, replicating a multithreaded application program using a semi-active or passive replication strategy, wherein said application program executes under the control of an operating system having a thread library, the mechanism, comprising

a consistent multithreading library that is interposed ahead of said operating system'"'"'s thread library;

said consistent multithreading library contains wrapper functions for functions of said operating system'"'"'s thread library;

said wrapper functions ensure that the threads in the replicas are granted their claims to mutexes in the same order, and similarly for releasing mutexes;

said application program invokes the wrapper functions of said consistent multithreading library instead of the corresponding functions in said operating system'"'"'s thread library; and

wherein when a Primary replica invokes a function of said consistent multithreading library to claim a mutex, said function invokes the claim function of the operating system'"'"'s thread library and subsequently piggybacks mutex ordering information onto the next regular message that it multicasts.

44. A software mechanism as recited in claim 43, wherein said regular message is multicast using a reliable source-ordered multicast group communication protocol.

45. A software mechanism as recited in claim 44:

wherein said multicast protocol delivers messages reliably and in the same source order from the Primary replica to said Backup replicas; and

wherein the mutexes are granted in the same order to the threads in said Backup replicas as dictated by the mutex ordering information piggybacked onto said multicast messages.

46. A software mechanism as recited in claim 45, wherein said granting of mutexes in the same order maintains strong replica consistency.

47. A software mechanism as recited in claim 46, wherein said multicasting uses two multicast messages, one message multicast by first said Primary replica to the replicas of other processes, objects or components and one message multicast by second Primary replica of said other processes, objects or components to first said Primary replica and its Backup replicas.

48. A software mechanism as recited in claim 47, wherein if said Primary replica does not have a regular message to multicast, it multicasts a control message containing said mutex ordering information.

49. A software mechanism as recited in claim 43:

wherein if the application program runs on an operating system that provides Dynamically Linked Libraries, the dynamic linking mechanisms are used to interpose the consistent multithreading library ahead of the operating system'"'"'s thread library; and

wherein said interpositioning causes the application program to invoke the functions of said consistent multithreading library, rather than the corresponding functions of said operating system'"'"'s thread library.

50. A software mechanism as recited in claim 43, further comprising dynamically linking said consistent multithreading library to said application program and interposing said consistent multithreading library ahead of said operating system'"'"'s thread library to maintain transparency to the application program and the operating system.

51. A software mechanism, embodied on a computer readable medium, replicating a multithreaded application program using a semi-active or passive replication strategy, wherein said application program executes under the control of an operating system, said mechanism comprising:

control program code;

said control program code configured to use mutex ordering information piggybacked on regular messages multicast by a source-ordered group communication Protocol from the Primary replica, which dictates the order in which the threads in the Backup replicas are granted their claims to mutexes, to render the replicated multithreaded application program virtually deterministic;

wherein if said Primary replica does not have a regular message to multicast, it multicasts a control message containing said mutex ordering information.

52. A software mechanism, embodied on a computer readable medium, replicating a multithreaded application program using a semi-active or passive replication strategy, wherein said application program executes under the control of an operating system, said mechanism comprising:

control program code;

said control program code configured to use mutex ordering information piggybacked on regular messages multicast by a source-ordered group communication protocol from the Primary replica, which dictates the order in which the threads in the Backup replicas are granted their claims to mutexes, to render the replicated multithreaded application program virtually deterministic;

said control program code is configured to intercept calls to the operating system'"'"'s thread library;

wherein strong replica consistency and application transparency are maintained by interpositioning said consistent multithreading library ahead of said operating system'"'"'s thread library and intercepting calls to functions of said operating system'"'"'s thread library;

wherein said functions of said operating system'"'"'s thread library are wrapped by functions of said consistent multithreading library; and

wherein said application program invokes the wrapper functions of said consistent multithreading library, instead of the corresponding functions of said operating system'"'"'s thread library, thereby maintaining strong replica consistency and application transparency.

53. A software mechanism, embodied on a computer readable medium, replicating a multithreaded application program using a semi-active or passive replication strategy, wherein said application program executes under the control of an operating system, said mechanism comprising:

control program code;

said control program code configured to use mutex ordering information piggybacked on regular messages multicast by a source-ordered group communication protocol from the Primary replica, which dictates the order in which the threads in the Backup replicas are granted their claims to mutexes, to render the replicated multithreaded application program virtually deterministic;

wherein said control program code is configured to allow concurrent processing of threads that do not claim the same mutex simultaneously and threads that claim different mutexes; and

wherein strong replica consistency is maintained.

54. A software mechanism, embodied on a computer readable medium, replicating a multithreaded application program using a semi-active or passive replication strategy, wherein said application program executes under the control of an operating system, said mechanism comprising:

control program code;

said control program code configured to use mutex ordering information piggybacked on regular messages multicast by a source-ordered group communication protocol from the Primary replica, which dictates the order in which the threads in the Backup replicas are granted their claims to mutexes, to render the replicated multithreaded application program virtually deterministic;

wherein said control program code is configured to allow threads to communicate with each other by multicasting messages;

wherein said control program code is configured to allow threads to use shared resources; and

wherein strong replica consistency of the different replicas is maintained.

55. A system for executing threads that share resources, within a computing environment that supports semi-active or passive replication of multithreaded application programs, comprising:

means for identifying requests for accesses to shared resources by threads in the Primary replica;

means for communicating to one or more Backup replicas the order in which said requests are granted to threads in said Primary replica; and

means for ordering and granting requests for accesses to shared resources by threads in a Backup replica, in response to the order in which corresponding requests were granted to threads in said Primary replica and communicated by said Primary replica to said Backup replica;

wherein said means of communicating information, about claims for shared resources by threads in said Primary replica and about the order in which said claims were granted, comprises piggybacking said information on a message, multicast by said Primary replica to its Backup replicas.

58. A system as recited in claim 55, 56 or 57, wherein said Primary replica dictates the order in which said threads in said Backup replicas are granted access to shared resources, as communicated by said Primary replica to said Backup replicas.

59. A system as recited in claim 55, 56 or 57, wherein control programming for said means for communicating and said means for ordering and granting are contained in, or are invoked by, functions of a consistent multithreading library.

60. A system as recited in claim 59, wherein to render said application programs virtually deterministic in a transparent manner, said system employs library interpositioning to intercept calls to functions of the operating system'"'"'s thread library and to direct them to said functions of said consistent multithreading library, which in turn invoke said functions of the operating system'"'"'s thread library.

61. A system as recited in claim 60, further comprising dynamically linking said consistent multithreading library to said application program and interposing said consistent multithreading library ahead of said operating system'"'"'s thread library.

62. A system as recited in claim 60, further comprising inserting a command into the makefile for the application program directing the linker to interpose said consistent multithreading library ahead of said operating system'"'"'s thread library.

63. A system as recited in claim 60, wherein functions of said consistent multithreading library are configured as a set of functions incorporated within the operating system'"'"'s thread library.

64. A system as recited in claim 55, 56 or 57, wherein said means for communicating comprises a reliable source-ordered multicast protocol which guarantees that said Backup replicas receive the messages from said Primary replica in an identical order, as multicast by said Primary replica.

65. A system as recited in claim 55, 56 or 57, wherein a shared resource comprises data configured for being shared between threads in a given replica or code sections configured for manipulating shared data or both.

66. A system as recited in claim 55, 56 or 57, wherein said shared resource is configured for being accessed by a thread utilizing a mutual exclusion construct (mutex).

67. A system as recited in claim 66, wherein a request by a thread of said Backup replica to access a mutual exclusion construct is not granted until the message from the Primary replica that contains information about the ordering and granting of said request is delivered to said Backup replica.

68. A system as recited in claim 55, 56 or 57, wherein said means for communicating to multiple replicas comprises a computing environment configured for providing reliable source-ordered multicasting of messages to Backup replicas in response to grants of requests to access shared resources by threads in said Primary replica.

69. A system as recited in claim 55, 56 or 57, wherein said means for communicating, and said means for ordering and granting, comprise functions that maintain strong replica consistency.

70. A system as recited in claim 69, wherein said means for granting accesses to shared resources to threads in a Backup replica comprises a computing environment that grants said accesses, based on the availability of said resources and on the order in which accesses to corresponding resources were granted to threads in said Primary replica and were communicated by said Primary replica and received by said Backup replica from said means for communicating.

71. A system as recited in claim 70, wherein within said Backup replica said means for ordering and granting is configured to grant a specific thread access to a specific shared resource for a specific claim if said Primary replica has previously communicated that the corresponding thread in said Primary replica has been granted access to the corresponding shared resource for the corresponding claim.

72. A system as recited in claim 71:

wherein said access to said shared resource is controlled by a mutual exclusion construct;

wherein a thread in said Backup replica is not granted said mutual exclusion construct for a given claim until said Primary replica has communicated that the corresponding thread in said Primary replica has been granted access to the corresponding shared resource for the corresponding claim.

56. A system for executing threads that share resources, within a computing environment that supports semi-active or passive replication of multithreaded application programs, comprising:

means for identifying requests for accesses to shared resources by threads in the Primary replica;

means for communicating to one or more Backup replicas the order in which said requests are granted to threads in said Primary replica; and

means for ordering and granting requests for accesses to shared resources by threads in a Backup replica, in response to the order in which corresponding requests were granted to threads in said Primary replica and communicated by said Primary replica to said Backup replica;

wherein said means of communicating information comprises piggybacking information, about claims for shared resources by threads in first said Primary replica and about the order in which said claims were granted, on two or more messages, one message multicast by first said Primary replica to the replicas of other processes, objects or components and one message multicast by second Primary replica of said other processes, objects or components to first said Primary replica and its Backup replicas.

57. A system for executing threads that share resources, within a computing environment that supports semi-active or passive replication of multithreaded application programs, comprising:

means for identifying requests for accesses to shared resources by threads in the Primary replica;

means for communicating to one or more Backup replicas the order in which said requests are granted to threads in said Primary replica; and

means for ordering and granting requests for accesses to shared resources by threads in a Backup replica, in response to the order in which corresponding requests were granted to threads in said Primary replica and communicated by said Primary replica to said Backup replica

wherein lacking regular multicast messages on which to piggyback ordering information, said means for communicating is configured to multicast a control message containing information about claims for shared resources by the threads in said Primary replica and about the order in which said claims were granted.

73. A system for maintaining strong replica consistency of replicas of a multithreaded application program within a computing environment, using semi-active or passive replication, comprising:

means for communicating the order in which access to a shared resource is granted to a thread in the Primary replica; and

means for ordering and granting access to a shared resource to threads in a Backup replica in response to the order of granting access to a corresponding shared resource by a corresponding thread in said Primary replica;

wherein said means for communicating to multiple replicas comprises a computing environment configured for providing reliable source-ordered multicasting of messages to Backup replicas in response to granting of accesses of shared resources by threads in said Primary replica; and

wherein said means of communicating information, about accesses to shared resources by threads in said Primary replica and about the order in which said accesses were granted, comprises piggybacking said information on a message, multicast by said Primary replica to its own Backup replicas.

76. A system as recited in claim 73, 74 or 75, wherein said Primary replica dictates the order in which said threads in said Backup replica are granted access to shared resources, as communicated by said means of communicating to said Backup replica.

77. A system as recited in claim 76, wherein said means for granting access to shared resources comprises a computing environment that grants said access to said shared resources, based on the availability of said shared resources and on the order in which corresponding accesses to shared resources were granted to the corresponding thread at said Primary replica and were communicated by said Primary replica and received by said Backup replica from said means for communicating.

78. A system as recited in claim 73, 74, or 75, wherein said means for determining the order in which threads can access shared resources comprises a mutual exclusion construct that is granted to a thread in response to a claim to access the resource, and which is then later released by said thread allowing said mutual exclusion construct to be claimed by other threads.

79. A system as recited in claim 78, wherein said means for communicating is configured to communicate the order in which threads in said Primary replica are granted said mutual exclusion construct.

80. A system as recited in claim 78, wherein said means for ordering and granting of accesses to threads in a Backup replica is configured to grant a mutual exclusion construct to said Backup replica as determined by the order in which the corresponding mutual exclusion construct was granted to the corresponding thread in said Primary replica, which order was communicated by said Primary replica to said Backup replica.

81. A system as recited in claim 80, wherein a thread in said Backup replica is not granted a mutual exclusion construct for a given claim until said Primary replica has communicated that the corresponding thread in said Primary replica has been granted the corresponding mutual exclusion construct to the corresponding shared resource for the corresponding claim.

82. A system as recited in claim 73, 74 or 75, wherein said means for communicating, and said means for ordering and granting, comprise functions that maintain strong replica consistency and are executed in response to calls to functions of a consistent multithreading library.

83. A system as recited in claim 82, wherein said functions of said consistent multithreading library are configured to intercept calls to corresponding functions of the operating system'"'"'s thread library.

84. A system as recited in claim 83, further comprising dynamically linking said consistent multithreading library to said application program and interposing said consistent multithreading library ahead of said operating system'"'"'s thread library.

85. A system as recited in claim 83, further comprising inserting a command into the makefile for the application program directing the linker to interpose said consistent multithreading library ahead of said operating system'"'"'s thread library.

86. A system as recited in claim 82, wherein functions of said consistent multithreading library are configured as a set of functions incorporated within the operating system'"'"'s thread library.

87. A system as recited in claim 82, wherein said functions of said consistent multithreading library comprise functions configured for claiming or releasing shared resources in a manner in which corresponding threads in different replicas are granted access to the shared resource in an identical order.

88. A system as recited in claim 73, 74 or 75, wherein said means for ordering and granting resource accesses in each said Backup replica is configured to order and grant said accesses in response to the order in which information about the claiming and granting of corresponding accesses to shared resources by corresponding threads in said Primary replica is communicated by said Primary replica to said Backup replica.

89. A system as recited in claim 73, 74 or 75, wherein said means for ordering and granting access to shared resources by threads in said Backup replica is configured to prevent said granting of shared resources until information about the claiming and granting of corresponding accesses to shared resources by corresponding threads in said Primary replica has been communicated to said Backup replica by said Primary replica.

90. A system as recited in claim 89, wherein said means for communicating to multiple replicas comprises a computing environment configured for providing reliable source-ordered multicasting of messages by said Primary replica to said Backup replicas in response to the granting of accesses to shared resources by threads in said Primary replica.

91. A system as recited in claim 90, wherein said means for ordering and granting of accesses to shared resources is configured to maintain an order of granting said accesses to threads in said Backup replicas that is identical to the order in which corresponding accesses are granted to threads in said Primary replica and are communicated to said Backup replicas by said Primary replica.

92. A system as recited in claim 73, 74 or 75, wherein said multicast messages comprise information about which shared resource is being claimed by a thread in said Primary replica, which thread is claiming the given shared resource, and which shared resource claim request of said thread is being made.

93. A system as recited in claim 73, 74 or 75:

wherein said means for communicating, and said means for ordering and granting, are configured for being executed transparently to said application program;

wherein said transparency comprises the inclusion of said means for communicating and said means for ordering and granting within said computing environment without modifying the code of said multithreaded application program.

94. A system as recited in claim 93, further comprising dynamically linking said consistent multithreading library to said application programming and interposing said consistent multithreading library ahead of said operating system'"'"'s thread library.

95. A system as recited in claim 93, further comprising inserting a command into the makefile for the application program directing the linker to interpose said consistent multithreading library ahead of said operating system'"'"'s thread library.

96. A system as recited in claim 93, wherein functions of said consistent multithreading library are configured as a set of functions incorporated within the operating system'"'"'s thread library.

97. A system as recited in claim 73, 74 or 75, wherein said means for communicating and said means for ordering and granting are provided by interposing a consistent multithreading library ahead of said operating system'"'"'s thread library and by intercepting calls of functions of said operating system'"'"'s thread library and by invoking instead corresponding functions of said consistent multithreading library, which in turn invoke functions of said operating system'"'"'s thread library.

98. A system as recited in claim 73, 74 or 75, wherein strong replica consistency can be maintained without the need to count the number of instructions between non-deterministic events.

99. A system as recited in claim 73, 74 or 75, wherein said computing environment comprises a client-server system or a fault-tolerant system or both.

100. A system as recited in claim 73, 74 or 75, wherein said shared resource comprises data shared between said threads in a given replica, or code for accessing said shared data in a given replica or both.

74. A system for maintaining strong replica consistency of replicas of a multithreaded application program within a computing environment, using semi-active or passive replication, comprising:

means for communicating the order in which access to a shared resource is granted to a thread in the Primary replica; and

means for ordering and granting access to a shared resource to threads in a Backup replica in response to the order of granting access to a corresponding shared resource by a corresponding thread in said Primary replica;

wherein said means for communicating to multiple replicas comprises a computing environment configured for providing reliable source-ordered multicasting of messages to Backup replicas in response to granting of accesses of shared resources by threads in said Primary replica; and

wherein said means of communicating said information comprises piggybacking information, about the granting of accesses to shared resources by threads in first said Primary replica and about the order in which said accesses were granted, on two or more messages, one message multicast by first said Primary replica to the replicas of other processes, objects or components and one message multicast by second Primary replica of said other processes, objects or components to first said Primary replica and its Backup replicas.

75. A system for maintaining strong replica consistency of replicas of a multithreaded application program within a computing environment, using semi-active or passive replication, comprising:

means for communicating the order in which access to a shared resource is granted to a thread in the Primary replica; and

means for ordering and granting access to a shared resource to threads in a Backup replica in response to the order of granting access to a corresponding shared resource by a corresponding thread in said Primary replica;

wherein said means for communicating to multiple replicas comprises a computing environment configured for providing reliable source-ordered multicasting of messages to Backup replicas in response to granting of accesses of shared resources by threads in said Primary replica; and

wherein lacking regular multicast messages on which to piggyback ordering information, said means for communicating is configured to multicast a control message containing information about the granting of corresponding accesses to corresponding shared resources by corresponding threads in said Primary replica and about the order in which said accesses were granted.

101. A system for executing a replicated multithreaded application program within a computing environment, using a semi-active or passive replication strategy, comprising:

means for granting access to shared resources to threads in a Backup replica in response to information received about the order in which access to said shared resources was granted to corresponding threads in said Primary replica; and

means for communicating the order of granting access of shared resources by the Primary replica to the Backup replicas;

wherein said means for communicating information comprises a routine configured for multicasting messages from said Primary replica to said Backup replicas in response to the granting of accesses of shared resources to threads in said Primary replica;

wherein said means for communicating information, about the order of granting accesses to shared resources, by said Primary replica to said Backup replicas, comprises piggybacking said information on a message, multicast by said Primary replica to its Backup replicas.

102. A system as recited in claim 101, wherein lacking regular multicast messages on which to piggyback ordering information, said means for communicating is configured to multicast a control message containing information about the order of granting accesses to shared resources by the Primary replica to the Backup replicas.

104. A system as recited in claim 101 or 103, wherein said means for communicating, and said means for ordering and granting, comprise functions that maintain strong replica consistency.

105. A system as recited in claim 104, further comprising means for transparently executing said ordering and granting, and said means for communicating, without modifying the code of said application program.

106. A system as recited in claim 105, further comprising dynamically linking said consistent multithreading library to said application program and interposing said consistent multithreading library ahead of said operating system'"'"'s thread library.

107. A system as recited in claim 105, further comprising inserting a command into the makefile for said application program directing the linker to interpose said consistent multithreading library ahead of said operating system'"'"'s thread library.

108. A system as recited in claim 105, wherein functions of said consistent multithreading library are configured as a set of functions incorporated within the operating system'"'"'s thread library.

103. A system for executing a replicated multithreaded application program within a computing environment, using a semi-active or passive replication strategy, comprising:

means for granting access to shared resources to threads in a Backup replica in response to information received about the order in which access to said shared resources was granted to corresponding threads in said Primary replica; and

means for communicating the order of granting access of shared resources by the Primary replica to the Backup replicas;

wherein said means for communicating information comprises a routine configured for multicasting messages from said Primary replica to said Backup replicas in response to the granting of accesses of shared resources to threads in said Primary replica;

wherein said means of communicating information, about the order of granting accesses to shared resources by first said Primary replica to said Backup replicas, comprises piggybacking said information on two or more messages, one message multicast by first said Primary replica to the replicas of other processes, objects or components and one message multicast by second Primary replica of said other processes, objects or components to first said Primary replica and its Backup replicas.

109. A method of maintaining strong replica consistency for a replicated multithreaded application program, using the semi-active or passive replication strategy, comprising:

granting access requests for shared resources to threads in the Backup replicas in response to the order in which corresponding requests were granted to corresponding threads in the Primary replica;

wherein said granting of access requests is performed by employing library interpositioning to intercept calls to functions of the operating system'"'"'s thread library;

wherein said shared resources are accessed using a mutual exclusion construct;

wherein said granting of access requests comprises;

piggybacking information, about the order of granting mutual exclusion constructs to threads in said Primary replica, onto regular messages that are multicast from said Primary replica to said Backup replicas, and

delivering said messages to said Backup replicas, that determine the order in which threads in said Backup replica are granted their claims to mutual exclusion constructs;

wherein said piggybacking of information comprises piggybacking information about claims for shared resources by threads in first said Primary replica and about the order in which said claims were granted, on two or more messages, one message multicast by first said Primary replica to the replicas of other processes, objects or components and one message multicast by second Primary replica of said other processes, objects or components to first said Primary replica and its Backup replicas.

110. A method of maintaining strong replica consistency for a replicated multithreaded application program, using the semi-active or passive replication strategy, comprising:

granting access requests for shared resources to threads in the Backup replicas in response to the order in which corresponding requests were granted to corresponding threads in the Primary replica;

wherein said granting of access requests is performed by employing library interpositioning to intercept calls to functions of the operating system'"'"'s thread library;

wherein said shared resources are accessed using a mutual exclusion construct;

wherein said granting of access requests comprises;

piggybacking information, about the order of granting mutual exclusion constructs to threads in said Primary replica, onto regular messages that are multicast from said Primary replica to said Backup replicas, and

delivering said messages to said Backup replicas, that determine the order in which threads in said Backup replica are granted their claims to mutual exclusion constructs;

wherein if said Primary replica does not have a regular message to multicast, it multicasts a control message containing said information to said Backup replica.

111. A method as recited in claim 110, further comprising a consistent multithreading library executing said ordering and granting of access requests by intercepting calls to said operating system'"'"'s thread library.

112. A method of replicating multithreaded application programs in which threads access shared resources, within a computing environment that uses semi-active or passive replication, comprising:

claiming shared resources by a thread in the Primary replica;

granting said claim to said thread in said Primary replica;

communicating to the Backup replicas the order of granting said claim; and

granting the corresponding claim of a shared resource to a corresponding thread in each Backup replica, as determined by the order in which corresponding claims to shared resources were granted to corresponding threads in said Primary replica;

wherein said claiming, said communicating, and said granting are controlled by the functions of a consistent multithreading library that is interposed ahead of said operating system'"'"'s thread library so that calls to functions of the operating system'"'"'s thread library are intercepted to render said application program virtually deterministic;

wherein said communicating of said claim comprises piggybacking information onto regular multicast messages specifying the order in which threads in the Primary replica have been granted their claims to said mutual exclusion constructs.

113. A method as recited in claim 112, wherein said multicasting comprises piggybacking information, about claims for shared resources by threads in first said Primary replica and about the order in which said claims were granted, on two or more messages, one message multicast by first said Primary replica to the replicas of other processes, objects or components and one message multicast by second Primary replica of said other processes, objects or components to first said Primary replica and its Backup replicas.

114. A method as recited in claim 112, wherein if said Primary replica does not have a regular message to multicast, it multicasts a control message containing said order of granting information.

116. A method as recited in claim 112 or 115, wherein said shared resources are accessed by using a mutual exclusion construct.

115. A method of replicating multithreaded application programs in which threads access shared resources, within a computing environment that uses semi-active or passive replication, comprising:

claiming shared resources by a thread in the Primary replica;

granting said claim to said thread in said Primary replica;

communicating to the Backup replicas the order of granting said claim; and

granting the corresponding claim of a shared resource to a corresponding thread in each Backup replica, as determined by the order in which corresponding claims to shared resources were granted to corresponding threads in said Primary replica;

wherein said claiming, said communicating, and said granting are controlled by the functions of a consistent multithreading library that is interposed ahead of said operating system'"'"'s thread library so that calls to functions of the operating system'"'"'s thread library are intercepted to render said application program virtually deterministic;

wherein when said thread T of said Primary replica has been granted a mutual exclusion construct M for its Nth claim of any mutual exclusion construct, a message is multicast that contains the ordering information (T, M, N); and

wherein said granting in said Backup replica comprises granting the corresponding mutual exclusion construct M to the corresponding thread T in said Backup replica for the corresponding claim N, only if said ordering information (T, M, N) from said Primary replica has been delivered to, and received by, said Backup replica.

117. A method as recited in claim 115, wherein said claiming of a shared resource by a thread at said Primary replica comprises:

invoking the claim function to claim mutex M for thread T;

diverting the invocation from the claim function of the operating system'"'"'s thread library to the corresponding claim function of the consistent multithreading library;

determining the information (T, M, N) for a claim to a mutual exclusion construct by a thread in the Primary replica, wherein T represents the thread making said claim, M represents the mutual exclusion construct being claimed, and N represents the claim number by thread T to access any mutual exclusion construct;

granting the mutual exclusion construct M to thread T in the Primary replica;

appending the information (T, M, N) to the queue of claims to be multicast to the Backup replicas; and

multicasting messages including the piggybacked claim (T, M, N) to the Backup replicas.

118. A method as recited in claim 115, wherein said granting of a shared resource to a thread in said Backup replica comprises:

invoking the claim function to claim mutex M for thread T;

diverting the invocation from the claim function of the operating system'"'"'s thread library to the corresponding claim function of the consistent multithreading library;

determining the information (T, M, N) for a claim to a mutual exclusion construct by a thread in said Backup replica, wherein T represents the thread in said Backup replica making said claim, M represents the mutual exclusion construct being claimed, and N represents the claim number by thread T to access any mutual exclusion construct;

determining if (T, M, N) matches the next grant for mutex M, as directed by said communication from said Primary replica;

if so, mutex M is granted to thread T when mutex M is available; and

determining that (T, M, N) does not match the next grant for mutex M, according to the order of mutex granting dictated by said Primary replica, wherein said thread T is suspended until (T, M, N) is delivered to, and received by said Backup replica, and is the next grant of mutex M in the order dictated by said Primary replica.