类Paxos共识算法研究进展

随着互联网数据量和业务量的快速增长,集群规模越来越大,由于机器和网络等故障使得业务中断的可能性越来越高.如何实现一个容错的分布式系统十分重要.多机达成共识是分布式容错系统中一个最基础,最核心的问题.Paxos等一系列共识算法的出现有效地解决了这个问题.近年来,越来越多的系统使用共识相关技术,关于分布式共识算法的研究也层出不穷.这些共识算法可以被划分成2个大类：强领导者共识算法和弱领导者共识算法.随着远程直接内存访问(remote direct memory access, RDMA)等网络技术和现场可编程门阵列(field-programmable gate array, FPGA)等硬件技术的发展,又出现了一些结合新型网络和硬件技术的共识算法研究,用来提升分布式系统的性能.将从分布式共识算法发展历程的角度,介绍Paxos系列算法,阐述算法演进过程中的关键研究,讨论相关算法在不同场景下的优劣势,并展望该类算法的未来发展方向与前景.     

基于有向网络的一致性跟踪算法

研究了leader有控制输入且followers未知该输入条件下的线性多智能 体一致性跟踪问题.提出两种一致性跟踪算法,证明两种算法在leader到followers存在一棵 有向生成树且follower间拓扑是有向条件下,网络就能跟踪leader的状态.对于第一种算法,节点根 据相邻节点或leader的状态来求解其控制输入,并基于代数Riccati不等式给出 连续情形下算法稳定性条件.第二种算法直接利用相邻节点或leader的状态,使followers在上述网络条件下跟踪leader的状态,同样基于代数Riccati不等式给出算法稳定性条件. 仿真结果验证了算法的有效性.     

基于LMI的非线性摄动系统鲁棒绝对稳定性判据

讨论了前馈通道同时存在对象和控制器的范数摄动,而反馈通道存在扇区非线性的摄动系统的稳定性问题.基于H∞理论和LMI方法,得到了一组由线性矩阵不等式表达的充分性条件,建立了判断非线性摄动系统鲁棒绝对稳定性的新判据.     

Adaptive Leader‐Following Consensus for Uncertain Nonlinear Multi‐Agent Systems

This paper is concerned with the adaptive leader‐following consensus for first‐ and second‐order uncertain nonlinear multi‐agent systems (NMASs) with single‐ and double‐integrator leader, respectively. Remarkably, the control coefficients of the followers need not belong to any known finite interval, which makes the systems in question essentially different from those in the related works. Moreover, parameterized unknowns exist in the nonlinearities of the followers, and unknown control input is imposed on the leader, which make the problems difficult to solve. To compensate for these uncertainties/unknowns, the leader‐following consensus protocols are constructed by employing adaptive technique for the first‐order and the second‐order NMASs. Under the designed adaptive consensus protocols and the connected graph, the leader‐following consensus is achieved. Finally, two examples are given to show the effectiveness of the proposed leader‐following consensus protocols.     

带有时变时滞和不确定性拓扑的双积分系统的一致性

研究带有不确定性拓扑的双积分系统在有时滞的情况下的一致性问题,通过线性矩阵不等式的方法,得到一致性的充分条件。本文最大的贡献是考虑双积分系统,在有不确定性信息和时变时滞的情况下,找出控制协议使其一致。最大合适的时变时滞和不确定性可以由线性矩阵不等式得到。最后给出仿真,证明定理的有效性。     

带有不确定时变延时的有向网络多智能体平均一致性研究

针对带有不确定时变通信延时的有向网络多智能体系统的平均一致性问题,本文首先深入分析了弱连接且平衡的固定/切换拓扑特性.然后,通过分解系统状态变量,建立了初始系统的降维综合模型.考虑降维模型带有不确定时变延时,基于Jensen's不等式和最近提出的新型互凸方法,得到了系统平均一致性的充分条件,特别是,给出了与目前研究结果相比具有更小保守性的时变通信延时上界.最后,数值仿真验证了提出方法的可行性和有效性.     

无线传感器网络中带延时的一致性时间同步

