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.

Robust Emulations of Shared Memory in a Crash-Recovery Model

Rachid Guerraoui, Ron Levy

A shared memory abstraction can be robustly emulated over an asynchronous message passing system where any process can fail by crashing and possibly recover (crash-recovery model), by having (a) the processes exchange messages to synchronize their read and ...

2004

Fast Non-Blocking Atomic Commit: An Inherent Trade-off

Rachid Guerraoui, Bastian Pochon, Partha Dutta

This paper investigates the time-complexity of the non-blocking atomic commit (NBAC) problem in a synchronous distributed model where t out of n processes may fail by crashing. We exhibit for t > 3 an inherent trade-off between the fast abort property of N ...

2004

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

The Complexity of Asynchronous Byzantine Consensus

Rachid Guerraoui, Marko Vukolic, Partha Dutta

This paper establishes the first theorem relating resilience, round complexity and authentication in distributed computing. We give an exact measure of the time complexity of consensus algorithms that tolerate Byzantine failures and arbitrary long periods ...

2004

NASCENT: Network Layer Service for Vicinity Ad-hoc Groups

Jean-Pierre Hubaux, Jun Luo

Many envisioned applications of ad hoc networks involve only small-scale networks that we term Vicinity Ad-hoc Groups (VAGs). Distributed coordination services, instead of pairwise communications, are the primary requirements of VAGs. Existing designs for ...

2004

The Weakest Failure Detector for Non-Blocking Atomic Commit

Rachid Guerraoui

This paper addresses the question of the weakest failure detector for solving the Non-Blocking Atomic Commit problem (NBAC) in a message passing system where processes can fail by crashing. We define a failure detector, denoted by X, which we show to be su ...

2003

Finally the Weakest Failure Detector for Non-Blocking Atomic Commit

Rachid Guerraoui

Recent papers [GK03,HT03] define the weakest failure detector for solving the Non-Blocking Atomic Commit problem (NBAC) in a message passing system where processes can fail by crashing and a majority of processes never crash. In this paper, we generalize t ...

2003

The many faces of publish/subscribe

Rachid Guerraoui, Anne-Marie Kermarrec, Patrick Eugster, Pascal Felber

Well adapted to the loosely coupled nature of distributed interaction in large-scale applications, the publish/subscribe communication paradigm has recently received increasing attention. With systems based on the publish/subscribe interaction scheme, subs ...

2003

An Efficient Universal Construction for Message-Passing Systems

Rachid Guerraoui, Bastian Pochon, Partha Dutta

A universal construction is an algorithm that transforms any object with a sequential specification into a wait-free and linearizable implementation of that object. This paper presents a novel universal construction algorithm for a message-passing system w ...

2002

Mutual Exclusion in Asynchronous Systems with Failure Detectors

Rachid Guerraoui

This paper defines the fault-tolerant mutual exclusion problem in a message-passing asynchronous system and determines the weakest failure detector to solve the problem. This failure detector, which we call the trusting failure detector, and which we denot ...

2002