[gclist] Distributed Garbage Collection Revisited 1

[H.C.C.Rodrigues]

Matthew,

>Will you be making a description of your algorithm available over the
>Web, or post it here?  Is this similar to Lang, et al.'s algorithm of
>ever growing groups?

I am preparing a camera-ready version for the WDAG96, that I will send to you
if you are intersted. I would like to get some comments from you.

>Since computation is not halted during DGC, it is inevitable that some
>garbage will not be collected, although one should certainly try to
>minimize this.  This is partly an implementation issue.  The local
>system can (should?) choose to perform a local GC, or briefly delay
>the algorithm until one can be performed, before continuing the
>distributed trace or replying.

I agree that the system can do that, but the algorithm would be very dependent
from the time a local collection is performed. May happen that the DGC returns
several times to the same processor. In this case I agree that an
implementation would be necessary to study theses cases.

>I assume by "confirming trace" you mean a local collection from the
>scions?  There are two ways to address this:
>1) Use a different bit for marking nodes involved in a DGC.
>2) Continue performing collections as before, which involves tracing
>   from the scions.  This will remark all the necessary nodes.

I didn't understand what do you mean with 1) and 2).
"confirming trace" is the token ("CHECK-SEQUENCE, ...) in Gustavo Algorithm,
and what Giuliano means when he says:

"The solution is to make a second pass, and to implement a "new
scion" barrier. This is similar to the write barrier used by
local collectors to determine that they must rescan an area of
memory."

>I am not sure I understand.  The algorithm would only not terminate if
>an infinite number of new incoming references appear before the
>distributed trace terminates.  The new incoming reference can only
>come to a scion, since there cannot be a remote reference to any
>object without a scion.  The new incoming reference can only belong to
>either:

I think it is not necessary an infinite number of new incoming references
appear before the distributed trace terminates to not terminate the algorithm.
We can have a cycle of objects spawning two processes being reachable from a
root either in one process or in the other. The DGC may never reach a root.

>1) A remotely rooted object.  If there are no garbage processes, we
>can just use this as proof the object is alive. 

I think the problem I presented does not exist if you consider the objects
 being remotely
accessed live. In this case I imagine that the back-search would terminate.
What would happen when a "grey" object is remoteley accessed?
Sorry If am thinking to much in an implementation level, but I think that it
was what is more important now. There are lots of algorithms in DGC
litterature, without being implemented.

I would like to ask as well to the people working in implementations, which
kind of applications/tests they are using?

Thank you,
Helena Rodrigues.