[gclist] Distr. GC general discussion for FAQ

[David Chase]

I've been wondering on and off for years, whether there was any role 
for randomization in some of these distributed GC algorithms, especially 
those that move data.  I'd hope that this did not seem completely 
off-the-wall; in hardware, networks use randomness to avoid hotspot 
contention at routing nodes, and super-duper-computers have been 
known to use hashing schemes for assigning addresses to memory banks 
to help avoid stride problems.  Ethernet protocols also incoprorate 
some notion of randomness (on collision, double(?) the backoff window, 
and retransmit at some randomly chosen time in the window).

So, has anyone else thought about this?  I was thinking of something 
along the lines of:

  objects with external references get (additional, local) finalizers

  the finalizer flips a coin, and either forwards the object to one
  of the external referers, or lets it sit for another round.  Or
  if it doesn't forward the object, maybe it forwards a description 
  of the link.

  (a miracle occurs here / the rest of the algorithm is left as
  an exercise)

Or, to look at it another way, there are otherwise-hard problems 
that have completely acceptable probablistic solutions.  Distributed 
GC is a hard problem.

It might make sense to restrict attention to the distributed 
detached-cycle-finding portion of the problem. (From experience in 
the land of flow analysis algorithms, I recall that the hardest incremental 
updates problems involve edge deletion; however, it is also the nature 
of the problem that once a subgraph is detached, it must stop changing 
its shape.) 

David