Publication

The Overhead of Consensus Failure Recovery

Related publications (93)

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

How Fast Can a Very Robust Read Be?

Rachid Guerraoui, Marko Vukolic

This paper studies the time complexity of reading unauthenticated data from a distributed storage made of a set of failure-prone base objects. More specifically, we consider the abstraction of a robust read/write storage that provides wait-free access to u ...

2006

Keypoint Recognition using Randomized Trees

Pascal Fua, Vincent Lepetit

In many 3--D object-detection and pose-estimation problems, run-time performance is of critical importance. However, there usually is time to train the system, which we will show to be very useful. Assuming that several registered images of the target obje ...

2006

Transformations in distributed computations and applications to set agreement

Bastian Pochon

In a distributed application, high-availability of a critical online service is ensured despite failures by duplicating the vital components of the server. Whilst guaranteeing the access to the server at all times, duplication requires particular care, so ...

EPFL2006

The Overhead of Indulgent Failure Recovery

Rachid Guerraoui, Partha Dutta

Many reliable distributed systems are consensus-based and typically operate under two modes: a fast normal mode in failure-free synchronous periods, and a slower recovery mode following asynchrony and failures. A lot of work has been devoted to optimize th ...

2006

The Inherent Price of Indulgence

Rachid Guerraoui, Partha Dutta

This paper presents a tight lower bound on the time complexity of indulgent consensus algorithms, i.e., consensus algorithms that use unreliable failure detectors. We state and prove our tight lower bound in the unifying framework of round-by-round fault d ...

2005

Failure Location in Transparent Optical Networks: The Asymmetry Between False and Missing Alarms

Patrick Thiran, Xuan Hung Nguyen

Failure location in transparent optical networks is difficult because of the large amount of alarms that a failure can trigger and because of corrupted alarms. One problem that network operators often face is how to set the thresholds in monitoring devices ...

2005

Time-complexity bounds on agreement problems

Partha Dutta

In many distributed systems, designing an application that maintains consistency and availability despite failure of processes, involves solving some form of agreement. Not surprisingly, providing efficient agreement algorithms is critical for improving th ...

EPFL2005

Lower Bounds on Generic Broadcast Algorithms

André Schiper, Fernando Pedone

This paper establishes tight lower bounds on the time complexity of algorithms solving the generic broadcast problem. Generic broadcast assumes a symmetric, non-reflexive conflict relation on the set of messages, and requires ordered delivery only for conf ...

2004

The Complexity of Asynchronous Byzantine Consensus

Rachid Guerraoui, Marko Vukolic, Partha Dutta

This paper establishes the first theorem relating resilience, round complexity and authentication in distributed computing. We give an exact measure of the time complexity of consensus algorithms that tolerate Byzantine failures and arbitrary long periods ...

2004

On the complexity of fixed parameter clique and dominating set

Friedrich Eisenbrand

We provide simple, faster algorithms for the detection of cliques and dominating sets of fixed order. Our algorithms are based on reductions to rectangular matrix multiplication. We also describe an improved algorithm for diamonds detection. © 2004 Elsevie ...

2004