[gclist] Re: gclist-digest V1 #68

[Matthew Fuchs]

> 
> >If you look carefully, you'll see that terminate messages are only
> >actually necessary when there cycles.
> 
> Precisely the point.
> 
> According to the paper the algorithm is of (5n) complexity in a worst 
> case scenario, where n is a call return over the wire so it is actually 2 
> messages (for checking the status of the neighbouring node, and figuring 
> out the coloring). As with these algorithms real use will usually not 
> bring out the worst case scenarios.
> 

No, it's 5n _messages_ - a call return is 2 messages - and the 5n only
occurs when everything is alive and in a cycle.  As you mention, worst
case scenarios are rare.

Please address the question of the upper limit of the number of times
a garbage node or live node is touched over a large number of
collection operations, which is where the difference appears.  As you
know, I came up with the simple DFS algorithm three years ago, but
have worked on improving it to handle the difficult cases.

The simple DFS has no upper bound, even for reasonable scenarios.
The simplified algorithm assumes that once a garbage cycle is found (and
eventually broken after some undetermined number of GC operations,
since only one node in the cycle knows it is garbage at a time) it is
collected acyclicly.  You must add this cost to the cost of the DFS,
which makes your lower bound of messages per garbage node my upper
bound.  I have also shown how I can use the additional information to
bound the number of messages per live node as a proportion of all
messages, although, of course it is not possible to put an absolute
bound. 

> We have a working implementation (for Java) of a different algorithm, 
> somewhat similar to the one posted by giuliano@ix.netcom.com (I'm sorry I 
> don't know your name), but it doesn't deadlock.  I hope to post it to the 
> mailing list soon.

If all you are presenting is a DFS of the inverse graph, then it is
really nothing new, although it is always nice to see one's ideas
implemented.  In the meantime, please present us with some analysis of
your algorithm to address the issues I've raised and why it is more
efficient over the long term (not for a single GC).

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