Semi-passive replication and Lazy Consensus

This paper presents two main contributions: semi-passive replication and Lazy Consensus. The former is a replication technique with parsimonious processing. It is based on the latter; a variant of Consensus allowing the lazy evaluation of proposed values.Semi-passive replication is a replication technique with parsimonious processing. This means that, in the normal case, each request is processed by only one single process. The most significant aspect of semi-passive replication is that it requires a weaker system model than existing techniques of the same family. For semi-passive replication, we give an algorithm based on the Lazy Consensus.Lazy Consensus is a variant of the Consensus problem that allows the lazy evaluation of proposed values, hence the name. The main difference with Consensus is the introduction of an additional property of laziness. This property requires that proposed values are computed only when they are actually needed. We present an algorithm based on Chandra and Toueg's Consensus algorithm for asynchronous distributed systems with a S failure detector.     

On Byzantine generals with alternative plans

This paper proposes a variation of the Byzantine generals problem (or Byzantine consensus). Each general has a set of good plans and a set of bad plans. The problem is to make all loyal generals agree on a good plan proposed by a loyal general, and never on a bad plan.     

The inherent price of indulgence

An indulgent algorithm is a distributed algorithm that tolerates asynchronous periods of the network when process crash detection is unreliable. This paper presents a tight bound on the time complexity of indulgent consensus algorithms. We consider a round-based eventually synchronous model, and we show that any t-resilient consensus algorithm in this model, requires at least t+2 rounds for a global decision even in runs that are synchronous. We contrast our lower bound with the well-known t+1 round tight bound on consensus in the synchronous model. We then prove the bound to be tight by exhibiting a new t-resilient consensus algorithm in the eventually synchronous model that reaches a global decision at round t+2 in every synchronous run. Our new algorithm is in this sense significantly faster than the most efficient indulgent algorithm we know of, which requires 2t+2 rounds in synchronous runs. Our lower bound applies to round-based consensus algorithms with unreliable failure detectors such as ⋄ P and ⋄ S, and our matching algorithm can be adapted to such failure detectors. This work is partially supported by the Swiss National Science Foundation (project number 510-207).     

Lower bounds for asynchronous consensus

Impossibility results and best-case lower bounds are proved for the number of message delays and the number of processes required to reach agreement in an asynchronous consensus algorithm that tolerates non-Byzantine failures. General algorithms exist that achieve these lower bounds in the normal case, when the response time of non-faulty processes and the transmission delay of messages they send to one another are bounded. Our theorems allow algorithms to do better in certain exceptional cases, and such algorithms are presented. Two of these exceptional algorithms may be of practical interest.     

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.     

Compaction of diagnostic messages for compilers

The use of a space optimal storage scheme for compiler diagnostic messages is described. The space reduction achievable through word coding may be predicted in terms of text length, vocabulary size and average word length. A method of word or phrase selection is discussed. Illustration is made by application to the FORTRAN FTN and COBOL compilers under the operating system KRONOS for the CDC 6400 computer.     

A simple proof of the uniform consensus synchronous lower bound

We give a simple and intuitive proof of an f+2 round lower bound for uniform consensus. That is, we show that for every uniform consensus algorithm tolerating t failures, and for every f?t−2, there is an execution with f failures that requires f+2 rounds.     

The weakest failure detector to solve nonuniform consensus

We determine the weakest failure detector to solve nonuniform consensus in any environment, i.e., regardless of the number of faulty processes. Together with previous results, this closes all aspects of the following question: What is the weakest failure detector to solve (uniform or nonuniform) consensus in any environment?     

离散时间系统的多智能体的一致性

动态多智能体系统的一致性是复杂动力学系统中很有现实意义的问题.假设智能体连接网络拓扑是无向、固定和连通的,而且个体之间信息传递存在通信时廷,分析了一个动态移动多智能体离散时间系统.应用广义Nyquist判据研究具有通信时延的多智能体离散时间系统,得到了保证系统达到一致的充分条件.最后应用计算机仿真验证了该结论的有效性.     

Automatic generation of useful syntax error messages

Many current compilers produce in some situations wrong error messages that mislead the user and harm his confidence in the system. It is demonstrated that a reliable and efficient syntax error handling system may be produced automatically by a compiler generator from the BNF specification of the language, and without any effort by the language implementor. This result is achieved in three ways:

