[gclist] Impl, terminate & obviousness

[Arturo Bejar]

This posting adresses implementation, terminate messages, obviousness, 
and a bit of IP stuff.

>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.

I agree with the need for a formal proof and work, if only these 
deadlines didn't keep popping up... :P

>How can you do that? If A is reachable, dropping B would be a disaster.
>But you are inducing an unecessary "failure". This is a bug not a failure.

Yes and no, perhaps the way I adressed the issue was incorrect, let me 
expound, in our implementation by construction there is no way for A to 
become reachable, in Java all of the pointers are strong, and if a 
reference to A leaves the machine it set up a strong remote reference. So 
A would not be reachable.

>>We could follow a more agressive strategy for cleaning up the cycle by 
>>sending terminate messages, but those could be spoofed,
>I'm not sure, but I believe that Matt Fuch's addresses this point in his 
>paper. Even if it is spoofed, you are still no worse off than you are with 
>your algoritm.

Fuchs assumes that pervasive encryption will be available to keep 
malicious messages from happenning, which will probably eventually be 
true and will lead to an interesting application. Right now taking that 
approach would be expensive, and the biggest difference is that his 
terminates get propagated to the IRG, sort of telling the objects that 
are pointing at you that they are garbage (hence the security issues). 
Dropping forward references on the other hand is a a different ballgame, 
the pointers you hold to other remote objects are inside your trust 
boundary and you can do whatever you want with them. If you drop them it 
is up to the other machine to decide wether it will collect the objects 
or not. Another, smaller advantage is that we don't actually have to 
implement terminate since the standard cleanup will take care of it.

>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."

Trying to adress the issue of originality, or lackof thereof ;)

We're all building on each other's work, and I believe there is no use 
tearing down each other's work in petty ways, if you find a hole in my 
posting, cool!.

I've seen remarks that describe this algorithm as a Depth First Search 
(which I will contest in a moment), which would be analogous to calling 
Fuch's algorithm just a graph coloring algorithm (which it is), that is 
not the point, we're combining different tools in our CS arsenal to solve 
different problems.

This algorithm is is a combination of a search and a topological sort, 
what is important about it is not how it finds, but rather how it doesn't 
find a local root, it is not formally a DFS because it never sends a 'not 
found' message, now some people implement DFS in a way that it doesn't 
overlap which gets closer to what this algorithm does, but if they still 
traverse a branch looking for something and if they don't find it they 
send back a 'not found' for that branch, those combined with the 
non-overlapping will give the result. The algorithm focuses purely on the 
non-overlapping aspect of thing, if you look this up in Robert's 
Combinatorics it is called a topological sort of a hamiltonian chain, and 
oddly enough it is two sections after the formal definition of a DFS ;), 
but again arguing about this is probably a waste of time, if it is, or it 
isn't, so what?

The important part is that if anybody has seen this documented in this 
context before I would appreciate the reference.

IP Stuff:

I don't want to talk about IP issues too much, The IP protection that we 
filed for did not try to cover any of the work that has been published 
before, as far as we knew, and gave credit to all the prior art we could 
find (including Fuchs which was the most recent publication that we could 
find), what we did only covers certain key aspects of the way we did 
things. Speaking for myself: When I worked at other places, including 
IBM, I refused to patent stuff afraid that the company would use it to 
hamper the field which goes against my principles. Before we proceeded 
here I spoke with management (After all a company pays for its 
intelectual property, it has the right to protect it), and I know that 
they will to the right thing, that's why they allowed me to post the 
description and hopefully they will allow me to post the implementation 
too so that everybody can tear at it. If there are licensing issues I'm 
sure (speaking for myself, not EC) they will only be related to 
commercial implementations and I'm sure that they will be liberal, we're 
not in the dgc business... Check out www.communities.com to see what 
we're about.

Take care,
Arturo

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