Title | ||
---|---|---|
The derivation of graph marking algorithms from distributed termination detection protocols |
Abstract | ||
---|---|---|
We show that on-the-fly garbage collection algorithms can be obtained by transforming distributed termination detection protocols. Virtually all known on-the-fly garbage collecting algorithms are obtained by applying the transformation. The approach leads to a novel and insightful derivation of, e.g., the concurrent garbage collection algorithms of Dijkstra et al. and of Hudak and Keller. The approach also leads to several new, highly parallel algorithms for concurrent garbage collection. We also analyze a garbage collecting system due to Hughes from our current perspective. |
Year | DOI | Venue |
---|---|---|
1988 | 10.1016/0167-6423(88)90024-X | Sci. Comput. Program. |
Keywords | Field | DocType |
termination detection protocol | Data structure,Graph,Garbage,Parallel algorithm,Computer science,Algorithm,Theoretical computer science,Garbage collection,Dijkstra's algorithm | Journal |
Volume | Issue | ISSN |
10 | 2 | Science of Computer Programming |
Citations | PageRank | References |
9 | 6.56 | 15 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
G. Tel | 1 | 20 | 8.46 |
R. B. Tan | 2 | 134 | 20.82 |
J. Van Leeuwen | 3 | 308 | 55.29 |