Protocols to ensure that messages are delivered in causal order are a ubiquitous building block of distributed systems. For instance, key-value stores can use causally ordered message delivery to ensure causal consistency, and replicated data structures rely on the existence of an underlying causally-ordered messaging layer. A causal delivery protocol ensures that when a message is delivered to a process, any causally preceding messages sent to the same process have already been delivered to it. While causal delivery protocols are widely used, verification of the correctness of those protocols is less common, much less machine-checked proofs about executable implementations. We implemented a standard causal broadcast protocol in Haskell and used the Liquid Haskell solver-aided verification system to express and mechanically prove that messages will never be delivered to a process in an order that violates causality. We express this property using refinement types and prove that it holds of our implementation, taking advantage of Liquid Haskell's underlying SMT solver to automate parts of the proof and using its manual theorem-proving features for the rest. We then put our verified causal broadcast implementation to work as the foundation of a distributed key-value store.


翻译:确保信息按因果顺序发送的协议是分布式系统无处不在的构件。例如,关键价值商店可以使用因果命令发送的信息以确保因果一致性,而复制的数据结构则取决于是否存在一个基本的因果命令的电文层。一个因果传送协议确保,在向一个程序发送信息时,向该程序发送的任何因果之前的电文已经发出。虽然因果传送协议被广泛使用,但核实这些协议的正确性不那么常见,而由机器核查的关于可执行执行的证明则要少得多。我们在哈斯凯尔实施了标准的因果广播协议,并使用Haskell液体溶液溶剂辅助的核查系统来表达和机械地证明,信息绝不会被发送到一个违反因果性秩序的进程中。我们使用精细的种类表达这种属性,并证明我们在执行过程中持有这种属性,利用Haskell液体作为SMT解剂的解决方案的根基,使证据部分自动化,并使用其手动的用于休息的标语特征。我们随后将经过核实的因果广播实施工作作为分布式关键价值储存的基础。

0
下载
关闭预览

相关内容

Haskell 是一种纯函数式编程语言,于 1990 年在编程语言 Miranda 的基础上标准化,并且以 λ 演算为基础发展而来。
专知会员服务
123+阅读 · 2020年9月8日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
78+阅读 · 2020年7月26日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
ACM MM 2022 Call for Papers
CCF多媒体专委会
5+阅读 · 2022年3月29日
【ICIG2021】Latest News & Announcements of the Tutorial
中国图象图形学学会CSIG
3+阅读 · 2021年12月20日
【ICIG2021】Latest News & Announcements of the Workshop
中国图象图形学学会CSIG
0+阅读 · 2021年12月20日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium8
中国图象图形学学会CSIG
0+阅读 · 2021年11月16日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium6
中国图象图形学学会CSIG
2+阅读 · 2021年11月12日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium5
中国图象图形学学会CSIG
1+阅读 · 2021年11月11日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium4
中国图象图形学学会CSIG
0+阅读 · 2021年11月10日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium2
中国图象图形学学会CSIG
0+阅读 · 2021年11月8日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium1
中国图象图形学学会CSIG
0+阅读 · 2021年11月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
国家自然科学基金
1+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Arxiv
0+阅读 · 2022年10月14日
Arxiv
0+阅读 · 2022年10月14日
Arxiv
0+阅读 · 2022年10月13日
Arxiv
0+阅读 · 2022年10月13日
VIP会员
相关VIP内容
专知会员服务
123+阅读 · 2020年9月8日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
78+阅读 · 2020年7月26日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
相关资讯
ACM MM 2022 Call for Papers
CCF多媒体专委会
5+阅读 · 2022年3月29日
【ICIG2021】Latest News & Announcements of the Tutorial
中国图象图形学学会CSIG
3+阅读 · 2021年12月20日
【ICIG2021】Latest News & Announcements of the Workshop
中国图象图形学学会CSIG
0+阅读 · 2021年12月20日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium8
中国图象图形学学会CSIG
0+阅读 · 2021年11月16日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium6
中国图象图形学学会CSIG
2+阅读 · 2021年11月12日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium5
中国图象图形学学会CSIG
1+阅读 · 2021年11月11日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium4
中国图象图形学学会CSIG
0+阅读 · 2021年11月10日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium2
中国图象图形学学会CSIG
0+阅读 · 2021年11月8日
【ICIG2021】Check out the hot new trailer of ICIG2021 Symposium1
中国图象图形学学会CSIG
0+阅读 · 2021年11月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
相关基金
国家自然科学基金
1+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Top
微信扫码咨询专知VIP会员