Concurrency verification for weak memory models is inherently complex. Several deductive techniques based on proof calculi have recently been developed, but these are typically tailored towards a single memory model through specialised assertions and associated proof rules. In this paper, we propose an extension to the logic \({\textsf{Piccolo}}\) to generalise reasoning across different memory models. \({\textsf{Piccolo}}\) is interpreted on the semantic domain of thread potentials. By deriving potentials from weak memory model states, we can define the validity of \({\textsf{Piccolo}}\) formulae for multiple memory models. We moreover propose unified proof rules for verification on top of \({\textsf{Piccolo}}\) . Once (a set of) such rules has been shown to be sound with respect to a memory model \({\textsf{MM}} \) , all correctness proofs employing this rule set are valid for \({\textsf{MM}}\) . We exemplify our approach on the memory models \({\textsf{SC}}\) , \({\textsf{TSO}}\) and \({\textsf{SRA}}\) using the standard litmus tests Message-Passing and IRIW.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Unifying Weak Memory Verification Using Potentials

  • Lara Bargmann,
  • Brijesh Dongol,
  • Heike Wehrheim

摘要

Concurrency verification for weak memory models is inherently complex. Several deductive techniques based on proof calculi have recently been developed, but these are typically tailored towards a single memory model through specialised assertions and associated proof rules. In this paper, we propose an extension to the logic \({\textsf{Piccolo}}\) to generalise reasoning across different memory models. \({\textsf{Piccolo}}\) is interpreted on the semantic domain of thread potentials. By deriving potentials from weak memory model states, we can define the validity of \({\textsf{Piccolo}}\) formulae for multiple memory models. We moreover propose unified proof rules for verification on top of \({\textsf{Piccolo}}\) . Once (a set of) such rules has been shown to be sound with respect to a memory model \({\textsf{MM}} \) , all correctness proofs employing this rule set are valid for \({\textsf{MM}}\) . We exemplify our approach on the memory models \({\textsf{SC}}\) , \({\textsf{TSO}}\) and \({\textsf{SRA}}\) using the standard litmus tests Message-Passing and IRIW.