Scalable termination detection for distributed actor systems

Dan Plyukhin, Gul Agha

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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 because 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 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).

Original languageEnglish (US)
Title of host publication31st International Conference on Concurrency Theory, CONCUR 2020
EditorsIgor Konnov, Laura Kovacs
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages111-1123
Number of pages1013
ISBN (Electronic)9783959771603
DOIs
StatePublished - Aug 1 2020
Event31st International Conference on Concurrency Theory, CONCUR 2020 - Virtual, Vienna, Austria
Duration: Sep 1 2020Sep 4 2020

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume171
ISSN (Print)1868-8969

Conference

Conference31st International Conference on Concurrency Theory, CONCUR 2020
CountryAustria
CityVirtual, Vienna
Period9/1/209/4/20

Keywords

  • Actors
  • Concurrency
  • Distributed systems
  • Garbage collection
  • Quiescence detection
  • Termination detection

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Scalable termination detection for distributed actor systems'. Together they form a unique fingerprint.

Cite this