[gclist] Impl, terminate & obviousness

[Giuliano Carlini]

Arturo,

I'm intrigued by the possibilities you claim for your algorithm, but I 
just don't see how they are correct. Perhaps I'm just not understanding 
you correctly, or perhaps we have different definitions for fundamental 
concepts. I'm hoping you'll be willing to explain in more detail. I'm not 
trying to be a smart-ass. Please forgive any poor choice of words I may use. 
I'm just trying to understand your algorithm.

First, you say that your algorithm does not use a depth first search. It 
appears to me to be so. Could you explain what differentiates you search order 
from a depth first search?

Marc presented an example with a reachable cycle ABC, in which the cycle is 
reclaimed. I was confused by your reply. So, given Marc's example, is the 
cycle reclaimed or not?

In particular, you mention a barrier design to handle this, but then seem to 
indicate that you don't use a barrier. Do you or don't you? If you don't use a 
barrier, how do you avoid falsely reclaiming a cycle if the IRG changes?

Then you say that a second method is to not destroy a "suspect", but to just 
destroy the references to it and from it. Is this what you do in the case Marc 
presents? If so, it seems like a bug to me. In your reply to a question 
regarding this, you gave a reply I didn't understand. Could you explain a bit 
more fully.

You also reject terminate messages, partly because they can be spoofed. But 
any of the messages you rely on could also be spoofed. In particular if 
"disregard" is spoofed, objects could be falsely reclaimed. This seems 
inconsistent. What don't I understand about what you are doing?

You discount encryption as a solution to spoofing. Why?

How do you handle the case where you have a large cycle, say A-B-C-...-X-Y-Z.
With such a large cycle, it is likely that several nodes will decide to 
initiate a search of the IRG at roughly the same time. Do all proceed without 
interacting with the others? If so, your algorithm is O(N^2) which is a 
problem for a huge network like the Internet. Or do they try to cooperate to 
avoid duplicating work? In this case you must avoid deadlocks. How do you do 
this?

If all are allowed to proceed, the algorithm works but is expensive. They can 
of course cooperate to avoid duplicating work. In this case, a node which has 
received AreYouRooted(I) and which then receives AreYouRooted(n) will not 
forward AreYouRooted(n). It simply waits for the replies to AreYouRooted(I), 
and reponds to both the senders of AreYouRooted(I) and AreYouRooted(N). The 
problem is that this will deadlock if implemented naively.


Best Regards,

g