[gclist] Four color distributed objects algorithm.

[Marc Shapiro]

 || Date: Fri, 8 Mar 1996 13:45:50 -0600
 || From: cef@geode.geodesic.com (Charles Fiterman)
 || 
 || When processor A requests a reference to something on processor B,
 || B sends out that reference and stores the fact on a list of pending
 || new references.
 ||
 || When processor A blacks a grey object that contains a reference to
 || another machine it saves the fact on a list for that machine. When
 || processor A completes a collection cycle it sends a message to B
 || saying which references it has greyed and which it recieved since
 || the last such message but which are now white.

Let's call this a "mark" message.

 || Processor B then uses this list to grey used items and mark reference
 || messages as recieved. Unrecieved reference messages are resent and
 || their objects greyed.

So: collection on processor B cannot proceed past the mark phase until it has
received the mark message from A.  Symmetrically (supposing there are
references from B to A) the collector on A cannot proceed past its mark phase
until it has received the mark message from B.  Since the mark message from B
might cause more objects to be marked by A, A may have to send another mark
message to B.  (And symmetrically of course.)  So, neither A nor B may
continue past the mark phase until each one has received the LAST mark message
from the other.  Ensuring this requires a termination protocol or a global
synchronization between all processors.

                                                Marc