• (a) Some errors may not be diagnosed without knowledge of the intentions of the programmer. Some compilers employ a sophisticated analysis that attempts to capture these intentions, but which is not always successful. Such an elaborate analysis is not employed here, and instead a list of all the legal corrections is displayed, so that the programmer may readily select the right one.
• (b) The recovery symbols are selected by a ‘careful’ algorithm resulting in a high probability for correct error recovery.
• (c) The ‘honest’ error messages show also the parts of the code which could not be analysed correctly because of errors, and where more errors may exist.

Efficiency is achieved by computing the recovery sets once and for all at compiler generation time, so that a fast error recovery at program compilation time is achieved. Experiments with erroneous programs suggest that the method compares well with the best compilers that we have seen, and is specially good at the avoidance of wrong error messages.     

Consensus of switched multi-agent systems with random networks

This paper studies the consensus problem of the switched multi-agent system composed of continuous-time and discrete-time subsystems. Communication among agents is modelled as a random network where the existence of any information channel is probabilistic and independent of other channels. Then, some necessary and sufficient conditions are presented for solving average consensus of the switched multi-agent system under arbitrary switching. Furthermore, we show that the average consensus in different sense (mean square, almost surely and in probability, respectively) are equivalent. Finally, simulations are provided to illustrate the effectiveness of our theoretical results.     

Consensus networks with time-delays over finite fields

In this paper, we investigate the consensus problem in networks with time-delays over finite fields. The delays are categorised into three cases: single constant delay, multiple constant delays, and time-varying bounded delays. For all cases, some sufficient and necessary conditions for consensus are derived. Furthermore, assuming that the communication graph is strongly connected, some of the obtained necessary conditions reveal that the conditions for consensus with time-delays over finite fields depend not only on the diagonal entries but also on the off-diagonal entries, something that is intrinsically distinct from the case over real numbers (where having at least one nonzero diagonal entry is a sufficient and necessary condition to guarantee consensus). In addition, it is shown that delayed networks cannot achieve consensus when the interaction graph is a tree if the corresponding delay-free networks cannot reach consensus, which is consistent with the result over real numbers. As for average consensus, we show that it can never be achieved for delayed networks over finite fields, although it indeed can be reached under several conditions for delay-free networks over finite fields. Finally, networks with time-varying delays are discussed and one sufficient condition for consensus is presented by graph-theoretic method.     

一致性多传感器数据融合方法的改进

多传感器数据融合是指将经过集成处理的多传感器数据进行合成，形成对外部环境某一特征的一种表达方式的过程。本文首先介绍了Ｌｕｏ［１］的一致性多传感器数据融合方法。然后，针对Ｌｕｏ方法的不足之处，改进了一致性融合方法。该改进方法计算量小，能简便、快速地确定一致性的传感器数据。     

Using asynchrony and zero degradation to speed up indulgent consensus protocols

Existing consensus protocols suffer from slowdowns caused by the failures of processes and the mistakes made by the underlying oracles. In this paper, we propose two novel techniques to circumvent such slowdowns in failure-detector-based consensus protocols. The first technique guarantees the Round-Zero-Degradation (RZD) property (an extension of the Zero-Degradation property) in order to avoid the slowdown caused by a failed coordinator process. The second technique, named “Look-Ahead”, helps speed up the execution of the consensus protocol by making use of the messages delivered before their receivers enter the corresponding phases or rounds. The first technique is effective only when the underlying failure detector makes no or few mistakes, while the second technique always works well regardless of the performance of the failure detector. Moreover, Look-Ahead is a general technique and can be applied to consensus protocols based on any kind of oracle. By applying the two proposed techniques, several consensus protocols are developed. The simulation results show that the RZD technique is effective even if the error rate of the failure detector reaches about 15%, while the Look-Ahead technique can always improve the performance in all cases.     

基于演化博弈的理性拜占庭容错共识算法

拜占庭容错算法(byzantine fault-tolerant)是保证区块链等分布式系统能够达成一致性的重要算法,其性能影响着系统的安全性和稳定性.针对现有共识算法存在效率低下和缺少激励机制等问题,提出了一种基于演化博弈的理性实用拜占庭容错共识算法.首先,通过引入信誉机制来确定节点在共识过程中的可信任度,以信誉值为理...     

Consensus of linear multi-agent systems with reduced-order observer-based protocols

This paper considers the consensus problems for both continuous- and discrete-time linear multi-agent systems with directed communication topologies. Distributed reduced-order observer-based consensus protocols are proposed, based on the relative outputs of neighboring agents. A multi-step algorithm is presented to construct a reduced-order protocol, under which a continuous-time multi-agent system whose communication topology contains a directed spanning tree can reach consensus. This algorithm is further modified to achieve consensus with a prescribed convergence rate. These two algorithms have a favorable decoupling property. In light of the modified algebraic Riccati equation, an algorithm is then given to construct a reduced-order protocol for the discrete-time case.     

