[gclist] Dgc algorithm for catching cycles

[Matthew Fuchs]

> 
> Hi,
> 
> I apologise if I had not introduced myself earlier, but I've been working 
> hard to try and get this posted for everyone as soon as possible. My name 
> is Arturo Bejar and I am one of the senior engineers at Electric 
...
> 
> First some quick background:
> 
> - Piquer and Birrel did all the foundation work in using IRG for the 
> purpose of distributed garbage collection. Fuchs contributed to it in his 
> phd disertation, the url is: http://galt.cs.nyu.edu/students/fuchs, you 
> can find references to Piquer and Birrel in his paper.
> 

Actually, Piquer and Birrel never trace the IRG.  Both of them are
variations on reference counting which use back-pointers to make up
for the deficiencies of weighted reference counting (WRC).  Neither can
collect cycles.  In both cases, an object keeps pointers to the other
processes which point to it as a way of keeping track of the number of
references it has handed out.  Each decrement message now says where
it comes from, so none of the WRC shenanigans are necessary.  Again,
neither traces the graph in any way.  What I first pointed out back in
1993 is that if one _does_ do a depth-first search of this graph from
any particular object, then if it is alive, you will find a persistent
root, and if you don't then it (and its parents) are garbage,
regardless of cycles in the graph.  This goes far beyond Piquer and
Birrel and I'd call it foundational for using the IRG.

> 
> The idea for the algorithm came from topology, to be precise a 
> Topological Sort of a Hamiltonian Chain. A Hamiltonian Chain is where you 
> can come up with a full graph traversal where you touch each node once. A 
> topological sort is where you take cycles in the graph and you reduce 
> them. (massive simplification, for all the fellow mathematicians out 
> there I'll be happy to expound)
> 

This might have been your inspiration, but the algorithm as presented
appears to be a standard DFS.  You start at some node and do a DFS
looking for a root.  In any DFS, if a node has already been
encountered, you retreat rather than traversing a second time, which
is exactly what your Disregard message does.  In an open distributed
system, there may always be concurrent transactions, so it is
frequently necessary to put an identifier (your n) on each action.

By the way, if the graph is a DAG, then your algorithm may traverse
some nodes more than once, so its worst case performance for a single
traversal is actually O(n^2).  Once a subtree is traversed, it must
forget about n, since you don't have a terminate message and you don't
want to remember n forever.  In a DAG, the subtree may be encountered
another time, and traversed again (since it forgot n), in the same
operation. 

Matthew Fuchs
matt@wdi.disney.com
http://galt.cs.nyu.edu/students/fuchs