Incremental, Distributed Orphan Detection and Actor Garbage Collection using graph partitioning and Euler cycles

. A new algorithm is presented for incremental, distributed, concurrent garbage collection in systems with 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 2 ) 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 O(N +E) time algorithm, making it more suitable for use in non-shared-memory distributed systems. ..