Publication

Generating Fast Indulgent Algorithms

Related publications (112)

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.

A Scalable and Oblivious Atomicity Assertion

Rachid Guerraoui, Marko Vukolic

This paper presents SOAR: the first oblivious atomicity assertion with polynomial complexity. SOAR enables to check atomicity of a single-writer multi-reader register implementation. The basic idea underlying the low overhead induced by SOAR lies in greedi ...

2008

Using Bounded Model Checking to Verify Consensus Algorithms

André Schiper

This paper presents an approach to automatic verification of asynchronous round-based consensus algorithms. We use model checking, a widely practiced verification method; but its application to asynchronous distributed algorithms is difficult because the s ...

2008

On the Complexity of Asynchronous Gossip

Rachid Guerraoui, Seth Gilbert

In this paper, we study the complexity of gossip in an asynchronous, message-passing fault-prone distributed system. In short, we show that an adaptive adversary can significantly hamper the spreading of a rumor, while an oblivious adversary cannot. In the ...

2008

Minkowski sums of polytopes

Christophe Weibel

Minkowski sums are a very simple geometrical operation, with applications in many different fields. In particular, Minkowski sums of polytopes have shown to be of interest to both industry and the academic world. This thesis presents a study of these sums, ...

EPFL2007

The Time-Complexity of Local Decision in Distributed Agreement

Rachid Guerraoui, Bastian Pochon, Partha Dutta

Agreement is at the heart of distributed computing. In its simple form, it requires a set of processes to decide on a common value out of the values they propose. The time-complexity of distributed agreement problems is generally measured in terms of the n ...

2007

Efficient static analysis of XML paths and types

We present an algorithm to solve XPath decision problems under regular tree type constraints and show its use to statically type-check XPath queries. To this end, we prove the decidability of a logic with converse for finite ordered trees whose time comple ...

2007

Tracking Atoms with Particles for Audio-visual Source Localization

Pierre Vandergheynst, Andrea Cavallaro, Gianluca Monaci, Emilio Maggio

We present a general framework and an efficient algorithm for tracking relevant video structures. The structures to be tracked are implicitly defined by a Matching Pursuit procedure that extracts and ranks the most important image contours. Based on the ra ...

2007

The medial axis of the union of inner Voronoi balls in the plane

Mark Pauly

Consider a dense sampling S of the smooth boundary of a planar shape O, i.e., an open subset of R-2. We show that the medial axis of the union of Voronoi balls centered at Voronoi vertices inside O has a particularly simple structure: it is the union of al ...

2007

On the Message Complexity of Indulgent Consensus

Rachid Guerraoui, Seth Gilbert

Many recommend planning for the worst and hoping for the best. In this paper we devise efficient indulgent consensus algorithms that can tolerate crash failures and arbitrarily long periods of asynchrony, and yet perform (asymptotically) optimally in well- ...

Springer2007

Refined Quorum Systems

Rachid Guerraoui, Marko Vukolic

It is considered good distributed computing practice to devise object implementations that tolerate contention, periods of asynchrony and a large number of failures, but perform fast if few failures occur, the system is synchronous and there is no contenti ...

2007