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

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

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

A profiling framework for high level design space exploration for memory and system architectures

In 1971, the first microprocessor produced in mass production had 2300 transistor and was able to compute 60'000 operations per second at 740 kHz. Nowadays, even a common gaming console uses a central unit including 243 millions of transistors running at 4 ...

EPFL2007

From unreliable objects to reliable objects: The case of atomic registers and consensus

Rachid Guerraoui

A concurrent object is an object that can be concurrently accessed by several processes. It has been shown by Maurice Herlihy that any concurrent object O defined by a sequential specification can be wait-free implemented from reliable atomic registers (sh ...

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

Synchronizing without Locks is Inherently Expensive

Rachid Guerraoui, Hagit Albo Attiya

It has been considered bon ton to blame locks for their fragility, especially since researchers identified obstruction-freedom: a progress condition that precludes locking while being weak enough to raise the hope for good performance. This paper attenuate ...

2006

Reducing Time Complexity in RFID Systems

Gildas Avoine, Philippe Oechslin, Etienne Dysli

Radio frequency identification systems based on low-cost computing devices is the new plaything that every company would like to adopt. Its goal can be either to improve the productivity or to strengthen the security. Specific identification protocols base ...

2006

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

How Fast Can a Very Robust Read Be?

Rachid Guerraoui, Marko Vukolic

2006

Reverse Search for Parametric Linear Programming

Colin Neil Jones

This paper introduces a new enumeration technique for (multi)parametric linear programs (pLPs) based on the reverse-search paradigm. We prove that the proposed algorithm has a computational complexity that is linear in the size of the output (number of so- ...

IEEE2006

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