The impossibility of boosting distributed service resilience

We study f-resilient services, which are guaranteed to operate as long as no more than f of the associated processes fail. We prove three theorems asserting the impossibility of boosting the resilience of such services. Our first theorem allows any connection pattern between processes and services but assumes these services to be atomic (linearizable) objects. This theorem says that no distributed system in which processes coordinate using f-resilient atomic objects and reliable registers can solve the consensus problem in the presence of f+1 undetectable process stopping failures. In contrast, we show that it is possible to boost the resilience of some systems solving problems easier than consensus: for example, the 2-set-consensus problem is solvable for 2n processes and 2n-1 failures (i.e., wait-free) using n-process consensus services resilient to n-1 failures (wait-free). Our proof is short and self-contained.We then introduce the larger class of failure-oblivious services. These are services that cannot use information about failures, although they may behave more flexibly than atomic objects. An example of such a service is totally ordered broadcast. Our second theorem generalizes the first theorem and its proof to failure-oblivious services.Our third theorem allows the system to contain failure-aware services, such as failure detectors, in addition to failure-oblivious services. This theorem requires that each failure-aware service be connected to all processes; thus, f+1 process failures overall can disable all the failure-aware services. In contrast, it is possible to boost the resilience of a system solving consensus using failure-aware services if arbitrary connection patterns between processes and services are allowed: consensus is solvable for any number of failures using only 1-resilient 2-process perfect failure detectors.As far as we know, this is the first time a unified framework has been used to describe both atomic and non-atomic objects, and the first time boosting analysis has been performed for services more general than atomic objects.     

多智能体系统分布式一致性算法研究现状

综述了多智能体系统分布式一致性问题的研究现状。从理论层面介绍了一致性问题的几种常见定义及与特性相关的主要参数;总结归纳了近年来几种一致性协议及其理论分析结果;分析和阐述了一致性问题的主要应用领域的进展。展望了未来的研究方向。     

A weakest failure detector-based asynchronous consensus protocol for f<n

has been shown to be the weakest realistic failure detector class needed to solve the consensus problem in an asynchronous distributed system prone to f<n process crashes in which communication is by message-passing. However, the only protocol that is known to meet this bound is based on three layers of protocol construction, and is therefore not efficient. This paper presents a surprisingly simple and very efficient direct message-passing implementation of a -based consensus protocol, and proves its correctness.     

Linear uncertain extensions of the minimum cost consensus model based on uncertain distance and consensus utility

Uncertainty theory adopts the belief degree and uncertainty distribution to ensure good alignment with a decision-maker’s uncertain preferences, making the final decisions obtained from the consensus-reaching process closer to the actual decision-making scenarios. Under the constraints of the uncertain distance measure and consensus utility, this article explores the minimum-cost consensus model under various linear uncertainty distribution-based preferences. First, the uncertain distance is used to measure the deviation between individual opinions and the consensus through uncertainty distributions. A nonlinear analytical formula is derived to avoid the computational complexity of integral and piecewise function operations, thus reducing the calculation cost of the uncertain distance measure. The consensus utility function defined in this article characterizes the adjustment value and degree of aggregation of individual opinions. Three new consensus models are constructed based on the consensus utility and linear uncertainty distribution. The results show that, in complex group decision-making contexts, the uncertain consensus models are more flexible than traditional minimum-cost consensus models: compared with the high volatility of the adjusted opinions in traditional deterministic consensus models with crisp number-based preferences, the variation trends of both individual adjusted opinions and the collective opinion with a linear uncertainty distribution are much smoother and the fitting range is closer to reality. The introduction of the consensus utility not only reflects the relative changes of individual opinions, but also accounts for individual psychological changes during the opinion-adjustment process. Most importantly, it reduces the cost per unit of consensus utility, facilitates the determination of the optimal threshold for the consensus utility, and improves the efficiency of resource allocation.     

Early consensus in an asynchronous system with a weak failure detector

