AVAILABLE ELECTRONICALLY			

"Distributed Garbage Collection for Network Objects"
Andrew Birrell, David Evers, Greg Nelson, Susan Owicki, Edward Wobber
December 15, 1993.  18 pages

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 identifiers 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 formaintaining 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 localcollector 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.