<XML><RECORDS><RECORD><REFERENCE_TYPE>0</REFERENCE_TYPE><REFNUM>5292</REFNUM><AUTHORS><AUTHOR>Dickman,P.W.</AUTHOR></AUTHORS><YEAR>1996</YEAR><TITLE>Efficient, Incremental, Distributed Orphan Detection and Actor Garbage Collection using Graph Partitioning and Euler Cycles</TITLE><PLACE_PUBLISHED>Proceedings of WDAG'96 (International Workshop on Distributed Algorithms and Graphs, now known as DISC), Lecture Notes in Computer Science, Volume No. 1151. </PLACE_PUBLISHED><PUBLISHER>Springer</PUBLISHER><PAGES>141-158</PAGES><ISBN>3-540-61769-8</ISBN><LABEL>Dickman:1996:5292</LABEL><ABSTRACT>A new algorithm is presented for incremental, distributed, concurrent garbage collection in systems of Actors. The algorithm also serves to detect orphan computations at low cost, as a side-effect of garbage collection, and permits the accurate elimination of unnecessary work without prejudicing the integrity of applications. Unlike all previous related algorithms, the new technique efficiently constructs a graph representation of the reachability relation within which Euler cycles can be used to determine the garbage objects. The new algorithm uses O(N+E) space and O(N+E) time, in the worst case, to collect a graph of N objects and E references; this is comparable to one previously known algorithm and superior to all others (which require O(N*N) time and O(N+E) space in the worst-case). The new algorithm also avoids an uneven space utilisation problem exhibited by the only other known O(N+E) time algorithm, making it more suitable for use in non-shared-memory distributed systems. </ABSTRACT></RECORD></RECORDS></XML>