Concurrent garbage collection in the actor model

Dan Plyukhin, Gul A Agha

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

Abstract

In programming languages where memory may be allocated dynamically, automatic garbage collection (GC) can improve the efficiency of program execution while preventing program errors caused by incorrectly removed memory locations. In actor systems, GC poses some challenges that make it much costlier than in the sequential setting: Besides references from reachable actors, we have to consider inverse references from potentially active actors to reachable actors. One proposal, adopted in the runtime for the actor programming language Pony, uses causal message delivery and a centralized detection algorithm. While this is efficient in a multicore setting, the solution is too expensive for a distributed actor runtime. In this work, we show how the causal order message delivery requirement may be removed. Specifically, we describe a tracing collector of distributed actor garbage with centralized and decentralized variants. Both are guaranteed not to collect any non-garbage actors (safety) and to eventually collect all garbage actors (liveness).

Original languageEnglish (US)
Title of host publicationAGERE 2018 - Proceedings of the 8th ACM SIGPLAN International Workshop on Programming Based on Actors, Agents, and Decentralized Control, co-located with SPLASH 2018
EditorsFederico Bergenti, Joeri De Koster, Juliana Franco
PublisherAssociation for Computing Machinery, Inc
Pages44-53
Number of pages10
ISBN (Electronic)9781450360661
DOIs
StatePublished - Nov 5 2018
Event8th International Workshop on Programming based on Actors, Agents, and Decentralized Control, AGERE! 2018, co-located with SPLASH 2018 - Boston, United States
Duration: Nov 5 2018Nov 5 2018

Other

Other8th International Workshop on Programming based on Actors, Agents, and Decentralized Control, AGERE! 2018, co-located with SPLASH 2018
CountryUnited States
CityBoston
Period11/5/1811/5/18

Fingerprint

Computer programming languages
Data storage equipment

Keywords

  • Distributed systems
  • Garbage collection

ASJC Scopus subject areas

  • Software

Cite this

Plyukhin, D., & Agha, G. A. (2018). Concurrent garbage collection in the actor model. In F. Bergenti, J. De Koster, & J. Franco (Eds.), AGERE 2018 - Proceedings of the 8th ACM SIGPLAN International Workshop on Programming Based on Actors, Agents, and Decentralized Control, co-located with SPLASH 2018 (pp. 44-53). Association for Computing Machinery, Inc. https://doi.org/10.1145/3281366.3281368

Concurrent garbage collection in the actor model. / Plyukhin, Dan; Agha, Gul A.

AGERE 2018 - Proceedings of the 8th ACM SIGPLAN International Workshop on Programming Based on Actors, Agents, and Decentralized Control, co-located with SPLASH 2018. ed. / Federico Bergenti; Joeri De Koster; Juliana Franco. Association for Computing Machinery, Inc, 2018. p. 44-53.

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

