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

Plyukhin, Dan

Permalink

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

Description

Title

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

Author(s)

Plyukhin, Dan

Issue Date

2024-04-18

Director of Research (if dissertation) or Advisor (if thesis)

Agha, Gul

Doctoral Committee Chair(s)

Agha, Gul

Committee Member(s)

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

Department of Study

Computer Science

Discipline

Computer Science

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• actor model
• concurrency
• fault tolerance
• distributed systems
• distributed computing
• garbage collection

Abstract

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.

Graduation Semester

2024-05

Type of Resource

Thesis

Copyright and License Information

Copyright 2024 Dan Plyukhin

Owning Collections