[gclist] Four color distributed objects algorithm.

Charles Fiterman cef@geode.geodesic.com
Fri, 8 Mar 1996 13:45:50 -0600


We start with a four color collector of some sort on each processor.

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.

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.

If a processor goes down ultimately it will either come up
or be declared dead by the system admisistrator. At which point
it will resurrect zero or more references to other machines.
It will then send these references as greyed as well as reciepts
for any pending reference messages. Dead systems are obvious.

There are no synchronization points and systems may go down or
become unaccessable. Out of sequence or lost messages are not
a problem.