This paper pursues the problems of scalability of parallel graph-marking algorithms in the context of garbage collection systems. The authors give a set of constraints inherent to any graph-marking approach and attempt to construct a scalable marking algorithm following these constraints. The resulting algorithm has been implemented in a Java Virtual Machine and evaluated on real-world Java applications. The obtained results indicate a substantial acceleration of marking in most cases.