[gclist] Four color distributed objects algorithm.

[Charles Fiterman]

> From maki!iecc.com!majordom Tue Mar 19 05:05 CST 1996
> >Received: from ivan.iecc.com by maki.wwa.com with smtp
> 	(Smail3.1.29.1 #3) id m0tyyqP-000rena; Tue, 19 Mar 96 04:40 CST
> Date: Tue, 19 Mar 1996 11:06:36 +0100
> From: Marc Shapiro <shapiro@prof.inria.fr>
> To: gclist@iecc.com
> Cc: gclist@iecc.com
> Subject: Re: [gclist] Four color distributed objects algorithm.
> 
>  || 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.

Not so. A new mark message may result in unmarking objects known
to be marked by a previous message but will not mark any new objects
as either they are marked by the previous message or marked as a 
result of being pointed to since the previous mark message.

Missing the new mark message will result in keeping objects longer
than required but not in deleting objects erroniously. Thus it
is safe.