[gclist] Collecting distributed cyclic garbage.

[Matthew Fuchs]

Giuliano:

This is essentially a restatement of the algorithm I presented at IWMM
'95 last September.  The paper, "Garbage Collection on an Open
Network", is in LNCS 986 or is accessible from my Web page (and in my
Disseration).  For independent work, you've done a good job.  Sorry -
I always hate being scooped.

If you look at my paper, you'll see I added a few wrinkles to handle
deadlock, when to run the algorithm, and getting all the additional
garbage out of the inverse trace.  I also recommend you look at the
paper by Maheshwar and Liskov, which has a decentralized algorithm for
forward tracing, but which requires mobility.  Contact me if you have
any questions.

If you (or anyone else) are interested in implementing an inverse
tracing algorithm, let me know.

Good Luck,

Matthew Fuchs
matt@wdi.disney.com
http://galt.cs.nyu.edu/students/fuchs

> 
> This message desicribes an algorithm for reclaiming distributed
> cyclic garbage.
> 
...
> 
> I apologize in advance to any one who has already developed an
> algorithm like this. My ties to the academic world are non-existent,
> and I'm unaware of much that happens there. Please let me know if
> I just re-invented the wheel.
> 
...
> Back-Searching to Collect Distributed Cyclic Garbage.
> 
> ABSTRACT:
> 
> This algorithm reclaims distributed cyclic garbage by
> "back-searching". It is designed for a client/server style of
> processing using proxies to represent objects located in a remote
> address space.
> 
> Back-searching inverts the traditional tracing collector's operation.
> Rather than tracing live objects, it traces through "zombie" objects.
> A zombie appears to be dead, but may on inspection still be live.
> A zombie object is one which is:
> 	remotely referenced
> 	locally unreachable
> 	has not been recently mentioned in an RPC
>