Session types are widely used as abstractions of asynchronous message passing systems. Refinement for such abstractions is crucial as it allows improvements of a given component without compromising its compatibility with the rest of the system. In the context of session types, the most general notion of refinement is the asynchronous session subtyping, which allows to anticipate message emissions but only under certain conditions. In particular, asynchronous session subtyping rules out candidates subtypes that occur naturally in communication protocols where, e.g., two parties simultaneously send each other a finite but unspecified amount of messages before removing them from their respective buffers. To address this shortcoming, we study fair compliance over asynchronous session types and fair refinement as the relation that preserves it. This allows us to propose a novel variant of session subtyping that leverages the notion of controllability from service contract theory and that is a sound characterisation of fair refinement. In addition, we show that both fair refinement and our novel subtyping are undecidable. We also present a sound algorithm, and its implementation, which deals with examples that feature potentially unbounded buffering.


翻译:会话类型被广泛用作非同步电文传递系统的抽取。 改进这种抽取至关重要, 因为它允许在不损及与系统其他部分兼容性的情况下改进给定部件。 在会议类型中,最普遍的改进概念是会话分型,它允许预测电文排放,但在某些条件下才允许。 特别是,会话分解规则排除在通信协议中自然出现的候选人子类型,在通信协议中,例如,两方在将对方从各自的缓冲中除去之前,同时发送数量有限但不确定的信息。 为了解决这一缺陷,我们研究对不同步会话类型和公平改进的公平合规性,作为保持这种差异的关系。这使我们能够提出一个会议分型的新变式,利用服务合同理论的可控性概念,这是公平改进的正确定性。 此外,我们表明,公平的改进和我们的新子型分型都无法确定。 我们还提出一种合理的算法, 其实施过程涉及可能没有限制的缓冲性特征的例子。

0
下载
关闭预览

相关内容

【WSDM2021-Tutorial】偏见感知推荐系统的进展,134页ppt
专知会员服务
49+阅读 · 2021年3月9日
专知会员服务
123+阅读 · 2020年9月8日
专知会员服务
39+阅读 · 2020年9月6日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
计算机 | CCF推荐期刊专刊信息5条
Call4Papers
3+阅读 · 2019年4月10日
计算机 | ISMAR 2019等国际会议信息8条
Call4Papers
3+阅读 · 2019年3月5日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
LibRec 精选:推荐系统的论文与源码
LibRec智能推荐
14+阅读 · 2018年11月29日
人工智能 | COLT 2019等国际会议信息9条
Call4Papers
6+阅读 · 2018年9月21日
计算机类 | 期刊专刊截稿信息9条
Call4Papers
4+阅读 · 2018年1月26日
【推荐】自然语言处理(NLP)指南
机器学习研究会
35+阅读 · 2017年11月17日
【推荐】用Python/OpenCV实现增强现实
机器学习研究会
15+阅读 · 2017年11月16日
【推荐】YOLO实时目标检测(6fps)
机器学习研究会
20+阅读 · 2017年11月5日
Arxiv
0+阅读 · 2021年3月13日
Arxiv
0+阅读 · 2021年3月12日
Arxiv
3+阅读 · 2018年3月27日
Arxiv
12+阅读 · 2018年1月28日
VIP会员
相关VIP内容
【WSDM2021-Tutorial】偏见感知推荐系统的进展,134页ppt
专知会员服务
49+阅读 · 2021年3月9日
专知会员服务
123+阅读 · 2020年9月8日
专知会员服务
39+阅读 · 2020年9月6日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
相关资讯
计算机 | CCF推荐期刊专刊信息5条
Call4Papers
3+阅读 · 2019年4月10日
计算机 | ISMAR 2019等国际会议信息8条
Call4Papers
3+阅读 · 2019年3月5日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
LibRec 精选:推荐系统的论文与源码
LibRec智能推荐
14+阅读 · 2018年11月29日
人工智能 | COLT 2019等国际会议信息9条
Call4Papers
6+阅读 · 2018年9月21日
计算机类 | 期刊专刊截稿信息9条
Call4Papers
4+阅读 · 2018年1月26日
【推荐】自然语言处理(NLP)指南
机器学习研究会
35+阅读 · 2017年11月17日
【推荐】用Python/OpenCV实现增强现实
机器学习研究会
15+阅读 · 2017年11月16日
【推荐】YOLO实时目标检测(6fps)
机器学习研究会
20+阅读 · 2017年11月5日
Top
微信扫码咨询专知VIP会员