[gclist] Re: gclist-digest V1 #70

[Matthew Fuchs]

Giuliano,

> 
> >More importantly, I think this algorithm is incorrect.  The mutator can be
> >concurrently affecting the graph in a way that tricks this algorithm.
> 
> As you noted later, this is easily handled with a write barier.
> 
> Arturo claims to handle this without a write barrier, but I'm very suspicious of 
> that claim. I'll need to look at his algorithm more closely. Even if it satisfies 
> my meager intellect, I'd still be a bit suspicious until a proof were 
> constructed. While academics sometimes neglect practical hands on testing of 
> their constructs, we industrial types have a habit of neglecting formal analysis.
> 

The following was my response to Marc which shows why his scenario is
incorrect.  The basic point is that we assume the IRG is constantly
maintained, as per Marc's own work on SSP chains.

>
> > 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
> >                     ^                    |
> >                     |                    |
> >                     ----------------------
> > 
> Remember that acyclic garbage is generally handled by SSP Chains, or
> the equivalent, so the backpointer (which I call the inverse reference
> graph) is always correct.  This changes the events of your scenario as below.
>
> > 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)
>
>         * between these two, x must have found out about B, so at
>           some point x had pointers to both A and B, and at another
>           to both B and C.  Both B and C now know they are alive
>           (unless we are considering garbage processes, as Kafura described)
>
> >         B sends areYouRooted to A
>        
>         * C sends areYouRooted to x because it has not yet heard from
>           all its children.  B may also send areYouRooted to x,
>           depending on timing
>
> >         x := x.next.next     (x now points to B)
>
>         * A sends areYouRooted to x
>           B does likewise if it hadn't already
>
> >         A sends areYouRooted to C
>
>         * somewhere in here, if x isn't a garbage process, it has
>           responded alive to A, B, and/or C before any of the rest
>           can happen
>
> >         C responds Disregard to A
>        
>         * nope, responds Alive to A
>
> >         x := x.next          (x now points to C)
> >         A responds Disregard to B
>        
>         * nope, responds Alive to B
>
> >         x := x.next          (x now points to A)
> >         B responds Disregard to C
>        
>         * nope, responds Alive to C
>
> >         C self-destructs
>
>         * the preceding doesn't happen
>
> >         x := x.next.next     Program crashes!
>         
>         * program doesn't crash
>
> > 
> > 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.
> > 
> The barrier happens because either 
> 1) a node knows it is alive when contacted by a new node (if no
>    garbage processes).
> 2) any new references are traced before returning to the parent.
>
> There are the following messages on each side:
>
> x gets B's address from A        | C sends areYouRooted to B
>                                  | B receives areYouRooted
> x contacts B                     | B sends areYouRooted to A 
> x removes its pointer from A     | A sends areYouRooted to C
> x contacts C                     | C answers A
> x removes its pointer from B     | A answers B
> x contacts C                     | B answers C
> x removes its Pointer from C     |
>
> x must remove its pointer to B before B receives areYouRooted and not
> establish its pointer with C until after B answers C.  This cannot be
> done, at least assuming that each process handles messages serially. 
>

> >Uugh!  On principle I am opposed to such claims of intellectual property on
> >any algorithm.
> 
> I lean in this direction. At the very least, obtaining a patent should require 
> much more inventive work than demonstrated here. As Arturo admits, using an IRG 
> was pioneered by others. And once you have the IRG, tracing it is should not be 
> considered so inventive as to deserve a patent. I mean, how hard is the thought 
> process: "Hmmm. Tracing forward is hard. But, there is an IRG. AHA! Let's trace 
> it."
> 

I'd like to think that tracing the IRG was original at the time, but
that's not the question here.  Arturo's claim to originality appears
to lie in using the Disregard message, but this is standard for doing
a depth-first search.  So, if we discount the IRG, then the claim lies
on how one traverses it.  Ask a group of CS grads the following
question:

"Suppose you have an arbitrary directed graph and you need to traverse
it to see if there are any nodes with a particular property (i.e., you
have a predicate to apply to each node).  What algorithm would you
use?" 

I predict that the vast majority will respond "Depth-first-search --
obviously!" 

> But this is out of our hands. Lawyers have far more clout than we do. They've 
> hoodwinked the politicians into believing that progress in CS will be impeded 
> without patent protection. Despite 30 to 40 years of evidence to the contrary.
> 
> >In this particular case, you have no basis, because the
> > algorithm has been published by others before.
> 
> I guess this depends on whether the patent was filed before the dates of 
> publication. Arturo: when was the application filed? Marc: what are the 
> publication dates you are aware of.
> 

The "previous publication" is mine, and is in LNCS 986.  From my
interactions with EC, I'm almost sure that publication preceded their
filing.  However, publication is not the only way to establish prior
knowledge.  That was my second submission, plus I've communicated with
several people about this for 3 years, which is why it seemed so
familiar to Marc, and I've kept around a lot of old email, plus I have
the previous submission with file dates of mid-94.  So several people
knew the idea even before publication.