Summary.  Consensus is one of the most fundamental problems in the context of fault-tolerant distributed computing. The problem consists, given a set Ω of processes having each an initial value v _i , in deciding among Ω on a common value v. In 1985, Fischer, Lynch and Paterson proved that the consensus problem is not solvable in an asynchronous system subject to a single process crash. In 1991, Chandra and Toueg showed that, by augmenting the asynchronous system model with a well defined unreliable failure detector, consensus becomes solvable. They also give an algorithm that solves consensus using the ◊? failure detector. In this paper we propose a new consensus algorithm, also using the ◊? failure detector, that is more efficient than the Chandra-Toueg consensus algorithm. We measure efficiency by introducing the notion of latency degree, which defines the minimal number of communication steps needed to solve consensus. The Chandra-Toueg algorithm has a latency degree of 3 (it requires at least three communication steps), whereas our early consensus algorithm requires only two communication steps (latency degree of 2). We believe that this is an interesting result, which adds to our current understanding of the cost of consensus algorithms based on ◊?. Received: April 1995 / Accepted: October 1996     

Necessary and sufficient conditions for broadcast consensus protocols

Summary We consider consensus protocols in asynchronous distributed systems that are based on broadcast communication. We show that a necessary and sufficient condition for the existence of a deterministic consensus protocol is delivery of each broadcast message to at least (n+k+1)/2 processes in ann-process system subject tok crash failures with either eventual fair broadcasting or eventual full broadcasting. The broadcast model captures the idea of a broadcast communication medium, such as the Ethernet, in which messages, if delivered, are delivered immediately and in order but not necessarily to all processes. Louise E. Moser received the Ph.D. degree in mathematics from the University of Wisconsin, Madison, in 1970. From 1970 to 1987 she was a professor of mathematics and computer science at California State University, Hayward. In 1987 she moved to the University of California, Santa Barbara, where is currently on the faculty of the Department of Electrical and Computer Engineering. Her current research interests include parallel and distributed systems, network architectures and communication protocols, and formal methods in software engineering. P.M. Melliar-Smith received the Ph.D. degree in computer science from the University of Cambridge, Cambridge, England, in 1987. He was a senior research scientist and program director at SRI International in Menlo Park (1976–1987), senior research associate at the University of Newcastle Upon Tyne (1973–1976), and principal designer for GEC Computers Ltd. in England (1964–1973). He is currently a professor in the Department of Electrical and Computer Engineering at the University of California, Santa Barbara. His research interests include fault-tolerant distributed systems, high-speed communication networks and protocols, and formal specification and verification. Vivek Agrawala received the B.Tech. degree in chemical engineering in 1984 and the M. Tech. degree in computer technology in 1986, both from the Indian Institute of Technology, Delhi, and a Ph.D. in computer science in 1991 from the University of California, Santa Barbara. Since then he has been a Research Scientist at Siemens Corporate Research, Princeton, New Jersey. His major research interests are distributed algorithms, software design methods, and distributed systems.This research was supported by the National Science Foundation, Grant Numbers CCR-8908515 and NCR-9016361. V. Agrawala's current address is Siemens Corporate Research, 755 College Road East, Princeton, NJ 08540, USA     

Distributed output feedback stationary consensus of multi-vehicle systems in unknown environments

In the traditional distributed consensus of multi-vehicle systems, vehicles agree on velocity and position using limited information exchange in their local neighborhoods. Recently, distributed leaderless stationary consensus has been proposed in which vehicles agree on a position and come to a stop. The proposed stationary consensus schemes are based on all vehicles'' access to their own absolute velocity measurements, and they do not guarantee this collective behavior in the presence of disturbances that persistently excite vehicles'' dynamics. On the other hand, traditional distributed disturbance rejection leaderless consensus algorithms may result in an uncontrolled increase in the speed of multi-vehicle system. In this paper, we propose a dynamic relative-output feedback leaderless stationary algorithm in which only a few vehicles have access to their absolute measurements. We systematically design the distributed algorithm by transforming this problem into a static feedback robust control design challenge for the low-order modified model of vehicles with fictitious modeling uncertainties. We further propose dynamic leader-follower stationary consensus algorithms for multi-vehicle systems with a static leader, and find closed-form solutions for the consensus gains based on design matrices and communication graph topology. Finally, we verify the feasibility of these ideas through simulation studies.     

多智能体系统协调控制一致性问题研究综述*

