Scalable distributed garbage collection for systems of active objects

Nalini Venkatasubramanian, Gul Agha, Carolyn Talcott

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

Abstract

Automatic storage management is important in highly parallel programming environments where large numbers of objects and processes are being constantly created and discarded. Part of the difficulty with automatic garbage collection in Systems of active objects, such as actors, is that an active object may not be garbage if it has references to other reachable objects, even when no other object has references to R. This is because an actor may at some point communicate its mail address to a reachable object thereby making itself reachable. Because messages may be pending in the network ' the asynchrony of distributed networks makes it difficult to determine the current topology. Existing garbage collection schemes halt the computation process in order to determine if a currently inaccessible actor may be potentially active, thus precluding a real-time response by the system. We describe a generation based algorithm which does not require ongoing computation to be halted during garbage collection. We also outline an informal proof of the correctness of the algorithm.

Original languageEnglish (US)
Title of host publicationMemory Management - International Workshop IWMM 1992, Proceedings
EditorsJacques Cohen, Yves Bekkers
PublisherSpringer-Verlag
Pages134-147
Number of pages14
ISBN (Print)9783540559405
StatePublished - Jan 1 1992
EventInternational Workshop on Memory Management, IWMM 1992 - St. Malo, France
Duration: Sep 17 1992Sep 19 1992

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume637 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

OtherInternational Workshop on Memory Management, IWMM 1992
CountryFrance
CitySt. Malo
Period9/17/929/19/92

Fingerprint

Garbage Collection
Storage management
Parallel programming
Topology
Programming Environments
Distributed Networks
Parallel Programming
Object
Correctness
Real-time
Actors

Keywords

  • Actors
  • Asynchrony
  • Broadcast and bulldoze communication
  • Distributed systems
  • Generation scavenging
  • Network clearance
  • Snapshot

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Venkatasubramanian, N., Agha, G., & Talcott, C. (1992). Scalable distributed garbage collection for systems of active objects. In J. Cohen, & Y. Bekkers (Eds.), Memory Management - International Workshop IWMM 1992, Proceedings (pp. 134-147). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 637 LNCS). Springer-Verlag.

Scalable distributed garbage collection for systems of active objects. / Venkatasubramanian, Nalini; Agha, Gul; Talcott, Carolyn.

Memory Management - International Workshop IWMM 1992, Proceedings. ed. / Jacques Cohen; Yves Bekkers. Springer-Verlag, 1992. p. 134-147 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 637 LNCS).

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

Venkatasubramanian, N, Agha, G & Talcott, C 1992, Scalable distributed garbage collection for systems of active objects. in J Cohen & Y Bekkers (eds), Memory Management - International Workshop IWMM 1992, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 637 LNCS, Springer-Verlag, pp. 134-147, International Workshop on Memory Management, IWMM 1992, St. Malo, France, 9/17/92.
Venkatasubramanian N, Agha G, Talcott C. Scalable distributed garbage collection for systems of active objects. In Cohen J, Bekkers Y, editors, Memory Management - International Workshop IWMM 1992, Proceedings. Springer-Verlag. 1992. p. 134-147. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
Venkatasubramanian, Nalini ; Agha, Gul ; Talcott, Carolyn. / Scalable distributed garbage collection for systems of active objects. Memory Management - International Workshop IWMM 1992, Proceedings. editor / Jacques Cohen ; Yves Bekkers. Springer-Verlag, 1992. pp. 134-147 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{9ca0512973e94870836b67a0ceeefdfe,
title = "Scalable distributed garbage collection for systems of active objects",
abstract = "Automatic storage management is important in highly parallel programming environments where large numbers of objects and processes are being constantly created and discarded. Part of the difficulty with automatic garbage collection in Systems of active objects, such as actors, is that an active object may not be garbage if it has references to other reachable objects, even when no other object has references to R. This is because an actor may at some point communicate its mail address to a reachable object thereby making itself reachable. Because messages may be pending in the network ' the asynchrony of distributed networks makes it difficult to determine the current topology. Existing garbage collection schemes halt the computation process in order to determine if a currently inaccessible actor may be potentially active, thus precluding a real-time response by the system. We describe a generation based algorithm which does not require ongoing computation to be halted during garbage collection. We also outline an informal proof of the correctness of the algorithm.",
keywords = "Actors, Asynchrony, Broadcast and bulldoze communication, Distributed systems, Generation scavenging, Network clearance, Snapshot",
author = "Nalini Venkatasubramanian and Gul Agha and Carolyn Talcott",
year = "1992",
month = "1",
day = "1",
language = "English (US)",
isbn = "9783540559405",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer-Verlag",
pages = "134--147",
editor = "Jacques Cohen and Yves Bekkers",
booktitle = "Memory Management - International Workshop IWMM 1992, Proceedings",

}

TY - GEN

T1 - Scalable distributed garbage collection for systems of active objects

AU - Venkatasubramanian, Nalini

AU - Agha, Gul

AU - Talcott, Carolyn

PY - 1992/1/1

Y1 - 1992/1/1

N2 - Automatic storage management is important in highly parallel programming environments where large numbers of objects and processes are being constantly created and discarded. Part of the difficulty with automatic garbage collection in Systems of active objects, such as actors, is that an active object may not be garbage if it has references to other reachable objects, even when no other object has references to R. This is because an actor may at some point communicate its mail address to a reachable object thereby making itself reachable. Because messages may be pending in the network ' the asynchrony of distributed networks makes it difficult to determine the current topology. Existing garbage collection schemes halt the computation process in order to determine if a currently inaccessible actor may be potentially active, thus precluding a real-time response by the system. We describe a generation based algorithm which does not require ongoing computation to be halted during garbage collection. We also outline an informal proof of the correctness of the algorithm.

AB - Automatic storage management is important in highly parallel programming environments where large numbers of objects and processes are being constantly created and discarded. Part of the difficulty with automatic garbage collection in Systems of active objects, such as actors, is that an active object may not be garbage if it has references to other reachable objects, even when no other object has references to R. This is because an actor may at some point communicate its mail address to a reachable object thereby making itself reachable. Because messages may be pending in the network ' the asynchrony of distributed networks makes it difficult to determine the current topology. Existing garbage collection schemes halt the computation process in order to determine if a currently inaccessible actor may be potentially active, thus precluding a real-time response by the system. We describe a generation based algorithm which does not require ongoing computation to be halted during garbage collection. We also outline an informal proof of the correctness of the algorithm.

KW - Actors

KW - Asynchrony

KW - Broadcast and bulldoze communication

KW - Distributed systems

KW - Generation scavenging

KW - Network clearance

KW - Snapshot

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

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

M3 - Conference contribution

AN - SCOPUS:84958820309

SN - 9783540559405

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 134

EP - 147

BT - Memory Management - International Workshop IWMM 1992, Proceedings

A2 - Cohen, Jacques

A2 - Bekkers, Yves

PB - Springer-Verlag

ER -