Many object-oriented programming languages support automatic garbage collection, such as Smalltalk, Scheme, Java, ... etc. Unfortunately, these garbage collection algorithms cannot be used for actor garbage collection directly, because each actor has a thread of control encapsulated in it. An actor can create or delete references to other actors, while an object cannot. The thread of control results in the essential difference of actor garbage collection and object garbage collection.
To formally define garbage actors, we have to clarify the concept of the root set of actors. The root set of actors cannot be reclaimed due to its nature. The root set of actors are:
The root set of actors are definately live. Live actors are those which can potentially communicate with the root set of actors. A garbage actor is one which has all the following properties:
The difficulty of local actor garbage collection is to get a consistent global state and minimize the penalty of actor garbage collection. The easiest approach for actor garbage collection is stop-the-world: no computation is allowed during actor garbage collection. There are two major drawbacks of this approach, the waiting time for message clearance and parallelism degrading (only the garbage collector is running and all actors are waiting).
A better solution for local actor garbage collection is to use a snapshot-based algorithm, which can alleviate parallelism degrading and does not require the waiting time for message clearance. SALSA uses a snapshot based algorithm, together with the SALSA two-pahse reference exchanging protocol and the SALSA asynchronous message acknowledgement protocol, in order to get a meaningful global state. The above two protocols are together named the SALSA garbage detection protocol. A SALSA local garbage collector uses the meaningful global snapshot to identify garbage actors.
Distributed actor garbage collection is much more complicated because of the mobility of actors, the difficulty of recording a meaningful global state of the distributed system, and the independent execution of the distributed and local garbage collection. The SALSA garbage detection protocol and the local actor garbage collectors help simplify the problem - they can handle acyclic distributed garbage and all local garbage.
The current SALSA distributed actor garbage collector is implemented as a logically centralized service. It is not a required service. When it is triggered to manage several hosts, it coordinates the local collectors to get a meaningful global snapshot. Actors referenced by those outside the selected hosts are never collected. The task of identifying garbage is done in the logically centralized service. Once garbage is identified, a garbage list is then sent to every participated hosts.
The next version of SALSA will provide two different types of distributed garbage collectors: the hierarchical centralized service, and the distributed garbage-identifying collector.