扩展心跳故障检测器

从判断一个节点好坏的全过程来看,利用传统心跳故障检测器的算法还是离不开超时技术。借助于心跳器的“计数”思路,提出了一个扩展心跳故障检测器模型,允许对计数器施行递增和递减操作,心跳序列随时间上下波动,从而输出更多的用于判断节点好坏的线索,使得基于扩展心跳故障检测器的算法彻底地摆脱了超时的阴影。     

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.     

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?     

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     

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.     

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

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

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.     

Implementing uniform reliable broadcast with binary consensus in systems with fair-lossy links

When implementing multivalued consensus using binary consensus, previous algorithms assume the availability of uniform reliable broadcast, which is not implementable in systems with fair-lossy links. In this paper, we show that with binary consensus we can implement uniform reliable broadcast directly in systems with fair-lossy links, and thus the separate assumption of the availability of uniform reliable broadcast is not necessary. We further prove that, when binary consensus instances are available only as black boxes, any implementation of uniform reliable broadcast in the fair-lossy link model requires the invocation of an infinite number of binary consensus instances even if no process ever broadcasts any messages, and this is true even when multivalued consensus is used.     

A simple and fast asynchronous consensus protocol based on a weak failure detector

Summary. The Consensus problem is a fundamental paradigm for fault-tolerant asynchronous systems. It abstracts a family of problems known as Agreement (or Coordination) problems. Any solution to consensus can serve as a basic building block for solving such problems (e.g., atomic commitment or atomic broadcast). Solving consensus in an asynchronous system is not a trivial task: it has been proven (1985) by Fischer, Lynch and Paterson that there is no deterministic solution in asynchronous systems which are subject to even a single crash failure. To circumvent this impossibility result, Chandra and Toueg have introduced the concept of unreliable failure detectors (1991), and have studied how these failure detectors can be used to solve consensus in asynchronous systems with crash failures. This paper presents a new consensus protocol that uses a failure detector of the class . Like previous protocols, it is based on the rotating coordinator paradigm and proceeds in asynchronous rounds. Simplicity and efficiency are the main characteristics of this protocol. From a performance point of view, the protocol is particularly efficient when, whether failures occur or not, the underlying failure detector makes no mistake (a common case in practice). From a design point of view, the protocol is based on the combination of three simple mechanisms: a voting mechanism, a small finite state automaton which manages the behavior of each process, and the possibility for a process to change its mind during a round. Received: August 1997 / Accepted: March 1999     

无线传感器网络中时间同步技术的综述

时间同步技术是无线传感器网络中非常重要的协议之一,也是其他协议可靠运行的前提条件,近年来也有相当多的同步机制被提出来,在大规模的无线传感器网络中,单跳同步误差的累加,时钟偏移与漂移同时补偿,同步机制的拓扑性能,同步收敛速度等是目前同步机制研究过程中的主要挑战,传统的集中式同步机制无法满足大规模无线传感器网络的性能要求,研究者们也提出了梯度同步机制,协作同步机制,以及分步式同步机制等来应对这些挑战.本文详细的分析了这些同步机制,并探讨了未来可能的发展方向.     

Communication-efficient failure detection and consensus in omission environments

Failure detectors have been shown to be a very useful mechanism to solve the consensus problem in the crash failure model, for which a number of communication-efficient algorithms have been proposed. In this paper we deal with the definition, implementation and use of communication-efficient failure detectors in the general omission failure model, where processes can fail by crashing and by omitting messages when sending and/or receiving. We first define a new failure detector class for this model in terms of completeness and accuracy properties. Then we propose an algorithm that implements a failure detector of the proposed class in a communication-efficient way, in the sense that only a linear number of links are used to send messages forever. We also explain how the well-known consensus algorithm of Chandra and Toueg can be adapted in order to use the proposed failure detector.     

On the computability power and the robustness of set agreement-oriented failure detector classes

Solving agreement problems deterministically, such as consensus and k-set agreement, in asynchronous distributed systems prone to an unbounded number of process failures has been shown to be impossible. To circumvent this impossibility, unreliable failure detectors for the crash failure model have been widely studied. These are oracles that provide information on failures. The exact nature of such information is defined by a set of abstract properties that a particular class of failure detectors satisfy. The weakest class of such failure detectors that allow to solve consensus is Ω. This paper considers failure detector classes from the literature that solve k-set agreement in the crash failure model, and studies their relative power. It shows that the family of failure detector classes (1 ≤ x ≤ n), and (0 ≤ y ≤ n), can be “added” to provide a failure detector of the class Ω ^z (1 ≤ z ≤ n, a generalization of Ω). It also characterizes the power of such an “addition”, namely, , can construct Ω ^z iff y + z > t, and can construct Ω ^z iff x + z > t + 1, where t is the maximum number of processes that can crash in a run. As an example, the paper shows that, while allows solving 2-set agreement (but not consensus) and allows solving t-set agreement (but not (t − 1)-set agreement), a system with failure detectors of both classes can solve consensus for any value of t. More generally, the paper studies the failure detector classes , and Ω ^z , and shows which reductions among these classes are possible and which are not. The paper also presents a message-passing Ω ^k -based k-set agreement protocol and shows that Ω ^k is not enough to solve (k − 1)-set agreement. In that sense, it can be seen as a step toward the characterization of the weakest failure detector class that allows solving the k-set agreement problem. An extended abstract of this paper has appeared in the proceedings of PODC 2006 [20]. This work has been supported partially by a grant from LAFMI (Franco-Mexican Lab in Computer Science), the European Network of Excellence ReSIST and PAPIIT-UNAM.     

