使用模型检测方法对Paxos算法进行验证与改进

因通信的同步问题、网络分区的可靠性问题等,分布式系统难以在通信、分区等环节失效的情况下对特定的状态达成共识．Paxos是近年分布式系统中常见且有效的共识算法,本文通过使用模型检测的方法对Paxos算法进行形式化建模,分析和验证了Paxos作为共识算法所应当满足的性质,结果表明,Paxos算法满足安全性、活性,但执行过程中有发生活锁的可能,并通过模型检测器重现了算法发生活锁时的运行轨迹．最后通过对算法进行改进,以应对现有算法执行过程中可能出现的活锁问题,并通过了模型检测器的验证．     

基于信用系数的动态改进的PBFT算法

随着以比特币为代表的数字货币的兴起,区块链作为其底层的技术受到越来越多的关注。区块链本身是一种点对点的分布式系统,共识算法是解决各节点达成共识的机制,以POW、POS为代表的公有链共识算法有算法效率低下,耗能严重,以Paxos、Raft为代表的传统分布式一支算法未考虑到拜占庭容错。因此,本文在对FBFT算法分析的基础上,提出了基于信用系数的动态改进算法,既考虑到了拜占庭容错、又增加了算法了灵活性,提高了算法的吞吐量、时延等性能。     

主流区块链共识算法对比研究

共识算法是区块链中的核心技术,直接决定了整个区块链系统的运行效率。对现有的共识算法进行了总结,将其分为基于节点某种属性值证明的共识算法、基于节点投票机制的共识算法和类Paxos共识算法三类。详细介绍了三类共识算法的实现细节,并依据蒙代尔不可能三角理论进行对比研究,给出了共识算法的发展方向,为区块链共识算法的深入研究提供借鉴。     

MEPaxos:低延迟的共识算法

共识问题作为分布式计算中最重要的基本问题之一,被广泛应用在状态机复制、原子广播、领导者选举等领域。解决共识问题的算法通常存在单领导者性能瓶颈、响应延迟受命令冲突的影响等问题。针对这些问题,在非拜占庭故障下的异步分布式系统中,提出了一种低延迟的共识算法MEPaxos(modified Egalitarian Paxos)。首先,提出了系统平均延迟的计算方法;然后,引入超时机制对二阶段提交算法进行改进;接着,根据系统平均延迟计算结果,利用改进的二阶段提交算法自动选择平均延迟较小的算法模式执行;最后,在亚马逊弹性计算云(elastic compute cloud,EC2)平台上将此算法与当前共识算法进行实验对比分析,结果表明,MEPaxos算法下,系统延迟性能得到了提升。     

PoW共识算法中的博弈困境分析与优化

区块链是随着比特币等数字加密货币逐渐兴起而盛行的一种新型去中心化分布式系统,具有去中心化、时序数据、集体维护、可编程和安全可信等特点.目前,区块链已引起政府部门、金融机构、科技企业和资本市场的高度重视与广泛关注.如何在一个去中心化的分布式系统中高效地达成共识是区块链技术研究的重要问题.本文从工作量证明（Proof of work,PoW）共识算法的挖矿困境入手,分析PoW共识过程中矿工策略选择的纳什均衡存在条件.利用零行列式（Zero determinant,ZD）策略对矿工策略选择进行优化,并通过数值仿真来验证优化算法的有效性.概括来说,本文从博弈论角度来理解和剖析PoW共识算法,为进一步设计基于博弈论的共识算法提供新的思路和方法.     

微信分布式数据存储协议对比

分布式系统是网络化的计算机系统,海量数据的互联网应用只能通过分布式系统协调大量计算机来支撑.微信后台存储大量使用了分布式数据存储方式的NoSQL集群.存储设备出现异常是必然,分布式系统通过多节点分布及冗余,避免个别异常节点影响到系统的正常服务,同时提供平行扩展能力.微信自研的分布式存储在发展的不同阶段,分别依赖过Paxos和Quorum两种方案维护一致性.Paxos和Quorum也是互联网企业主要使用的分布式协议.     

基于消息传递的Paxos算法研究

针对分布式系统中的一致性问题,对基本Paxos算法中的3种角色进行分步骤阶段分析,提出5种行为优化改进措施,其中包括限制角色提案、引入随机机制、提前拦截消息、减少消息传递和增加角色行为等方法。实验结果表明,改进后的算法能降低通信负载,提高系统安全,从而使分布式系统具有高可用性及高一致性。     