针对无线传感器网络(WSNs)中节点间通信存在传输延迟,影响同步精度的情况,将加权平均应用于相对时钟斜率的计算,提出了一种带延时的一致性时间同步算法.该算法中每个传感器节点通过与邻居节点通信交换时钟信息,根据一致性理论更新时钟参数,从而到达时间同步的目的.研究了在假定传输延时服从正态分布的情况下对一致性时间同步算法的影响,提出的算法降低了延时对同步精度的影响,Matlab仿真验证了该算法的有效性.     

线性和非线性动态异构多自主体系统的有限时间一致性

研究了由线性和非线性动态自主体组成的异构多自主体系统的有限时间一致性问题.针对该异构系统提出了非线性的一致性协议,并分别给出了无领航者和有领航者情形下异构系统在有限时间内实现一致性的充分条件.所得结果还推广到具有有向通信拓扑且满足细致平衡条件的多自主体系统情形.最后,给出一些仿真结果来验证所得结论的正确性和有效性.     

Leader-follower Consensus of Upper-triangular Nonlinear Multi-agent Systems

This paper is concerned with the leader-follower consensus problem by using both state and output feedback for a class of nonlinear multi-agent systems. The agents considered here are all identical upper-triangular nonlinear systems which satisfy the Lipschitz growth condition. First, it is shown that the leader-follower consensus problem is equivalent to the control design problem of a high-dimensional multi-variable system. Second, by introducing an appropriate state transformation, the control design problem can be converted into the problem of finding a constant parameter, which can be obtained by solving the Lyapunov equation and estimating the nonlinear terms of the given system. At last, an example is given to verify effectiveness of the proposed consensus algorithms.      

对一类不确定系统的推广波波关判据

本文将对一类不确定系统提出推广的波波夫判据,这类系统的线性部分乃诸顶点模型的凸组合,而非线性函数是处于某扇区内。判据说:不确定系统是某扇区绝对稳定的如果存在一条公共的波波夫直线使所有顶点系统的修正奈氏曲线位于这直线右侧。     

NNs‐Based Event‐Triggered Consensus Control of a Class of Uncertain Nonlinear Multi‐Agent Systems

We are concerned with the consensus problem for a class of uncertain nonlinear multi‐agent systems (MASs) connected through an undirected communication topology via event‐triggered approaches in this paper. Two distributed control strategies, the adaptive centralized event‐triggered control one and adaptive distributed event‐triggered control one, are presented utilizing neural networks (NNs) and event‐driven mechanisms, where the advantages of the proposed control laws lie that they remove the requirement for exact priori knowledge about parameters of individual agents by taking advantage of NNs approximators and they save computing and communication resources since control tasks only execute at certain instants with respect to predefined threshold functions. Also, the trigger coefficient can be regulated adaptively with dependence on state errors to ensure not only the control performance but also the efficiency of the network interactions. It is proven that all signals in the closed‐loop system are bounded and the Zeno behavior is excluded. Finally, simulation examples are presented for illustration of the theoretical claims.     

Bounded Consensus Algorithms for Multi‐Agent Systems in Directed Networks

In this paper, the consensus problem is investigated via bounded controls for the multi‐agent systems with or without communication. Based on the nested saturation method, the saturated control laws are designed to solve the consensus problem. Under the designed saturated control laws, the transient performance of the closed‐loop system can be improved by tuning the saturation level. First of all, asymptotical consensus algorithms with bounded control inputs are proposed for the multi‐agent systems with or without communication delays. Under these consensus algorithms, the states’ consensus can be achieved asymptotically. Then, based on a kind of novel nonlinear saturation functions, bounded finite‐time consensus algorithms are further developed. It is shown that the states’ consensus can be achieved in finite time. Finally, two examples are given to verify the efficiency of the proposed methods.     

含通信延时及输入延时的线性多智能体的一致性

针对通信延时及输入延时并存的情况下,研究具有一般线性动态特性的高阶多智能体在固定且无向的网络拓扑下的一致性.通过将多智能体的特征方程分解为一系列低阶的因子,一致性问题转换为一系列低阶因子的稳定性分析问题,降低了问题的分析复杂度.进一步地,分析无延时情况下多智能体达到一致性的控制增益的取值范围,即增益的稳定区间.当从稳定区间选取一个固定的控制增益时,应用频率扫描高级聚类法分析多个因子在两延时参数空间中的稳定性,并由此获得多智能体延时无关及延时相关的一致性结论.一个说明性的例子验证了分析结论.     

