Fault-tolerant and fault-recovering garbage collection for the actor model: a collage-based approach

An actor garbage collector (actor GC) is a tool for automatically identifying actors that are safe to delete, and reclaiming their resources. Actor GC could be particularly useful in distributed applications, because programmers have difficulty reclaiming resources after faults such as crashed nodes or dropped messages. Unfortunately, faults are a pain point in existing actor GCs: in existing approaches, an actor on a crashed node with a reference to an actor on a healthy node will prevent the healthy actor---and its references---from ever being garbage collected. Moreover, existing GC algorithms have poor scalability in a distributed systems. This is because of the synchronization and message overhead they introduce by requiring causal delivery, or by introducing a large number of control messages. For these reasons, it has not been practical to add actor GC to popular frameworks like Akka and Erlang. This thesis explores an emerging technique for actor GC, dubbed the collage-based approach. Collage-based GCs are capable of high performance because they do not dictate when an actor should participate in garbage collection, and by design they naturally make progress with only partial information. The thesis presents two collage-based GCs: PRL and CRGC. Both GCs are provably correct and impose no locks, memory barriers, or message ordering requirements. PRL uses distributed reference listing to collect acyclic garbage and allows node-local garbage collectors to detect distributed cyclic garbage via a lightweight gossip protocol. We then use insights from PRL to develop CRGC: the first actor GC capable of recovering from crashed nodes and dropped messages. We have formalized CRGC in TLA+ and implemented CRGC in Akka. Preliminary evaluation shows that CRGC imposes little overhead in practice and is capable of collecting actors that become garbage caused by crashed nodes.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2024

Author dc:creator

• Plyukhin, Dan

Contributors dc:contributor

• Agha, Gul
• Gupta, Indranil
• Xu, Tianyin
• Haller, Philipp

• Actor Model
• Concurrency
• Fault Tolerance
• Distributed Systems
• Distributed Computing
• Garbage Collection

Statement dc:rights

• Copyright 2024 Dan Plyukhin

Language dc:language

en, eng

Handle dc:identifier

https://hdl.handle.net/2142/124328

OAI record oai:identifier

https://www.ideals.illinois.edu/oai-pmh?verb=GetRecord&metadataPrefix=etdms&identifier=oai%3Awww.ideals.illinois.edu%3A2142%2F124328