Publication

Randomized versus Deterministic Implementations of Concurrent Data Structures

Related publications (154)

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.

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

Three Algorithms for Interface Synthesis: A Comparative Study

Vasu Singh, Dirk Thilo Beyer

A temporal interface for a system component is a finite automaton that specifies the legal sequences of input events. We evaluate and compare three different algorithms for automatically extracting the temporal interface from the transition graph of a comp ...

2006

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

Transformations in distributed computations and applications to set agreement

Bastian Pochon

In a distributed application, high-availability of a critical online service is ensured despite failures by duplicating the vital components of the server. Whilst guaranteeing the access to the server at all times, duplication requires particular care, so ...

EPFL2006

Fast Probabilistic Subsumption Checking for Publish/Subscribe Systems

Karl Aberer, Ivana Podnar, Oana Anca Jurca

Efficient subsumption checking, deciding whether a subscription or publication is subsumed (covered) by a set of previously defined subscriptions, is of paramount importance for publish/subscribe systems. It provides the core system functionality, and addi ...

2006

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

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

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

Range queries in trie-structured overlays

Karl Aberer, Manfred Hauswirth, Anwitaman Datta, Roman Schmidt, Renault John Lecoultre

Among the open problems in P2P systems, support for non-trivial search predicates, standardized query languages, distributed query processing, query load balancing, and quality of query results have been identified as some of the most relevant issues. This ...

2005