Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Distributed garbage collection algorithms for timestamped data
Ramachandran U., Knobe K., Harel N., Mandviwala H. IEEE Transactions on Parallel and Distributed Systems17 (10):1057-1071,2006.Type:Article
Date Reviewed: May 22 2007

Three different solutions for garbage collection in Stampede, a system that supports streaming application programming, are described in this paper. Essentially, a Stampede program is a dynamic collection of threads, which process data, and channels, which transport timestamped data items. Given the distributed nature of the computation and the dynamics of the thread-to-channel connections, the global time is derived from the local times of the threads, which are in turn defined from the timestamps of the data elements. Further, the problem of garbage collection is introduced. The paper introduces two ways of looking at garbage collection: a reference count-based solution and a time-based solution, where outdated references can be considered garbage.

For the time-based solution, the authors provide two garbage collectors: a transparent garbage collector (TGC) that works without taking into account application-specific details, and a dead timestamps-based garbage collector (DGC) that is able to remove nonrelevant data (as well as irrelevant computation, as a side effect) based on application knowledge. While TGC solutions are easier to grasp and implement, the more complicated DGC allows for more aggressive optimizations, leading to better results. The experiments included in the paper confirm the increase in performance with the increase in garbage collection algorithm complexity.

The paper is very well written and complete. Each algorithm is properly introduced, explained, and supported by short relevant pseudocode snippets to allow implementation and correctness verification. The best part of the paper is the section dedicated to experiments, due to the relevance of the metrics it proposes, the generality of the benchmarks, and the clear and coherent manner in which it explains the results. In terms of usability, the authors admit that there is no clear winner as the best algorithm for all applications, and that the choice of an optimal solution can be heavily application dependent. Providing a solution for predicting the optimal garbage collector for a given application, based on either generic application classification or on more specific information, may be a valuable direction of future work.

Reviewer:  H. Sips Review #: CR134306 (0804-0374)
Bookmark and Share
 
Memory Management (Garbage Collection) (D.3.4 ... )
 
 
Distributed Programming (D.1.3 ... )
 
 
Distributed Systems (C.2.4 )
 
 
Performance of Systems (C.4 )
 
Would you recommend this review?
yes
no
Other reviews under "Memory Management (Garbage Collection)": Date
Hardware support for real-time embedded multiprocessor system-on-a-chip memory management
Shalan M., Vincent J I.  Hardware/software codesign (Proceedings of the tenth international symposium, Estes Park, Colorado, May 6-8, 2002)79-84, 2002. Type: Proceedings
Jan 30 2004
Memory as a programming concept in C and C++
Franek F., Cambridge University Press, New York, NY, 2003.  250, Type: Book (9780521520430)
Apr 30 2004
Interprocedural pointer alias analysis
Hind M., Burke M., Carini P., Choi J. ACM Transactions on Programming Languages and Systems 21(4): 848-894, 1999. Type: Article
Mar 1 2000
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy