Failure detector | EPFL Graph Search

In a distributed computing system, a failure detector is a computer application or a subsystem that is responsible for the detection of node failures or crashes. Failure detectors were first introduced in 1996 by Chandra and Toueg in their book Unreliable Failure Detectors for Reliable Distributed Systems. The book depicts the failure detector as a tool to improve consensus (the achievement of reliability) and atomic broadcast (the same sequence of messages) in the distributed system. In other words, failure detectors seek errors in the process, and the system will maintain a level of reliability. In practice, after failure detectors spot crashes, the system will ban the processes that are making mistakes to prevent any further serious crashes or errors. In the 21st century, failure detectors are widely used in distributed computing systems to detect application errors, such as a software application stops functioning properly. As the distributed computing projects (s

Efficient Algorithms to Implement Failure Detectors and Solve Consensus in Distributed Systems

The consensus problem is a fundamental paradigm for fault-tolerant distributed computing. It abstracts a family of problems known as agreement problems, e.g., atomic broadcast, atomic commitment, group membership, and leader election. Any solution to Consensus can serve as a basic building block for solving such problems. It is well known that Consensus cannot be solved deterministically in an asynchronous system that is subject to even a single process crash. This impossibility result stems from the lack of reliable failure detection in such a system. To circumvent such impossibility results, Chandra and Toueg introduced the concept of unreliable failure detectors, and show how to use them to solve Consensus. Instead of giving specific implementations, they characterized failure detectors in terms of abstract properties. This thesis focuses on the design of algorithms implementing failure detectors and its use to solve Consensus. We consider a partially synchronous system in which Consensus has been proven to be solvable. We first show that no one of the failure detector classes satisfying perpetual accuracy can be implemented in such a system. We then propose efficient algorithms implementing all the failure detector classes satisfying eventual accuracy. We also propose an optimal algorithm implementing diamond S, the weakest failure detector class for solving Consensus. We also propose a new class of failure detectors, the Eventually Consistent class, denoted diamond C. This class adds an eventual leader election capability to the failure detection capability of other classes. We show that diamond C is equivalent to diamond S. We also show that diamond C can be implemented as efficiently as diamond S. We propose a Consensus algorithm that successfully exploits the leader election capability of diamond C and performs better that all the previously proposed algorithms, which shows the potential of this new class of failure detectors.

2000

Reliable and Real-Time Distributed Abstractions

David Kozhaya

The celebrated distributed computing approach for building systems and services using multiple machines continues to expand to new domains. Computation devices nowadays have additional sensing and communication capabilities, while becoming, at the same time, cheaper, faster and more pervasive. Consequently, areas like industrial control, smart grids and sensor networks are increasingly using such devices to control and coordinate system operations. However, compared to classic distributed systems, such real-world physical systems have different needs, e.g., real-time and energy efficiency requirements. Moreover, constraints that govern communication are also different. Networks become susceptible to inevitable random losses, especially when utilizing wireless and power line communication. This thesis investigates how to build various fundamental distributed computing abstractions (services) given the limitations, the performance and the application requirements and constraints of real-world control, smart grid and sensor systems. In quest of completeness, we discuss four distributed abstractions starting from the level of network links all the way up to the application level. At the link level, we show how to build an energy-efficient reliable communication service. This is especially important for devices with battery-powered wireless adapters where recharging might be unfeasible. We establish transmission policies that can be used by processes to decide when to transmit over the network in order to avoid losses and minimize re-transmissions. These policies allow messages to be reliably transmitted with minimum transmission energy. One level higher than links is failure detection, a software abstraction that relies on communication for identifying process crashes. We prove impossibility results concerning implementing classic eventual failure detectors in networks with probabilistic losses. We define a new implementable type of failure detectors, which preserves modularity. This means that existing deterministic algorithms using eventual failure detectors can still be used to solve certain distributed problems in lossy networks: we simply replace the existing failure detector with the one we define. Using failure detectors, processes might get information about failures at different times. However, to ensure dependability, environments such as distributed control systems (DCSs), require a membership service where processes agree about failures in real time. We prove that the necessary properties of this membership cannot be implemented deterministically, given probabilistic losses. We propose an algorithm that satisfies these properties, with high probability. We show analytically, as well as experimentally (within an industrial DCS), that our technique significantly enhances the DCS dependability, compared to classic membership services, at low additional cost. Finally, we investigate a real-time shared memory abstraction, which vastly simplifies programming control applications. We study the feasibility of implementing such an abstraction within DCSs, showing the impossibility of this task using traditional algorithms that are built on top of existing software blocks like failure detectors. We propose an approach that circumvents this impossibility by attaching information to the failure detection messages, analyze the performance of our technique and showcase ways of adapting it to various application needs and workloads.

EPFL2016

Reliable and Real-Time Distributed Abstractions

David Kozhaya

EPFL2016

Efficient Algorithms to Implement Failure Detectors and Solve Consensus in Distributed Systems

2000