Time Averaging Algorithms with Stopping Rules for Multi‐Agent Consensus with Noisy Measurements

A time averaging technique is introduced to consensus algorithms in networked multi‐agent systems under a noisy environment. Each agent communicates with its neighboring agents via a constant gain, while the time averaging states of the agents are considered as the values for agreement. The variation of the time averaging states then is evaluated at a specific number of iterations, where the number is given explicitly in terms of parameters related to the consensus accuracy and its probabilistic guarantee. This result establishes a rigorous stopping rule for the multi‐agent consensus with noisy measurements. Several results on this type of stopping rules are provided for undirected, directed, and time‐varying communication graphs. These theoretical results are illustrated through numerical examples.     

Asynchronous Distributed Algorithms for Heading Consensus of Multi‐Agent Systems with Communication Delay

In this paper, we propose two asynchronous distributed protocols for the heading consensus of a multi‐agent group which cannot access a global coordinate system and a global time. Both the leaderless and leader‐following cases are addressed, and inter‐agent communication delay is taken into account. It is proved, under some standard connectivity assumptions, that our leaderless algorithm ensures the heading consensus provided the initial headings are not balanced; and the leader‐based algorithm guarantees the global heading consensus.     

具有时滞的不确定鲁里叶控制系统的绝对鲁棒稳定性

讨论了具有时滞的非线性不确定鲁里叶控制系统的鲁棒绝对稳定性问题,应用Bellman-Gronwell不等式和Lyapunov泛函方法研究了不确定鲁里叶控制系统的鲁棒绝对稳定性并给出了系统的滞相关稳定和时滞无关稳定的充分判据,运用这些条件可以直接估计具有时滞的非线性不确定鲁里叶控制系统的鲁棒绝对稳定界和时滞界。     

带有预验证机制的区块链动态共识算法

委员会共识和混合共识通过选举委员会来代替全网节点完成区块验证, 可有效加快共识速度, 提高吞吐量, 但恶意攻击和收买易导致委员会发生腐败问题, 严重时将影响共识结果甚至造成系统瘫痪. 现有工作虽引入信誉机制降低委员会节点腐败的可能性, 但开销大、可信度低且无法降低腐败问题对系统的影响. 提出一种带有预验证机制的区块链动态共识算法(DBCP), 通过预验证机制在较小开销的前提下对委员会进行可靠的信誉评估, 及时淘汰委员会中的恶意节点. 若腐败问题已影响到共识结果, DBCP会通过动态共识将区块验证权转移到全网节点, 并淘汰给出错误意见的委员会节点, 避免系统瘫痪. 若委员会通过迭代达到高可信状态, 则DBCP会将区块验证权交由委员会, 全网节点将认同委员会的共识结果, 并不再对区块进行验证, 进而加快共识速度. 经实验验证, DBCP的吞吐量与比特币相比提升了两个数量级, 且与Byzcoin相近, 可在一个出块周期内快速应对委员会腐败问题, 安全性优于Byzcoin.     

有结构摄动非线性系统的鲁棒绝对稳定性

考虑非线性闭环系统的鲁棒绝对稳定性,系统的线性部分受结构摄动以区间传递函数表示,而其非线性(不确定)反馈函数在一个扇区内.将鲁棒性分析的现代结果与经典的圆判据相结合,给出检验上述系统鲁棒绝对稳定性的方法.这个方法只用到16个特别选出的传递函数的奈氏曲线.这个数目不随系统的线性部分的阶次增高而加大,在某些特别情况下却可能更小.于是,将原问题的计算复杂性降到了一个非常低的水平.     

Quantized Consensus of Multi‐Agent Systems Via Broadcast Gossip Algorithms

Distributed consensus problems of multi‐agent systems on directed networks are studied in this paper. For the communication of agents, it is assumed that only one agent can be selected with a prescribed probability, and it broadcasts its own state to neighbors via quantized communication (for any arbitrary quantization) at each time step. For this kind of communication, the fundamental questions are how to design distributed algorithms and what kinds of network topology together lead to the quantized consensus. A class of broadcast gossip algorithms is proposed, and a necessary and sufficient graphical condition is given to ensure the quantized consensus. In particular, the obtained graphical condition does not require a symmetric network topology, which is weaker than those in some other literature. Several numerical simulations are given to show the effectiveness of the proposed algorithms.