Bounded cost algorithms for multivalued consensus using binary consensus instances

In this paper, we present two bounded cost algorithms that solve multivalued consensus using binary consensus instances. Our first algorithm uses log₂n number of binary consensus instances where n is the number of processes, while our second algorithm uses at most binary consensus instances, where is the maximum length of the binary representation of all proposed values in the run. Both algorithms are significant improvements over the previous algorithm in [A. Mostefaoui, M. Raynal, F. Tronel, From binary consensus to multivalued consensus in asynchronous message-passing systems, Information Processing Letters 73 (5–6) (2000) 207–212], where the number of binary consensus instances needed to solve one multivalued consensus is unbounded.     

多智能体系统跟踪领导节点的随机一致性问题研究

针对一阶连续时间多智能体系统,研究了在带有通信噪声情况下跟踪领导节点的随机一致性问题。将代数图理论、矩阵理论和随机Lyapunov方法相结合,给出了在领导节点状态的一阶导数有界的情况下,系统达到随机一致的条件,并给出了误差均方期望上界的表达式。通过研究该误差上界表达式,可以找到控制误差上界的关键参数。其中分别研究了系统中所有个体都可以获取领导节点信息和只有一部分个体可以获取领导节点信息的两种情形。第二种情形更接近实际情况,也有更大的研究价值。最后通过仿真实验证明:理论推导与仿真结果相一致。     

具有动态领导节点的多智能体系统一致性分析

具有领导节点的一致性问题是多智能体协调控制重要研究内容。目前其研究结论主要集中在系统通信拓扑关系固定不变这一前提下,对于系统通信拓扑关系为动态变化时具有领导节点的一致性问题尚未得到完全解决。对系统通信拓扑关系为有向、时变情况下的具有领导节点的多智能体系统一致性问题进行研究。分析并给出了在领导节点为常值和时变两种情况下多智能体系统达到一致的条件。并通过矩阵论和图论相关知识给出了详细证明。最后通过仿真实例验证了结论的正确性。     

Efficient parallel algorithms can be made robust

Summary The efficient parallel algorithms proposed for many fundamental problems, such as list ranking, integer sorting and computing preorder numberings on trees, are very sensitive to processor failures. The requirement of efficiency (commonly formalized usingParallel-timexProcessors as a cost measure) has led to the design of highly tuned PRAM algorithms which, given the additional constraint of simple processor failures, unfortunately become inefficient or even incorrect. We propose a new notion ofrobustness, that combines efficiency with fault tolerance. For the common case of fail-stop errors, we develop a general and easy to implement technique to make robust many efficient parallel algorithms, e.g., algorithms for all the problems listed above. More specifically,for any dynamic pattern of fail-stop errors on a CRCW PRAMwith at least one surviving processor, our method increases the original algorithm cost by at most a log² multiplicative factor. Our technique is based on a robust solution of the problem ofWrite-All, i.e., usingP processors, write 1's in all locations of anN-sized array. In addition we show that at least a log/log log multiplicative overhead will be incurred for certain patterns of failures by any algorithm that implements robust solutions toWrite-All withP=N. However, by exploiting parallel slackness, we obtain an optimal cost algorithm when Paris C. Kanellakis is a professor of computer science at Brown University. His primary research interests are in the application of logic to computer science, such as high-level query languages for database systems, parallel evaluation of logic programs, and type inference for programming languages. He has published many articles on these subjects and is the author of the chapter Elements of Relational Database Theory in theHandbook of Theoretical Computer Science (Elsevier, 1990). He has also contributed to the theory of distributed computing and to combinatorial optimization. Alex Allister Shvartsman is an engineer at Digital Equipment Corporation. His professional interests include design and development of efficient distributed systems, distributed resource management, and theoretical foundations of fault-tolerant parallel computation. At Digital he architected and managed the development of distributed control systems that automated several of Digital's manufacturing processes. He is currently on an academic leave at Brown University.An extended abstract of a part of this work appears as: Kanellakis and Shvartsman (1989) in the Proceedings of the 8th ACM Symposium on Principles of Distributed Computing, Edmonton 1989This author was supported by NSF grant IRI-8617344, an Alfred P. Sloan fellowship and ONR grant N00014-83-K-0146 ARPA Order No. 4786This author was supported by DEC GEEP Doctoral program and ONR grant N00014-91-J-1613