[gclist] Re: gclist-digest V1 #74

[Marc Shapiro]

>From: giuliano@ix.netcom.com (Giuliano Carlini)
>Date: Fri, 14 Jun 1996 08:29:57 -0700
>Subject: Re: [gclist] Re: gclist-digest V1 #70

>Why is it cheaper to go forward? The local IRG is computed during the local GC
>very cheaply.

I admit the local collector may compute the Inverse Reference Graph, which
will bring the cost of a reverse search down.  However, remember that a
standard tracing collector goes through any reachable object only once.
Therefore it will not give you the complete IRG.  Ex:

        A ----> B --> C  ------> D
                 \   /
                  \ /
                   X
                  / \
                 /   \
        E ----> F --> G  ------> H

If the trace starts with A, it will tell you about  A->D and A->H, but not
E->H and E->D.  Ladin and Liskov made a similar mistake in the first
version of their protocol.

You might conceivably extend the trace to handle this case, but it will
increase the cost (instead of being order of the number of reachable
objects, it will be order of the number of reachable paths).

Also, as soon as the mutator changes something, your local IRG may become
inconsistent with the reachability graph.  This may or may not be important
depending on the details of the algorithm.

                                                        Marc