Asynchronous bounded lifetime failure detectors

A failure detector provides processes with a single primitive that, each time it is invoked, returns to the invoking process information related to failures. This research note extends failure detectors by allowing processes to invoke an additional primitive whose effect is to limit the time scope of some properties offered by the failure detector. This simple addition makes possible to weaken the definition of failure detector classes without weakening their power. Two distributed computing problems are used to illustrate the benefit of such an approach, namely the consensus problem and the construction of an atomic register.     

Design of consensus and adaptive consensus filters for distributed parameter systems

This work establishes an abstract framework that considers the distributed filtering of spatially varying processes using a sensor network. It is assumed that the sensor network consists of groups of sensors, each of which provides a number of state measurements from sensing devices that are not necessarily identical and which only transmit their information to their own sensor group. A modification to the local spatially distributed filters provides the non-adaptive case of spatially distributed consensus filters which penalize the disagreement amongst themselves in a dynamic manner. A subsequent modification to this scheme incorporates the adaptation of the consensus gains in the disagreement terms of all local filters. Both the well-posedness of these two consensus spatially distributed filters and the convergence of the associated observation errors to zero in appropriate norms are presented. Their performance is demonstrated on three different examples of a diffusion partial differential equation with point measurements.     

Dynamic hierarchical control for distributed problem solving

Distributed problem solving (DPS) has become one of the central topics in AI. Much research has been concerned with finding an appropriate distributed control regime. We propose the concept of dynamic, hierarchical control (DHC) for distributed problem solving.

In many domains, DPS has a natural hierarchy or a subproblem hierarchy can be imposed by utilizing appropriate decomposition techniques. DHC aims at exploiting the power inherent in the hierarchical approach. It also enables the control of the problem solving process to fit the structure of a domain. This results in well-coordinated cooperation and coherent negotiation among distributed controllers.

We have used the DHC to perform plant combine production planning (PCPP). This task involves the activity of a network of production units, each with possibly different characteristics, collaborating to produce various items under dynamically changing conditions. We also describe the general structure of a single controller which adopts a blackboard and a knowledge source (KS) scheduling mechanism to carry out dynamic process execution.

The paper describes the results of our first solution to this problem. Finally, we discuss on-going research that aims at handling additional problems.     

Disc margins of the discrete-time LQR and its application to consensus problem

This article presents a complex gain margin of discrete-time linear quadratic regulator (DLQR) and its application to a consensus problem of multi-agent higher order linear systems. Since the consensus problem can be converted into a robust control problem with perturbation expressed by complex numbers, and since the classical gain and phase margins are not enough to handle the current case, we study the so-called ‘disc margin’ which is somehow a combination of gain and phase margins. We first compute the disc margin of DLQR controller based on a Lyapunov argument, which is simple but yields a relaxed result over those previously reported in the literature. Then, it is shown that the disc margin can be enlarged arbitrarily when the system is asymptotically null controllable with bounded controls and when a low-gain feedback is employed. Based on this fact, the discrete-time consensus problem is solved by a DLQR-based consensus controller. Simulation study shows that the DLQR-based consensus controller has better robustness property against model uncertainties in the input channel.     

The gap in circumventing the impossibility of consensus

The impossibility of reaching deterministic consensus in an asynchronous and crash prone system was established for a weak variant of the problem, usually called weak consensus, where a set of processes need to decide on a common value in {0,1}, so that both 0 and 1 are possible decision values. On the other hand, approaches to circumventing the impossibility focused on a stronger variant of the problem, called consensus, where the processes need to decide on one of the values they initially propose (0 or 1). This paper studies the computational gap between the two problems. We show that any set of deterministic object types that, combined with registers, implements weak consensus, also implements consensus. Then we exhibit a non-deterministic type that implements weak consensus, among any number of processes, but, combined with registers, cannot implement consensus even among two processes. In modern terminology, this type has consensus power 1 and weak consensus power ∞.     

Multi-target consensus circle pursuit for multi-agent systems via a distributed multi-flocking method

This paper studies the multi-target consensus pursuit problem of multi-agent systems. For solving the problem, a distributed multi-flocking method is designed based on the partial information exchange, which is employed to realise the pursuit of multi-target and the uniform distribution of the number of pursuing agents with the dynamic target. Combining with the proposed circle formation control strategy, agents can adaptively choose the target to form the different circle formation groups accomplishing a multi-target pursuit. The speed state of pursuing agents in each group converges to the same value. A Lyapunov approach is utilised to analyse the stability of multi-agent systems. In addition, a sufficient condition is given for achieving the dynamic target consensus pursuit, and which is then analysed. Finally, simulation results verify the effectiveness of the proposed approaches.     

A tissue P system and a DNA microfluidic device for solving the shortest common superstring problem

This paper describes a tissue P system for solving the Shortest Common Superstring Problem in linear time. This tissue P system is well suited for parallel and distributed implementation using a microfluidic device working with DNA strands. The approach is not based on the usual brute force generate/test technique applied in DNA computing, but it builds the space solution gradually. The possible solutions/superstrings are build step by step through the parallel distributed combination of strings using the overlapping concatenation operation. Moreover, the DNA microfluidic device solves the problem autonomously, without the need of external control or manipulation.An erratum to this article can be found at