[gclist] Distributed Garbage Collection Revisited 1

[H.C.C.Rodrigues]

Dear GC-LIST members,

My name is Helena Rodrigues. I am a PhD student at the University of Kent, UK.
I am working on distributed garbage collection as well.
I am implementing a distributed algorithm for collecting cycles on the Network
Objects system from DEC. My algorithm is based on the work by Richard Jones
and Rafael Lins on partial mark-sweep and the idea of groups.

I was studying all the stuff lately presented and I have some
comments/questions about it. I think they are addressed to all the authors/works
presented.

You all seem to agree about the need of some barrier to catch the changes of
the local IRG. Giuliano said:

>However, while the local mutator can't make a stub locally reachable, some remo
te mutator may.
>A locally unreachable stub's IRG can be altered, if the space recieves a messag
e which
>mentions one of the scions which can reach the stub. This can be detected by ma
intaining a
>barrier. Any scion mentioned by a message is marked dirty. Among other conditio
ns, a stub is
>considered reachable if one of the scions in its IRG is marked dirty. This may
temporarily
>prevent an unreachable stub from being collected. But that isn't a big deal. Wh
at is important
>is that this guarantees that a stub is not reclaimed too early.

>g

I think that the degree of conservatism you mentioned here is important. In
your back search you can find some object marked locally reachable by the last
local collector which is not locally reachable in the current state. This would
make you giving up and some amount of work will be wasted!

Furthermore, I think the algorithm is more complicated. I think there is a
problem of termination introduced by the barriers. It may happen that a local
collection is performed during the first or second trace. This local collection
would delete the "dirty" information and consequently live objects can be
wrongly collected or it would be necessary another confirming trace, and
another.....

Matthew Fuchs's algorithm, whenever a new incoming reference appears, it
starts a new distributed trace along that path instead of doing a confirming
trace. In this case, how do you terminate?


I would like to know what do you think about this.
Thank you.
Helena Rodrigues.