本文综述了多智能体系统协调控制一致性问题的发展情况,介绍了解决一致性问题的主要原理和适用范围,对一致性协议进行了总结,对一致性问题的研究的主要领域进行了深入阐述,对群集、蜂涌、聚集、传感器网络估计等问题进行分析和阐述。最后讨论了以上领域尚未解决的问题和未来的研究方向。     

A review of soft consensus models in a fuzzy environment

In the consensus reaching processes developed in group decision making problems we need to measure the closeness among experts’ opinions in order to obtain a consensus degree. As it is known, to achieve a full and unanimous consensus is often not reachable in practice. An alternative approach is to use softer consensus measures, which reflect better all possible partial agreements, guiding the consensus process until high agreement is achieved among individuals. Consensus models based on soft consensus measures have been widely used because these measures represent better the human perception of the essence of consensus. This paper presents an overview of consensus models based on soft consensus measures, showing the pioneering and prominent papers, the main existing approaches and the new trends and challenges.     

An impossibility about failure detectors in the iterated immediate snapshot model

The Iterated Immediate Snapshot model (IIS) is an asynchronous computation model where processes communicate through a sequence of one-shot Immediate Snapshot (IS) objects. It is known that this model is equivalent to the usual asynchronous read/write shared memory model, for wait-free task solvability. Its interest lies in the fact that its runs are more structured and easier to analyze than the runs in the shared memory model. As the IIS model and the shared memory model are equivalent for wait-free task solvability, a natural question is the following: Are they still equivalent for wait-free task solvability, when they are enriched with the same failure detector? The paper shows that the answer to this question is “no”.     

Condition-based consensus solvability: a hierarchy of conditions and efficient protocols

The condition-based approach for consensus solvability consists of identifying sets of input vectors, called conditions, for which there exists an asynchronous protocol solving consensus despite the occurrence of up to f process crashes. This paper investigates , the largest set of conditions which allow us to solve the consensus problem in an asynchronous shared memory system.The first part of the paper shows that is made up of a hierarchy of classes of conditions, where d is a parameter (called degree of the condition), starting with and ending with d = 0, where . We prove that each one is strictly contained in the previous one: . Various properties of the hierarchy are also derived. It is shown that a class can be characterized in two equivalent but complementary ways: one is convenient for designing protocols while the other is for analyzing the class properties. The paper also defines a linear family of conditions that can be used to derive many specific conditions. In particular, for each d, two natural conditions are presented.The second part of the paper is devoted to the design of efficient condition-based protocols. A generic condition-based protocol is presented. This protocol can be instantiated with any condition C, , and requires at most shared memory read/write operations per process in the synchronization part of the protocol. Thus, the value (f-d) represents the difficulty of the class . An improvement of the protocol for the conditions in is also presented.Received: 15 November 2001, Accepted: 15 April 2003, Published online: 6 February 2004Parts of it have previously appeared in [23] and [25].     

The anatomy study of consensus agreement in MANETs

Reliability is an important research topic of distributed systems. To achieve fault-tolerance in the distributed systems, healthy processors need to reach a common agreement before performing certain special tasks, even if faults exist in many circumstances. This problem is called as the Byzantine Agreement (BA) problem and it must be addressed. In general, the traditional BA problem is solved in well-defined networks. However, the MANETs (Mobile Ad-hoc Network) are increasing in popularity and its network topology is dynamic in nature. In this paper, the BA problem is re-examined in MANETs. Our protocol uses the minimum number of message exchanges to reach an agreement within the distributed system while tolerating the maximum number of faulty processors in MANETs.     

A bivalency proof of the lower bound for uniform consensus

Bivalency argument is a widely-used technique that employs forward induction to show impossibility results and lower bounds related to consensus. However, for a synchronous distributed system of n processes with up to t potential and f actual crash failures, applying bivalency argument to prove the lower bound for reaching uniform consensus is still an open problem. In this paper, we address this problem by presenting a bivalency proof that the lower bound for reaching uniform consensus is (f+2)-rounds where 0?f?t−2.     

Distributed consensus of discrete‐time multi‐agent systems with multiplicative noises

