Publication

How fast can a distributed atomic read be?

Related publications (62)

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.

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

The Weakest Failure Detectors to Boost Obstruction-Freedom

Rachid Guerraoui, Michal Kapalka

It is considered good practice in concurrent computing to devise shared object implementations that ensure a minimal obstruction-free progress property and delegate the task of boosting liveness to independent generic oracles called contention managers. Th ...

2007

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

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

How Fast can a Distributed Atomic Read be?

Rachid Guerraoui, Marko Vukolic, Ron Levy, Partha Dutta

We study efficient and robust implementations of an atomic read-write data structure over an asynchronous distributed message-passing system made of reader and writer processes, as well as failure prone server processes implementing the data structure. We ...

2005

Lucky Read/Write Access to Robust Atomic Storage

Rachid Guerraoui, Marko Vukolic, Ron Levy

This paper establishes tight bounds on the best-case time-complexity of distributed atomic read/write storage implementations that tolerate worst-case conditions. We study asynchronous robust implementations where a writer and a set of reader processes (cl ...

2005