Decyde decentralized cycle detection for actors
File(s)
Author(s)
Blessing, Sebastian
Type
Thesis
Abstract
Applications built on the actor paradigm dynamically generate actors, which can strain memory resources
and degrade performance. Managing and eliminating ``dead'' actors is crucial. Manual deallocation
is error-prone, potentially leading to inefficiencies or runtime errors. Garbage collection addresses
these issues effectively.
This thesis introduces Decyde, a novel garbage collection protocol for actor-based runtime systems on multicore machines
and distributed systems. Decyde operates concurrently with the actor program, eliminating the need for stop-the-world
synchronization or a central authority. Detecting cycles of dead actors, which form strongly connected components and do not
feature in ongoing messages, is challenging due to the absence of a single entity capable of observing the global state and
the asynchronous, concurrent alterations in actor topology and liveness.
Decyde employs a decentralized approach using message passing and reference counting, inspired by MAC, where cycle detection
relies on a central system actor. Unlike MAC, Decyde is decentralized: actors communicate their enhanced perceived topology to each other,
gradually discovering their deceased status. A locally elected leader coordinates deallocation, avoiding extensive global graph exploration.
We formally model Decyde and provide proof sketches affirming its soundness (collecting only dead actors)
and completeness (collecting all dead actors). Causal message delivery, essential for Decyde, is easily guaranteed
in multicore settings and can be achieved in distributed systems by structuring nodes in a tree topology.
The implementation of Decyde and benchmark results show improved responsiveness compared to MAC, especially in programs with many small cycles.
Decyde collects actors closer to the point where cycles become quiescent. Decyde encounters challenges when confronted with large, fully connected cycles, leading
to performance degradation compared to MAC. We claim that this an atypical pattern of behavior in programs adhering to the actor programming model
and counterbalanced by Decyde's ability to collect node-spanning cyclic garbage in large distributed systems.
and degrade performance. Managing and eliminating ``dead'' actors is crucial. Manual deallocation
is error-prone, potentially leading to inefficiencies or runtime errors. Garbage collection addresses
these issues effectively.
This thesis introduces Decyde, a novel garbage collection protocol for actor-based runtime systems on multicore machines
and distributed systems. Decyde operates concurrently with the actor program, eliminating the need for stop-the-world
synchronization or a central authority. Detecting cycles of dead actors, which form strongly connected components and do not
feature in ongoing messages, is challenging due to the absence of a single entity capable of observing the global state and
the asynchronous, concurrent alterations in actor topology and liveness.
Decyde employs a decentralized approach using message passing and reference counting, inspired by MAC, where cycle detection
relies on a central system actor. Unlike MAC, Decyde is decentralized: actors communicate their enhanced perceived topology to each other,
gradually discovering their deceased status. A locally elected leader coordinates deallocation, avoiding extensive global graph exploration.
We formally model Decyde and provide proof sketches affirming its soundness (collecting only dead actors)
and completeness (collecting all dead actors). Causal message delivery, essential for Decyde, is easily guaranteed
in multicore settings and can be achieved in distributed systems by structuring nodes in a tree topology.
The implementation of Decyde and benchmark results show improved responsiveness compared to MAC, especially in programs with many small cycles.
Decyde collects actors closer to the point where cycles become quiescent. Decyde encounters challenges when confronted with large, fully connected cycles, leading
to performance degradation compared to MAC. We claim that this an atypical pattern of behavior in programs adhering to the actor programming model
and counterbalanced by Decyde's ability to collect node-spanning cyclic garbage in large distributed systems.
Version
Open Access
Date Issued
2023-09
Date Awarded
2024-06
Copyright Statement
Creative Commons Attribution NonCommercial NoDerivatives Licence
Advisor
Drossopoulou, Sophia
Publisher Department
Computing
Publisher Institution
Imperial College London
Qualification Level
Doctoral
Qualification Name
Doctor of Philosophy (PhD)