[gclist] Dgc algorithm for catching cycles

[Arturo Bejar]

Hi all,

Rick Hudson sent me the following concerns about the algorithm I posted 
earlier this weekend, the answer addresses issue (iv) raised by Gustavo 
Rodriguez-Rivera:

>	iv.  Back-references may change during back-tracing

Rick Hudson wrote: 

>Consider....
>
>We have 4 objects A B C and M. M is a rooted object that holds pointers for
>the Mutator. The A -> B-> C -| cyclic structure with a pointer from M
>                 ^-----------|
>
>to C. For this example assume no other pointers are relevant and A is 
>'suspect.'
>We used the rules you numbered below. 
>
>Rule 0.0 - B gets a AreYouRooted(n) message from A at time 1.  
>M creates a pointer to A at time 2  
>M destroys the pointer to C at time 3.  
>Rule 1.2 - B sends a AreYourRooted(n) message to C at time 4. 
>Rule 1.2 - C sends a AreYouRooted(n) to A at time 5. 
>Rule 1.3 - A sends a disregard(n) to C at time 6 (ignoring the pointer from
>           M).
>Rule 2.2 - C sends a disregard(n) to B at time 7. 
>Rule 2.2 - B sends a disregard(n) to A at time 8. 
>Rule 3.2 - A self destructs at time 9. M is left holding a 
>           pointer with a worthless A.
>
>There are other devious things M can do but this one is the simplest I could
>think of.
>
>Let me know what I missed.
>
>- Rick Hudson
>hudson@cs.umass.edu

Rick,

Thanks for your feedback. As you probably know a distributed system there 
is not much one can do about constantly changing references, there is no 
inexpensive way to establish a lock like you can with a local gc.

In a way, because of network latency, the algorithm is run for a very 
relative time t on the network, so on the way out the reference graph 
will be at time t for the first node, (t + latency), for any node node (t 
+ latency1 + ...), and then you add them on the way back, this would 
apply to any algorithm.

There are a number of ways to address your point, the formal way is that 
[A], as any other node can detect a change in the set of objects directly 
referring to it, and you have to choose a policy to address them, i.e. if 
while A is waiting for a response from B it notices that a new reference 
to it (from [M]) has showed up, so it sends a message with the same (n) 
to [M], which will be replied postively. If [M] is the same machine 
boundary as [A], [A] will just become locally rooted again.

We can tell these changes easily because we are using the mark & sweep of 
the local Java GC to build the inverse reference graph of a specific set 
of objects, which we then work on.

The second way of handling it is implementation related, we don't 
actually destroy A but we make it drop the remote references that it 
holds and the remote references to it (the pointer to B in this case), 
something that could happen in a network failure or partition, as is 
usual with distributed programming any object that has to talk to another 
across a machine boundary needs to be able to cope with failiure. Then we 
let the local GC clean it up.

We could follow a more agressive strategy for cleaning up the cycle by 
sending terminate messages, but those could be spoofed, if all of the 
machines that were running the algorithm were in a trusted boundary, like 
a company, then we can pursue much more agressive collection strategies.

Let me know what you think,
Arturo

___________________________________________________________________
Arturo Bejar                   "What you can see, you can achieve."
arturo@communities.com                          - J. Verne, sort of