Simple concurrent garbage collection almost without synchronization

We present two simple mark and sweep algorithms, A and B, for concurrent garbage collection by a single collector running concurrently with a number of mutators that concurrently modify shared data. Both algorithms are based on the ideas of Ben-Ari's classical algorithm for on-the-fly garbage collection with one mutator. The algorithms require the mutators to estimate the set of objects they currently hold in private variables. They differ in the grain of atomicity of this estimate and in their mutator marking requirements. For algorithm A, the only synchronization needed is at the point where the list of newly collected garbage nodes is included in the free list to again become available to the mutators. Such synchronization of access to the free list seems unavoidable. For algorithm A, the estimate can be constructed concurrently with mutator actions. Algorithm B requires that the estimate is constructed atomically. Algorithms of this form have always been error-prone. We therefore provide assertional proofs of correctness, which moreover have been verified with the proof assistant PVS