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.
- Aug87.Lex Augusteijn. Garbage collection in a distributed environment. In PARLE '87- Parallel Architectures and Languages Europe, pages 75-93. Lecture Notes in Computer Science 259, Springer- Verlag, June 198'7. Google Scholar
- Bak78.Henry G Baker. List processing in real time on a serial computer. Communications of the A CM, 21(4):280-294, April 1978. Google ScholarDigital Library
- Bak91.Henry G Baker. Cantabile immobile--reM-time garbage collection without motion sickness. ~1991 Nimble Computer Corporation, 1991.Google Scholar
- BDS91.Hans J Boehm, Alan Demers, and Scott Shenker. Mostly parallel garbage collection. In PLDI '91 -ACM SIGPLAN Programming Languages Design and Implementation, pages 157-164, Toronto (Ontario, Canada), June 1991. SIGPLAN Notices Vol 26N6. Google ScholarDigital Library
- Bev87.D I Bevan. Distributed garbage collection using reference counting. In PARLE '87- Parallel Architectures and Languages Europe, pages 176-187. Lecture Notes in Computer Science 259, Springer- Verlag, June 1987. Google Scholar
- Bis77.Peter Bishop. Computer Systems With a Very Large Address Space and Garbage Collection. PhD thesis, MIT, May 1977.Google Scholar
- Chr84.Thomas W Christopher. Reference count garbage collection. Software-Practice and Experience, 14(6):503-507, June 1984.Google ScholarCross Ref
- DB76.Peter L. Deutsch and Daniel G. Bobrow. An efficient incremental automatic garbage collector. Com. munications of the ACM, 19(9):522-526, September 1976. Google ScholarDigital Library
- Der90.Margaret H Derbyshire. Mark scan garbage collection on a distributed architecture. Lisp and Symbolic Computation, 3(2):135-170, April 1990. Google ScholarDigital Library
- DLM+78.Edsger W Dijkstra, Leslie Lamport, A J Martins, C S Scholten, and E F M Steffens. On-the-fly garbage collection: An exercise in cooperation. Communications of the A CM, 21(11):966-975, November 1978. Google ScholarDigital Library
- Gol89.Benjamin Goldberg. Generational reference counting: A reduced-communication distributed storage reclamation scheme. In A CM SIGPLAN Programming Languages Design and Implementation, pages 313-321, Portland (OR), June 1989. Google ScholarDigital Library
- Gra78.J N Gray. Notes on database operating systems. In R Bayer et al., editor, Operating Systems: An Advanced Course, pages 394-481. Lecture Notes in Computer Science 60, Springer-VerIag, 1978. Google Scholar
- HK82.Paul Hudak and Robert Keller. Garbage collection and task deletion in distributed applicative processing systems. In A CM Symposium on Lisp and Functional Programming, pages 168-178, August 1982. Google ScholarDigital Library
- Hug85.John Hughes. A distributed garbage collection. In Functional Programming and Computer Architecture, pages 256-272. Lecture Notes in Computer Science 201, Springer-Verlag, September 1985. Google ScholarCross Ref
- 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.Google ScholarDigital Library
- LD87.Bernard Lung and Francis Dupont. Incremental incrementally compacting garbage collection. In SIGPLAN '87- Symposium on Interpreters and Interpretive Techniques, pages 253-263, Saint Paul, MA, 1987. Google ScholarDigital Library
- LH83.Henry Lieberman and Carl Hewitt. A reM-time garbage collector based on the lifetimes of objects. Communications of the A CM, 26(6):419-429, June 1983. Google ScholarDigital Library
- LL86.Barbara Liskov and Rivka Ladin. Highly-available distributed services and fault-tolerant distributed garbage collection. In PODC '86- Proceedings of the 5th Symposium on the Principles of Distributed Computing, pages 29-39, Vancouver (Canada), August 1986. Google ScholarDigital Library
- 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.Google Scholar
- Piq91.Jos~ Miguel Piquer. Indirect reference counting: A distributed garbage collection algorithm. In PARLE '91 - Parallel Architectures and Languages Europe, pages 150-165. Lecture Notes in Computer Science 505, Springer-Verlag, June 1991. Google ScholarDigital Library
- QBQ89.Christian Queinnec, Barbara Beuudoing, and Jean-Pierre Queille. Mark DURING sweep rather than mark THEN sweep. In PARLE '89- Parallel Architectures and Languages Europe. Lecture Notes in Computer Science 365, Springer-Verlag, June 1989. Google ScholarDigital Library
- Rud86.Martin Rudalics. Distributed copying garbage collection. In A CM Symposium on Lisp and Functional Programming, pages 364-372, Cambridge, MA, 1986. Google ScholarDigital Library
- Sch89.Marcel Schelvis. Incremental distribution of timestamp packets: A new approach to distributed garbage collection. In Object-Oriented Programming Systems and LAnguages, pages 37-48, October 1989. Google ScholarDigital Library
- 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.Google Scholar
- vdS87.Jan L A van de Snepscheut. "algorithms for onthe-fly garbage collection" revisited. Information Processing Letters, 24:211-216, March 1987. Google ScholarDigital Library
- Ves87.Stephen C Vestal. Garbage Collection: An Exercise in Distributed, Fault-Tolerant Programmin9. PhD thesis, Washington University, January 1987. Google ScholarDigital Library
- Wad76.Phil L. Wadler. Analysis of an algorithm for real time garbage collection. Communications of the A CM, 19(9):491-500, September 1976. Google ScholarDigital Library
- WF77.David S. Wise and Daniel P. Friedman. The onebit reference count. BIT, 17(3):351-359, 1977.Google ScholarDigital Library
- Yua90.Taiichi Yuasa. Real-time garbage collection on general-purpose machines. Journal of System Software, 11:181-198, 1990. Google ScholarDigital Library
Index Terms
- Garbage collecting the world
Recommendations
Garbage collecting the grid: a complete DGC for activities
Middleware '07: Proceedings of the ACM/IFIP/USENIX 2007 International Conference on MiddlewareGrids are becoming more and more dynamic, running parallel applications on large scale and heterogeneous resources. Explicitly stopping a whole distributed application is becoming increasingly difficult. In that context, there is a strong need to free ...
Age-based garbage collection
Modern generational garbage collectors look for garbage among the young objects, because they have high mortality; however, these objects include the very youngest objects, which clearly are still live. We introduce new garbage collection algorithms, ...
Garbage collecting the grid: a complete DGC for activities
MIDDLEWARE2007: Proceedings of the 8th ACM/IFIP/USENIX international conference on MiddlewareGrids are becoming more and more dynamic, running parallel applications on large scale and heterogeneous resources. Explicitly stopping a whole distributed application is becoming increasingly difficult. In that context, there is a strong need to free ...
Comments