共识协议的形式化验证研究现状与展望

分布式系统在计算环境中发挥重要的作用,其中的共识协议算法用于保证节点间行为的一致性.共识协议的设计错误可能导致系统运行故障,严重时可能对人员和环境造成灾难性的后果,因此保证共识协议设计的正确性非常重要.形式化验证能够严格证明设计模型中目标性质的正确性,适合用于验证共识协议.然而,随着分布式系统的规模增大,问题复杂度提升,使得分布式共识协议的形式化验证更为困难.采用什么方法对共识协议的设计进行形式化验证、如何提升验证规模,是共识协议形式化验证的重要研究问题.对目前采用形式化方法验证共识协议的研究工作进行调研,总结其中提出的重要建模方法和关键验证技术,并展望该领域未来有潜力的研究方向.     

一种基于令牌的新的互斥算法分析与设计

在对现有典型分布式系统中互斥算法研究的基础上, 本文依据令牌技术, 提出了一种分布式系统中解决互斥问题的新算法.文中对算法的设计思想及实现过程进行了详细描述, 同时对其性能进行了严格的理论证明和分析, 该算法能有效地提高系统的通信效率.     

基于信誉值投票与随机数选举的PBFT共识算法

实用拜占庭容错（PBFT）算法在Raft和Paxos共识算法的基础上,解决了分布式系统中恶意节点向其他节点发送错误消息以扰乱系统正常运行的问题,但PBFT算法由于主节点选举随意导致共识效率低下,而现有PBFT改进算法普遍通信复杂度较高且容易出现系统集中化趋势。针对上述问题,提出一种基于信誉值投票与随机数选举的RN-VPBFT共识算法。通过增设监督节点,实现权力分散和信息中转,保证系统安全运行。在投票确定初始信誉值的过程中,引入随机参数使得满足条件的节点均有机会当选主节点,缓解系统集中化趋势。建立节点动态信誉模型,区分系统中的诚实节点与恶意节点,简化共识算法的一致性协议,降低算法通信复杂度。实验结果表明,与PBFT算法和基于信誉投票的PBFT改进算法相比,RN-VPBFT算法将通信复杂度由O（N²）降至O（N）,并且所有诚实节点的信誉值之差仅为0.02,具有更低的通信复杂度及更好的去中心化特性。     

PaxosStore中共识协议TPaxos的推导、规约与精化

PaxosStore是腾讯开发的高可用分布式存储系统，现已用于全面支持微信核心业务.PaxosStore实现了分布式共识协议Paxos的一种变体，我们称之为TPaxos.TPaxos的新颖之处在于它的"统一性"：它为每个参与者维护统一的状态类型，并采用统一格式的消息进行通信.然而，这种设计方案也带来了TPaxos与Paxos之间的诸多差异，给理解TPaxos造成了障碍.其次，虽然腾讯开源了TPaxos协议的核心代码（包括伪代码与C++代码），TPaxos仍缺少抽象而精确的形式化规约.最后，就我们所知，TPaxos的正确性尚未经过必要的数学论证或者形式化工具的检验.针对这些情况，本文有三个主要贡献.首先，我们从经典的Paxos协议出发，论证如何逐步推导出TPaxos协议.基于这种推导，我们可以将TPaxos看作Paxos的一种自然变体，更易于理解.其次，我们给出了TPaxos协议的TLA+形式化规约.在开发规约的时候，我们发现TPaxos协议描述中存在至关重要但并未充分阐明的微妙之处：在消息处理阶段，参与者（作为接受者角色）是先作出"不再接受具有更小编号的提议"的承诺（Promise）还是先接受（Accept）提议?这导致对TPaxos的两种不同理解，并促使我们提出TPaxos的一种变体，称为TPaxosAP.在TPaxosAP中，参与者先接受提议后作承诺.最后，我们使用精化（refinement）技术论证了TPaxos与TPaxosAP的正确性.特别地，由于已知的投票机制Voting不能完全描述TPaxosAP的行为，我们首先提出了适用于TPaxosAP的投票机制EagerVoting，然后建立了从TPaxosAP到EagerVoting以及从EagerVoting到Consensus的精化关系，并使用TLC模型检验工具验证了它们的正确性.     

