李亚男,邓玉欣,刘静.基于Coq的Paxos形式化建模与验证.软件学报,2020,31(8):2362-2374 |
基于Coq的Paxos形式化建模与验证 |
Formal Modeling and Verification of Paxos Based on Coq |
投稿时间:2019-08-31 修订日期:2019-11-02 |
DOI:10.13328/j.cnki.jos.005960 |
中文关键词: 分布式系统 Basic Paxos 定理证明工具 Coq 验证 |
英文关键词:distributed system Basic Paxos theorem proof assistant Coq verification |
基金项目:国家自然科学基金(61672229,61832015) |
|
摘要点击次数: 1294 |
全文下载次数: 1043 |
中文摘要: |
Paxos是一个在不可靠的分布式处理器网络中解决共识问题的算法族.共识问题是指分布式系统中一组参与者就一个结果达成一致的过程.随着Paxos在大型分布式系统中的广泛运用,比如区块链系统以及谷歌文件系统等,其安全性证明越来越重要.在定理证明工具Coq中,形式化描述和定义了Lamport的Basic Paxos算法,并且证明了其满足共识性. |
英文摘要: |
Paxos is a family of algorithms that solve consensus problems in unreliable distributed processor networks. Consensus is a process in which a group of participants in the system reach agreement on a result. As Paxos is widely used in large distributed systems, such as block chain system and Google file system, its security verification becomes more and more important. With Coq, a theorem proving tool, the formal description and definition of Lamport's basic Paxos algorithm are described, and it is proved that it satisfies the consensus property. |
HTML 下载PDF全文 查看/发表评论 下载PDF阅读器 |