Plyukhin, D & Agha, GA 2018, Concurrent garbage collection in the actor model. in F Bergenti, J De Koster & J Franco (eds), AGERE 2018 - Proceedings of the 8th ACM SIGPLAN International Workshop on Programming Based on Actors, Agents, and Decentralized Control, co-located with SPLASH 2018. Association for Computing Machinery, Inc, pp. 44-53, 8th International Workshop on Programming based on Actors, Agents, and Decentralized Control, AGERE! 2018, co-located with SPLASH 2018, Boston, United States, 11/5/18. https://doi.org/10.1145/3281366.3281368
Plyukhin D, Agha GA. Concurrent garbage collection in the actor model. In Bergenti F, De Koster J, Franco J, editors, AGERE 2018 - Proceedings of the 8th ACM SIGPLAN International Workshop on Programming Based on Actors, Agents, and Decentralized Control, co-located with SPLASH 2018. Association for Computing Machinery, Inc. 2018. p. 44-53 https://doi.org/10.1145/3281366.3281368
Plyukhin, Dan ; Agha, Gul A. / Concurrent garbage collection in the actor model. AGERE 2018 - Proceedings of the 8th ACM SIGPLAN International Workshop on Programming Based on Actors, Agents, and Decentralized Control, co-located with SPLASH 2018. editor / Federico Bergenti ; Joeri De Koster ; Juliana Franco. Association for Computing Machinery, Inc, 2018. pp. 44-53
@inproceedings{02cca76be7f3496db75662442a3a18da,
title = "Concurrent garbage collection in the actor model",
abstract = "In programming languages where memory may be allocated dynamically, automatic garbage collection (GC) can improve the efficiency of program execution while preventing program errors caused by incorrectly removed memory locations. In actor systems, GC poses some challenges that make it much costlier than in the sequential setting: Besides references from reachable actors, we have to consider inverse references from potentially active actors to reachable actors. One proposal, adopted in the runtime for the actor programming language Pony, uses causal message delivery and a centralized detection algorithm. While this is efficient in a multicore setting, the solution is too expensive for a distributed actor runtime. In this work, we show how the causal order message delivery requirement may be removed. Specifically, we describe a tracing collector of distributed actor garbage with centralized and decentralized variants. Both are guaranteed not to collect any non-garbage actors (safety) and to eventually collect all garbage actors (liveness).",
keywords = "Distributed systems, Garbage collection",
author = "Dan Plyukhin and Agha, {Gul A}",
year = "2018",
month = "11",
day = "5",
doi = "10.1145/3281366.3281368",
language = "English (US)",
pages = "44--53",
editor = "Federico Bergenti and {De Koster}, Joeri and Juliana Franco",
booktitle = "AGERE 2018 - Proceedings of the 8th ACM SIGPLAN International Workshop on Programming Based on Actors, Agents, and Decentralized Control, co-located with SPLASH 2018",
publisher = "Association for Computing Machinery, Inc",

}

TY - GEN

T1 - Concurrent garbage collection in the actor model

AU - Plyukhin, Dan

AU - Agha, Gul A

PY - 2018/11/5

Y1 - 2018/11/5

N2 - In programming languages where memory may be allocated dynamically, automatic garbage collection (GC) can improve the efficiency of program execution while preventing program errors caused by incorrectly removed memory locations. In actor systems, GC poses some challenges that make it much costlier than in the sequential setting: Besides references from reachable actors, we have to consider inverse references from potentially active actors to reachable actors. One proposal, adopted in the runtime for the actor programming language Pony, uses causal message delivery and a centralized detection algorithm. While this is efficient in a multicore setting, the solution is too expensive for a distributed actor runtime. In this work, we show how the causal order message delivery requirement may be removed. Specifically, we describe a tracing collector of distributed actor garbage with centralized and decentralized variants. Both are guaranteed not to collect any non-garbage actors (safety) and to eventually collect all garbage actors (liveness).

AB - In programming languages where memory may be allocated dynamically, automatic garbage collection (GC) can improve the efficiency of program execution while preventing program errors caused by incorrectly removed memory locations. In actor systems, GC poses some challenges that make it much costlier than in the sequential setting: Besides references from reachable actors, we have to consider inverse references from potentially active actors to reachable actors. One proposal, adopted in the runtime for the actor programming language Pony, uses causal message delivery and a centralized detection algorithm. While this is efficient in a multicore setting, the solution is too expensive for a distributed actor runtime. In this work, we show how the causal order message delivery requirement may be removed. Specifically, we describe a tracing collector of distributed actor garbage with centralized and decentralized variants. Both are guaranteed not to collect any non-garbage actors (safety) and to eventually collect all garbage actors (liveness).

KW - Distributed systems

KW - Garbage collection

UR - http://www.scopus.com/inward/record.url?scp=85059042645&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85059042645&partnerID=8YFLogxK

U2 - 10.1145/3281366.3281368

DO - 10.1145/3281366.3281368

M3 - Conference contribution

AN - SCOPUS:85059042645

SP - 44

EP - 53

BT - AGERE 2018 - Proceedings of the 8th ACM SIGPLAN International Workshop on Programming Based on Actors, Agents, and Decentralized Control, co-located with SPLASH 2018

A2 - Bergenti, Federico

A2 - De Koster, Joeri

A2 - Franco, Juliana

PB - Association for Computing Machinery, Inc

ER -