[gclist] Termination of global trace

[Marc Shapiro]

Context: discussion a distributed tracing algorithm.  Charles says it can be
done without synchronizing the local traces.  I say not.

 || Date: Tue, 19 Mar 1996 08:48:07 -0600
 || From: cef@geode.geodesic.com (Charles Fiterman)
 ||
 || > 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.

Example:

        Process A                           Process B

        root ---> x -------------------------->y--+
                                                  |
                                                  |
              +-- z <-----------------------------+
              |
              |
              +------------------------------->t

Process A traces from root, marks x.  Cannot continue until receiving a mark
message from B.  Sends its own mark message to B, saying y is reachable.

Process B traces from root, marks nothing.  Cannot continue until receiving a
mark message from A.

Process B receives mark message, marks y.  Sends mark message to A.

Process A receives mark message, marks z, sends another mark message to B
sayig that t is reachable.

If B does not wait for this new mark message, t will be reclaimed unsafely.

Conclusion: B cannot proceed past the mark phase until it has received the
LAST mark message from A; and vice-versa.

                                                        Marc