The title of this paper will attract the attention of many people, but the content will be meaningful to only a select few. The very formal treatment of the subject includes 24 theorems, lemmas, and corollaries and many definitions. The authors provide a good introduction that motivates the work and states the goals. They give an example of the problem they are addressing, which concerns correct access to a shared memory when two program segments in a parallel program update a given variable. The basic goal is “to determine the minimal set of delays that enforce sequential consistency.” This seemingly simple situation leads to much complexity when stated formally.

The categories and subject descriptors given by the authors are all related to architectures and processors, but the text is also directed toward compilation. The practicality of their results is brought into question in the conclusion when the authors state that in “an actual implementation of this method . . . one has to find all the minimal cycles in a graph. This requires time exponential in the number of nodes in a general graph.” They comment that the constrained structure of program graphs makes the problem easier.

Should you read the paper? Yes, if you are interested in theoretical questions related to the title. The technical content should be good, based on the quality of the journal in which it appeared and the refereeing acknowledged in the paper.