[gclist] gclist-digest V2 #122

[Eliot Moss]

While Selgmann and Grarup reported the first implementation and experience
with the "Train Algorithm", it was actually devised by Rick Hudson and me in
the paper cited below, also available at the URL indicated.

Seligmann and Grarup found (minor) flaws, which they fixed, and we have
incorporated the fixes in our later work. These fixes relate to guaranteeing
progress; the algorithm as originally published could fail to make progress if
the mutator always switched pointers around in particular ways in between
invocations of the train algorithm. Lack of progress would be extrememly
unlikely in practice, but it is also not difficult to fix, though it reduces
the elegance of the algorithm and may affect promptness of collection
slightly. I can expound on all of this in more detail on another occasion if
there is interest.

I understand that Grarup is working for JavaSoft and that new/forthcoming JVMs
will incorporate the algorithm, as mentioned in InfoWorld last fall.

Since the 1992 paper, Rick and I, with additional collaborators, have devised
extensions to the Train algorithm for (a) collecting persistent object stores
(loosely, "databases") and (b) collecting objects in distributed
systems. These algorithms are being implemented by research groups in
Australia, and with luck we'll have reports on those activities in conferences
within a year or so.

@InProceedings{HuMo92,
  author = 	 "Richard L. Hudson and J. Eliot B. Moss",
  title = 	 "Incremental Collection of Mature Objects",
  crossref =  "iwmm92",
  pages = 	 "388--403"
}
@Proceedings{iwmm92,
  title = 	 "International Workshop on Memory Management",
  booktitle = 	 "International Workshop on Memory Management",
  year = 	 1992,
  editor = 	 "Yves Bekkers and Jacques Cohen",
  number =       637,
  series = 	 "Lecture Notes in Computer Science",
  publisher = "Springer-Verlag",
  address = 	 "St. Malo, France",
  month = 	 sep
}

ftp://ibis.cs.umass.edu/pub/papers/iwmm92.ps.Z

Regards to you all --						Eliot
==============================================================================
J. Eliot B. Moss, Associate Professor      http://www.cs.umass.edu/~moss   www
Computer Science Department, LGRC          +1-413-545-4206               voice
University of Massachusetts, Box 34610     +1-413-545-1249                 fax
Amherst MA  01003-4610  USA                moss@cs.umass.edu             email
==============================================================================