[gclist] Re: Garbage collection FAQ: distributed systems

[Marc Shapiro]

In response to my contribution to the GC FAQ, on distributed GC,
cef@geode.geodesic.com (Charles Fiterman) added:

 || Distributed Treadmill with synchronization.
 ||
 ||   Independent processors do their own gc treating externally held
 ||   pointers as roots.

"Treating externally held pointers as roots" is called Partitioned GC or
Hybrid GC (described a little bit later in my contribution).

The idea is that when some subset of the global memory (e.g. a process) sends
a pointer to another subset, that pointer is recorded in a "scion set" (akin
to a remembered set).  You keep a count of such inter-subset references.
Thus, each subset can independently and locally perform tracing of any kind
(hence the name "partitioned GC").  Inter-subset references are
reference-counted (hence the name "Hybrid GC").

The big difference between a remembered set and a scion set is that in the
former case the memory subsets are ordered, so no cycles of garbage can form.
In the latter case there is no natural ordering and inter-subset garbage
cycles cannot be collected.

Variations on this theme have to do with doing the whole job more efficiently
and tolerating faults (my own work on SSP Chains), collecting cycles of
garbage that span subsets (Hughes, or Lang Queinnec and Piquer), avoiding
expensive memory synchronization and I/O operations (my own work on Larchant),
using the counting information to choose the best subset to trace (Cook Wolf
and Zorn, or Rosenblum and Ousterhout), or avoiding problems with transaction
aborts (Amsaleg and Franklin).  I will stick some references at the end of
this message for those interested.

 || At synchronization time
 || unavalable processors are regarded as keeping all their known pointers.

This part I don't understand.  The whole point of the hybrid scheme is that
processes never need to synchronize.  Only available processes can delete
scions, so there is never any safety problem.  (There is a liveness problem of
course but that is inherent.)

                                                        Marc

@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
}

@Article{fic:885bis,
  author = 	 "Mendel Rosenblum and John K. Ousterhout",
  title = 	 "The Design and Implementation of a Log-Structured
		  File System",
  journal = 	 tocs,
  year = 	 1992,
  volume = 	 10,
  number = 	 1,
  pages = 	 "26--52",
  month = 	 feb
}

@InProceedings{gc:rep:953,
  author = 	 "Lang, Bernard and Queinnec, Christian and Piquer, Jos\'{e}",
  title = 	 "Garbage Collecting the World",
  booktitle = "Proc.\ of the 19th Annual {ACM} SIGPLAN-SIGACT
		  Symp.\ on Principles of Programming Lang.",
  year = 	 1992,
  address = 	 "Albuquerque, New Mexico ({USA})",
  month = 	 jan
}

@TechReport{sor:nom:1083,
  author = 	 "Shapiro, Marc and Dickman, Peter and Plainfoss\'{e}, David",
  title = 	 "{SSP} Chains: Robust, Distributed References
		  Supporting Acyclic Garbage Collection",
  institution =  inria,
  year = 	 1992,
  type = 	 "Rapport de Recherche",
  number = 	 1799,
  address = 	 rocquencourt,
  month = 	 "nov",
  note =         "Also available as Broadcast Technical Report \#1",
}

@InProceedings{gc:mv:rep:sor:1227ter,
  author = 	 "Shapiro, Marc and Ferreira, Paulo",
  title = 	 "Larchant-{RDOSS}: a Distributed Shared Persistent
		  Memory and its Garbage Collector",
  booktitle = 	 "Workshop on Distributed Algorithms (WDAG)",
  year = 	 1995,
  editor =	 "J.-M. H\'elary and M. Raynal",
  number =	 972,
  series =	 "Springer-Verlag LNCS",
  pages =	 "198--214",
  address =	 "Le Mont Saint-Michel (France)",
  month =	 sep
}

@InProceedings{gc:prs:1260bis,
  author = 	 "Amsaleg, Laurent and Gruber, Olivier and Franklin, Michael",
  title = 	 "Efficient Incremental Garbage Collection for
		  Workstation-Server Database Systems",
  booktitle =	 "Proc.\ 21st Very Large Data Bases (VLDB) Int.\ Conf.",
  year =	 1995,
  address = 	 "Z{\"u}rich (Switzerland)",
  month =	 sep
}

@InProceedings{mv:rep:gc:alg:1324,
  author = 	 "Ferreira, Paulo and Shapiro, Marc",
  title = 	 "Garbage Collection in the {L}archant Persistent
		  Distributed Store",
  booktitle = 	 "Proc.\ of the 5th Workshop on Future Trends in
		  Distributed Computing Systems (FTDCS'95)",
  year = 	 1995,
  address =	 "Cheju Island (Republic of Korea)",
  month =	 aug
}