[gclist] Re: gclist-digest V1 #70

[Matthew Fuchs]

Gustavo:

> 
> My name is Gustavo Rodriguez-Rivera. I am a Ph.D. student
> in the Computer Science Department at Purdue University.
> 
> More than a year ago (April 28, 1995) in my preliminary
> examination I proposed an algorithm for distributed garbage
> collection similar to the one Carlini and Fuchs describe.
> 

Does this mean that your algorithm will be the subject of your
disseration?

> 
> Also I would like to make the implementation of the distributed
> garbage collector work transparently with a commercial CORBA
> implementation such as ORBIX.
> 

This is a great idea.  I would suggest we start looking at standard
interfaces for DGC.

> 
> 
>        DIFFERENCES BETWEEN CARLINI's, FUCHS', AND MY APPROACH
>        ------------------------------------------------------
> 
> Carlini's, Fuchs' and my approach share the same concept of
> distributed garbage collection through back-tracing. However
> there are several differences in the proposals.
> 
> I consider that in order to implement the back tracing algorithm,
> there are at least four issues that have to be solved:
> 
> 	i.   How to obtain the back-references to do back-tracing.
> 		Local-back-references and Remote-back-references
> 
> 	ii.  How are garbage suspects (zombies or GCRs) determined?
> 
> 	iii. Need to synchronize multiple back-tracings running at
>              the same time
> 
> 	iv.  Back-references may change during back-tracing
> 
> 
> 1) Fuchs in his paper
> 
> 	http://galt.cs.nyu.edu/students/fuchs/dist-gc.ps
> 
> describes the basic back-tracing algorithm and addresses ii. and iii.
> However he assumes that back-references are already given (i.).
> He also does not explain how to handle changes in the back-references
> while the back-tracing is going on (iv.). The later could cause live
> objects to be erroneously collected. 
> 

Let me just address how I handle i. and iv.

i.  Marc Shapiro once took me to task (in email) for glibly passing
over this.  Erroneous algorithms have apparently been published in the
past.  However, as it obviously could be done, the exact algorithm was
not done was not directly relevant to my paper (although _very_
relevant to an implementation).  I am glad to see someone developing a
reasonably lightweight method, so my hat's off to you.

iv.  This is actually not a problem for my algorithm, although perhaps
I did not make that appropriately clear.  The DFS itself creates the
necessary barrier.  Since I assume either Piquer's or Birrel's
algorithm, there is always a complete tree for the graph, i.e., if you
were to stop time and trace from a node, if it were not garbage, a
root would be encountered.  Let me make one additional point clear, if
it is not clear from reading the paper - if an object finds out about
a new child in the inverse graph which it is traversing its children
it will trace that child as well (actually, if we don't include
collecting garbage processes, as discussed by Kafura, the object can
just assume it is alive).

Now, for a given object, delta, and a given DGC, a reference can
change either before delta is encountered in the traversal, while the
tree rooted at delta is being traversed, or after it has been left.
Now for the second case.  Given the way the backpointers are
implemented, for a new reference to delta to arise the following
sequence must occur somewhere in the inverse tree rooted at delta (in
Birrel's algorithm, gamma and delta are always the same object, in
Piquer's they are occasionally the same).


alpha----|
  |      |
  |      ----->gamma--...->delta
 \|/       
beta

alpha----|
  |      |
  |      ----->gamma--...->delta
 \|/     |
beta<----|

alpha
  |  
  |      ----->gamma--...->delta
 \|/     |
beta<----|

(NB, these are forward pointers)  

Now the traversal arrives at gamma either:

2) before the second graph happens in which case either:
   a) it also finishes traversing alpha before the second graph, in
      which case alpha is found to be alive.
   b) the second graph occurs before it is finished traversing alpha,
      in which case beta is traversed as well.
3) between the second third graphs, in which case both alpha and beta
   are traversed.
4) after the third graph has occured, in which case beta is definitely
   tranversed, and alpha as well if the reference from alpha to beta
   still exists.

Now, if we don't worry about garbage processes, the transition from
the first graph to the second graph is enough to establish that gamma,
and hence delta, is alive.  If we consider garbage processes, we need
still need to traverse as I've just outlined, and wherever processes
are encountered, both their back and forward references need to be
traced, as a process can always hand a reference to itself to some
live object is knows about (see Kafura's paper for more details).

In your case, you don't directly use the DFS to back trace, so you
can't use it as an implicit control structure, requiring the
synchronization. 

I'd be interested in seeing some formal analysis of the
runtime costs of the algorithm, and I'd be particularly interested in
how you'd address security concerns for an open network. 

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