Marrying rely/guarantee and separation logic

Опубликовано 7 сентября 2016, 17:00

In the quest for tractable reasoning methods about concurrent algorithms both rely/guarantee logic and separation logic have made great advances, but neither is the ultimate approach. Rely-guarantee copes naturally with interference, but its specifications are complex as they describe the entire state. Conversely, separation logic has difficulty dealing with interference, but its specifications are simpler because they describe only the relevant state that the program accesses. Taking a lock-coupling linked list as an example, I will present a new program logic, RGSep that combines the benefits of the two approaches. RGSep describes interference naturally (using a relation as in rely/guarantee), and where there is no interference, enables local reasoning (as in separation logic). Time permitting; I will demonstrate a prototype tool that automates this reasoning.