An incremental garbage collection algorithm for multi-mutator systems

An elementary correctness proof for Ben-Ari's algorithm (1984) for incremental garbage collection is given. We give a new algorithm for systems in which there are multiple mutators and a proof of its correctness, which is a minor modification of the previous proof. Finally, we remark upon a way to implement these algorithms that may increase their performance on certain architectures.Carl Pixley holds B.S., M.S. and Ph.D. degrees in mathematics from the University of Omaha, Rutgers-The State University, and the State University of New York at Binghamton, respectively. His principal contributions are the Pixley-Roy construction of set-theoretic topology, a example in the selection theory of infinite-dimensional spaces, a decomposition theorem (with W. Eaton) in geometric topology, and the design and implementation of demanddriven arithmetic in a functional programming language. He is now a member of the technical staff of the VLSI Computer Aided Design Program of Microelectronics and Computer Technology Corporation (MCC) in Austin Texas, where he is investigating mathematical methods in the verification of hardware.