Non-blocking atomic commit in asynchronous distributed systems with failure detectors

This paper addresses the Non-Blocking Atomic Commit (NB-AC) problem in asynchronous distributed systems augmented with failure detectors. We first show that, in these systems, NB-AC and Consensus are incomparable. Roughly speaking, there is a failure detector that solves NB-AC but not Consensus and a failure detector that solves Consensus but not NB-AC. Then we introduce the Anonymously Perfect failure detector . We show that, to solve NB-AC, is necessary (while is not), whereas is sufficient when a majority of the processes are correct. We draw from our results some observations on the practical solvability of NB-AC. Received: August 2000 / Accepted: May 2001     

Quorum-based mutual exclusion in asynchronous distributed systems with unreliable failure detectors

This paper considers the fault-tolerant quorum-based mutual exclusion problem in a message-passing asynchronous system and determines a failure detector to solve the problem. This failure detector, which we call the modal failure detector star, and which we denote by M ^?, is strictly weaker than the perfect failure detector P but strictly stronger than the eventually perfect failure detector ?P. The paper shows that at any environment, the problem is solvable with M ^?. In addition, we make an analysis of our algorithm performance in terms of the number of messages and synchronization delay.     

Computing global functions in asynchronous distributed systems with perfect failure detectors

A Global Data is a vector with one entry per process. Each entry must be filled with an appropriate value provided by the corresponding process. Several distributed computing problems amount to compute a function on a global data. This paper proposes a protocol to solve such problems in the context of asynchronous distributed systems where processes may fail by crashing. The main problem that has to be solved lies in computing the global data and in providing each noncrashed process with a copy of it, despite the possible crash of some processes. To be consistent, the global data must contain, at least, all the values provided by the processes that do not crash. This defines the Global Data Computation (GDC) problem. To solve this problem, processes execute a sequence of asynchronous rounds during which they construct, in a decentralized way, the value of the global data and eventually each process gets a copy of it. To cope with process crashes, the protocol uses a perfect failure detector. The proposed protocol has been designed to be time efficient: it allows early decision. Let t be the maximum number of processes that may crash, t相似文献   

Hybrid binary consensus in anonymous asynchronous systems using coins and failure detectors

The Journal of Supercomputing - Fault tolerance and agreement are essential capabilities of current distributed systems. In this context, Binary Consensus is a key problem. It is well-known that...     

Dynamic FTSS in asynchronous systems: The case of unison

Distributed fault-tolerance can mask the effect of a limited number of permanent faults, while self-stabilization provides forward recovery after an arbitrary number of transient faults hit the system. FTSS (Fault-Tolerant Self-Stabilizing) protocols combine the best of both worlds since they tolerate simultaneously transient and (permanent) crash faults. To date, deterministic FTSS solutions either consider static (i.e. fixed point) tasks, or assume synchronous scheduling of the system components.In this paper, we present the first study of deterministic FTSS solutions for dynamic tasks in asynchronous systems, considering the unison problem as a benchmark. Unison can be seen as a local clock synchronization problem as neighbors must maintain digital clocks at most one time unit away from each other, and increment their own clock value infinitely often. We present several impossibility results for this difficult problem and propose an FTSS solution (when the problem is solvable) for the state model that exhibits optimal fault-containment.     

Faster asynchronous systems

A testing scenario in the sense of De Nicola and Hennessy is developed to measure the worst-case efficiency of asynchronous systems. The resulting testing-preorder is characterized with a variant of refusal traces and shown to satisfy some properties that make it attractive as a faster-than relation. Finally, one implementation of a bounded buffer is shown to be strictly faster than two others – in contrast to a result obtained with a different approach by Arun-Kumar and Hennessy.     

VLSI asynchronous systems: specification and synthesis

Most of today's digital systems are realized using synchronous (i.e. globally clocked) VLSI circuits. For many reasons, it is becoming increasingly hard to build large synchronous circuits. Although several techniques for building non-clocked (i.e. asynchronous) sequential circuits have been known for some time, they have been largely ignored by the digital design community. Recently, however, asynchronous circuits have been enjoying a revival. After reviewing recent research in this area, we take a simple collection of examples and, through them, explain our design system for specifying and synthesizing asynchronous circuits. We show that by being able to work in a framework where circuit activities do not have to coincide with clock pulses, designers obtain several avenues for circuit optimization that are highly promising for creating efficient and modularly expandable circuits.     

On reduction of asynchronous systems

In this paper, we give a formal treatment of the reduction idea in Lipton's paper, and investigate its application in proving correctness of asynchronous systems. In a complex system, it is both tempting and convenient to assume that certain sequences of actions behave like single indivisible or instantaneous actions. Such conceptual reduction of sequences of relatively small actions to single occurrences of relatively large actions is encountered very often in computer science. For asynchronous systems, reduction is particularly appealing because it helps to reduce the amount of interleaving of actions involved and also the complexity of the systems, thereby making correctness proofs more tractable. However, reduction is also very dangerous for it could easily lead to erroneous and disastrous conclusions about systems.We establish, in this paper, simple and general sufficient conditions for reduction under which correctness is preserved, and any conclusions obtained about the correctness of the reduced systems are also valid for the original systems, as far as deadlock-freedom, homing, determinacy and the Church-Rosser property are concerned. We also show that the results in Lipton's paper are special cases of some of our results here.     

Stability of nonlinear asynchronous systems

