[gclist] Hughes' algorithm

[Marc Shapiro]

Topic is Hughes' algorithm for doing a distributed trace.  A reference is
provided at the end for those who would like to jump in.

 || From: wilson@cs.utexas.edu (Paul R. Wilson)
 || Date: Thu, 21 Mar 1996 09:51:04 -0600
 || 
 || Suppose I have a very long list, which takes a very long time to traverse.
 || Initially, everything has mark 0---it's never been traversed at all.
 || For simplicity, assume that this list is so long we'll never actually
 || finish tracing it.

Then the global minimum (GC timestamp threshold) will never get any higher
than 0, and nothing will be collected.  It's safe.

As long as ANY process still has a 0 mark to propagate, then the global
minimum will not make any progress.

 || I start a mark 1 going around the system, and it makes a little headway
 || on this list.  Later, I start mark 2, and again later I start mark 3.
 || 
 || At some point, all of the 1 marks may get clobbered by 2's or 3's,
 || even if the list has never been traversed completely.

That's fine.  That means that everything that could be reachable from a 1 mark
is also reachable from a 2 or 3 mark.  If there are no more 1 marks left to be
propagated, that means that all 1 traces have been caught up by 2 and 3
traces, so it's safe to increase the threshold to 1.

                                                Marc

Reference:

@InProceedings{gc:rep:685,
  author = 	 "John Hughes",
  title = 	 "A Distributed Garbage Collection Algorithm",
  editor = 	 "Jouannaud, Jean-Pierre",
  number = 	 201,
  series = 	 "Lecture Notes in Computer Science",
  pages = 	 "256--272",
  booktitle = "Functional Languages and Computer Architectures",
  year = 	 1985,
  publisher = "Springer-Verlag",
  address = 	 "Nancy (France)",
  month = 	 sep
}