Garbage collecting the world

ABSTRACT

Distributed symbolic computations involve the existence of remote references allowing an object, local to a processor, to designate another object located on another processor. To reclaim inaccessible objects is the non trivial task of a distributed Garbage Collector (GC). We present in this paper a new distributed GC algorithm which (i) is fault-tolerant, (ii) is largely independent of how a processor garbage collects its own data space, (iii) does not need centralized control nor global stop-the-world synchronization, (iv) allows for multiple concurrent active GCs, (v) does not require to migrate objects from processor to processor and (vi) eventually reclaims all inaccessible objects including distributed cycles. These results are mainly obtained through the concept of a group of processors (or processes). Processors of a same group cooperate together to a GC inside this group; this GC is conservative with respect to the outside of the group. A processor contributes to the global GC of all groups to which it belongs. Garbage collection on small groups reclaims quickly locally distributed garbage clusters, while garbage collection on large groups ultimately reclaims widely distributed garbage clusters, albeit more slowly. Groups can be reorganized dynamically, in particular to tolerate failures of some member processors. These properties make the algorithm usable on very large and evolving networks of processors. Other than distributed symbolic computations, possible applications include for example distributed file or database systems.

REFERENCES

• Aug87: L Augusteijn, Garbage collection in a distributed environment, Volume II: Parallel Languages on PARLE: Parallel Architectures and Languages Europe, p.75-93, March 1987, Eindhoven, The Netherlands
• Bak78: Henry G. Baker, Jr., List processing in real time on a serial computer, Communications of the ACM, v.21 n.4, p.280-294, April 1978 [doi>10.1145/359460.359470]
• Bak91: Henry G Baker. Cantabile immobile--reM-time garbage collection without motion sickness. ~1991 Nimble Computer Corporation, 1991.
• BDS91: Hans-J. Boehm , Alan J. Demers , Scott Shenker, Mostly parallel garbage collection, ACM SIGPLAN Notices, v.26 n.6, p.157-164, June 1991
• Bev87: D I Bevan, Distributed garbage collection using reference counting, Volume II: Parallel Languages on PARLE: Parallel Architectures and Languages Europe, p.176-187, March 1987, Eindhoven, The Netherlands
• Bis77: Peter Bishop. Computer Systems With a Very Large Address Space and Garbage Collection. PhD thesis, MIT, May 1977.
• Chr84: Thomas W Christopher. Reference count garbage collection. Software-Practice and Experience, 14(6):503-507, June 1984.
• DB76: L. Peter Deutsch , Daniel G. Bobrow, An efficient, incremental, automatic garbage collector, Communications of the ACM, v.19 n.9, p.522-526, Sept. 1976 [doi>10.1145/360336.360345]
• Der90: Margaret H. Derbyshire, Mark scan garbage collection on a distributed architecture, Lisp and Symbolic Computation, v.3 n.2, p.135-170, Apr. 1990 [doi>10.1007/BF01806256]
• DLM+78: Edsger W. Dijkstra , Leslie Lamport , A. J. Martin , C. S. Scholten , E. F. M. Steffens, On-the-fly garbage collection: an exercise in cooperation, Communications of the ACM, v.21 n.11, p.966-975, Nov. 1978 [doi>10.1145/359642.359655]
• Gol89: B. Goldberg, Generational reference counting: a reduced-communication distributed storage reclamation scheme, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.313-321, June 19-23, 1989, Portland, Oregon, United States
• Gra78: Jim Gray, Notes on Data Base Operating Systems, Operating Systems, An Advanced Course, p.393-481, January 1978
• HK82: Paul Hudak , Robert M. Keller, Garbage collection and task deletion in distributed applicative processing systems, Proceedings of the 1982 ACM symposium on LISP and functional programming, p.168-178, August 15-18, 1982, Pittsburgh, Pennsylvania, United States [doi>10.1145/800068.802147]
• Hug85: John Hughes, A distributed garbage collection algorithm, Proc. of a conference on Functional programming languages and computer architecture, p.256-272, January 1985, Nancy, France
• KS77: H T Kung and S W Song. An efficient garbage collection system and its correctness proof. In Proceedings of IEEE 18th Symposium on Foundation of Computer Science, pages 120-131, Providence (RI), October 1977.
• LD87: B. Lang , F. Dupont, Incremental incrementally compacting garbage collection, Papers of the Symposium on Interpreters and interpretive techniques, p.253-263, June 24-26, 1987, St. Paul, Minnesota, United States
• LH83: Henry Lieberman , Carl Hewitt, A real-time garbage collector based on the lifetimes of objects, Communications of the ACM, v.26 n.6, p.419-429, June 1983 [doi>10.1145/358141.358147]
• LL86: Barbara Liskov , Rivka Ladin, Highly available distributed services and fault-tolerant distributed garbage collection, Proceedings of the fifth annual ACM symposium on Principles of distributed computing, p.29-39, August 11-13, 1986, Calgary, Alberta, Canada [doi>10.1145/10590.10593]
• LS76: B Lampson and H Sturgis. Crash recovery in a distributed data storage system. Technical report, Palo Alto Research Center, Xerox, Palo Alto, CA, 1976.
• Piq91: José M. Piquer, Indirect reference counting: a distributed garbage collection algorithm, Proceedings on Parallel architectures and languages Europe : volume I: parallel architectures and algorithms: volume I: parallel architectures and algorithms, p.150-165, June 1991, Eindhoven, The Netherlands
• QBQ89: Christian Queinnec , Barbara Beaudoing , Jean-Pierre Queille, Mark DURING Sweep rather than Mark THEN Sweep, Proceedings of the Parallel Architectures and Languages Europe, Volume I: Parallel Architectures, p.224-237, June 12-16, 1989
• Rud86: Martin Rudalics, Distributed copying garbage collection, Proceedings of the 1986 ACM conference on LISP and functional programming, p.364-372, August 1986, Cambridge, Massachusetts, United States [doi>10.1145/319838.319877]
• Sch89: M. Schelvis, Incremental distribution of timestamp packets: a new approach to distributed garbage collection, Conference proceedings on Object-oriented programming systems, languages and applications, p.37-48, October 02-06, 1989, New Orleans, Louisiana, United States
• SGP90: Marc Shapiro, Olivier Gruber, and David Plainfossil. A garbage detection protocol for a realistic distributed object-support system. Research Report 1320, lNRIA-Rocquencourt, November 1990.
• vdS87: Jan L. A. Van de Snepscheut, "Algorithms for on-the-fly garbage collection" revisited, Information Processing Letters, v.24 n.4, p.211-216, March 1987 [doi>10.1016/0020-0190(87)90135-9]
• Ves87: S. C. Vestal, Garbage collection: an exercise in distributed, fault-tolerant programming, University of Washington, Seattle, WA, 1987
• Wad76: Philip L. Wadler, Analysis of an algorithm for real time garbage collection, Communications of the ACM, v.19 n.9, p.491-500, Sept. 1976 [doi>10.1145/360336.360338]
• WF77: David S. Wise and Daniel P. Friedman. The onebit reference count. BIT, 17(3):351-359, 1977.
• Yua90: T. Yuasa, Real-time garbage collection on general-purpose machines, Journal of Systems and Software, v.11 n.3, p.181-198, Mar. 1990 [doi>10.1016/0164-1212(90)90084-Y]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

General Terms:
Algorithms