Publication

A Thrifty Universal Construction

Publications associées (106)

Graph Chatbot

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Connectez-vous pour utiliser Chat avec Graph Search

Introducing Speculation in Self-Stabilization: An Application to Mutual Exclusion

Rachid Guerraoui

Self-stabilization ensures that, after any transient fault, the system recovers in a finite time and eventually exhibits correct behavior. Speculation consists in guaranteeing that the system satisfies its requirements for any execution but exhibits signif ...

2013

Randomized versus Deterministic Implementations of Concurrent Data Structures

Dan Alistarh

One of the key trends in computing over the past two decades has been increased distribution, both at the processor level, where multi-core architectures are now the norm, and at the system level, where many key services are currently distributed overmulti ...

EPFL2012

Generating Fast Indulgent Algorithms

Rachid Guerraoui, Seth Gilbert, Dan Alistarh

Synchronous distributed algorithms are easier to design and prove correct than algorithms that tolerate asynchrony. Yet, in the real world, networks experience asynchrony and other timing anomalies. In this paper, we address the question of how to efficien ...

Springer Verlag2012

Practicality and time complexity of a sparsified RNA folding algorithm

Philipp Bucher, Slavica Dimitrieva Janeva

Commonly used RNA folding programs compute the minimum free energy structure of a sequence under the pseudoknot exclusion constraint. They are based on Zuker's algorithm which runs in time O(n^3). Recently, it has been claimed that RNA folding can be achie ...

2012

How to Allocate Tasks Asynchronously

Rachid Guerraoui, Seth Gilbert, Dan Alistarh

Asynchronous task allocation is a fundamental problem in distributed computing, in which p asyn- chronous processes must execute a set of m tasks. Also known as write-all or do-all, this problem been studied extensively, both independently and as a key bui ...

2012

A Tractable Framework for Estimating and Combining Spectral Source Models for Audio Source Separation

Rémi Gribonval

The underdetermined blind audio source separation (BSS) problem is often addressed in the time-frequency (TF) domain assuming that each TF point is modeled as an independent random variable with sparse distribution. On the other hand, methods based on stru ...

2012

Rethinking FPGAs: Elude the Flexibility Excess of LUTs with And-Inverter Cones

Paolo Ienne, David Novo Bruna, Hadi Parandeh Afshar, Hind Benbihi

Look-Up Tables (LUTs) are universally used in FPGAs as the elementary logic blocks. They can implement any logic function and thus covering a circuit is a relatively straightforward problem. Naturally, flexibility comes at a price, and increasing the numbe ...

Acm Order Department, P O Box 64145, Baltimore, Md 21264 Usa2012

The complexity of robust atomic storage

Rachid Guerraoui, Marko Vukolic

We study the time-complexity of robust atomic read/write storage from fault-prone storage components in asynchronous message-passing systems. Robustness here means wait-free tolerating the largest possible number t of Byzantine storage component failures ( ...

ACM Press2011

Complexity of the critical node problem over trees

Marco Di Summa

In this paper we deal with the critical node problem (CNP), i.e., the problem of searching for a given number K of nodes in a graph G, whose removal minimizes the (weighted or unweighted) number of connections between pairs of nodes in the residual graph. ...

2011

Generating Fast Indulgent Algorithms

Rachid Guerraoui, Seth Gilbert, Dan Alistarh

Springer-Verlag New York, Ms Ingrid Cunningham, 175 Fifth Ave, New York, Ny 10010 Usa2011