Distributed Garbage Collection for Network Objects

  • Andrew Birrell ,
  • Ted Wobber

116 |

Also appeared as SRC Note 66

In this report we present a fault-tolerant and efficient algorithm for distributed garbage collection and prove its correctness. The algorithm is a generalization of reference counting; it maintains a set of identi fiers for processes with references to an object. The set is maintained with pair-wise communication between processes, so no global synchronization is required. The primary cost for maintaining the set is one remote procedure call when an object reference is transferred to a new process for the first time. The distributed collector collaborates with the local collector in detecting garbage; any local collector may be used, so long as it can be extended to provide notification when an object is collected. In fact, the distributed collector could be used without a local collector; in that case, the programmer would insert explicit dispose commands to release an object. The algorithm was designed and implemented as part of the Modula-3 network objects system, but it should be suitable for a wide range of applications. It tolerates communication and process failure, and can reclaim the space for objects held by a crashed process. The algorithm balances functionality, performance, and fault-tolerance in a way that makes it highly practical to use in implementing distributed systems.