University of Illinois Urbana-Champaign

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

Plyukhin, Dan

Content Files
PLYUKHIN-DISSERTATION-2024.pdf

Permalink

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

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
Handle URL
https://hdl.handle.net/2142/124328
Copyright and License Information
Copyright 2024 Dan Plyukhin

Owning Collections

Graduate Dissertations and Theses at Illinois PRIMARY
Graduate Theses and Dissertations at Illinois