Fast Paxos

As used in practice, traditional consensus algorithms require three message delays before any process can learn the chosen value. Fast Paxos is an extension of the classic Paxos algorithm that allows the value to be learned in two message delays. How and why the algorithm works are explained informally, and a TLA⁺ specification of the algorithm appears as an appendix.     

Using simulated execution in verifying distributed algorithms

This paper presents a methodology for using simulated execution to assist a theorem prover in verifying safety properties of distributed systems. Execution-based techniques such as testing can increase confidence in an implementation, provide intuition about behavior, and detect simple errors quickly. They cannot by themselves demonstrate correctness. However, they can aid theorem provers by suggesting necessary lemmas and providing tactics to structure proofs. This paper describes the use of these techniques in a machine-checked proof of correctness of the Paxos algorithm for distributed consensus .     

Disk Paxos

We present an algorithm, called Disk Paxos, for implementing a reliable distributed system with a network of processors and disks. Like the original Paxos algorithm, Disk Paxos maintains consistency in the presence of arbitrary non-Byzantine faults. Progress can be guaranteed as long as a majority of the disks are available, even if all processors but one have failed. Received: January 2001 / Accepted: March 2002     

Adaptive trade‐off between consistency and performance in data replication

Replication is widely adopted in modern Internet applications and distributed systems to improve the reliability and performance. Though maintaining the strong consistency among replicas can guarantee the correctness of application behaviors, however, it will affect the application performance at the same time because there is a well‐known trade‐off between consistency and performance. Many real‐world applications favoring performance often choose to enforce weak consistency. Although there has been some work on flexible configuration of consistency, most focuses on design or deployment time. As the system settings constantly change during runtime, the tuning of the consistency‐performance trade‐off needs to be handled dynamically. Failing to do that will cause either underestimation or overestimation of the consistency and performance that can be achieved. Existing work does not well support the dynamic tuning of the aforementioned trade‐off in runtime, which is mainly because of the lack of an appropriate quantitative model of consistency and performance. In this work, based on our previous effort on the quantitative model of consistency and latency, we design a replication protocol, CC‐Paxos, to achieve an adaptive trade‐off between consistency and performance according to application preferences and runtime information. By design, CC‐Paxos is not bound to any specific underlying data stores. We have implemented CC‐Paxos and applied it to MySQL databases. And real experiments both within a data center and across data centers show that CC‐Paxos not only can dynamically adjust the delivered consistency in return for ensured performance but also outperforms MySQL Cluster in the case of strong consistency guarantee. Copyright © 2016 John Wiley & Sons, Ltd.     

Reconfigurable distributed storage for dynamic networks

This paper presents a new algorithm for implementing a reconfigurable distributed shared memory in an asynchronous dynamic network. The algorithm guarantees atomic consistency (linearizability) in all executions in the presence of arbitrary crash failures of the processing nodes, message delays, and message loss. The algorithm incorporates a classic quorum-based algorithm for read/write operations, and an optimized consensus protocol, based on Fast Paxos for reconfiguration, and achieves the design goals of: (i) allowing read and write operations to complete rapidly and (ii) providing long-term fault-tolerance through reconfiguration, a process that evolves the quorum configurations used by the read and write operations. The resulting algorithm tolerates dynamism. We formally prove our algorithm to be correct, we present its performance and compare it to existing reconfigurable memories, and we evaluate experimentally the cost of its reconfiguration mechanism.     

On the coordinator's rule for Fast Paxos

Fast Paxos is an algorithm for consensus that works by a succession of rounds, where each round tries to decide a value v that is consistent with all past rounds. Rounds are started by a coordinator process and consistency is guaranteed by the rule used by this process for the selection of v and by the properties of process sets called quorums. We show a simplified version of this rule for the specific case where the quorums are defined by the cardinality of these process sets. This rule is of special interest for implementors of the algorithm.     

一种基于Paxos算法的容错机制

针对在普通的硬件和网络环境下实现系统数据的高可用性的目标,设计了一个由两个松耦合的模块组成的容错机制。该机制的核心使用了高效的共识算法Paxos。描述了这一容错机制的架构和主要模块,日志层的实现算法和数据层冗余机制。给出了该机制能够处理的各种故障。实验证明系统的稳定可靠,性能良好。