Person

Rachid Guerraoui

Related publications (428)

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.

A General Characterization of Indulgence (Invited Paper)

Rachid Guerraoui

An indulgent algorithm is a distributed algorithm that, besides tolerating process failures, also tolerates arbitrarily long periods of instability, with an unbounded number of timing and scheduling failures. In particular, no process can take any irrevoca ...

2006

The Alpha of Indulgent Consensus

Rachid Guerraoui

This paper presents a simple framework unifying a family of consensus algorithms that can tolerate process crash failures and asynchronous periods of the network, also called indulgent consensus algorithms. Key to the framework is a new abstraction we intr ...

2006

Of Malicious Motes and Suspicious Sensors

Rachid Guerraoui, Seth Gilbert

How efficiently can a malicious device disrupt communication in a wireless network? Imagine a basic game involving two honest players, Alice and Bob, who want to exchange information, and an adversary, Collin, who can disrupt communication using a limited ...

2006

A Topological Treatment of Early-Deciding Set-Agreement

Rachid Guerraoui, Bastian Pochon

This paper considers the k-set-agreement problem in a synchronous message passing distributed system where up to t processes can fail by crashing. We determine the number of communication rounds needed for all correct processes to reach a decision in a giv ...

2006

Frugal Event Dissemination in a Mobile Environment

Rachid Guerraoui

This paper describes an event dissemination algorithm that implements a topic-based publish/subscribe interaction abstraction in mobile ad-hoc networks (MANETs). Our algorithm is frugal in two senses. First, it reduces the total number of duplicates and pa ...

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

On the Impossibility of Boosting Distributed Service Resilience

Rachid Guerraoui

We show that no deterministic algorithm can solve consensus in the presence of t+1 process crash failures, in a system of n processes that communicate in a reliable way and synchronize their activities using any number of t-resilient services. These base s ...

2005

Frugal Mobile Objects

Rachid Guerraoui, Maxime Monod, Benoît Garbinato, Jesper Honig Spring

This paper presents a computing model for resource-limited mobile devices. The originality of the model lies in the integration of a strongly-typed event-based communication paradigm with abstractions for frugal control, assuming a small footprint runtime. ...

2005

Gracefully Degrading Fair Exchange with Security Modules

Rachid Guerraoui, Marko Vukolic, Gildas Avoine

The fair exchange problem is key to trading electronic items in systems of mutually untrusted parties. In modern variants of such systems, each party is equipped with a security module. The security modules trust each other but can only communicate by exch ...

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