[gclist] - with adding Linda to distributed GC

[Matthew Fuchs]

Gustavo:

Have you considered a Linda implementation of your algorithm?  I'm not
a Linda fan personally, but some of the ideas in your approach sound
like they might map really nicely to Linda's distributed structures.

You might even be able to have a gc arise in a completely asynchronous
fashion, i.e., objects start looking for gc tuples when they think
they might be garbage, and any object in the operation which discovers
it is alive can eat the tuple at once.  

I can't speak to the efficiency of it, but it could be a pretty
elegant approach.

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

> 
> In my approach all the state related to a back tracing is represented
> by a single token-message that has a list of the ids of the proxies
> involved in the back tracing. The token-message is first created for
> a suspect. When the token is created, all the ids of the proxies whose
> scions reach the suspect are added to the token. The token is sent to
> the node where the next unvisited proxy lives. Then it determines if
> any of the proxies in the list is reachable from a local root. If this
> is the case, the token is discarded. Otherwise the current proxy is
> marked visited in the token, and all the proxy ids of the unvisited
> proxies whose scions reach the current proxy are added to the token.
> When all the proxies in the token have been visited, the objects these
> proxies represent are garbage. However this is only true if the
> back-references have not changed since the token was created.
> To verify that the back-references have not changed, a verification
> phase starts. The verification phase is described below. (If this
> explanation seems unfamiliar to you, I would recommend you to read
> the report first).
>