Publication

A scalable and oblivious atomicity assertion

Related publications (36)

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.

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-Verlag New York, Ms Ingrid Cunningham, 175 Fifth Ave, New York, Ny 10010 Usa2011

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

The Collective Memory of Amnesic Processes

Rachid Guerraoui, Bastian Pochon, James Pugh, Ron Levy

This paper considers the problem of robustly emulating a shared atomic memory over a distributed message passing system where processes can fail by crashing and possibly recover. We revisit the notion of atomicity in the crash-recovery context and introduc ...

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

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

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

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

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