A Scalable Algorithm for Decentralized Actor Termination Detection
Automatic garbage collection (GC) prevents certain kinds of bugs and reduces programming overhead. GC techniques for sequential programs are based on reachability analysis. However, testing reachability from a root set is inadequate for determining whether an actor is garbage: Observe that an unreac...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Logical Methods in Computer Science e.V.
2022-03-01
|
| Series: | Logical Methods in Computer Science |
| Subjects: | |
| Online Access: | https://lmcs.episciences.org/7353/pdf |
| _version_ | 1797268522840096768 |
|---|---|
| author | Dan Plyukhin Gul Agha |
| author_facet | Dan Plyukhin Gul Agha |
| author_sort | Dan Plyukhin |
| collection | DOAJ |
| description | Automatic garbage collection (GC) prevents certain kinds of bugs and reduces
programming overhead. GC techniques for sequential programs are based on
reachability analysis. However, testing reachability from a root set is
inadequate for determining whether an actor is garbage: Observe that an
unreachable actor may send a message to a reachable actor. Instead, it is
sufficient to check termination (sometimes also called quiescence): an actor is
terminated if it is not currently processing a message and cannot receive a
message in the future. Moreover, many actor frameworks provide all actors with
access to file I/O or external storage; without inspecting an actor's internal
code, it is necessary to check that the actor has terminated to ensure that it
may be garbage collected in these frameworks. Previous algorithms to detect
actor garbage require coordination mechanisms such as causal message delivery
or nonlocal monitoring of actors for mutation. Such coordination mechanisms
adversely affect concurrency and are therefore expensive in distributed
systems. We present a low-overhead deferred reference listing technique (called
DRL) for termination detection in actor systems. DRL is based on asynchronous
local snapshots and message-passing between actors. This enables a
decentralized implementation and transient network partition tolerance. The
paper provides a formal description of DRL, shows that all actors identified as
garbage have indeed terminated (safety), and that all terminated actors--under
certain reasonable assumptions--will eventually be identified (liveness). |
| first_indexed | 2024-04-25T01:33:49Z |
| format | Article |
| id | doaj.art-cdc86a9f0daa45ee99ded0df7c7fc89f |
| institution | Directory Open Access Journal |
| issn | 1860-5974 |
| language | English |
| last_indexed | 2024-04-25T01:33:49Z |
| publishDate | 2022-03-01 |
| publisher | Logical Methods in Computer Science e.V. |
| record_format | Article |
| series | Logical Methods in Computer Science |
| spelling | doaj.art-cdc86a9f0daa45ee99ded0df7c7fc89f2024-03-08T10:36:53ZengLogical Methods in Computer Science e.V.Logical Methods in Computer Science1860-59742022-03-01Volume 18, Issue 110.46298/lmcs-18(1:39)20227353A Scalable Algorithm for Decentralized Actor Termination DetectionDan PlyukhinGul AghaAutomatic garbage collection (GC) prevents certain kinds of bugs and reduces programming overhead. GC techniques for sequential programs are based on reachability analysis. However, testing reachability from a root set is inadequate for determining whether an actor is garbage: Observe that an unreachable actor may send a message to a reachable actor. Instead, it is sufficient to check termination (sometimes also called quiescence): an actor is terminated if it is not currently processing a message and cannot receive a message in the future. Moreover, many actor frameworks provide all actors with access to file I/O or external storage; without inspecting an actor's internal code, it is necessary to check that the actor has terminated to ensure that it may be garbage collected in these frameworks. Previous algorithms to detect actor garbage require coordination mechanisms such as causal message delivery or nonlocal monitoring of actors for mutation. Such coordination mechanisms adversely affect concurrency and are therefore expensive in distributed systems. We present a low-overhead deferred reference listing technique (called DRL) for termination detection in actor systems. DRL is based on asynchronous local snapshots and message-passing between actors. This enables a decentralized implementation and transient network partition tolerance. The paper provides a formal description of DRL, shows that all actors identified as garbage have indeed terminated (safety), and that all terminated actors--under certain reasonable assumptions--will eventually be identified (liveness).https://lmcs.episciences.org/7353/pdfcomputer science - logic in computer science |
| spellingShingle | Dan Plyukhin Gul Agha A Scalable Algorithm for Decentralized Actor Termination Detection Logical Methods in Computer Science computer science - logic in computer science |
| title | A Scalable Algorithm for Decentralized Actor Termination Detection |
| title_full | A Scalable Algorithm for Decentralized Actor Termination Detection |
| title_fullStr | A Scalable Algorithm for Decentralized Actor Termination Detection |
| title_full_unstemmed | A Scalable Algorithm for Decentralized Actor Termination Detection |
| title_short | A Scalable Algorithm for Decentralized Actor Termination Detection |
| title_sort | scalable algorithm for decentralized actor termination detection |
| topic | computer science - logic in computer science |
| url | https://lmcs.episciences.org/7353/pdf |
| work_keys_str_mv | AT danplyukhin ascalablealgorithmfordecentralizedactorterminationdetection AT gulagha ascalablealgorithmfordecentralizedactorterminationdetection AT danplyukhin scalablealgorithmfordecentralizedactorterminationdetection AT gulagha scalablealgorithmfordecentralizedactorterminationdetection |