Consider increment program inc(x) || inc(x), where inc(x) increments x atomically. It is difficult to show that, with pre-condition x = 0, the post-condition is x = 2. The Owicki-Gries method (1970s) proves this specification by adding auxillary variables y,z and invariant x = y+z. However, this work is not compositional since more threads require more auxilary variables. Rely-guarantee reasoning (1980s) provides a form of compositional reasoning, but the post-condition is (exists n>=1. x = n). Concurrent separation logic (2000s) is more compositional, providing local reasoning about the machine state with invariants constraining the use of shared state. For the increment program, the invariant (exists n >=0. x = n) is again too weak. Since this work, RGSep combined separation logic with rely-guarantee to reason about more fine-grained concurrent algorithms and CAP reasoning added abstraction. This talk provides an introduction to modern CAP reasoning, giving an overview of the strengths of current approaches and highlighting places where there is room for improvement. We can finally give a compositional proof of the strong specification of the increment program.
Track: ECOOP Summer School