In this paper, we consider the consensus problem of discrete‐time multi‐agent systems with multiplicative communication noises. Each agent can only receive information corrupted by noises from its neighbors and/or a reference node. The intensities of these noises are dependent on the relative states of agents. Under some mild assumptions of the noises and the structure of network, consensus is analyzed under a fixed topology, dynamically switching topologies and randomly switching topologies, respectively. By combining algebraic graph theory and martingale convergence theorem, sufficient conditions for mean square and almost sure consensus are given. Further, when the consensus is achieved without a reference, it is shown that the consensus point is a random variable with its expectation being the average of the initial states of the agents and its variance being bounded. If the multi‐agent system has access to the state of the reference, the state of each agent can asymptotically converge to the reference. Numerical examples are given to illustrate the effectiveness of our results. Copyright © 2014 John Wiley & Sons, Ltd.     

测量受限线性多智能体系统一致性迭代学习控制

本文针对通讯拓扑同时沿时间轴和迭代轴切换且存在测量受限的情形,研究了基于迭代学习控制方法的连续线性多智能体系统输出一致性跟踪问题.在系统通信拓扑始终含有以虚拟领航者为根节点的生成树,以及所有智能体初态在每次迭代均可重置的条件下,针对跟随者能够获得的局部信息而设计了测量受限分布式输出一致性协议.然后,利用λ范数的方法和圆...     

The consensus region design and analysis of fractional-order multi-agent systems

The consensus problem of fractional-order multi-agent systems is studied in this paper. To achieve consensus, a fractional-order observer-type consensus protocol based on relative output measurements is proposed and its stability is also certified theoretically. The notion of consensus region for fractional-order dynamic is introduced and analysed. A multistep consensus protocol design procedure is presented for given consensus region. Several numerical simulations are given to demonstrate the effectiveness of the theoretical results.     

分布式存储系统读写一致性算法性能优化研究综述

读写一致性算法被广泛部署到分布式存储系统,以保证读写数据的正确性。然而,读写一致性算法通常需要使用一个复杂的通信协议来保证多个节点读写数据的正确性,会带来较大网络传输开销和读写时延。由于各种读写一致性算法实现机制存在较大差异,特定的读写一致性算法往往需要部署到特定的存储应用场景,才能高效地执行数据读写操作,保障对其上应用的服务质量。因此,实际的存储系统开发过程中,开发人员往往需要根据存储应用场景选择读写一致性算法,从而减少数据读写操作带来的系统开销。为了明确各种读写一致性算法适合的应用场景,介绍了分布式存储系统中存在的读写一致性问题,并综述了当前读写一致性算法的实现机制。总结了在副本和纠删码2种存储机制下主流的读写一致性算法,比较了这些读写一致性算法在实现机制、网络开销和数据存储开销等方面的特性。在此基础上,结合了单数据中心分布式存储系统和跨数据中心云际存储系统2种经典的应用场景,总结了开发人员在实际存储系统中部署读写一致性算法过程中需要注意的要点,分析了亟需解决的问题和提升数据读写操作性能的可能途径,展望了读写一致性算法未来的发展方向。     

Generalised exponential consensus of the fractional-order nonlinear multi-agent systems via event-triggered control

In this paper, the leader-following consensus problem of the fractional-order nonlinear multi-agent systems via event-triggered control is considered. An effective event-triggered controller is designed and then generalised exponential consensus of the controlled multi-agent systems is studied in the sense of Mittag-Leffler stability of fractional-order systems. The event-triggering function design is dependent on the parameter of the system structure and the minimum inter-event interval can be flexibly adjusted with different fractional-order α. With the event-triggered control scheme, the consensus condition is obtained and the convergence rate of the system is estimated. Numerical simulation indicates the effectiveness of the theoretical results.     

Leader‐following consensus of multiple uncertain Euler‐Lagrange systems

A new adaptive distributed controller is developed for the leader‐following consensus problem of multiple uncertain Euler‐Lagrange systems. A distinct feature of our proposed approach as opposed to the existing ones is that it does not need the exchange of controller's state among the communication network. As a consequence, it not only makes the implementation of the controller much easier but also reduces the communication cost. The effectiveness of the main result is demonstrated by some exemplary applications to cooperative control of multiple two‐link robot arms.