Process for distributed garbage collection

In a distributed computer system having a plurality of concurrently active processes that have instantiated a plurality of objects in a memory associated with the distributed computer system, a method of operating the distributed computer system comprising the steps of:

• establishing a suspect list of a subset of said plurality of objects wherein said subset of objects are candidates for garbage collection;
• selecting a first object from said suspect list;
• defining an inverse reference graph for said first object wherein each object of said plurality of objects referentially coupled to said first object is represented as a node on said inverse reference graph and wherein edges define a referential relationship between any particular two objects of said plurality of objects;
• generating an identifier;
• transmitting a root request message, tagged with said identifier, to each of a plurality of referring objects of said first object as identified by said inverse reference graph;
• receiving a reply message, tagged with said identifier, from each object in a subset of said plurality of referring objects that is directly coupled to said first object, said reply message indicating whether any object in said subset of said plurality of referring objects is relevant to determine whether said first object is garbage;
• and
• identifying said first object as garbage when none of said reply messages, tagged with said identifier and received from said subset of referring objects indicates any object in said subset of said plurality of referring objects is relevant to determine whether said first object is garbage.

A computer system, comprising:

• a multiplicity of concurrently active processes executing on a plurality of machines for instantiating a plurality of objects;
• a memory, coupled to said plurality of machines, for storing said plurality of objects;
• and
• garbage identification means, coupled to said memory, for:
• maintaining a suspect list of a subset of said plurality of objects that are candidates for garbage collection;
• selecting a first object from said suspect list;
• generating an identifier;
• transmitting a root request message, tagged with said identifier, to each of a plurality of referring objects of said first object as identified by an inverse reference graph, wherein each object of said plurality of objects is represented as a node on said inverse reference graph and wherein edges define a referential relationship between any particular two objects of said plurality of objects;
• receiving a reply message, tagged with said identifier, from each object in a subset of said plurality of referring objects that is directly coupled to said first object, said reply message indicating whether any object in said subset of said plurality of referring objects is relevant to determining whether said first object is garbage;
• and
• identifying said first object as garbage when none of said reply messages, tagged with said identifier and received from said subset of referring objects, indicates any object in said subset of said plurality of referring objects is relevant to determining whether said first object is garbage.