De Nicola and Hennessy’s \(\textsc {must}\) -preorder is a liveness preserving refinement which states that a server  \(q\) refines a server  \(p\) if all clients satisfied by  \(p\) are also satisfied by  \(q\) . Owing to the universal quantification over clients, this definition does not yield a practical proof method, and alternative characterisations are necessary to reason over it. Finding these characterisations for asynchronous semantics, i.e. where outputs are non-blocking, has thus far proven to be a challenge, usually tackled via ad-hoc definitions. We show that the standard characterisations of the \(\textsc {must}\) -preorder carry over as they stand to asynchronous communication, if servers are enhanced to act as forwarders, i.e. they can input any message as long as they store it back into the shared buffer. Our development is constructive, is completely mechanised in Coq, and is independent of any calculus: our results pertain to Selinger output-buffered agents with feedback. This is a class of Labelled Transition Systems that captures programs that communicate via a shared unordered buffer, as in asynchronous CCS or the asynchronous \(\pi \) -calculus. We show that the standard coinductive characterisation lets us prove in Coq that concrete programs are related by the \(\textsc {must}\) -preorder. Finally, our proofs show that Brouwer’s bar induction principle is a useful technique to reason on liveness preserving program transformations.

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

Constructive characterisations of the MUST-preorder for asynchrony

  • Giovanni Bernardi,
  • Ilaria Castellani,
  • Paul Laforgue,
  • Léo Stefanesco

摘要

De Nicola and Hennessy’s \(\textsc {must}\) -preorder is a liveness preserving refinement which states that a server  \(q\) refines a server  \(p\) if all clients satisfied by  \(p\) are also satisfied by  \(q\) . Owing to the universal quantification over clients, this definition does not yield a practical proof method, and alternative characterisations are necessary to reason over it. Finding these characterisations for asynchronous semantics, i.e. where outputs are non-blocking, has thus far proven to be a challenge, usually tackled via ad-hoc definitions. We show that the standard characterisations of the \(\textsc {must}\) -preorder carry over as they stand to asynchronous communication, if servers are enhanced to act as forwarders, i.e. they can input any message as long as they store it back into the shared buffer. Our development is constructive, is completely mechanised in Coq, and is independent of any calculus: our results pertain to Selinger output-buffered agents with feedback. This is a class of Labelled Transition Systems that captures programs that communicate via a shared unordered buffer, as in asynchronous CCS or the asynchronous \(\pi \) -calculus. We show that the standard coinductive characterisation lets us prove in Coq that concrete programs are related by the \(\textsc {must}\) -preorder. Finally, our proofs show that Brouwer’s bar induction principle is a useful technique to reason on liveness preserving program transformations.