A TAXONOMY OF RACE CONDITIONS

Parallel programs are frequently nondeterministic, meaning they can gi ve different results even when using the same input. These different r esults arise because variations in the timing of the multiple threads cause the threads to access shared resources in different orders. The phenomena that cause the nondeterministic behavior have been (and cont inue to be) variously referred to as access anomalies, race conditions , or just races. In a 1992 paper, Netzer and Miller (Netzer, R. H. B., and Miller, B. P. ACM Lett. Programming Languages Systems (Mar. 1992) , 74-88.) made an important contribution to formalizing and standardiz ing adjectives that can be applied to ''races'' (e.g., data race, actu al race). In this paper, we continue this effort by presenting a refin ed taxonomy for races in parallel programs. The terminology we suggest is not always consistent with that used previously, and we describe w hy we believe our terminology is more descriptive. Appropriate termino logy will facilitate discussion of races and improve the usefulness of messages reported by testing and debugging tools. (C) 1996 Academic P ress, Inc.