Name
Abstract | ||
|---|---|---|
This paper introduces the concept of a commutativity race. A commutativity race occurs in a given execution when two library method invocations can happen concurrently yet they do not commute. Commutativity races are an elegant concept enabling reasoning about concurrent interaction at the library interface. We present a dynamic commutativity race detector. Our technique is based on a novel combination of vector clocks and a structural representation automatically obtained from a commutativity specification. Conceptually, our work can be seen as generalizing classical read-write race detection. We also present a new logical fragment for specifying commutativity conditions. This fragment is expressive, yet guarantees a constant number of comparisons per method invocation rather than linear with unrestricted specifications. We implemented our analyzer and evaluated it on real-world applications. Experimental results indicate that our analysis is practical: it discovered harmful commutativity races with overhead comparable to state-of-the-art, low-level race detectors. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1145/2594291.2594322 | PLDI |
Keywords | Field | DocType |
harmful commutativity race,library interface,classical read-write race detection,commutativity race detection,library method invocation,commutativity condition,dynamic commutativity race detector,commutativity specification,elegant concept,commutativity race,low-level race detector,static analysis | Vector clock,Programming language,Commutative property,Generalization,Computer science,Abstract interpretation,Static analysis,Structural representation,Theoretical computer science | Conference |
Volume | Issue | ISSN |
49 | 6 | 0362-1340 |
Citations | PageRank | References |
8 | 0.59 | 12 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Dimitar Dimitrov | 1 | 376 | 49.21 |
| Veselin Raychev | 2 | 540 | 19.97 |
| Martin Vechev | 3 | 620 | 30.99 |
| Eric Koskinen | 4 | 300 | 17.93 |