A Non-blocking Snapshot Algorithm for Distributed Garbage Collection of Mobile Active Objects Wei-Jen Wang Carlos A. Varela Distributed actor garbage collection differs from distributed object garbage collection in that it needs to consider in-transit message detection, unordered message reception, and actor migration. In this paper, we propose a new snapshot-based distributed actor garbage collection algorithm. The algorithm does not require First-In-First-Out or blocking communication, nor message logging. Furthermore, actor migration is allowed while capturing global snapshots and partial snapshots can be safely used to collect garbage, therefore not requiring comprehensive cooperation among all computing nodes. These features make it unique in the area of distributed garbage collection. We formally prove the following safety and conditional liveness properties of the algorithm: 1) the garbage in a global snapshot, created by composing several local snapshots, remains the same from the beginning to the end of the global snapshot algorithm, and 2) garbage is eventually collected if the global garbage collection algorithm is periodically activated and every blocked actor is always captured before a global garbage collection phase is triggered. Department of Computer Science, Rensselaer Polytechnic Institute, Troy, NY cs-06-15
A Non-blocking Snapshot Algorithm for Distributed Garbage Collection of Mobile Active Objects
Wei-Jen Wang
Carlos A. Varela
Distributed actor garbage collection differs from distributed object garbage collection in that it needs to consider in-transit message detection, unordered message reception, and actor migration. In this paper, we propose a new snapshot-based distributed actor garbage collection algorithm. The algorithm does not require First-In-First-Out or blocking communication, nor message logging. Furthermore, actor migration is allowed while capturing global snapshots and partial snapshots can be safely used to collect garbage, therefore not requiring comprehensive cooperation among all computing nodes. These features make it unique in the area of distributed garbage collection. We formally prove the following safety and conditional liveness properties of the algorithm: 1) the garbage in a global snapshot, created by composing several local snapshots, remains the same from the beginning to the end of the global snapshot algorithm, and 2) garbage is eventually collected if the global garbage collection algorithm is periodically activated and every blocked actor is always captured before a global garbage collection phase is triggered.
Department of Computer Science, Rensselaer Polytechnic Institute, Troy, NY
cs-06-15