In this work, we focus on a class of nonlinear asynchronous systems defined by two different modes of operation, one stable and the other one unstable. The switching between the two modes of operation is driven by external asynchronous events. It is assumed that on any time interval of a given length, the maximum time in which the system evolves in the unstable mode is bounded. This property is given in the form of a rate constraint. Under this assumption, we study the behavior of this class of systems and provide existential results of conditions on this rate constraint under which various types of stability of the origin of the nonlinear asynchronous system can be assured.     

Performance of pipelined asynchronous systems

A testing-based faster-than relation has previously been developed that compares the worst-case efficiency of asynchronous systems. This approach reveals that pipelining does not improve efficiency in general; that it does so in practice depends on assumptions about the user behaviour. Accordingly, the approach was adapted to a setting where user behaviour is known to belong to a specific, but often occurring class of request–response behaviours; some quantitative results on the efficiency of the respective so-called response processes were given. In particular, it was shown that in the adapted setting a very simple case of a pipelined process with two stages is faster than a comparable atomic processing of the two stages.In this paper, we determine the performance of general pipelines, which is not so easy in an asynchronous setting. Pipelines are built with a chaining operator; we also study whether the adapted faster-than relation is compatible with chaining and two other parallel composition operators, and give results on the performance of the respective compositions. These studies also demonstrate how rich the request–respond setting is.     

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.     

Renaming and the weakest family of failure detectors

We address the question of the weakest failure detector to circumvent the impossibility of $(2n-2)$ -renaming in a system of up to $n$ participating processes. We derive that in a restricted class of eventual failure detectors there does not exist a single weakest oracle, but a weakest family of oracles $\zeta _n$ : every two oracles in $\zeta _n$ are incomparable, and every oracle that allows for solving renaming provides at least as much information about failures as one of the oracles in $\zeta _n$ . As a by product, we obtain one more evidence that renaming is strictly easier to solve than set agreement.     

Control of asynchronous sampled data systems

This paper is concerned with the problem of controller design in the case of asynchronous sampled data systems. Optimal LQG controllers are obtained for the class of two-rate systems where all the control inputs are held at a rate which is asynchronously related to the rate with which all of the outputs are sampled. Furthermore for this class, a parameterization of all stabilizing controllers is provided     

Actuator fault detection in aircraft systems: Oscillatory failure case study

This paper is devoted to the detection of Oscillatory Failure Case (OFC) in the Electrical Flight Control System (EFCS). Such failures lead to a strong interaction between loads and aeroelasticity and must be quickly detected and passivated. This paper proposes a hybrid monitoring scheme for robust and early detection of such unauthorized oscillatory events. The proposed technique has been developed within ADDSAFE project (a collaborative project supported by the European Seventh Framework Program: Advanced Fault Diagnosis for Sustainable Flight Guidance and Control). A robust finite-time differentiator is used to estimate derivatives in a noisy environment. Fault reconstruction is next achieved by solving on-line a nonlinear equation using a gradient descent method. Finally, fault detection and confirmation stage is based on the decision making rules currently used for in-service Airbus A380 airplane. Robustness and performance of the proposed fault detection scheme are tested using a high fidelity benchmark and intensive Monte Carlo simulations for several flight scenarios as specified within ADDSAFE project.     

Concurrent common knowledge: defining agreement for asynchronous systems

Summary In this paper we present a new, knowledgetheoretic definition of agreement designed for asynchronous systems. In analogy with common knowledge, it is calledconcurrent common knowledge. Unlike common knowledge, it is a form of agreement that is attainable asynchronously. In defining concurrent common knowledge, we give a logic with new modal operators and a formal semantics, both of which are based on causality and consequently capture only the relevant structure of purely asynchronous systems. We give general conditions by which protocols attain concurrent common knowledge and prove that two simple and efficient protocols do so. We also present several applications of our logic. We show that concurrent common knowledge is a necessary and sufficient condition for the concurrent performance of distributed actions. We also demonstrate the role of knowledge in taking snapshots for stable property detection and asynchronous broadcasts. In general, applications that involve all processes reaching agreement about some porperty of a consistent global state can be understood in terms of concurrent common knowledge. Prakash Panangaden was born in Pune, India in 1954. He attended Calcutta Boys' School and subsequently attended the Indian Institute of Technology, Kanpur where he received an M.Sc. in Physics in 1975. He went to graduate school at the University of Chicago where he studied relativity. He moved to the University of Wisconsin-Milwaukee to study with Leonard Parker to work on quantum field theory on curved space times. After a post-doc at the University of Utah, he decided that it was time for something completely different. He began a Masters with Robert Keller on the semantics of indeterminate dataflow networks. He became an Assistant professor at Cornell University in 1985 and an Associate Professor at McGill University in 1990. He has also made extended visits to the Computer Laboratory, University of Cambridge and to the C.W.I. Amsterdam. Kim Taylor has been an assistant professor at the University of California at Santa Cruz since July 1990. Her research interests are in the design and analysis of algorithms for distributed systems. She received the BS degree in Electrical Engineering and Computer Science from Rice University in May 1985, and the PhD in Computer Science from Cornell University in August 1990.An earlier version of this work appears in Proceedings of the Seventh Annual ACM Symposium on Principles of Distributed Computing, August 1988Supported in part by NSF grants DCR-8602072 and CCR-8818979.Supported in part by an AT&T Ph.D. Scholarship.     

Diagnosis of asynchronous discrete-event systems: a net unfolding approach

In this paper, we consider the diagnosis of asynchronous discrete event systems. We follow a so-called true concurrency approach, in which no global state and no global time is available. Instead, we use only local states in combination with a partial order model of time. Our basic mathematical tool is that of net unfoldings originating from the Petri net research area. This study was motivated by the problem of event correlation in telecommunications network management.