[gclist] Re: gclist-digest V1 #70

[Marc Shapiro]

>From: Arturo Bejar <arturo@communities.com>
>Date: Fri, 7 Jun 96 17:47:39 +0100
>Subject: [gclist] Dgc algorithm for catching cycles
>
>When a suspect node [a] is to be inspected it generates a big random
>identifier (n) and sends a AreYouRooted(n) message is sent to all the
>objects in the IRG of [a].
>
>For every object in the IRG of [a] including it the following rules apply:
>
>1. Whenever an object [x] receives an AreYouRooted(n) message:
>
>1.1 If the object is locally rooted in that machine it replies with a
>Yes(n) message.
>
>1.2 Otherwise, if it is the first time it has heard of (n) it stores the
>identifier and sends a AreYouRooted(n) message to all the objects that
>are referring remotely.
>
>1.3 *this is the key* If it has (n) already stored it replies with a
>Disregard(n) message.
>
>2. For every object in the IRG of [a] except [a] that is processing (n):
>
>2.1 If a single Yes(n) message comes back it replies with a Yes(n).
>
>2.2 Otherwise if all the responses it was waiting for are Disregard(n),
>it replies with a Disregard(n).
>
>3. For [a]
>
>3.1 If a single Yes(n) comes back it becomes remote rooted and waits for
>either a remote reference to it to drop, or time to pass, or any other
>criterion before becoming suspect again.
>
>3.2  If all the responses it was waiting for are Disregard(n) it
>self-destructs, with it breaks it and the cycle gets cleaned up by
>consequence.

In other words: you go through the (inverse) graph until you get back to
yourself; then you go back to where you came from (yourself again).  If
this succeeds and you have encoutered no object reachable from a local
root, you conclude you are on a cycle of garbage.

I reiterate my comment that you might as well go forward because it is less
costly.

More importantly, I think this algorithm is incorrect.  The mutator can be
concurrently affecting the graph in a way that tricks this algorithm.
Consider this simple graph:

           x -----> A -------> B ------> C
                    ^                    |
                    |                    |
                    ----------------------

x is a root pointer accessible to the mutator.  Each object A, B, C has a
field 'next' pointing to the next one in the circular list.  The following
actions occur:

        C sends areYouRooted to B
        x := x.next.next     (x now points to C)
        B sends areYouRooted to A
        x := x.next.next     (x now points to B)
        A sends areYouRooted to C
        C responds Disregard to A
        x := x.next          (x now points to C)
        A responds Disregard to B
        x := x.next          (x now points to A)
        B responds Disregard to C
        C self-destructs
        x := x.next.next     Program crashes!

To make the algorithm correct you need to add a write barrier between the
forward and backward pass.  Even then, I would not trust it until I see a
proof and an implementation.

>Electric Communities is seeking intellectual property protection on the
>key aspects of the algorithm, at the same time it is more than open to
>discussion of very liberal licensing terms for interested commercial
>parties.

Uugh!  On principle I am opposed to such claims of intellectual property on
any algorithm.  In this particular case, you have no basis, because the
algorithm has been published by others before.

                                                Marc