Skip to main content

Birrell's Distributed Reference Listing Revisited

Moreau, Luc, Dickman, Peter, Jones, Richard E. (2005) Birrell's Distributed Reference Listing Revisited. ACM Transactions on Programming Languages and Systems (TOPLAS), 27 (6). pp. 1-52. ISSN 0164-0925. (KAR id:14235)

PDF
Language: English
Download (607kB) Preview
[thumbnail of Birrell_Richard.pdf]
Preview
This file may not be suitable for users of assistive technology.
Request an accessible format

Abstract

The Java RMI collector is arguably the most widely used distributed garbage collector. Its distributed reference listing algorithm was introduced by Birrell in the context of Network Objects, where the description was informal and heavily biased toward implementation. In this paper, we formalise this algorithm in an implementation-independent manner, which allows us to clarify weaknesses of the initial presentation. In particular, we discover cases critical to the correctness of the algorithm that are not accounted for by Birrell. We use our formalisation to derive an invariant-based proof of correctness of the algorithm that avoids notoriously difficult temporal reasoning. Furthermore, we offer a novel graphical representation of the state transition diagram, which we use to provide intuitive explanations of the algorithm and to investigate its tolerance to faults in a systematic manner. Finally, we examine how the algorithm may be optimised, either by placing constraints on message channels or by tightening the coupling between application program and distributed garbage collector.

Item Type: Article
Uncontrolled keywords: Distributed reference counting, garbage collection, proof, Java, RMI
Subjects: Q Science > QA Mathematics (inc Computing science) > QA 76 Software, computer programming,
Divisions: Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Computing
Depositing User: Richard Jones
Date Deposited: 24 Nov 2008 18:02 UTC
Last Modified: 16 Nov 2021 09:52 UTC
Resource URI: https://kar.kent.ac.uk/id/eprint/14235 (The current URI for this page, for reference purposes)
Jones, Richard E.: https://orcid.org/0000-0002-8159-0297
  • Depositors only (login required):

Downloads

Downloads per month over past year